Sortowanie QuickSort

Opis

Sortowanie QuickSort zostało wynalezione przez C.A.R. Hoare'a. Jest to jeden z najpopularniejszych algorytmów sortowania. Wpłynęły na to dwie rzeczy. Po pierwsze jest ono bardzo szybkie (jak sama nazwa wskazuje), a po drugie - proste do wytłumaczenia i implementacji. Pesymistyczny czas jego działania wynosi O(n²), a średni O(n*lg(n)). Mimo tego w praktyce jest to najszybszy algorytm sortowania dużych tablic danych.

Sortowanie szybkie opiera się na technice "dziel i zwyciężaj". Wejściowa tablica jest dzielona (po przestawieniu niektórych z jej elementów) na dwie mniejsze. Każdy element pierwszej tablicy nie jest większy niż każdy element drugiej tablicy. Liczbę, według której wykonuje się podziału to najczęściej pierwszy element tablicy. Następnie dla tych dwóch podtablic wywoływany jest rekurencyjnie ten sam algorytm. Wywołania rekurencyjne kończą się aż któraś z kolejnych podtablic będzie zawierała tylko jeden element. QuickSort działa w miejscu.

Przykład

Posortujmy dla przykładu następującą tablicę:

Liczbą, według której będziemy wykonywać podział będzie pierwsza liczba danej tablicy - w tym przypadku jest to 5. Na początku przeglądamy tablicę od lewej strony, aż znaldziemy element większy od naszej liczby. W tym przypadku jest to element drugi, czyli 7. Następnie przeglądamy naszą tablicę od końca aż znajdziemy element mniejszy od naszej liczby (5). Tym elementem jest trzeci od końca, czyli liczba 2.

Elementy, które już "przeszliśmy" są pogrubione, a te, na których zatrzymaliśmy się podkreślone. Tak więc po lewej stronie zatrzymaliśmy się na 7, a po prawej na 2. Teraz zamieniamy te elementy ze sobą:

Znowu kontynuujemy przeglądanie od lewej strony. Zatrzymujemy się na elemencie trzecim, czyli 8. A w przeglądaniu od końca zatrzymujemy się na elemencie 5 od końca, czyli 1:

Zamieniamy te elementy ze sobą:

Postępując jak wyżej po lewej dochodzimy do elementu nr 8, czyli 6, a po prawej do 6 od końca, czyli 2:

Jak zwykle zamieniamy je ze sobą:

Idąc od lewej zatrzymujemy się na 8, a od prawej na dwójce, ponieważ nasze przeglądania od lewej i od prawej "spotkały się" tak więc cofamy się w każdym o jedną pozycję do tyłu i w ten sposób mamy wyznaczony podział:

Z tymi podtablicami postępujemy tak, jak z tablicą wejściową. Nie będę tutaj prezentował poszczególnych kroków sortowania. Elementem dzielącym po lewej jest liczba 5, a po prawej liczba 8 (pierwsze w tych tablicach). Po podziale takim jak przeprowadzonym wyżej otrzymujemy:

Zauważmy, że dla liczby 5, która jest "sama" nie będzie już wywołania rekurencyjnego. Po następnym podziale otrzymamy:

W tym przypadku mógł być problem z podziałem tablicy 6,6,7,5. W tym przypadku z lewej strony i prawej doszliśmy do elementu drugiego, tj. liczby 6 i zatrzymaliśmy się. Nie można zamienić elementu z nim samym. W tej sytuacji można przyjąć, że "sporna" liczba będzie należeć do lewej lub do prawej strony. Ja przyjełem, że do prawej.

Po następnym podziale otrzymamy:

Kolejny podział daje nam:

No, a po ostatnim podziale nasze dane będą wyglądać następująco:

Teraz łączymy wszystkie liczby i powstaje następujący ciąg:

Liczby są już posortowane. Oczywiście wszystkie podziały są wykonywane rekurencyjnie. Poprzez zastosowanie rekurencyjności algorytm QuickSort ma zwięzły kod i jest łatwy w implementacji.

Inna odmiana QuickSort

Wyżej wspomniałem, że algorytm szybkiego sortowania ma pesymistyczny czas działania O(n²). Występuje to w przypadku, gdy tablica wejściowa jest posortowana odwrotnie, tzn. jej wyrazy stanowią ciąg nierosnący. Na przykład taką tablicą może być:

Proszę spróbować przeprowadzić algorytm QuickSort dla tych danych. Wynika to z tego, że jako element dzielący daną tablicę wybieramy jej pierwszy element. Dla tablicy powyżej takie założenie powoduje, że za każdym razem granica podziału jest za pierwszą liczbą tej tablicy. Można oczywiście wybrać inny element jako granicę podziału. W ten spowodujemy, że algorytm szybkiego sortowania dla wyżej przedstawionych danych będzie działał dużo szybciej. Ale który element wybrać? Najlepiej wylosować. Jak się okazuje to bardzo dobre rozwiązanie, które nie wymaga dużo obliczeń. Najbardziej optymalnym rozwiązaniem jest wybranie mediany (najbardziej "środkowego" elementu tablicy). Jednakże wymaga to dużo dodatkowego czasu. Można także zmieszać losowanie liczb z wyborem mediany. Po prostu losujemy z tablicy do podziału pewną ilość liczb (najlepiej 3) i wyznaczamy wśród nich medianę, czyli element środkowy pod względem wartości. Następnie dokonujemy podziału według tego elementu.