Vergelijkingen
Verwisselingen
Partities

  • Deel dat gepartitioneerd wordt
  • Pivot
  • Vergeleken
  • Verwisseld
  • Op zijn plek

Meer over quicksort

Quicksort

Quicksort kiest een pivot, zet elke kleinere waarde ervoor en elke andere waarde erachter, en sorteert dan beide kanten op dezelfde manier. Na elke partitie staat de pivot op zijn definitieve plek. Kies hoe de pivot gekozen wordt, speel het sorteren af op elke snelheid of loop het per vergelijking door, en zie waarom een slechte pivot op een gesorteerde lijst quicksort traag maakt. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om ergens naartoe te springen. De tegels tellen vergelijkingen, verwisselingen en partities. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen, en hoe de pivot gekozen wordt. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.

Hoe het werkt

  1. Kies hoeveel staven en hoe ze beginnen: willekeurig, bijna gesorteerd, omgekeerd of met weinig unieke waarden. Of typ je eigen getallen.
  2. Druk op Afspelen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
  3. Kies de pivotregel: de laatste waarde, de middelste waarde, een willekeurige waarde of de mediaan van drie. Probeer ze allemaal op een gesorteerde lijst.

Zo werkt quicksort

Kies één waarde van het te sorteren deel als pivot en zet die aan het eind. Loop de andere waarden van links naar rechts door; elke waarde die kleiner is dan de pivot wordt verwisseld naar een linkerdeel dat vanaf het begin groeit. Verwissel de pivot dan naar de plek direct na het linkerdeel. Alles ervoor is nu kleiner en niets erachter, dus de pivot staat op zijn definitieve plek. Sorteer het deel ervoor en het deel erachter op dezelfde manier, tot elk deel één waarde is.

Waarom de pivot ertoe doet

Als de pivot dicht bij het midden uitkomt, halveert elke partitie het probleem en groeit het aantal vergelijkingen als n log n: voor 40 willekeurige waarden ongeveer 190. Als de pivot de kleinste of grootste waarde is, is één kant leeg en heeft de andere al de rest. Met de laatste waarde als pivot gebeurt dat bij elke stap op een gesorteerde of omgekeerde lijst, en kost het sorteren n(n − 1)/2 vergelijkingen, 780 voor 40 waarden. Een willekeurige pivot of de mediaan van de eerste, middelste en laatste waarde voorkomt dat in de praktijk.

Veelgestelde vragen

Hoe werkt quicksort?

Het kiest een pivot, partitioneert de lijst zodat de kleinere waarden vóór de pivot komen en de rest erachter, en sorteert dan beide kanten met quicksort. Na elke partitie staat de pivot op zijn definitieve plek.

Waarom is quicksort traag op een gesorteerde lijst?

Met de eerste of laatste waarde als pivot geeft een gesorteerde lijst altijd de kleinste of grootste waarde als pivot. Eén kant van de partitie is dan leeg, dus elke partitie haalt maar één waarde weg, en het sorteren kost n(n − 1)/2 vergelijkingen. Een willekeurige pivot of de mediaan van drie lost dit in de praktijk op.

Is quicksort sneller dan mergesort?

Vaak wel, in de praktijk: het sorteert in-place, heeft geen buffer nodig en de binnenste lus is heel eenvoudig. Gemiddeld doet het iets meer vergelijkingen dan mergesort, en het slechtste geval is n², terwijl mergesort altijd n log n is. Sorteerfuncties in bibliotheken, zoals introsort, beginnen met quicksort en schakelen over op heapsort als de splitsingen te ongelijk worden.

Is quicksort stabiel?

Nee. Een partitie verwisselt waarden over grote afstanden, dus gelijke waarden kunnen van volgorde veranderen.

Worden mijn getallen ergens naartoe gestuurd?

Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor