Jak Quicksort Funguje
Quicksort (zejména v místě Quicksort) může být trochu matoucí, takže pojďme se projít například ukázat, jak tento třídící algoritmus funguje.
Předpokládejme, že jsou uvedeny následující pole třídit:
Teď pojďme vybrat něco, co nazývá „pivot point“., Cílem je uspořádat pole tak, aby všechny prvky menší než pivot byly vlevo a všechny prvky větší než pivot jsou vpravo. Volba otočného bodu je libovolná; může to být první prvek pole, poslední prvek pole nebo dokonce náhodný prvek! Pro naše účely však zvolme otočný bod jako poslední prvek v poli, 5.,
Po uspořádání pole kolem otočného bodu 5, měli bychom získat následující pole:
Pak jsme rekurzivně postupujte podle výše uvedeného postupu pro subarrays vlevo a vpravo od otočného bodu.
subarray vlevo od otočného bodu je pouze jeden prvek. Nemá smysl třídit pole délky, takže tady není co dělat!,
Na druhou stranu, do pole vpravo od otočného bodu, není tak triviální. V návaznosti na výše popsaný postup si vybereme 7, který bude novým otočným bodem pro tento subarray.,“>
Po přeskupí prvky pole kolem otočného bodu, dostaneme následující:
pokračovat rekurzivně, a sloučení levého pole, s otočným a pravé pole, seřazené pole je vrácena.,
