Algoritmo QuickSort en JavaScript

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

Ordenación rápida El algoritmo sigue el enfoque Divide y vencerás. Divide elementos en partes más pequeñas según alguna condición y realiza las operaciones de clasificación en esas partes más pequeñas divididas.

El algoritmo Quick Sort es uno de los algoritmos más utilizados y populares en cualquier lenguaje de programación. Pero, si es un desarrollador de JavaScript, es posible que haya oído hablar de ordenar() que ya está disponible en JavaScript. Entonces, quizás hayas estado pensando cuál es la necesidad de este algoritmo de clasificación rápida. Para entender esto, primero necesitamos qué es la clasificación y cuál es la clasificación predeterminada en JavaScript.

¿Qué es Ordenar?

Ordenar no es más que disponer los elementos en el orden que queramos. Es posible que te hayas encontrado con esto en tu época escolar o universitaria. Como ordenar números de menor a mayor (ascendente) o de mayor a menor (descendente), es lo que vimos hasta ahora y se llama ordenar.

Clasificación predeterminada en JavaScript

Como se mencionó anteriormente, JavaScript tiene ordenar(). Tomemos un ejemplo con una pequeña matriz de elementos como [5,3,7,6,2,9] y queremos ordenar los elementos de esta matriz en orden ascendente. Solo llama ordenar() en la matriz de elementos y ordena los elementos de la matriz en orden ascendente.

Clasificación predeterminada en JavaScript

Código:

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

¿Cuál es el motivo para elegir la clasificación rápida en lugar de la clasificación predeterminada () en JavaScript

Aunque sort() da el resultado que queremos, el problema radica en la forma en que ordena los elementos de la matriz. Clasificación predeterminada () en usos de JavaScript tipo de inserción by Motor V8 de cromo y Ordenar fusión by Mozilla Firefox y Safari.

Pero, por lo demás, esto no es adecuado si necesita ordenar una gran cantidad de elementos. Entonces, la solución es utilizar la clasificación rápida para conjuntos de datos grandes.

Entonces, para comprenderlo completamente, necesita saber cómo funciona la clasificación rápida y déjenos verlo en detalle ahora.

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

A continuación se realiza una clasificación rápida Divide y vencerás algoritmo. Consiste en dividir elementos en partes más pequeñas según alguna condición y realizar las operaciones de clasificación en esas partes más pequeñas divididas. Por tanto, funciona bien para grandes conjuntos de datos. Entonces, estos son los pasos sobre cómo funciona la clasificación rápida en palabras simples.

  1. Primero seleccione un elemento que se llamará como pivote .
  2. A continuación, compare todos los elementos de la matriz con el elemento pivote seleccionado y organícelos de tal manera que los elementos menores que el elemento pivote estén a su izquierda y los mayores que el pivote estén a su derecha.
  3. Finalmente, realice las mismas operaciones en los elementos del lado izquierdo y derecho del elemento pivote.

Entonces, ese es el esquema básico de la clasificación rápida. Estos son los pasos que deben seguirse uno por uno para realizar la clasificación rápida.

¿Cómo funciona QuickSort?

  1. Primero encuentra el "pivote" elemento en la matriz.
  2. Inicie el puntero izquierdo en el primer elemento de la matriz.
  3. Inicie el puntero derecho en el último elemento de la matriz.
  4. Compare el elemento que apunta con el puntero izquierdo y, si es menor que el elemento pivote, mueva el puntero izquierdo hacia la derecha (agregue 1 al índice izquierdo). Continúe esto hasta que el elemento del lado izquierdo sea mayor o igual que el elemento de pivote.
  5. Compare el elemento que apunta con el puntero derecho y, si es mayor que el elemento pivote, mueva el puntero derecho hacia la izquierda (resta 1 al índice derecho). Continúe esto hasta que el elemento del lado derecho sea menor o igual que el elemento pivote.
  6. Compruebe si el puntero izquierdo es menor o igual que el puntero derecho y luego intercambie los elementos en las ubicaciones de estos punteros.
  7. Incrementa el puntero izquierdo y disminuye el puntero derecho.
  8. Si el índice del puntero izquierdo sigue siendo menor que el índice del puntero derecho, repita el proceso; de lo contrario, devuelve el índice del puntero izquierdo.

¿Cómo funciona QuickSort?

Entonces, veamos estos pasos con un ejemplo. Consideremos que la matriz de elementos que necesitamos ordenar es [5,3,7,6,2,9].

Determinar el elemento pivote

Pero antes de continuar con la clasificación rápida, seleccionar el elemento pivote juega un papel importante. Si selecciona el primer elemento como elemento pivote, obtendrá el peor rendimiento en la matriz ordenada. Por lo tanto, siempre es recomendable elegir el elemento central (longitud de la matriz dividida por 2) como elemento pivote y hacemos lo mismo.

Estos son los pasos para realizar la clasificación rápida que se muestra con un ejemplo [5,3,7,6,2,9].

PASO 1: Determine el pivote como elemento intermedio. Entonces, 7 es el elemento pivote.

PASO 2: Inicie los punteros izquierdo y derecho como primer y último elemento de la matriz respectivamente. Entonces, el puntero izquierdo apunta a 5 en el índice 0 y el puntero derecho apunta a 9 en el índice 5.

PASO 3: Compare el elemento en el puntero izquierdo con el elemento pivote. Desde entonces, 5 <6 desplaza el puntero izquierdo hacia la derecha hasta el índice 1.

PASO 4: Ahora, todavía 3 6 deja de incrementar el puntero izquierdo y ahora el puntero izquierdo está en el índice 7.

PASO 5: Ahora, compare el valor en el puntero derecho con el elemento pivote. Desde 9 > 6 mueve el puntero derecho hacia la izquierda. Ahora, como 2 <6, deja de mover el puntero derecho.

PASO 6: Intercambie ambos valores presentes en los punteros izquierdo y derecho entre sí.

PASO 7: Mueva ambos punteros un paso más.

PASO 8: Dado que 6 = 6, mueva los punteros a un paso más y deténgase cuando el puntero izquierdo cruce el puntero derecho y devuelva el índice del puntero izquierdo.

Entonces, según el enfoque anterior, necesitamos escribir código para intercambiar elementos y particionar la matriz como se menciona en los pasos anteriores.

Código para intercambiar dos números en JavaScript

intercambiar dos números en JavaScript

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

Código para realizar la partición como se menciona en los pasos anteriores

Código para realizar la partició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;
}

Realizar la operación recursiva

Una vez que realice los pasos anteriores, se devolverá el índice del puntero izquierdo y debemos usarlo para dividir la matriz y realizar la clasificación rápida en esa parte. De ahí que se le llame algoritmo divide y vencerás.

Por lo tanto, la clasificación rápida se realiza hasta que todos los elementos de la matriz izquierda y derecha estén ordenados.

Nota: La clasificación rápida se realiza en la misma matriz y no se crean nuevas matrices en el proceso.

Entonces, debemos llamar a esto dividir() explicado anteriormente y en base a eso dividimos el matriz en partes. Entonces aquí está el código donde lo usas,

Operación recursiva

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 result = quickSort(items, 0, items.length - 1);

Código de clasificación rápida completo

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); //sawpping 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); //prints [2,3,5,6,7,9]

Ordenación rápida

NOTA: La clasificación rápida se ejecuta con Time Complexity de O(nlogn).