Clasificación rápida en JavaScript

En este artículo, veremos cómo implementar el algoritmo Quicksort. Revisaremos el enfoque recursivo e iterativo, y veremos la eficiencia de Quicksort.

Introducción

Ordenar se refiere a organizar los elementos de una lista en un orden específico (numérico o alfabético). La clasificación se usa generalmente junto con la búsqueda.

A lo largo de los años, se han desarrollado muchos algoritmos de clasificación, y uno de los más rápidos hasta la fecha es Quicksort.

Quicksort utiliza la estrategia divide y vencerás para ordenar la lista de elementos dada. Esto significa que el algoritmo descompone el problema en subproblemas hasta que se vuelven lo suficientemente simples para resolverlos directamente.

Algorítmicamente, esto se puede implementar de forma recursiva o iterativa. Sin embargo, el enfoque recursivo es más natural para este problema.

Comprender la lógica detrás de Quicksort

Echemos un vistazo a cómo funciona Quicksort:

  1. Seleccione un elemento de la matriz. Este elemento generalmente se llama pivote. La mayoría de las veces, este elemento es el primero o el último elemento de la matriz.
  2. Luego, reorganice los elementos de la matriz para que todos los elementos a la izquierda del pivote sean más pequeños que el pivote y todos los elementos a la derecha sean más grandes que el pivote. El paso se llama partición. Si un elemento es igual al pivote, no importa de qué lado vaya.
  3. Repita este proceso individualmente para el lado izquierdo y derecho del pivote, hasta que se ordene la matriz.

Entendamos más estos pasos al caminar a través de un ejemplo. Considere una matriz de elementos no ordenados [7, -2, 4, 1, 6, 5, 0, -4, 2]. Elegiremos el último elemento para que sea el pivote. El desglose paso a paso de la matriz sería como se muestra en la imagen a continuación:

Quick Sort Example

Los elementos que se han elegido como pivote en un paso del algoritmo tienen un contorno de color. Después de la partición, los elementos de pivote siempre están en sus posiciones correctas en la matriz.

Las matrices que tienen un contorno negro en negrita representan el final de esa rama recursiva específica, ya que terminamos con una matriz que contenía solo un elemento.

Podemos ver la clasificación resultante de este algoritmo simplemente revisando el elemento más bajo en cada "columna".

Implementación de Quicksort en JavaScript

Como pudimos ver, la columna vertebral de este algoritmo es el paso de partición. Este paso es el mismo independientemente de si usamos el enfoque recursivo o iterativo.

Con eso en mente, primero escribamos el código para particionar() una matriz:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function partition(arr, start, end){
    // Taking the last element as the pivot
    const pivotValue = arr[end];
    let pivotIndex = start; 
    for (let i = start; i < end; i++) {
        if (arr[i] < pivotValue) {
        // Swapping elements
        [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
        // Moving to next element
        pivotIndex++;
        }
    }
    
    // Putting the pivot value in the middle
    [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]] 
    return pivotIndex;
};

Aquí, estamos tomando el último elemento como pivote. Estamos utilizando una variable pivotIndex para realizar un seguimiento de la posición "central", donde todos los elementos a la izquierda son menores y todos los elementos a la derecha son mayores que el pivotValue.

Como último paso, intercambiamos el pivote, que es el último elemento en nuestro caso, con pivotIndex. Entonces, al final, nuestro elemento pivote terminaría en el "medio". Con todos los elementos menores que el pivote a la izquierda y todos los elementos mayores o iguales que el pivote a la derecha del pivote .

Implementación recursiva {#implementación recursiva}

Ahora que tenemos la función partition(), tenemos que desglosar recursivamente este problema y aplicar la lógica de partición para realizar los pasos restantes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function quickSortRecursive(arr, start, end) {
    // Base case or terminating case
    if (start >= end) {
        return;
    }
    
    // Returns pivotIndex
    let index = partition(arr, start, end);
    
    // Recursively apply the same logic to the left and right subarrays
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end);
}

En esta función, comenzamos dividiendo la matriz. Después de eso, dividimos los subarreglos izquierdo y derecho. Repetimos ese proceso siempre que el método reciba una matriz que no esté vacía o tenga más de un elemento.

Esto se debe a que las matrices vacías y las matrices con un solo elemento se consideran ordenadas.

Probemos este código en nuestro ejemplo original llamando:

1
2
3
4
array = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortRecursive(array, 0, array.length - 1)

console.log(array)

Esto nos daría la salida:

1
-4,-2,0,1,2,4,5,6,7

