Zum Inhalt
wannacode

Quicksort und der schlechte Pivot

Kurz gesagt: Quicksort teilt das Array an Ort und Stelle um einen Pivot und sortiert beide Teile: im Durchschnitt O(n log n), aber ein schlechter Pivot macht ihn bei sortierter Eingabe zu O(n²).

Problem

Die sortierte Preisliste friert ein

Der Shop sortiert seine 100.000 Produkte mit Quicksort: Bei einem gemischten Katalog sind das 2.136.015 Vergleiche, und die Seite öffnet sich sofort. Dann beginnt der Lieferant, seine Preisliste schon nach Preis sortiert zu schicken. Derselbe Knopf „Nach Preis sortieren“ denkt lange nach und hört mit einem Fehler auf:

const prices = catalog(100000).sort((a, b) => a - b);
try {
  quickSort(prices, 0, prices.length - 1);
  console.log("Sortiert");
} catch (e) {
  console.log(`Stack erschöpft: ${e.name}`);
}
Ausgabe
Stack erschöpft: RangeError

Die Eingabe ist nicht größer, nur sortiert. Eine sortierte Eingabe sollte die leichteste sein, und hier ist sie die schwerste. Um zu sehen, warum, schau zuerst, wie Quicksort arbeitet.

Die Idee

Pivot und Partition

Mergesort teilt die Liste in zwei Hälften, ohne die Preise anzusehen, und die ganze Arbeit steckt im Zusammenfügen. Quicksort macht das Gegenteil: Die Arbeit steckt im Teilen, und es gibt kein Zusammenfügen. Es ist trotzdem Teile und herrsche, wie bei Mergesort.

  1. Wähle einen Preis als Pivot. Hier ist es der erste Preis des Teils.
  2. Partitioniere: Die Preise, die kleiner sind als der Pivot, gehen nach links, der Rest nach rechts, und der Pivot landet dazwischen. Das ist auch sein endgültiger Platz.
  3. Sortiere den linken und den rechten Teil mit derselben Methode. Ein Teil mit einem Preis oder ein leerer ist schon sortiert: Das ist der Basisfall der Rekursion.

Das Partitionieren tauscht Preise im selben Array, ohne Kopien. Deshalb braucht Quicksort nicht O(n) zusätzlichen Speicher wie Mergesort.

Sieh es dir an

Das Partitionieren Schritt für Schritt

Die Partition ist hier die nach Lomuto: j geht die Preise einzeln durch, und i markiert das Ende der linken Zone, in der die Preise unter dem Pivot stehen. Jeder kleinere Preis tritt der Zone mit einem Tausch bei. Am Ende tauscht der Pivot mit prices[i] und landet an seinem Platz:

function partition(prices, lo, hi) {
  const pivot = prices[lo];
  let i = lo;
  for (let j = lo + 1; j <= hi; j++) {
    if (prices[j] < pivot) {
      i++;
      [prices[i], prices[j]] = [prices[j], prices[i]];
    }
  }
  [prices[lo], prices[i]] = [prices[i], prices[lo]];
  return i;
}
Schritt für Schritt, in Worten
  1. Der Pivot ist der erste Preis, 45. i = 0 markiert das Ende der linken Zone, der Preise unter 45. Sie ist noch leer.
  2. j = 1: 80 < 45? Nein. 80 bleibt rechts, i bewegt sich nicht.
  3. j = 2: 20 < 45? Ja. i wird 1 und 20 tauscht den Platz mit 80: Die linke Zone wächst.
  4. j = 3: 65 < 45? Nein. 65 bleibt rechts, i bewegt sich nicht.
  5. j = 4: 10 < 45? Ja. i wird 2 und 10 tauscht den Platz mit 80: Die linke Zone wächst.
  6. j = 5: 90 < 45? Nein. 90 bleibt rechts, i bewegt sich nicht.
  7. j = 6: 30 < 45? Ja. i wird 3 und 30 tauscht den Platz mit 65: Die linke Zone wächst.
  8. j = 7: 55 < 45? Nein. 55 bleibt rechts, i bewegt sich nicht.
  9. j hat das Ende erreicht: 7 Vergleiche bei 8 Preisen, n − 1. Der Pivot tauscht mit prices[i] = 30 und landet bei Index 3.
  10. Links 30, 20, 10, alle unter 45; rechts 80, 90, 65, 55. 45 steht an seinem endgültigen Platz, und die zwei Teile werden getrennt sortiert, im selben Array, ohne zusätzlichen Speicher.
