Algoritmo QuickSort en JavaScript

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

El algoritmo de clasificación rápida sigue el enfoque de dividir y conquistar. Divide los elementos en partes más pequeñas en función de alguna condición y realiza las operaciones de clasificación en esas partes más pequeñas divididas.

El algoritmo de clasificación rápida 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 sort () que ya está disponible en JavaScript. Entonces, es posible que haya estado pensando cuál es la necesidad de este algoritmo de clasificación rápida. Para entender esto, primero necesitamos qué es la ordenación y cuál es la ordenación predeterminada en JavaScript.

¿Qué es la clasificación?

Ordenar no es más que organizar los elementos en el orden que queramos. Es posible que te hayas encontrado con esto en tu escuela o en la universidad. Como ordenar los números de menor a mayor (ascendente) o de mayor a menor (descendente) es lo que vimos hasta ahora y se llama clasificación.

Clasificación predeterminada en JavaScript

Como se mencionó anteriormente, JavaScript tiene sort () . Tomemos un ejemplo con pocas matrices de elementos como [5,3,7,6,2,9] y queremos ordenar esta matriz de elementos en orden ascendente. Simplemente llame a sort () en la matriz de elementos y clasifica los elementos de la matriz en orden ascendente.

Código:

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

¿Cuál es la razón para elegir la ordenación rápida sobre la ordenació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. La ordenación predeterminada () en JavaScript utiliza la ordenación por inserción por motor V8 de Chrome y la ordenación por fusión de Mozilla Firefox y Safari .

Pero, por lo demás, esto no es adecuado si necesita ordenar una gran cantidad de elementos. Por lo tanto, 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 ordenación rápida y déjenos ver eso en detalle ahora.

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

La clasificación rápida sigue el algoritmo Divide and Conquer . Está dividiendo elementos en partes más pequeñas según alguna condición y realizando las operaciones de clasificación en esas partes más pequeñas divididas. Por lo tanto, funciona bien para grandes conjuntos de datos. Entonces, estos son los pasos de cómo funciona la ordenación rápida en palabras simples.

Primero seleccione un elemento que se llamará como elemento pivote .
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 la izquierda y más grandes que el pivote a la derecha.
Finalmente, realice las mismas operaciones en los elementos del lado izquierdo y derecho del elemento de pivote.

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

¿Cómo funciona QuickSort?

Primero busque el elemento "pivote" en la matriz.
Inicie el puntero izquierdo en el primer elemento de la matriz.
Inicie el puntero derecho en el último elemento de la matriz.
Compare el elemento apuntando 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.
Compare el elemento que apunta con el puntero derecho y si es mayor que el elemento pivote, mueva el puntero derecho hacia la izquierda (reste 1 al índice derecho). Continúe con esto hasta que el elemento del lado derecho sea menor o igual que el elemento de pivote.
Compruebe si el puntero izquierdo es menor o igual que el puntero derecho, luego vea los elementos en las ubicaciones de estos punteros.
Incrementa el puntero izquierdo y decrementa el puntero derecho.
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.

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

Determinar el elemento Pivot

Pero antes de seguir adelante con la clasificación rápida, la selección del elemento pivote juega un papel importante. Si selecciona el primer elemento como elemento de pivote, entonces ofrece el peor rendimiento en la matriz ordenada. Por lo tanto, siempre es recomendable elegir el elemento del medio (la longitud de la matriz dividida por 2) como elemento pivote y nosotros hacemos lo mismo.

Estos son los pasos para realizar la ordenació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. Dado que, 5 <6 desplaza el puntero izquierdo hacia la derecha hasta el índice 1.

PASO 4: Ahora, todavía 3 <6, así que mueva el puntero izquierdo a un índice más a la derecha. Así que ahora 7> 6 deja de incrementar el puntero izquierdo y ahora el puntero izquierdo está en el índice 2.

PASO 5: Ahora, compare el valor en el puntero derecho con el elemento pivote. Dado que 9> 6 mueve el puntero derecho hacia la izquierda. Ahora, como 2 <6, deje 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 cruza el puntero derecho y devuelva el índice del puntero izquierdo.

Entonces, aquí, 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:

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:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;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. Por lo tanto, se llama algoritmo Divide and Conquer.

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

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

Entonces, necesitamos llamar a esta partición () explicada anteriormente y en base a eso dividimos la matriz en partes. Así que aquí está el código donde lo usa,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Código de clasificación rápido 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 elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]