Obraz-algorytm

Sortowanie "szybkie"


Strona główna

Ważne definicje: Algorytmy sortowania:

Porównanie algorytmów

Instrukcja użytkownika

Informacja o programie

Do góry Do tyłu

obraz-opis

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!

Algorytm służący do dzielenia ciągu na dwie części, spełniające opisany warunek, ma następującą postać:
  • 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
Można teraz podać pełny algorytm sortujący:
  • 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.

obraz-działanie

Demonstracja

Poniższy applet demonstruje opisany algorytm sortowania. Dane do sortowania mogą być losowe, uporządkowane lub odwrotnie uporządkowane.
  • 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.

Sortowanie "szybkie"

Typ danych:   Wielkość danych:  

Strona główna Sortowanie bąbelkowe Sortowanie przez wstawianie Sortowanie przez binarne wstawianie Sortowanie przez wybór Sortowanie przez scalanie Sortowanie przez scalanie - rozszerzone Sortowanie szybkie Sortowanie stogowe Sortowanie stogowe rozszerzone Porównanie algorytmów