QuickSort
Napisano w Tematy
Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie “dziel i zwyciężaj
Działa nie algorytmu
Z tablicy wybiera się element rozdzielający, po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie większe od rozdzielającego, do końcowego wszystkie większe. Potem sortuje się osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania.
5 | 7 | 3 | 1 | 9 | 4 |
Lewy | Piwot | Prawy |
Algorytm partycjonujący
- Wykonuj naprzemiennie
- idź od prawej do lewej i znajdź liczbę mniejszą od osi (Pivot). Zamień znalezioną liczbę z osią i przestaw Prawy.
- idź z lewej do prawej i znajdź liczbę większą od osi (Piwot). Zamień znalezioną liczbę z osią i przestaw Lewy.
- Zakończy gdy Prawy = Lewy
źródło: Wikipedia