Stap 6: Uitvoering van quick_sort
Achtergrond
Nu dat we hebben geschreven de functie die het grootste deel van het werk doet, kunnen we naar het makkelijke gedeelte. Onze quick_sort functie is zeer gemakkelijk te begrijpen en is gebaseerd op het idee dat wij willen zo weinig werken zoveel mogelijk zelf doen.
Onze eerste vraag is: wat is de makkelijkste array te sorteren? Het is in mijn mening, een met een enkel element. Wanneer u mij één nummer verlenen, kan ik het direct sorteren. Werken met dit begrip, laten we schrijven quick_sort.
Doel
Wij willen breken van het werk met behulp van onze qs_partition -functie, zodat die nooit hebben geen echte werk te verrichten.
Stappen
1) we controleren eerst als wij voorkomen werk helemaal dat kunnen. Als onze linkerrand kleiner dan onze rechterrand is, dan hebben we werk te doen, helaas. Als onze linkerrand hetzelfde als onze rechterrand is, is de sectie, die wij zijn sorteren slechts één element. Als links groter is dan recht, wij bevinden ons in een foutstatus.
2) onze volgende strategie bij werk vermijden is vertellen andere mensen om het te doen. We bellen qs_partition en krijgen van de pivot- index die het gebruikt. Zoals u uit de laatste stap weet, is om het even wat in de array voordat deze index kleiner dan of gelijk aan de waarde op het scharnierpunt. Na is alles groter dan de spil.
3) wat betekent dat? Dat betekent dat als we alles voordat het scharnierpunt en alles na het scharnierpunt sorteren, we een gesorteerde array hebben, omdat de spil al op de juiste plek is. Zo zullen wij enkel dat doen. Weten we elke sorteren algoritmen? Wij hebben quick_sort.
Beoordeling
Het lijkt erop dat we wegkomen kunnen met een echte werk niet te doen. U zult zien dat als we quick_sortnoemen, het resulteert in twee meer quick_sort oproepen, een aan iedere kant van onze pivot. Deze vertakkende gedrag wordt voortgezet totdat elke aanroep wordt uitgevoerd in een array dat is slechts één element. Aangezien een matrix met één element is gesorteerd, wordt vervolgens onze hele array gesorteerd.