Implementación iterativa {#implementación iterativa}

Como mencionamos anteriormente, el enfoque recursivo de Quicksort es mucho más intuitivo. Sin embargo, implementar Quicksort iterativamente es una pregunta de entrevista relativamente común para los ingenieros de software.

Al igual que con la mayoría de las conversiones recursivas a iterativas, lo primero que debe pensar es usar una pila para simular llamadas recursivas. Esto se hace para que podamos reutilizar parte de la lógica recursiva con la que estamos familiarizados y usarla en una configuración iterativa.

Necesitamos hacer un seguimiento de alguna manera de los subarreglos sin ordenar que nos quedan. Una forma de hacer esto es simplemente mantener "pares" de elementos en una pila, representando el ‘inicio’ y el ‘final’ de un subarreglo no ordenado dado.

JavaScript no tiene una estructura de datos de pila explícita, pero las matrices admiten las funciones push() y pop(). Sin embargo, no admiten la función peek(), por lo que tendremos que verificar manualmente la parte superior de la pila usando stack[stack.length - 1].

Usaremos la misma función de partición que usamos para el enfoque recursivo. Veamos cómo escribir la parte Quicksort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function quickSortIterative(arr) {
    // Creating an array that we'll use as a stack, using the push() and pop() functions
    stack = [];
    
    // Adding the entire initial array as an "unsorted subarray"
    stack.push(0);
    stack.push(arr.length - 1);
    
    // There isn't an explicit peek() function
    // The loop repeats as long as we have unsorted subarrays
    while(stack[stack.length - 1] >= 0){
        
        // Extracting the top unsorted subarray
        end = stack.pop();
        start = stack.pop();
        
        pivotIndex = partition(arr, start, end);
        
        // If there are unsorted elements to the "left" of the pivot,
        // we add that subarray to the stack so we can sort it later
        if (pivotIndex - 1 > start){
            stack.push(start);
            stack.push(pivotIndex - 1);
        }
        
        // If there are unsorted elements to the "right" of the pivot,
        // we add that subarray to the stack so we can sort it later
        if (pivotIndex + 1 < end){
            stack.push(pivotIndex + 1);
            stack.push(end);
        }
    }
}

Probemos este código también en nuestro ejemplo, llamando a:

1
2
3
4
ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortIterative(ourArray)

console.log(ourArray)

Obtenemos la salida esperada de:

1
-4,-2,0,1,2,4,5,6,7

Visualización de clasificación rápida

Cuando se trata de clasificar algoritmos, siempre es bueno visualizarlos. Simplemente nos ayuda a “verlos” en acción. Aquí hay un ejemplo de cómo funciona el algoritmo Quicksort:

Quick Sort Visualisation GIF

[Fuente: Wikipedia{rel=“nofollow noopener” target="_blank"}]{.small}

En este caso, el pivote también se toma como último elemento. Después de dividir la matriz dada, el lado izquierdo se recorre recursivamente hasta que se ordena por completo. Luego, el algoritmo llega al lado derecho y realiza la clasificación.

La eficiencia de la clasificación rápida

Ahora que sabemos cómo implementar el algoritmo Quicksort, analicemos la complejidad del tiempo y el espacio. La complejidad temporal en el peor de los casos de Quick Sort es O(n^2^). La complejidad de tiempo de caso promedio es O(nlogn). El peor de los casos generalmente se evita mediante el uso de una versión aleatoria de Quicksort.

El punto débil del algoritmo Quicksort es la elección del pivote. Elegir un mal pivote (uno que sea mayor o menor que la mayoría de los elementos) cada vez, nos daría la complejidad de tiempo en el peor de los casos. Mientras que elegir repetidamente un pivote que tenga aproximadamente el mismo número de elementos que son menores o mayores que el pivote nos daría una complejidad de tiempo de O(nlogn).

Quicksort es uno de esos algoritmos donde el tiempo de ejecución del caso promedio es realmente importante. Empíricamente, se notó que Quicksort tiende a tener un tiempo de ejecución O(nlogn) independientemente de la estrategia de elección de pivote.

Además, cuando se trata de la complejidad del espacio, Quicksort no ocupa espacio adicional (excluyendo el espacio reservado para llamadas recursivas). Este tipo de algoritmos se denominan técnicamente algoritmos in situ. No necesitamos espacio adicional porque estamos realizando la operación en la misma matriz.

Conclusión

En este artículo, repasamos la teoría detrás de Quicksort y luego la implementamos de forma recursiva e iterativa usando JavaScript.