Quicksort

Quick Sort jest teoretycznie najszybszym1 sortowaniem świata, działa w czasie O(n log n) jak nam to zostało już wytłumaczone na lekcji ;)

OK, ale jaka jest jego idea?? Ano taka, że bierzemy sobie całkowicie dowolną2 liczbę w tablicy (pivot), a potem na jedną stronę przerzucamy wszystkie mniejsze od niej, a na drugą wszystkie większe. Na przykładzie prezentuje się to tak:

3 1 7 2 10 5 4

Wybieramy np. 4 i do dzieła:

3 1 2 4 10 5 7

No więc na lewo od 4 mamy liczby mniejsze, na prawo zaś większe. A co dalej?? Dla liczb mniejszych niż pivot powtarzamy to samo, dla większych też. Mniejsze liczby to 3 1 2, no to wybierzmy np 2 i wyjdzie:
1 2 3 - posortowane :D
no to wracamy do większych niż 4, 10 5 7, weźmy za pivot np 5 i wyjdzie:
5 7 10 - magia, posortowane :D

Jak to zaklepać?? Ano są dwie wersje - Lomuto i Hoare.

Lomuto Quick Sort

Idea jest taka, mamy tablicę z liczbami np. 3 1 7 2 10 5 4, teraz wybieramy jakąś liczbę (pivot), powiedzmy 3 i zamieniamy ją miejscami z ostatnią (1).
4 1 7 2 10 5 3
Teraz ustawiamy sobie dwa wskaźniki (powiedzmy a i b) na pierwszy element, no i lecimy przez tablicę wskaźnikiem a aż do końca. (2)
W momencie gdy znajdziemy coś, co jest równe lub mniejsze niż pivot, zamieniamy miejscami liczby, na które wskazują wskaźniki a i b, po czym przesuwamy wskaźnik b o jedno miejsce dalej (3). Na końcu zamieniamy miejscami pivot i liczbe, na którą wskazuje wskaźnik b. (4)
Czyli w naszym przykładzie to wygląda tak:
4 1 7 2 10 5 3
wskaźniki a i b skazują na 4, no to lecimy wskaźnikiem a dalej, napotykamy "1", które jest mniejsze niż 3 (pivot), więc zamieniamy miejscami liczby na które pokazują a i b:
1 4 7 2 10 5 3
no i przesuwamy wskaźnik b o jedno miejsce, czyli na 4. Lecimy dalej, "a" napotyka na "2", no to znowu zamieniamy:
1 2 7 4 10 5 3
wskaźnik b pokazuje teraz na 7. Przesuwając się dalej po tablicy nie znajdziemy już nic więcej, a więc zamieniamy to na co pokazuje wskaźnik b z pivotem:
1 2 3 4 10 5 7
Teraz powtarzamy wszystko dla części tablicy od początku do pivota, a następnie dla reszty, w obu przypadkach bez pivota (on już jest na swoim miejscu) (5).

A jak to wygląda w C++?? Mamy jakąś tablicę A, w której komórki są ponumerowane od p do q…

void LomutoQuickSort(int A[], int p, int q)
{
   int s=(4*p+5*q)/9; //jakieś miejsce w tablicy, gdzie jest nasz pivot (Musi występować operator mnożenia między liczbą a zmienną - by Kszyhoo)
   int pivot=A[s];  //(1)
   swap(A[s], A[q]);   //(1)
   int b=p;   //(2)
   for (int a=p; a<q; a++)   //(2)
      if (A[a]<=pivot)   //(3)
      {
         swap(A[a], A[b]);   //(3)
         b++;   //(3)
      }
   swap(A[b], A[q]);   //(4)
   LomutoQuickSort(A, p, b-1);   //(5)
   LomutoQuickSort(A, b+1, q);   //(5) (trzeba wywołać funkcję z wszystkimi argumentami!!)
}

//Maćku - zanim wrzucisz jakiś kod na Wiki skompiluj go i sprawdź poprawność - bo błąd taki jak wywołanie funkcji mającej trzy argumenty, zapodając jej tylko dwa, nie zdarzyłby się gdybyś to skompilował. Następnym razem albo pisz że kod zawiera błędy i jest do poprawienia albo nie pisz go w ogóle - by Kszyhoo

Hoare Quick Sort

Tutaj idea jest taka, że zapamiętujemy pivota, a teraz lecimy od lewej aż napotkamy coś większego lub równego pivotowi, potem lecimy od prawej szukając czegoś mniejszego lub równego, po czym jeśli wskaźniki się nie minęły zamieniamy te 2 liczby miejscami i przesuwamy wskaźniki o jedno pole dalej. Jeśli wskaźnik, który "leciał" od końca "nie doleciał" do początku, to wywołujemy się dla części od początku do tego wskaźnika, po czym jeśli wskaźnik który "leciał" od początku "nie doleciał" do końca wywołujemy się dla części od niego do końca.

Implementacja by Lech Duraj, zapisana na naszej lekcji na tablicy bezczelnie przeze mnie spisana do zeszytu ^^

void HoareQuickSort(int A[], int p, int q)  //p-początek, q-koniec
{
   if (p>=q) return; //bo jaki sens sortować jednoelementowe, albo takie, gdzie koniec jest przed początkiem?
   int s=(p+q)/2; //jeśli chcecie wymyślcie se coś innego
   int piwot=A[s], i=p, j=q;
   while (i<=j) //póki się nie miną
   {
      while (A[i]<piwot) i++; //szukamy skubańca, co jest większy lub równy, a przed piwotem
      while (A[j]>piwot) j--; //szukamy skubańca, co jest mniejszy lub równy od piwota, a za nim
      if (i<=j) //jeśli się jeszcze nie minęły
      {
         swap(A[i], A[j]);
         i++; j--;
      }
   }
   if (j>p) // jeśli nie "dolecieliśmy" na początek
      HoareQuickSort(A, p, j);
   if (i<q) // jeśli nie "dolecieliśmy" do końca
      HoareQuickSort(A, i, q);
}

Bez nerwów, wiem, że obiecałem, że na wikidocie pisać już nie bede, ale trza było dokończyć o Quick Sorcie ;)


1 Najszybszy z klasycznych algorytmów sortowania przez porównania.
2 Nie ma wielkiej różnicy ale optymalniejsze jest wybranie takiego pivota - by ilość liczb do poprzestawiania była najmniejsza.
// Komentarze by Kszyhoo

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License