Algoritmo de clasificación rápida en JavaGuion con ejemplo

¿Qué es la ordenación rápida?

Ordenación rápida es un algoritmo de ordenación por comparación que sigue el Divide y vencerás Este método selecciona un elemento como pivote, divide el array en una parte que contiene valores menores que el pivote y otra que contiene valores mayores, y luego aplica el mismo procedimiento a cada parte hasta que todo el array esté ordenado.

Quick Sort es uno de los algoritmos de ordenación más utilizados en todos los lenguajes de programación. Si escribes JavaScript, probablemente ya hayas utilizado la función integrada ordenar() método, por lo que puede que se pregunte por qué vale la pena aprender una implementación separada de Quick Sort. Para responder a eso, primero necesita saber qué significa ordenar y qué es el ordenamiento predeterminado en JavaEl script sí lo hace.

La función Quick Sort se define por tres propiedades:

• En su lugar: reorganiza el original matriz y no asigna una segunda matriz del mismo tamaño.
• Recursivo: Cada partición produce dos rangos más pequeños que se ordenan mediante la misma función.
• Inestable: Dos elementos con claves iguales pueden terminar en un orden relativo diferente al que tenían inicialmente.

¿Qué es Ordenar?

Ordenar significa organizar elementos en un orden definido. Casi con seguridad te has encontrado con esto en la escuela: poner los números de menor a mayor es ascendente orden, y colocarlos de mayor a menor es descendiendo Ordenar. La clasificación no se limita a números. Se pueden ordenar cadenas alfabéticamente, fechas cronológicamente y objetos por cualquier campo que elijas, como precio o puntuación.

La ordenación es importante porque los datos ordenados permiten operaciones más rápidas. Una búsqueda binaria se ejecuta en tiempo O(log n), pero solo con datos ordenados. La deduplicación, las consultas de rango, la clasificación y las operaciones de fusión resultan mucho más económicas una vez que los datos están ordenados, razón por la cual todos los lenguajes incluyen al menos una rutina de ordenación.

Ordenación predeterminada en JavaScript

Como se mencionó anteriormente, JavaEl script proporciona ordenar(). Toma un pequeño array como [5,3,7,6,2,9] que quieras en orden ascendente. Llamando a ordenar() En el array parece hacer exactamente eso.

La captura de pantalla anterior muestra la consola del navegador imprimiendo el array ordenado. Aquí está el mismo código:

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

Salida:

[ 2, 3, 5, 6, 7, 9 ]

Ese resultado es correcto, pero solo por casualidad. Array.prototype.sort() convierte cada elemento en una cadena y compara las cadenas. a menos que proporciones una función de comparación. Cada valor en este array es un dígito, por lo que el orden de las cadenas coincide con el orden numérico. Si cambias los datos, la ilusión se rompe.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Salida:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

¿Qué algoritmo utiliza sort()?

La especificación no indica ningún algoritmo, por lo que cada motor elige el suyo. Todos los motores modernos utilizan un algoritmo basado en la fusión:

• V8 (Chrome, Edge, Node.js) ha utilizado TimSort Desde la versión 8.0, incluida en Chrome 7.0.
• Mono araña (Firefox) usos tipo de fusión.
• JavaScriptCore (Safari) también utiliza tipo de fusión.

Desde ES2019 el lenguaje garantiza que sort() is estable, lo que descarta un Quick Sort simple dentro del motor. La ordenación basada en fusión necesita memoria auxiliar O(n) y debe llamar a su JavaComparador de scripts para cada comparación. Un Quick Sort numérico escrito a mano compara números directamente y los ordena en el mismo lugar, por lo que puede ser más eficiente con grandes matrices numéricas. Ordenar 1,000,000 de enteros aleatorios en Node.js 22 tomó aproximadamente 100 ms con la Ordenación rápida a continuación y aproximadamente 210 ms con sort((a, b) => a - b).

Por lo tanto, vale la pena escribir Quick Sort cuando se necesita ordenar in situ, un control preciso de la memoria o simplemente una comprensión sólida de cómo funciona la ordenación. Analicemos la mecánica en detalle.

¿Cómo funciona la ordenación rápida?

El algoritmo Quick Sort repite una operación central, llamada particionamiento, en rangos cada vez más pequeños. Estos son los pasos en orden:

1. Encuentre el elemento pivote elemento en la matriz.
2. Coloca el puntero izquierdo en el primer elemento del rango.
3. Coloque el puntero derecho en el último elemento del rango.
4. Compara el elemento indicado por el puntero izquierdo con el pivote. Si es menor que el pivote, mueve el puntero izquierdo un paso a la derecha. Continúa hasta que el elemento izquierdo sea mayor o igual que el pivote.
5. Compara el elemento de la derecha con el pivote. Si es mayor que el pivote, mueve la derecha un paso a la izquierda. Continúa hasta que el elemento de la derecha sea menor o igual que el pivote.
6. Si el puntero izquierdo sigue siendo menor o igual que el puntero derecho, intercambie los dos elementos.
7. Incrementa el puntero izquierdo y disminuye el puntero derecho.
8. Si el índice izquierdo sigue siendo menor o igual que el índice derecho, repita desde el paso 4. De lo contrario, devuelva el índice del puntero izquierdo.