const prices = [45, 80, 20, 65, 10, 90, 30, 55];
const p = partition(prices, 0, prices.length - 1);
console.log(`[${prices.join(", ")}], p = ${p}`);
Ausgabe
[30, 20, 10, 45, 80, 90, 65, 55], p = 3

partition liefert, wo der Pivot gelandet ist, p = 3. Es gibt n − 1 Vergleiche: Jeder Preis außer dem Pivot wird genau einmal mit ihm verglichen.

[prices[i], prices[j]] = [prices[j], prices[i]]; ist ein Tausch mit Destrukturierung: Die rechte Seite wird ganz ausgewertet, bevor die linke geschrieben wird.

Sieh es dir an

Der ganze Quicksort

quickSort partitioniert den Teil von lo bis hi und ruft sich für beide Seiten des Pivots selbst auf. Der Pivot selbst steht schon an seinem Platz und geht in keine von beiden:

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const p = partition(prices, lo, hi);
  quickSort(prices, lo, p - 1);
  quickSort(prices, p + 1, hi);
}
const prices = [45, 80, 20, 65, 10, 90, 30, 55];
console.log(`Vorher: [${prices.join(", ")}]`);
quickSort(prices, 0, prices.length - 1);
console.log(`Nachher: [${prices.join(", ")}]`);
Ausgabe
Vorher: [45, 80, 20, 65, 10, 90, 30, 55]
Nachher: [10, 20, 30, 45, 55, 65, 80, 90]

Die Idee

Im Durchschnitt n · log n, manchmal n²

Was Quicksort kostet, hängt vom Pivot ab.

  • Ein guter Pivot liegt irgendwo in der Nähe der Mitte. Die zwei Teile sind je etwa die Hälfte, und wie bei Mergesort gibt es etwa log₂ n Ebenen. Auf jeder Ebene gehen die Partitionen zusammen einmal durch alle n Preise: insgesamt etwa n · log₂ n. Bei zufällig gemischten Preisen ist der erste Preis zufällig, also ist das der durchschnittliche Fall.
  • Ein schlechter Pivot ist der kleinste (oder der größte) Preis im Teil. Der linke Teil ist leer, und der rechte verliert nur den Pivot. Es gibt n Ebenen und (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 Vergleiche. Das ist O(n²), so viel wie bei den einfachen Sortierverfahren.

Bei sortierter Eingabe ist der erste Preis jedes Teils der kleinste. Die leichteste Eingabe wird also zum schlechtesten Fall:

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const p = partition(prices, lo, hi);
  quickSort(prices, lo, p - 1);
  quickSort(prices, p + 1, hi);
}
Schritt für Schritt, in Worten
  1. Die Preisliste ist schon sortiert, von 7 bis 80. Der Pivot ist der erste Preis jedes Teils.
  2. Der Pivot 7 ist der kleinste Preis: 7 Vergleiche, und nach links geht nichts. Der linke Teil ist leer, der rechte hat 7 Preise.
  3. Auf jeder Ebene dasselbe: Der Pivot ist wieder der kleinste, und der Teil verliert nur einen Preis. Jede Ebene ist ein weiterer verschachtelter Aufruf.
  4. 8 Ebenen und 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 Vergleiche, n(n − 1)/2. Bei 100.000 Preisen: 4.999.950.000 Vergleiche und 100.000 verschachtelte Aufrufe, mehr, als der Stack fasst.
  5. Die Abhilfe: Vor dem Partitionieren wandert ein zufälliger Preis des Teils nach vorn. Der Rest des Codes ist derselbe.
  6. Ein möglicher Ablauf auf derselben sortierten Liste. Ein zufälliger Pivot liegt meist irgendwo in der Mitte, also bekommen beide Teile Preise.
  7. 5 Ebenen statt 8 und 17 Vergleiche statt 28. Ein anderer Ablauf wäre etwas anders, aber die Reihenfolge der Eingabe spielt keine Rolle mehr: im Durchschnitt etwa n · log₂ n.

Probier es aus

Sage die Ausgabe voraus

Fünf Preise, und der Pivot ist der erste, 50. Was gibt das Programm aus?

function partition(prices, lo, hi) {
  const pivot = prices[lo];
  let i = lo;
  for (let j = lo + 1; j <= hi; j++) {
    if (prices[j] < pivot) {
      i++;
      [prices[i], prices[j]] = [prices[j], prices[i]];
    }
  }
  [prices[lo], prices[i]] = [prices[i], prices[lo]];
  return i;
}


