Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj"[1].
Sortowanie QuickSort zostało wynalezione w 1962 przez C.A.R. Hoare'a[2].
Algorytm sortowania szybkiego jest wydajny: jego średnia złożoność obliczeniowa jest rzędu [1]. Ze względu na szybkość i prostotę implementacji jest powszechnie używany. Jego implementacje znajdują się w bibliotekach standardowych wielu środowisk programowania.
Algorytm postępowania
_ wybiera się losowo jakiś element x z sortowanego zbioru,
_ przegląda się zbiór od strony „lewej”, aż znaleziony zostanie taki
element Ai, że Ai≥x,
_ przegląda się zbiór od strony „prawej”, aż znajdzie się element Aj, taki
że Aj≤x,
_ zamienia się miejscami elementy Ai i Aj ,
_ kontynuuje się proces przeglądania i zamiany, aż nastąpi spotkanie
gdzieś w środku tablicy.
Miejsce spotkania wyznacza punkt podziału tablicy na dwie
części. „Lewa” część składa się z elementów nie większych niż
wybrany element x, „prawa” zaś z elementów nie mniejszych
niż x.
_ Takie części sortuje się następnie oddzielnie w sposób
opisany powyżej.
_ Powtarzanie tych operacji aż do momentu gdy części tablicy
będą składały się z jednego elementu, doprowadzi do
posortowania całej tablicy.
_ Efektywność metody: Po ~ n*log(n), Pr ~ n
Przykład:
{ 9 7 4 5 0 6 3 2 1 8 } Na element środkowy wybieramy ostatni element zbioru - liczbę 8
{ 7 4 5 0 6 3 2 1 } 8 { 9 } Zbiór dzielimy na dwa podzbiory zawierające odpowiednio elementy mniejsze i większe od wybranego elementu środkowego. Prawy podzbiór jest już posortowany, ponieważ zawiera tylko jeden element - liczbę 9. Przechodzimy do sortowania lewego zbioru.
{ 7 4 5 0 6 3 2 1 }{ 8 9 } Wybieramy ostatni element - liczbę 1.
{ 0 } 1 {7 4 5 6 3 2 }{ 8 9 } Dzielimy zbiór wg wybranego elementu środkowego na dwa podzbiory. Podzbiór lewy jest już posortowany, ponieważ zawiera tylko jeden element - liczbę 0.
{ 0 1 }{7 4 5 6 3 2 }{ 8 9 } Wybieramy w podzbiorze prawym element środkowy - liczbę 2.
{ 0 1 }{ } 2 { 7 4 5 6 3 }{ 8 9 } Dokonujemy podziału zbioru na dwa podzbiory względem wybranego elementu. Lewy podzbiór jest teraz pusty.
{ 0 1 2 }{ 7 4 5 6 3 }{ 8 9 } Wybieramy element środkowy.
{ 0 1 2 }{ } 3 { 7 4 5 6 }{ 8 9 } Lewy podzbiór znów pusty.
{ 0 1 2 3 }{ 7 4 5 6 }{ 8 9 } Wybieramy element środkowy
{ 0 1 2 3 }{ 4 5 } 6 { 7 }{ 8 9 } Prawy podzbiór jest posortowany, ponieważ zawiera tylko jeden element.
{ 0 1 2 3 }{ 4 5 }{ 6 7 8 9 } Wybieramy element środkowy
{ 0 1 2 3 }{ 4 } 5 { }{ 6 7 8 9 } Lewy i prawy podzbiór posortowany.
{ 0 1 2 3 4 5 6 7 8 9 } Ponieważ nie ma więcej podzbiorów, zbiór wejściowy został w całości posortowany.