Inhoudsopgave:
Definitie - Wat betekent Quicksort?
Quicksort is een populair sorteeralgoritme dat in de praktijk vaak sneller is in vergelijking met andere sorteeralgoritmen. Het maakt gebruik van een verdeel-en-verover-strategie om gegevensitems snel te sorteren door een grote array in twee kleinere arrays te verdelen. Het werd ontwikkeld door Charles Antony Richard Hoare (algemeen bekend als CAR Hoare of Tony Hoare) in 1960 voor een project over machinevertaling voor het National Physical Laboratory.Techopedia legt Quicksort uit
Quicksort is een algoritme dat wordt gebruikt om items binnen een array snel te sorteren, ongeacht hoe groot de array is. Het is vrij schaalbaar en werkt relatief goed voor kleine en grote gegevenssets en is eenvoudig te implementeren met weinig tijdcomplexiteit. Het doet dit via een verdeel-en-verover-methode die een enkele grote array in twee kleinere verdeelt en herhaalt dit proces vervolgens voor alle gecreëerde arrays totdat de sortering voltooid is.
Het quicksort-algoritme wordt als volgt uitgevoerd:
- Een draaipunt wordt gekozen uit de array.
- De array wordt opnieuw geordend zodat alle waarden die kleiner zijn dan de pivot ervoor worden verplaatst en alle waarden die groter zijn dan de pivot erna worden verplaatst, met waarden die gelijk zijn aan de pivot. Wanneer dit is gedaan, bevindt het draaipunt zich in zijn definitieve positie.
- De bovenstaande stap wordt herhaald voor elke subreeks met kleinere waarden en wordt afzonderlijk uitgevoerd voor de subreeks met grotere waarden.
Dit wordt herhaald totdat de hele array is gesorteerd.
