QuickSort in JavaScript

Wie Merge Sort verwendet QuickSort eine Teile-und-Herrsche-Strategie. Es wählt ein Element als Drehpunkt aus und partitioniert das angegebene Array darum herum.

Es gibt mehrere verschiedene QuickSort-Varianten, die alle Pivots unterschiedlich auswählen.

QuickSort in JavaScript

Eine Partition ist der Hauptprozess von quickSort(). Bei einem Array und einem Array-Member x als Drehpunkt besteht das Ziel der Partitionierung darin, x an der richtigen Position in einem sortierten Array zu platzieren und alle kleineren Elemente vor x und alle grösseren Elemente nach x zu platzieren. ; All dies sollte in linearer Zeit abgeschlossen werden.

JavaScript hat die Methode sort(). Obwohl sort() das gewünschte Ergebnis liefert, ist das Problem, wie es die Array-Komponenten sortiert.

Das standardmäßige sort() in JavaScript verwendet Insertion Sort von Chromes V8 Engine und Merge Sort von Mozilla Firefox und Safari. Dies ist jedoch nicht geeignet, wenn Sie viele Elemente sortieren müssen.

Daher ist die Lösung für große Datasets die Verwendung von Quick Sort.

Hier sind die einfachen Schritte zur Implementierung von Quick Sort.

Schauen wir uns diese Prozesse am Beispiel eines Arrays mit unsortierten Elementen [9, 1, 4, 7, 0, 2, 5, 8] genauer an. Wir machen das letzte Element zum Pivot.

JavaScript-Code für die Partitionierung:

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;
};

JavaScript-Code zum Ausführen des Austauschs:

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

Die Schnellsortierung wird verwendet, bis alle Elemente in den linken und rechten Arrays sortiert wurden. Während der Schnellsortierung werden keine neuen Arrays erstellt; es verwendet einfach das aktuelle Array.

Daher müssen wir die oben beschriebene Funktion partitionFunction() aufrufen, um das Array in Stücke zu teilen. Der Code wird Ihnen hier zur Verfügung gestellt.

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);

Führen Sie die obige Codezeile in jedem mit JavaScript kompatiblen Browser aus. Es wird das folgende Ergebnis angezeigt:

Ausgang:

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

Zur Demo gelangen Sie hier.