Sortowanie "szybkie"

Opis algorytmu

W przypadku tej metody sortowania jest wykorzystywana strategia "dziel i zwyciężaj". Jest to bardzo efektywna technika algorytmiczna (wykorzystana jest także w algorytmie sortowania przez scalanie).

Przypuśćmy, że potrafimy podzielić dany ciąg na dwie takie części, że elementy pierwszego ciągu są mniejsze od elementów drugiego ciągu, czyli nieformalnie mówiąc, na elementy "małe" i "duże". Mając taki podział ciągu, możemy każdą z części uporządkować osobno (pomińmy na razie, w jaki sposób to zrobić). Otrzymamy ciąg składający się z uporządkowanych elementów "małych", a po nich następują uporządkowane elementy "duże" - czyli cały ciąg jest już uporządkowany!

• Weź pierwszy element ciągu (oznaczmy go przez x).
• Podziel ciąg tak, aby w pierwszej części znalazły się elementy mniejsze lub równe x, a w drugiej większe lub równe x

• Jeżeli liczba elementów w ciągu jest większa od 1, to podziel ciąg na dwie części tak, aby elementy z pierwszej części były nie większe niż elementy z drugiej części.
• Wywołaj procedurę sortującą dla pierwszej części ciągu.
• Wywołaj procedurę sortującą dla drugiej części ciągu.

Dla poprawności działania powyższego algorytmu nie ma znaczenia, który element zostanie wybrany jako element rozdzielający ciąg na dwie części. Ma to jednak wpływ na efektywność algorytmu. Najczęściej wybierany jest pierwszy element ciągu (tak jest w naszym przypadku) lub element losowy.

Czas działania tego algorytmu sortowania zależy od wielkości podziałów wykonywanych przez procedurę dzielącą ciąg. Jeżeli podziały te są zrównoważone, czyli wielkości powstających części są sobie równe, to algorytm ten jest praktycznie najszybszą metodą sortowania – stąd jego nazwa: sortowanie szybkie (ang. quicksort). Jeżeli natomiast otrzymane w wyniku podziału ciągi mają bardzo różne długości, to złożoność algorytmu jest większa.

Demonstracja

• Zieloną i niebieską kropką są zaznaczone aktualnie porównywane elementy.
• Żółtą linią jest oznaczona uporządkowana część ciągu.
• pomarańczową linią jest oznaczona rozdzielana część ciągu.

• Aby uruchomić demonstrację naciśnij Start.
• Aby zatrzymać demonstrację naciśnij Stop.
• Aby wykonać jeden krok algorytmu naciśnij Krok.
• Aby przyspieszyć działanie naciśnij >.
• Aby spowolnić działanie naciśnij <.
• Aby zmienić typ danych użyj pola wyboru poniżej.
• Aby zmienić wielkość danych użyj pola edycyjnego i przycisku Zmień. Wielkość danych musi być liczbą z zakresu od 5 do 300.