Quicksort (ordenación rápida)

def quicksort(a, ini, fin):
    if ini >= fin:                              # 0 o 1 elementos: ya está ordenado
        return
    p = particion(a, ini, fin)                  # el pivote queda en su sitio definitivo
    print(f"pivote {a[p]} → posición {p}: {a}")
    quicksort(a, ini, p - 1)                    # los menores o iguales que el pivote
    quicksort(a, p + 1, fin)                    # y los mayores


def particion(a, ini, fin):
    """Partición de Lomuto: el pivote es a[fin]; los <= pivote pasan a la izquierda
    y el pivote queda justo entre los dos grupos. Devuelve su posición."""
    pivote = a[fin]
    i = ini - 1                                 # a[ini..i] son los <= pivote
    for j in range(ini, fin):
        if a[j] <= pivote:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[fin] = a[fin], a[i + 1]
    return i + 1


a = [10, 80, 30, 90, 40, 50, 70]
quicksort(a, 0, len(a) - 1)
print("Resultado:", a)

const texto = (a) => "[" + a.join(", ") + "]";

function quicksort(a, ini, fin) {
    if (ini >= fin) return;                         // 0 o 1 elementos: ya está ordenado
    const p = particion(a, ini, fin);               // el pivote queda en su sitio definitivo
    console.log(`pivote ${a[p]} → posición ${p}: ${texto(a)}`);
    quicksort(a, ini, p - 1);                       // los menores o iguales que el pivote
    quicksort(a, p + 1, fin);                       // y los mayores
}

/** Partición de Lomuto: el pivote es a[fin]; los <= pivote pasan a la izquierda
    y el pivote queda justo entre los dos grupos. Devuelve su posición. */
function particion(a, ini, fin) {
    const pivote = a[fin];
    let i = ini - 1;                                // a[ini..i] son los <= pivote
    for (let j = ini; j < fin; j++) {
        if (a[j] <= pivote) {
            i++;
            [a[i], a[j]] = [a[j], a[i]];
        }
    }
    [a[i + 1], a[fin]] = [a[fin], a[i + 1]];
    return i + 1;
}

const a = [10, 80, 30, 90, 40, 50, 70];
quicksort(a, 0, a.length - 1);
console.log("Resultado: " + texto(a));

using System;

class Program {
    static string Texto(int[] a) => "[" + string.Join(", ", a) + "]";

    static void Quicksort(int[] a, int ini, int fin) {
        if (ini >= fin) return;                         // 0 o 1 elementos: ya está ordenado
        int p = Particion(a, ini, fin);                 // el pivote queda en su sitio definitivo
        Console.WriteLine(
quot;pivote {a[p]} → posición {p}: {Texto(a)}");
        Quicksort(a, ini, p - 1);                       // los menores o iguales que el pivote
        Quicksort(a, p + 1, fin);                       // y los mayores
    }

    // Partición de Lomuto: el pivote es a[fin]; los <= pivote pasan a la izquierda
    // y el pivote queda justo entre los dos grupos. Devuelve su posición.
    static int Particion(int[] a, int ini, int fin) {
        int pivote = a[fin];
        int i = ini - 1;                                // a[ini..i] son los <= pivote
        for (int j = ini; j < fin; j++) {
            if (a[j] <= pivote) {
                i++;
                (a[i], a[j]) = (a[j], a[i]);
            }
        }
        (a[i + 1], a[fin]) = (a[fin], a[i + 1]);
        return i + 1;
    }

    static void Main() {
        int[] a = { 10, 80, 30, 90, 40, 50, 70 };
        Quicksort(a, 0, a.Length - 1);
        Console.WriteLine("Resultado: " + Texto(a));
    }
}

<?php
function texto(array $a): string { return "[" . implode(", ", $a) . "]"; }

function quicksort(array &$a, int $ini, int $fin): void {
    if ($ini >= $fin) return;                       // 0 o 1 elementos: ya está ordenado
    $p = particion($a, $ini, $fin);                 // el pivote queda en su sitio definitivo
    echo "pivote {$a[$p]} → posición $p: " . texto($a) . "\n";
    quicksort($a, $ini, $p - 1);                    // los menores o iguales que el pivote
    quicksort($a, $p + 1, $fin);                    // y los mayores
}

/** Partición de Lomuto: el pivote es $a[$fin]; los <= pivote pasan a la izquierda
    y el pivote queda justo entre los dos grupos. Devuelve su posición. */
function particion(array &$a, int $ini, int $fin): int {
    $pivote = $a[$fin];
    $i = $ini - 1;                                  // $a[$ini..$i] son los <= pivote
    for ($j = $ini; $j < $fin; $j++) {
        if ($a[$j] <= $pivote) {
            $i++;
            [$a[$i], $a[$j]] = [$a[$j], $a[$i]];
        }
    }
    [$a[$i + 1], $a[$fin]] = [$a[$fin], $a[$i + 1]];
    return $i + 1;
}

$a = [10, 80, 30, 90, 40, 50, 70];
quicksort($a, 0, count($a) - 1);
echo "Resultado: " . texto($a) . "\n";

import random


def particion_aleatoria(a, ini, fin):
    """Con un pivote al azar, el peor caso (O(n²)) ya no depende de cómo vengan los datos."""
    r = random.randint(ini, fin)          # una posición al azar del tramo…
    a[r], a[fin] = a[fin], a[r]           # …se lleva al final y se parte como siempre
    return particion(a, ini, fin)

/** Con un pivote al azar, el peor caso (O(n²)) ya no depende de cómo vengan los datos. */
function particionAleatoria(a, ini, fin) {
    const r = ini + Math.floor(Math.random() * (fin - ini + 1));   // una posición al azar del tramo…
    [a[r], a[fin]] = [a[fin], a[r]];                                // …se lleva al final y se parte como siempre
    return particion(a, ini, fin);
}

// Con un pivote al azar, el peor caso (O(n²)) ya no depende de cómo vengan los datos.
static int ParticionAleatoria(int[] a, int ini, int fin) {
    int r = Random.Shared.Next(ini, fin + 1);      // una posición al azar del tramo…
    (a[r], a[fin]) = (a[fin], a[r]);               // …se lleva al final y se parte como siempre
    return Particion(a, ini, fin);
}

/** Con un pivote al azar, el peor caso (O(n²)) ya no depende de cómo vengan los datos. */
function particionAleatoria(array &$a, int $ini, int $fin): int {
    $r = random_int($ini, $fin);                   // una posición al azar del tramo…
    [$a[$r], $a[$fin]] = [$a[$fin], $a[$r]];       // …se lleva al final y se parte como siempre
    return particion($a, $ini, $fin);
}