Stap 5: Uitvoering van qs_partition
Achtergrond
Voordat je rond aan de uitvoering van de functie quick_sort, moeten we begrijpen dat quick_sort niet veel werk doen door zelf. Onze qs_partition functie doet het meeste werk. qs_partition neemt als parameters een matrix van gehele getallen, een linkerrand in die matrix en een rechterrand in die matrix, en geeft een geheel getal, net als belangrijkste.
* Opmerking: omdat een bibliotheek die wij gebruiken (algorithm.h) al een functie genaamd partitie heeft, zullen we onze partitie functie qs_partitionnoemen.
Doel
De taak van qs_partition is om Kies een nummer in de matrix als een spil en alle getallen in de matrix te scheiden in twee groepen: die kleiner is dan of gelijk is aan de spil en degenen die groter zijn. De Unie stelt alle lagere of gelijke getallen voordat de spil en alle grotere getallen na. Hier is een manier die kan worden bereikt.
Stappen
1) qs_partition eerste neemt het eerste ding dat het is toegestaan te raken (het item op de linkerrand) en noemt het een spil. Er is niets bijzonders hier gaande. De functie doet eerst alles verklaren dat een waarde met de naam van de pivot is gelijk aan het eerste item dat de functie is toegestaan om toegang.
2) op dezelfde manier, we bellen een variabele toSwap en de index van het scharnierpunt toewijzen.
3) we lopen door de array, kijkend naar elk item van de tweede waarde de rechterrand. We vergelijken niet de eerste waarde die moet de pivot-waarde omdat de eerste waarde is de waarde van de draaitabel.
4) op elke plek vergelijken we de waarde op die plek met onze pivot. Als die waarde kleiner dan of gelijk aan de spil is, willen we die waarde zo ver naar het begin van de array mogelijk verplaatsen. Dat is waar toSwap komt binnen. Wij zullen de waarde bij toSwap ruilen (omdat toSwap een index) en de huidige waarde we zien, dan wij zult toSwap verhogen door een, dus we zijn niet van die omwisselen waarden terug uit in het midden van de matrix.
5) zodra we alle getallen hebben doorlopen, zullen onze index toSwap de plek waar we willen plaatsen onze pivot vertegenwoordigen. Zo wisselen we het belang van toSwap en de waarde van de draaitabel. Tot slot, we keren, of gaan terug naar de functie die aangeroepen van qs_partition, de index van waar wij de spil. U zult waarom spoedig zien.
Beoordeling
Hopelijk kunt u zien dat we door het opeenvolgend omwisselen van getallen kleiner dan de spil in de eerste plek na onze laatste swap, het gewenste effect hebt gemaakt: alle getallen voordat de spil zijn kleiner dan of gelijk aan de spil en alle getallen na het groter.
