Sorteer

Maandag, 2 september 2002
Quick sort (gamedev.net/...) is een aardig sorteer algoritme, al in 1962 uitgevonden door prof. C. A. R. Hoare (...infcharles.html).
  • Het sorteert in de array zelf, met behulp van slechts een paar pointers die van buiten naar binnen lopen.
  • Het gebruikt krachtige recursie om de getallenreeksen steeds verder te splitsen (...sortieren/quick...).
  • Het is vrij snel.
Genomen stap <=4 te doen >4
4 als pivot   5, 3, 4, 2, 1  
1 en 5 verwisseld 1 3, 4, 2 5
3, 4, en 2 naar links 1, 3, 4, 2   5
3 als pivot <=3 te doen >3   5
1 en 3 naar links 1, 3 4, 2     5
4 en 2 verwisseld 1, 3, 2   4   5
3 als pivot <=3 te doen >3   4   5
  1, 3, 2     4   5
1, 3, 2 naar links? 1, 3, 2       4   5
Ik heb nooit kunnen begrijpen hoe Quicksort de array {1, 3, 2} kan sorteren, met '3' als pivot.
  1. Alle getallen in de array zijn <=3.
  2. Het pivot getal blijft 3 in diepere recursies.
  3. De recursie wordt oneindig diep, zonder verder resultaat.

Alternatief

Een elegant alternatief:
Genomen stap <=4 te doen >=4
4 als pivot   5, 3, 4, 2, 1  
1 en 5 verwisseld 1 3, 4, 2 5
3 naar links 1, 3 4, 2 5
2 en 4 verwisseld 1, 3, 2   4, 5
3 als pivot <=3 te doen >=3   4, 5
1 naar links 1 3, 2     4, 5
3 en 2 verwisseld 1, 2   3   4, 5
  • Kleinere getallen gaan nog steeds naar links.
  • Grotere getallen gaan nog steeds naar rechts.
  • Maar alle gelijke getallen zijn kandidaat voor verwisseling.
De getallen die gelijk aan de pivot zijn, kunnen dus zowel naar links als naar rechts gaan. Dat lijkt wat vreemd, besluiteloos en daardoor inefficiënt. Maar integendeel, het versnelt de sortering van reeksen omdat
  1. het reeksen in delen van gelijkere grootte opsplitst,
  2. het per recursie meer getallen de goede kant op wisselt,
  3. wat de recursie minder diep maakt.
Tot de volgende week, met een demo van dit alternatieve Quicksort algoritme,
Henk Jan Nootenboom