El diagrama de arriba tracSe muestran esos movimientos de puntero en un array de ejemplo. Cada elemento menor que el pivote termina a su izquierda y cada elemento mayor termina a su derecha, que es precisamente lo que indica el índice devuelto. La siguiente sección describe el mismo array paso a paso.

Cómo determinar el elemento pivote

Elegir el pivote es la única decisión que separa un Quick Sort rápido de uno lento. Si siempre tomas el first elemento, un arreglo ya ordenado produce la peor división posible: un lado vacío y un lado con todos los elementos restantes. Eso convierte el algoritmo en O(n²). Tomando el medio El elemento (la longitud del array dividida por dos) evita ese problema para entradas ordenadas y en orden inverso, razón por la cual el código a continuación lo utiliza.

Estrategias de cambio de rumbo comunes:

• Primer o último elemento: Es el más sencillo de programar, pero tiene una complejidad de O(n²) en datos ordenados.
• Elemento central: una buena configuración predeterminada que maneja matrices ordenadas y en orden inverso en O(n log n).
• Elemento aleatorio: hace que sea imposible construir de antemano el peor escenario posible.
• Mediana de tres: toma la mediana del primer, el del medio y el último valor; la opción estándar en las bibliotecas de producción.

Ahora, recorra el algoritmo de ordenación rápida en el array. [ 5,3,7,6,2,9 ].

PASO 1: El pivote es el elemento central. Con izquierda = 0 y derecha = 5, Math.floor((5 + 0) / 2) da el índice 2, por lo que el valor pivote es 7.

PASO 2: Comience los punteros en los extremos del array. El puntero izquierdo está en el índice 0 (valor 5) y el puntero derecho está en el índice 5 (valor 9).

PASO 3: Compara el valor de la izquierda con el pivote. 5 < 7, así que avanza a la derecha hasta el índice 1. 3 < 7, así que avanza a la derecha hasta el índice 2. El valor allí es 7, que no es menor que el pivote, por lo que el puntero izquierdo se detiene en el índice 2.

PASO 4: Compara el valor de la derecha con el pivote. 9 > 7, así que avanza a la izquierda hasta el índice 4. El valor allí es 2, que no es mayor que el pivote, por lo que el puntero derecho se detiene en el índice 4.

PASO 5: El índice izquierdo (2) es menor o igual que el índice derecho (4), por lo que se intercambian los dos valores. El array queda [ 5,3,2,6,7,9 ].

PASO 6: Mueva ambos punteros un paso hacia adentro. El puntero izquierdo ahora está en el índice 3 y el puntero derecho también en el índice 3.

PASO 7: Repite el escaneo. El valor en el índice 3 es 6, y 6 < 7, por lo que el puntero izquierdo avanza al índice 4. El valor en el índice 3 no es mayor que el pivote, por lo que el puntero derecho permanece en el índice 3.

PASO 8: El índice izquierdo (4) ahora es mayor que el índice derecho (3), por lo que el bucle termina y la función devuelve 4Todo lo que está antes del índice 4 es menor o igual que el pivote, y todo lo que está a partir del índice 4 es mayor o igual que él.

Según esa guía, necesitas código para dos operaciones: intercambioping dos elementos y partición de un rango.

Code intercambiar dos Numbers in JavaScript

Como muestra la captura de pantalla del editor anterior, la función auxiliar de intercambio utiliza una variable temporal para intercambiar los valores en dos índices. Modifica directamente el array y no devuelve nada.

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Salida:

[ 9, 3, 7, 6, 2, 5 ]

Code para realizar la partición

El código de la captura de pantalla anterior convierte los pasos del 1 al 8 en una función. Los dos internos bucles avanzar los punteros, el if El bloque realiza el intercambio y la función devuelve el índice de división.

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Salida:

[ 5, 3, 2, 6, 7, 9 ]
4

El resultado coincide exactamente con el tutorial manual: después de una pasada de partición, el array es [5,3,2,6,7,9] y el índice de división devuelto es 4.

Realizar la recursión Operadisrupción

Una vez que la partición devuelve el índice de división, úselo para dividir el rango y ejecute el algoritmo de ordenación rápida en cada mitad. Por eso se le llama algoritmo de divide y vencerás. La recursión continúa hasta que cada subrango contiene un solo elemento, momento en el que todo el array está ordenado.

