Sortowanie szybkie ( quick sort )
Algorytm
Sortowanie szybkie (ang. Quick sort) jest uważane za najszybszą w praktyce metodę prostego sortowania. Algorytm jest łatwy do zrozumienia, trochę trudniejsza jest implementacja, mimo to zachęcam Cię bardzo do poznania tej metody sortowania.
Na bazie tego algorytmu powstają również mieszane metody sortowania, które charakteryzują się jeszcze większą szybkością od algorytmu quicksort przedstawionego w tym artykule.
Musisz wiedzieć, że w algorytmie sortowania szybkiego wykorzystuje się najczęściej rekurencję - jeśli nie wiesz czym jest rekurencja, radzę Ci zapoznać się z tym zagadnieniem zanim przejdziesz do analizy algorytmu.
Sprecyzujmy warunki sortowania:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator porównania
tych elementów, za pomocą którego możemy stwierdzić który z dwóch porównywanych elementów jest mniejszy, a który większy
oraz operator równości, za pomocą którego możemy stwierdzić, kiedy dwa elementy są sobie równe.
Wynik: n elementów uporządkowanych w taki sposób, że pierwszy element jest najmniejszy w sensie
operatora porównania elementów, a ostatni jest elementem największym w sensie tego samego operatora.
Algorytm w postaci listy kroków
- Zmiennej lewo przypisz 1, zmiennej prawo przypisz n
-
Jeśli lewo<prawo, to:
- Zmiennej p przypisz x[lewo]
- Rozmieść elementy w tablicy x[lewo+1],...,x[prawo] tak, że na początku tablicy będą znajdowały się elementy mniejsze lub równe zmiennej p, a na końcu będą się znajdowały elementy większe od zmiennej p.
- Zmiennej k przypisz indeks elementu w tablicy x[lewo+1], ..., x[prawo], takiego że, element ten jest mniejszy lub równy zmiennej p i jednocześnie znajduje się najbardziej na prawo wśród wszystkich elementów mniejszych lub równych zmiennej p.
- Zamień miejscami elementy x[lewo] i x[k]
- Zmiennej lewo przypisz lewo, zmiennej prawo przypisz k-1 i powtórz algorytm (cały krok 2)
- Zmiennej lewo przypisz k+1, zmiennej prawo przypisz prawo i powtórz algorytm (cały krok 2)
