Sorteo rápido en JavaScript
Cómo funciona el algoritmo de clasificación
El algoritmo QuickSort elige un elemento y lo considera un elemento dinámico; ahora el elemento pivote está reservado.
A continuación, tomaremos los dos consejos 'P' y 'Q'.
El puntero 'P' se moverá del lado izquierdo al lado derecho y no se detendrá hasta que encuentre un elemento más grande o igual que el elemento pivote.
El segundo puntero 'Q' se moverá del lado derecho hacia el lado izquierdo y dejará de buscar cuando encuentre un elemento menor o igual al elemento pivote.
Entonces, 'P' ordenará los elementos más pequeños en el lado izquierdo y 'Q' ordenará los elementos mayores al lado derecho.
Ahora entenderemos el funcionamiento del algoritmo de clasificación rápida con la ayuda de un ejemplo:
Supongamos que tenemos una variedad de seis elementos y queremos ordenarlo en orden ascendente usando un algoritmo Quicksort:
En el paso inicial, seleccionamos '36' como un elemento dinámico (elemento medio):
En el siguiente paso, seleccionamos nuestros punteros, el puntero 'P' para movernos de izquierda a la derecha y 'Q' Punter para moverse de lado derecho al lado izquierdo:
Ahora el valor del puntero izquierdo 'P' se comparará con el valor de pivote, ya que '35' es menor que '36' mover el puntero 'P' al elemento adyacente. Por otro lado, compare el valor del puntero derecho 'Q' con el valor de pivote, '39' es mayor que '36' para que el puntero 'Q' se moverá hacia el elemento adyacente izquierdo:
Ahora, el puntero 'P' apunta a '33' y se compara con el pivote '36', el valor del puntero 'P' es menor que el valor de pivote, por lo tanto, el puntero 'P' se cambiará al elemento adyacente. Mientras que el valor de 'Q' puntero '32' es menor que el valor dinámico '36', por lo que se detendrá aquí:
El valor del puntero izquierdo '37' es mayor que el valor del pivote '36', por lo que también se detendrá aquí. Ahora, 'P' se detiene en '37' y 'Q' se detiene en '32'.
Ahora verificaremos si el puntero 'P' cruza el puntero 'Q' o no. En este caso, hasta ahora 'P' no cruza el puntero 'Q', por lo que cambiaremos el valor de Pointer 'P' con el valor del puntero 'Q':
Ahora 'P' y 'Q' están apuntando a '32' y '37' respectivamente, cambian los punteros una vez más, ahora P = Q ('36 '=' 36 '):
Mueva los punteros una vez más, ya que el puntero 'P' cruza el puntero 'Q', así que aquí se detendrá y devolverá el índice del puntero 'P'. Hasta ahora, el elemento pivote está en su posición correcta y todos los elementos mayores que el elemento pivote están en el lado derecho del pivote, y todos los elementos menos que los elementos de pivote están en el lado izquierdo del pivote. De esta manera, ordenaremos toda la lista.
Ahora implementaremos este concepto en JavaScript. Primero, el código para intercambiar elementos:
function swap_elements (Elements, Left_index, right_index)var temp = Elements [Left_index];
Elementos [Left_index] = Elements [Right_index];
Elementos [right_index] = temp;
A continuación, el código para dividir una lista en las subsists:
function sub_lists (Elements, Left_pointer, derecho_pointer)var pivot = elements [matemáticas.piso ((Right_pointer + Left_pointer) / 2)],
i = Left_pointer,
j = right_pointer;
mientras yo <= j)
while (elementos [i] pivote)
J--;
if (i 1)
index = sub_lists (Elements, Left_pointer, Right_pointer);
if (left_pointer < index - 1)
Quick_sort (Elements, Left_pointer, índice - 1);
if (índice < right_pointer)
Quick_sort (Elementos, índice, derecho_pointer);
Elementos de retorno;
Creamos una función que toma tres parámetros dentro de la función. Dividamos toda la lista en sub-listas y descubrimos el puntero izquierdo y el puntero derecho y escribimos el código para incrementar el puntero izquierdo si es menos que el elemento pivote y disminuye el puntero derecho si es mayor que el elemento pivote:
Ahora escribiremos el código para manejar el comportamiento recursivo del tipo rápido. Dado que en el paso anterior se devuelve el índice de izquierda_pointer y lo utilizaremos para dividir la lista en sub-listas y aplicar QuickSort en esas sub-listas:
función Quick_sort (Elements, Left_pointer, Right_pointer)índice var;
if (elementos.longitud> 1)
index = sub_lists (Elements, Left_pointer, Right_pointer);
if (left_pointer < index - 1)
Quick_sort (Elements, Left_pointer, índice - 1);
if (índice < right_pointer)
Quick_sort (Elementos, índice, derecho_pointer);
Elementos de retorno;
El fragmento de código completo irá así:
Elementos var = [35,33,37,36,32,39];function swap_elements (Elements, Left_index, right_index)
var temp = Elements [Left_index];
Elementos [Left_index] = Elements [Right_index];
Elementos [right_index] = temp;
function sub_lists (Elements, Left_pointer, derecho_pointer)
var pivot = elements [matemáticas.piso ((Right_pointer + Left_pointer) / 2)],
i = Left_pointer,
j = right_pointer;
mientras yo <= j)
while (elementos [i] pivote)
J--;
if (i 1)
index = sub_lists (Elements, Left_pointer, Right_pointer);
if (left_pointer < index - 1)
Quick_sort (Elements, Left_pointer, índice - 1);
if (índice < right_pointer)
Quick_sort (Elementos, índice, derecho_pointer);
Elementos de retorno;
var sorted_array = Quick_sort (elementos, 0, elementos.longitud - 1);
consola.log ("La lista ordenada:", sorted_array);
Inicializamos la matriz no organizada al comienzo del programa y al final del programa llamamos la función "Quick_sort ()" para obtener la matriz ordenada final:
Finalmente, cuando ejecutamos este código obtenemos la salida resultante como:
Conclusión:
Quicksort es un algoritmo de clasificación que funciona en la división y conquista la filosofía y divide el problema en subproblemas más pequeños. Y continúe este proceso hasta que logre el objetivo resultante. En este artículo, discutimos cómo funciona QuickSort e implementan ese concepto en JavaScript para resolver cualquier matriz de la manera más eficiente.