|
|
Sortowanie "szybkie" |
Ważniejsze definicje:
Algorytmy sortowania:
|
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ć:
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.
|
Sortowanie "szybkie"
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
