Clasificación rápida en JavaScript

Al igual que Merge Sort, QuickSort utiliza una estrategia de divide y vencerás. Selecciona un elemento como pivote y divide la matriz especificada a su alrededor.

Hay varias variaciones diferentes de QuickSort, y todas seleccionan pivotes de manera diferente.

Clasificación rápida en JavaScript

Una partición es el proceso principal de quickSort(). Dada una matriz y un miembro de matriz x como pivote, el objetivo de la partición es colocar x en su posición correcta en una matriz ordenada y colocar todos los elementos más pequeños antes de x y todos los elementos mayores después de x. ; todo esto debe completarse en tiempo lineal.

JavaScript tiene el método sort(). Aunque sort() da el resultado deseado, el problema es cómo ordena los componentes de la matriz.

El sort() predeterminado en JavaScript utiliza Ordenar por inserción del motor V8 de Chrome y Merge Sort de Mozilla Firefox y Safari. Sin embargo, esto no es apropiado si necesita clasificar muchos elementos.

Como resultado, la solución para grandes conjuntos de datos es usar Ordenación rápida.

Estos son los pasos simples para implementar Quick Sort.

Echemos un vistazo más de cerca a estos procesos utilizando un ejemplo de una matriz con elementos sin clasificar [9, 1, 4, 7, 0, 2, 5, 8]. Haremos que el último elemento sea el pivote.

Código JavaScript para particionar:

const partitionFunction = (arratItems, left, right) => {
  let pivotElement = arratItems[Math.floor((right + left) / 2)];
  let leftElement = left;
  let rightElement = right;
  while (leftElement <= rightElement) {
    while (arratItems[leftElement] < pivotElement) {
      leftElement++;
    }
    while (arratItems[rightElement] > pivotElement) {
      rightElement--;
    }
    if (leftElement <= rightElement) {
      swapFunction(arratItems, leftElement, rightElement);
      leftElement++;
      rightElement--;
    }
  }
  return leftElement;
};

Código JavaScript para realizar el intercambio:

const swapFunction = (arratItems, leftIndex, rightIndex) => {
  const temp = arratItems[leftIndex];
  arratItems[leftIndex] = arratItems[rightIndex];
  arratItems[rightIndex] = temp;
};

La ordenación rápida se utiliza hasta que se han ordenado todos los elementos de las matrices izquierda y derecha. No se crean nuevas matrices durante la ordenación rápida; simplemente usa la matriz actual.

Por lo tanto, debemos llamar a la función partitionFunction() descrita anteriormente para dividir la matriz en partes. El código se proporciona aquí para su uso.

const arratItems = [9, 1, 4, 7, 0, 2, 5, 8];
const quickSortFunction = (arratItems, left, right) => {
  let index;
  if (arratItems.length > 1) {
    index = partitionFunction(arratItems, left, right);
    if (left < index - 1) {
      quickSortFunction(arratItems, left, index - 1);
    }
    if (index < right) {
      quickSortFunction(arratItems, index, right);
    }
  }
  return arratItems;
};
// Initial call to quick sort function
const result = quickSortFunction(arratItems, 0, arratItems.length - 1);
console.log(result);

Ejecute la línea de código anterior en cualquier navegador compatible con JavaScript. Mostrará el siguiente resultado:

Producción :

[0, 1, 2, 4, 5, 7, 8, 9]

Acceda a la demostración aquí.