const prices = [50, 70, 20, 90, 40];
const p = partition(prices, 0, prices.length - 1);
console.log(`[${prices.join(", ")}], p = ${p}`);
Antwort

Sieh es dir an

Miss es: der erste Pivot und ein zufälliger Pivot

Lass Quicksort auf einem gemischten und auf einem sortierten Katalog laufen. Gezählt werden die Vergleiche mit dem Pivot. Der erste Pivot bei 100.000 sortierten Preisen läuft nicht wirklich: Bench schätzt ihn aus der Kurve.

  • Quicksort, erstes Pivot, gemischte Preise O(n log n)
  • Quicksort, erstes Pivot, sortierte Preise O(n²)
  • Quicksort, zufälliges Pivot, sortierte Preise O(n log n)
Algorithmusn = 10n = 1.000n = 10.000n = 100.000
Quicksort, erstes Pivot, gemischte Preise3510.591151.4932.136.015
Quicksort, erstes Pivot, sortierte Preise45499.50049.995.000≈ 4.999.500.000
Quicksort, zufälliges Pivot, sortierte Preise2110.576153.7252.316.280
Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.
function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const k = lo + Math.floor(Math.random() * (hi - lo + 1));
  [prices[lo], prices[k]] = [prices[k], prices[lo]];
  const p = partition(prices, lo, hi);
  quickSort(prices, lo, p - 1);
  quickSort(prices, p + 1, hi);
}

Bei einem gemischten Katalog mit 1000 Preisen macht der erste Pivot 10.591 Vergleiche. Beim selben Katalog, sortiert, sind es 499.500, genau 1000 · 999 / 2. Ein zufälliger Pivot beim sortierten Katalog: 10.576, fast so viele wie beim gemischten. Bei 100.000 Preisen macht der zufällige Pivot 2.316.280 Vergleiche, und der erste Pivot würde n(n − 1)/2 = 4.999.950.000 machen (Bench schätzt aus der Kurve etwa 5 Milliarden).

Genauer, für Neugierige

Dieselben Zahlen in deiner Sprache. Der Katalog und die zufälligen Positionen kommen aus einem kleinen Generator mit Seed, sind also bei jedem Lauf, in jeder Sprache und in Bench gleich. Das ist die endgültige Version aus der Lektion (mit Rekursion in den kleineren Teil, siehe unten), und sie gibt auch aus, wie tief der Stack wurde:

let comparisons = 0;
let seed = 0;
let deepest = 0;


function catalog(n) {
  const prices = [];
  let x = 2026;
  for (let k = 0; k < n; k++) {
    x = (x * 48271) % 2147483647;
    prices.push(1 + (x % 10000));
  }
  return prices;
}


function quickSort(prices, lo, hi, random, depth) {
  deepest = Math.max(deepest, depth);
  while (lo < hi) {
    if (random) {
      seed = (seed * 48271) % 2147483647;
      const k = lo + (seed % (hi - lo + 1));
      [prices[lo], prices[k]] = [prices[k], prices[lo]];
    }
    const p = partition(prices, lo, hi);
    if (p - lo < hi - p) {
      quickSort(prices, lo, p - 1, random, depth + 1);
      lo = p + 1;
    } else {
      quickSort(prices, p + 1, hi, random, depth + 1);
      hi = p - 1;
    }
  }
}


function partition(prices, lo, hi) {
  const pivot = prices[lo];
  let i = lo;
  for (let j = lo + 1; j <= hi; j++) {
    comparisons++;
    if (prices[j] < pivot) {
      i++;
      [prices[i], prices[j]] = [prices[j], prices[i]];
    }
  }
  [prices[lo], prices[i]] = [prices[i], prices[lo]];
  return i;
}


const runs = [
  ["erster Pivot, gemischt", 1000, false, false],
  ["erster Pivot, gemischt", 100000, false, false],
  ["erster Pivot, sortiert", 1000, true, false],
  ["zufälliger Pivot, sortiert", 1000, true, true],
  ["zufälliger Pivot, sortiert", 100000, true, true],
];
for (const [label, n, isSorted, random] of runs) {
  const prices = catalog(n);
  if (isSorted) {
    prices.sort((a, b) => a - b);
  }
  comparisons = 0;
  seed = 12345;
  deepest = 0;
  quickSort(prices, 0, prices.length - 1, random, 1);
  console.log(`${label}, n = ${n}: ${comparisons} Vergleiche, Tiefe ${deepest}`);
}
Ausgabe
erster Pivot, gemischt, n = 1000: 10591 Vergleiche, Tiefe 7
erster Pivot, gemischt, n = 100000: 2136015 Vergleiche, Tiefe 11
erster Pivot, sortiert, n = 1000: 499500 Vergleiche, Tiefe 2
zufälliger Pivot, sortiert, n = 1000: 10576 Vergleiche, Tiefe 7
zufälliger Pivot, sortiert, n = 100000: 2316280 Vergleiche, Tiefe 11

