Quicksort
Quicksort is een sorteeralgoritme dat wordt gebruikt om elementen in een array te sorteren. Het is bedacht door Tony Hoare in 1959, en wordt nog steeds veel gebruikt. Quicksort maakt partities binnen de array, wat in wezen betekent dat het de array in twee delen splitst, en dan verder gaat met het splitsen van die delen in meer delen, en onderweg sorteert. Het sorteren zelf gebeurt omdat het een vergelijkingssortering is. Dit betekent dat het een scharnierpunt in de matrix kiest, en dit dan vergelijkt met alle andere punten in de matrix.
Geanimeerde visualisatie van het quicksort-algoritme. De horizontale lijnen zijn spilwaarden
Algoritme
- Kies een willekeurig element in de matrix, dit wordt nu het draaipunt.
- Verdeel de elementen. Vergelijk alle elementen in de matrix met de spil, de elementen die lager zijn dan de spil worden naar links van de spil verplaatst, en alle elementen in de matrix die hoger zijn dan de spil worden naar rechts van de spil verplaatst. Onze spil staat nu op de gesorteerde positie.
- Terugverwijzen naar de twee partities. Pas de bovenstaande twee stappen toe op de twee partities die we in stap 2 hebben gemaakt.
Vaak wordt het meest linkse element als spil gekozen. De recursie betekent dat het algoritme exact hetzelfde algoritme uitvoert op de twee partities die ontstaan zijn door de vergelijkingen met de spil. Merk op dat dit algoritme de array blijft verdelen in subarrays, en deze subarrays blijft verdelen in nog kleinere subarrays. Telkens wanneer het dit doet, kiest het een nieuwe spil binnen de subarray en vergelijkt het de elementen met de subarray. Het basisgeval is wanneer het algoritme een subarray met slechts één element bereikt, waarin het gewoon stopt omdat één element niet gesorteerd hoeft te worden.
