Strona główna » Algorytmy » Sortowanie » Sortowanie Szybkie

Sortowanie Szybkie

Algorytm

Algorytm Szybkie sortowanie (ang. quicksort) to jeden z najpowszechniej używanych obecnie algorytmów sortujących. Jego złożoność wynosi dla większości przypadków . Jednak jego złożoność pesymistyczna wynosi . Są to jednak przypadki bardzo skrajne i z reguły bardzo rzadko występują.

Zasada działania opiera się na technice "dziel i zwyciężaj" - wstępna tablica jest dzielona na dwie podtablice na podstawie elementu środkowego r. Wszystkie elementy mniejsze od r, a po prawej stronie wszystkie większe bądź równe. Później każda z tablic jest sortowana oddzielnie, aż do uzyskania tablic jednoelementowych, których już nie trzeba sortować. Zastosowana technika polega na zastosowaniu tej samej techniki sortowania do każdej kolejnej rozpatrywanej tablicy.

Jeśli wylosowany element okaże się skrajnym tj. elementem, który powinien być na początku / końcu sortowanej tablicy to złożoność może osiągnąć wspomniane pesymistyczne . Z tego powodu często stosuje się dodatkowo algorytm, który szuka mediany na liście. W ten sposób złożoność jest zawsze gwarantowana, ponieważ w jednej i drugiej podliście zawsze znajdzie się tyle samo elementów (albo jeden mniej lub więcej zależy od rozpatrywanej listy).

Quicksort jest algorytmem natywnie zaimplementowanym w języku C++. Służy tego funkcja sort() w bibliotece algorithm.

Przykład

Przyjmijmy, że do posortowania jest tablica L={5, 1, 3, 7, 2}. W celu wyjaśnienia wartości zostaną umieszczone w tabelce. Na początku należy wyznaczyć tzw. pivot. Jest to element odniesienia według, którego elementy trafią na prawo lub lewo. Pivot to zazwyczaj środkowy element, albo mediana. W tym przypadku pivotem będzie element środkowy 3:

51372

Kolejny krok polega na pozamienianiu elementów tak, aby po lewej stronie znalazły się wszystkie elementy mniejsze od pivota, a na prawo większe (lub równe). Do przeprowadzenia tej operacji potrzebne są dwa indeksy: i oraz j. Pierwszy indeks i będzie szukał po lewej stronie, od początku elementu do zamiany, a j od końca, od prawej strony listy:

51372

Pierwszy i ostatni element są na niewłaściwych pozycjach. Z tego powodu należy je zamieniać miejscami, a następnie zwiększyć indeks i oraz zmniejszyć indeks j. Po tym należy ponownie porównać kolejną parę elementów wskazywanych przez indeksy:

21375

Wskazywane elementy znajdują się po dobrych stronach. W tym momencie indeksy i oraz j wskazują pivota. Teraz kolejny krok polega na posortowaniu dwóch tablic. Pierwsza ma zakres [1, i], a druga [j, n]. Dla każdej z tablic wykonywane są te same operacje co dla pierwszej:

213

Element na pozycji j jest na właściwej pozycji, ale element 2 nie jest, dlatego nie jest zwiększany indeks i, ale jest zmniejszany indeks j:

213

Po zamianie otrzymana jest podtablica [1, 2, 3]. Program o tym nie wie, dlatego wykona jeszcze sortowanie podtablicy [2, 3], a sortowanie podtablic jednoelementowych pominie. Teraz algorytm przechodzi do drugiej podtablicy listy podanej na wejściu:

375

Tym razem to element 5 jest na złej pozycji, dlatego w celu znalezienia pary, aby zamienić element zmniejszony zostanie indeks j. Potem jak w przypadku poprzedniej tablicy tablica zostanie podzielona na [3] i [5 7] i każda zostanie posortowana. Tylko w ten sposób istnieje gwarancja, że tablica zostanie posortowana. Sprawdzanie czy tablica jest już posortowane zwalniało by tylko algorytm.

Na koniec zestawienie posortowanych dwóch podtablic pokazuje, że sort(L) to [1, 2, 3, 5, 7].

Implementacja

Do implementacji przyda się funkcja zamieniająca wartości miejscami swap():

  1. void swap(int& a, int& b){
  2.   int temp = a;
  3.   a = b;
  4.   b = temp;
  5. }

Mają powyższą funkcję można przystąpić do pisania kodu funkcji sortującej quicksort():

  1. void quickSort(int* l, int left, int right) {
  2.   int i = left, j = right;
  3.   int pivot = l[(left + right) / 2];
  4.   while (i <= j) {
  5.     while (l[i] < pivot)
  6.       i++;
  7.     while (l[j] > pivot)
  8.       j--;
  9.     if (i <= j) {
  10.       swap(l[i], l[j]);
  11.       i++;
  12.       j--;
  13.     }
  14.   };
  15.   if (left < j) quickSort(l, left, j);
  16.   if (i < right) quickSort(l, i, right);
  17. }

Jest to wersja rekurencyjna szybkiego sortowania, dlatego funkcja musi znać: l - wskaźnik na listę elementów, left i right - rozpatrywany zakres tablicy [left, right]. (2.) Ustalenie indeksów i oraz j. (2.) Wyznaczenia pivota - elementu odniesienia. (3.) Poszukiwania par do zamiany trwają, aż i <= j: (4. - 5.) poszukiwanie "niewłaściwego" elementu po lewej stronie oraz (6. - 7.) poszukiwanie niewłaściwego elementu w drugiej części. (8.) W przypadku wyznaczenia pary do zamiany i różnych indeksów: (9.) elementy są zamieniane i (10. - 11.) indeksy są odpowiednio zmieniane. (14. - 15.) Na sam koniec należy rekurencyjnie wywołać sortowanie podlist - zastosowane warunki uniemożliwiają sortowania tablic o mniej niż dwóch elementach.

Testowanie funkcji

Kod można przetestować przy pomocy poniższej funkcji main(). Warto zwrócić uwagę na to, że przy pierwszym wywołaniu należy podać jako left 0, a jako right n-1.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   int* L = new int[n];
  5.   for(int i = 0; i < n; i++)
  6.     cin >> L[i];
  7.   quickSort(L, 0, n - 1);
  8.   for(int i = 0; i < n; i++)
  9.     cout << L[i] << " ";
  10.   delete[] L;
  11.   system("pause");
  12.   return 0;
  13. }

Zadania

Zadanie 1

Zmień funkcję quicksort() tak, aby sortowała listę malejąco.

Zadanie 2

Ułatw korzystanie z funkcji quicksort() poprzez dodanie przeciążenia funkcji quicksort(). Jedyny wymaganymi elementami powinna być wskaźnik na listę liczb l oraz n - ile ma elementów.