Mergesort macht bei denselben 100.000 Preisen 1.536.292 Vergleiche, weniger als Quicksort. Trotzdem ist Quicksort in der Praxis oft schneller: Er tauscht Preise im selben Array, ohne Kopien, und liest den Speicher der Reihe nach.

Die Idee

Warum der Stack zu Ende ist

Jeder Aufruf von quickSort bleibt auf dem Aufrufstapel, bis er zurückkehrt. Bei einem schlechten Pivot ist der rechte Teil nur um einen Preis kleiner, also verschachteln sich die Aufrufe ineinander: n Ebenen bei n Preisen. Der Stack ist begrenzt, oft etwa 1 MB, und bei 100.000 verschachtelten Aufrufen ist er zu Ende.

JavaScript wirft RangeError: Maximum call stack size exceeded. In Node ist der Stack etwa 1 MB groß, und wie viele Aufrufe hineinpassen, hängt von der Größe des Frames ab.

Getrennt vom Stack ist die Zeit: n(n − 1)/2 Vergleiche. Bei 100.000 Preisen sind das etwa 5 Milliarden, deshalb „denkt“ der Knopf nach, bevor er scheitert.

Die Idee

Drei Abhilfen

Ein zufälliger Pivot. Vor dem Partitionieren wandert ein zufälliger Preis des Teils nach vorn und wird der Pivot. Dann ist keine Eingabe absichtlich schlecht: sortiert, umgekehrt und gemischt ergeben im Durchschnitt alle etwa n · log₂ n. Der schlechteste Fall existiert weiter, aber seine Wahrscheinlichkeit ist verschwindend klein: Auf jeder Ebene müsste der zufällige Preis genau der kleinste oder der größte im Teil sein.

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const k = lo + Math.floor(Math.random() * (hi - lo + 1));
  [prices[lo], prices[k]] = [prices[k], prices[lo]];
  const p = partition(prices, lo, hi);
  quickSort(prices, lo, p - 1);
  quickSort(prices, p + 1, hi);
}

Median aus drei. Statt eines zufälligen Preises nimmst du den dem Wert nach mittleren aus dem ersten, dem in der Mitte und dem letzten Preis. Bei sortierter Eingabe ist das genau die Mitte. Diese Abhilfe ist die Aufgabe am Ende der Lektion.

Rekursion in den kleineren Teil. Der Aufruf gilt nur dem kleineren der zwei Teile, und der größere bleibt für die Schleife: lo oder hi rückt weiter, und die Schleife partitioniert ihn erneut. Der kleinere Teil ist höchstens die Hälfte, also ist der Stack bei jedem Pivot höchstens log₂ n Ebenen tief: bis zu 17 bei 100.000 Preisen (das zählende Programm kommt auf 11). Die Vergleiche sinken dadurch nicht, deshalb gehört diese Abhilfe zum zufälligen Pivot:

function quickSort(prices, lo, hi) {
  while (lo < hi) {
    const k = lo + Math.floor(Math.random() * (hi - lo + 1));
    [prices[lo], prices[k]] = [prices[k], prices[lo]];
    const p = partition(prices, lo, hi);
    if (p - lo < hi - p) {
      quickSort(prices, lo, p - 1);
      lo = p + 1;
    } else {
      quickSort(prices, p + 1, hi);
      hi = p - 1;
    }
  }
}
const prices = catalog(100000).sort((a, b) => a - b);
quickSort(prices, 0, prices.length - 1);
console.log(`Sortiert: ${prices.every((x, i) => i === 0 || prices[i - 1] <= x)}`);
Ausgabe
Sortiert: true

Probier es aus

Finde den Fehler

Die acht Preise kommen fast sortiert heraus:

const prices = [45, 80, 20, 65, 10, 90, 30, 55];
console.log(`Vorher: [${prices.join(", ")}]`);
quickSort(prices, 0, prices.length - 1);
console.log(`Nachher: [${prices.join(", ")}]`);
Ausgabe
Vorher: [45, 80, 20, 65, 10, 90, 30, 55]
Nachher: [20, 30, 10, 45, 65, 80, 90, 55]

Das ist das partition des Programms. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Probier es aus

Fülle die Lücke