Nota: El algoritmo Quick Sort trabaja con el mismo array en todo momento. No se crean nuevos arrays durante el proceso, lo que lo convierte en un algoritmo in situ.

Entonces llamas al dividir() la función explicada anteriormente y usar su valor de retorno para dividir el matriz en partes. Aquí está el código que lo hace:

Observe las dos condiciones de seguridad resaltadas en la captura de pantalla. left < index - 1 confirma que al menos dos elementos permanecen en el lado izquierdo, y index < right Se confirma lo mismo para el lado derecho. Sin esas protecciones, la función se llamaría a sí misma indefinidamente en rangos de un solo elemento.

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Salida:

[ 2, 3, 5, 6, 7, 9 ]

Ordenación rápida completa Code

Al combinar las partes de intercambio, partición y recursión, se obtiene la implementación completa:

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

Salida:

[ 2, 3, 5, 6, 7, 9 ]

La captura de pantalla anterior muestra el programa completo en el editor junto con el array ordenado en la consola. Esta implementación se verificó con un array ya ordenado, un array ordenado en orden inverso, arrays que contenían valores duplicados e idénticos, números negativos, un solo elemento y un array vacío, y devuelve el resultado correcto en todos los casos.

Complejidad temporal y espacial del algoritmo de ordenación rápida (Quick Sort)

Cada pasada de partición accede a cada elemento del rango una sola vez, por lo que una sola pasada tiene un coste de O(n). Por lo tanto, el coste total depende de cuántas veces se pueda dividir el array antes de que los rangos se vuelvan triviales.

La complejidad espacial es O(log n). Para esta versión in situ, no se asigna un segundo array, por lo que la única memoria adicional es la pila de recursión, y la división equilibrada mantiene esa pila con una profundidad de aproximadamente log₂(n) marcos. En el peor caso degenerado, la pila crece hasta O(n) marcos, razón por la cual los arrays muy grandes pueden desbordar la pila de llamadas.

Dos cifras lo demuestran. Ordenar 4,096 valores aleatorios con el código anterior requirió aproximadamente 65 000 comparaciones frente a un n·log₂(n) teórico de 49 152, y la recursión más profunda alcanzó los 24 marcos, mientras que log₂(4096) es 12. Ambas cifras se encuentran dentro del pequeño factor constante esperado para un algoritmo O(n log n).

Ordenación rápida frente a otros métodos de ordenación Algorithms

El algoritmo Quick Sort rara vez es la única opción. La siguiente tabla lo compara con los demás algoritmos que probablemente encontrará, para que pueda elegir el más adecuado para sus datos.

En la práctica, Quick Sort suele ser la mejor opción debido a que su bucle interno es eficiente y funciona en rangos contiguos que optimizan el uso de la caché. Elija merge sort cuando necesite un límite garantizado de O(n log n) o un ordenamiento estable, heap sort cuando la memoria sea extremadamente limitada y insertion sort para arreglos muy pequeños o casi ordenados. Las bibliotecas de producción suelen combinarlos: introsort comienza con Quick Sort, cambia a heap sort si la recursión se vuelve demasiado profunda y finaliza con insertion sort en rangos pequeños.

Cómo ordenar rápidamente objetos y cadenas de texto

La implementación mostrada hasta ahora compara valores con < y >, lo que lo restringe a números. Las aplicaciones reales necesitan ordenar objetos por una propiedad, cadenas alfabéticamente o fechas cronológicamente. La solución es mover la comparación a una función de devolución de llamada, exactamente como la función integrada. sort() hace.

Un comparador recibe dos valores y devuelve un número negativo cuando el primero debe ir primero, un número positivo cuando el segundo debe ir primero y cero cuando ambos son equivalentes. Reemplazar las dos comparaciones predefinidas con llamadas al comparador permite que el algoritmo funcione con cualquier tipo de dato.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Salida:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Hay tres detalles que merecen ser destacados. El guardia de recursión ahora es left >= right, lo cual es correcto para cualquier rango y no depende de la longitud del array externo. La comparación de cadenas utiliza localeCompare() De esta forma, los caracteres acentuados y las mayúsculas/minúsculas se manejan correctamente, en lugar de hacerlo mediante código fuente. Además, dado que la ordenación rápida no es estable, los registros que comparten un salario pueden intercambiar posiciones; si el orden original es importante, ordene por una segunda clave de desempate.

¿Listo para seguir adelante? Fortalece los fundamentos con el JavaIntroducción al guion, practica la mecánica del puntero en JavaBucles de scripttrabajar a través de más Información JavaEjemplos de código de script, comparar implementaciones en Tipo de inserción y Ordenar montóno agregue tipos estáticos a este algoritmo con el TypeScript referencia.

Preguntas Frecuentes