Die Rekursion geht in den kleineren, linken Teil. Was ist der neue Wert von lo, damit die Schleife mit dem rechten Teil weitermacht?

function quickSort(prices, lo, hi) {
  while (lo < hi) {
    const k = lo + Math.floor(Math.random() * (hi - lo + 1));
    [prices[lo], prices[k]] = [prices[k], prices[lo]];
    const p = partition(prices, lo, hi);
    if (p - lo < hi - p) {
      quickSort(prices, lo, p - 1);
      lo = ;
    } else {
      quickSort(prices, p + 1, hi);
      hi = p - 1;
    }
  }
}

Übung

Median aus drei

Löse die Aufgabe in deinem Editor.

Median aus drei. Schreibe median(prices, lo, hi), das drei Preise ansieht: bei lo, in der Mitte lo + (hi - lo) / 2 und bei hi, und die Position des dem Wert nach mittleren liefert. Tausche in quickSort (die einfache Rekursion aus der Lektion) diesen Preis vor dem Partitionieren mit prices[lo]. Zähle die Vergleiche mit dem Pivot in partition auf dem sortierten Katalog aus der Lektion (catalog aus dem zählenden Programm, dann sortiert) bei 1000 und bei 100.000 Preisen.

Ausgabe
Median aus drei, sortiert, n = 1000: 8005 Vergleiche
Median aus drei, sortiert, n = 100000: 1773717 Vergleiche

Vergleiche mit dem ersten Pivot: 499.500 Vergleiche bei 1000 sortierten Preisen, und bei 100.000 ist der Stack zu Ende.

Weitere Aufgaben

  • Eine umgekehrte Preisliste. Übergib den Katalog vom teuersten zum billigsten sortiert. Wie viele Vergleiche macht der erste Pivot? Und der Median aus drei?
  • Gleiche Preise. Übergib 1000 gleiche Preise. Wie viele Vergleiche macht die Partition nach Lomuto, und warum? (Hinweis: Nichts ist echt kleiner als der Pivot.)
  • Der teuerste zuerst. Ändere ein Zeichen in partition, damit die Liste vom teuersten zum billigsten herauskommt.

Genauer

Quicksort in der eingebauten Sortierung

Quicksort wurde 1959 von Tony Hoare erfunden, und er sitzt immer noch im Herzen der eingebauten Sortierung vieler Sprachen, aber nicht in reiner Form: Jede ergänzt Schutz gegen den schlechten Pivot.

Genauer, für Neugierige

Lomuto und Hoare. Die Partition hier ist die nach Lomuto: Sie ist leicht zu lesen, tauscht aber mehr. Die Partition nach Hoare, die ursprüngliche, lässt zwei Zeiger von beiden Enden aufeinander zulaufen und tauscht nur Paare von Preisen, die auf der falschen Seite stehen. Sie macht etwa dreimal weniger Tausche und kommt besser mit gleichen Preisen zurecht, aber der Pivot landet nicht unbedingt an seinem endgültigen Platz, und der Code ist leichter falsch zu schreiben.

Gleiche Preise. Bei vielen gleichen Preisen ergibt Lomuto trotzdem schlechte Teile: Alles, was dem Pivot gleicht, geht nach rechts. Eine Dreiwege-Partition bildet drei Zonen: kleiner, gleich und größer. Die gleichen sind erledigt und gehen nicht in die Rekursion.

Die eingebaute Sortierung. In JavaScript ist Array.prototype.sort in V8 (Chrome und Node) TimSort, eine Variante des Mergesort. Bis 2018 nutzte V8 Quicksort. Dann stieg es auf TimSort um, und seit ES2019 verlangt der Standard eine stabile Sortierung, die Quicksort nicht ist.

Quicksort ist nicht stabil: Ein Tausch kann über einen gleichen Preis springen, und gleiche Produkte ändern ihre Reihenfolge. Was das heißt und wann es zählt, steht in der Lektion Stabiles Sortieren und die eingebaute Sortierung.

Test

Teste dich

1. Was macht das Partitionieren um einen Pivot?
2. Der Pivot ist der erste Preis. Welche Eingabe ist der schlechteste Fall?
3. Warum scheitert der einfache Quicksort bei 100.000 sortierten Preisen mit StackOverflowError (RecursionError, RangeError)?
4. Die Rekursion geht nur in den kleineren Teil, und den größeren erledigt eine Schleife. Was bringt das?
5. Wie viel zusätzlichen Speicher braucht Quicksort, wenn er in den kleineren Teil rekursiert?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·