Quicksort (sortowanie szybkie)
Quicksort opiera się na naprawdę prostej zasadzie. Wybieramy dowolny element tablicy (najlepiej medianę). Umieszczamy mniejsze wartości na lewo, a większe na prawo od wybranego elementu. Traktujemy lewą i prawą stronę jako osobne tablice i postępujemy z nimi w taki sam sposób. Kończymy gdy zostanie nam tylko jeden element.
Jak dokonujemy tego podziału? Są dwie "szkoły" dzielenia. Pierwsza polega na przesuwaniu dwóch wskaźników: jeden od końca drugi od początku i zamienia się wartości jeśli jest taka konieczność. Nie będę przedstawiał tej metody, bo jest ona trochę kłopotliwa. Zajmiemy się za to drugą metodą.
Jako wartości dzielącej użyjemy ostatniego elementu tablicy. Nazwijmy go "pivot". Posłużymy się aż czterema wskaźnikami: "left" i "right" oznaczają pierwszy i ostatni indeks tablicy. "pointer" będzie służył po prostu do przechodzenia tablicy. Na początku jego wartość ustawiamy na pierwszy element. "lastLower" będzie wskazywał ostatnią najmniejszą wartość. Początkowa wartość to "left" - 1. W rzeczywistości te cztery wskaźniki wyznaczają nam pewne obszary. Od "left" do "lastLower" znajdują się elementy mniejsze od "pivota". Od "lastLower" do "pointer" większe. Natomiast od "pointera" do końca nie sprawdzone. No to zaczynamy. Przesuwamy "pointer" dopóki nie osiągniemy przedostatniego elementu. W tym czasie sprawdzamy, czy wartość pod "pointerem" jest mniejsza od "pivota". Jeśli tak, to przesuwamy "lastLower" o jedno miejsce i zamieniamy jego wartość z "pointerem". Jeśli nie, to nic nie robimy. Na końcu znów zwiększamy wartość "lastLower" o 1 i ją zwracamy jako wynik funkcji. Prześledźmy ten proces na przykładzie.
Początkowa sytuacja wygląda tak jak pokazałem na (1). Następnie przesuwamy "pointer" aż natkniemy się na 1. Przesuwamy "lastLower" i zamieniamy z "pointerem". Myślę, że to jest jasne. W (5) przedstawiona jest sytuacja po dojechaniu do przedostatniego elementu, a w (6) po dokonaniu zamiany "pivota" z "lastLower". To teraz zobaczmy w końcu implementację tej funkcji.
public static int Partition(int[] array, int left, int right) {
int pivot = array[right];
int lastLower = left - 1;
for (int pointer = left; pointer < right; pointer++) {
if (array[pointer] <= pivot) {
lastLower++;
QuickSort.Swap(array, lastLower, pointer);
}
}
lastLower++;
QuickSort.Swap(array, lastLower, right);
return lastLower;
}
Myślę, że wszystko jasne. Jak nie, to pisać maila:) Zrobiłem osobną funkcję do zamieniania wartości w tablicy. Jej treść jest na tyle prosta, że nie będę jej tu przytaczał. Zerknij sobie do kodu źródłowego.
No to teraz zajmiemy się właściwą procedurą sortującą. Jako wejście dostajemy tablicę i wskaźniki końca i początku. Jeśli początek jest większy lub równy końcowi to nie sortujemy. W przeciwnym razie znajdujemy element podziału metodą Partition. Nazwijmy go p. Teraz wywołujemy Quicksorta dla lewej połówki, a następnie prawej. I po krzyku:) Zobaczmy kod.
public static void Sort(int[] array, int left, int right) {
if (left >= right)
return;
int q = QuickSort.Partition(array, left, right);
QuickSort.Sort(array, left, q - 1);
QuickSort.Sort(array, q + 1, right);
}
Teraz czas działania. W najgorszym przypadku wynosi O(n^2). Czyli żadnej poprawy! Jak to? Przecież nawet nazywa się "szybkie"! Już wyjaśniam. Wszystko zależy od elementu dzielącego. Jeśli za każdym razem element podziału będzie tym skrajnym (w naszym przykładzie z rysunku będzie to 10 lub 1), to nie osiągniemy lepszego czasu niż O(n^2). Zauważmy, że w takiej sytuacji zrobimy n porównań i podzielimy tablicę na dwie części po (n - 1) i 1. Następnie zrobimy (n - 1) porównań i podział na (n - 2) i 1 element. itd. Co daje nam wzór który pojawiał się już wyżej. Nie będę już go powtarzał. No to teraz załóżmy, że mamy szczęście i za każdym razem tablica podzieli się na dwie idealne połowy. Różnica jest duża, bo czas działania obniża się do poziomu O(n * logn). Skąd ta wielkość się wzięła? Oznaczmy czas działania jako T(n). Równa się on czasom działania dla dwóch połówek plus jedno przejście tablicy, więc T(n) = T(n/2) + T(n/2) + n. Wierzcie mi lub nie, ale rozwiązaniem tej rekurencji jest właśnie n * logn. No to dla lepszego zobrazowania: posortowanie 1000 oznacza wykonanie 10000 operacji. Czyli różnica jest kolosalna w porównaniu do sortowania na przykład bąbelkowego.
Tylko jak zagwarantować tak dobry podział? Dobre rezulaty uzyskamy nawet wtedy gdy zapewnimy, że element dzielący nie będzie tym skrajnym. Możemy nawet dzielić na (n-2) i 2 elementy, a czas nadal będzie O(n*logn). Pierwszy sposób, to wybrać element losowy. Pewnie się czasem zdarzy, że wylosujemy element skrajny, ale nie często. Drugi sposób (zaimplementowany przeze mnie poniżej): wybierzmy 3 dowolne elementy i weźmy środkowy jako element podziału. Mamy więc pewność, że nie wybierzemy skrajnego. No to popatrzmy na kod.
public static int Partition2(int[] array, int left, int right) {
int pivotIndex = QuickSort.FindPivotIndex(array, left, right);
int pivot = array[pivotIndex];
QuickSort.Swap(array, pivotIndex, right);
int lastLower = left - 1;
for (int pointer = left; pointer < right; pointer++) {
if (array[pointer] <= pivot) {
lastLower++;
QuickSort.Swap(array, lastLower, pointer);
}
}
lastLower++;
QuickSort.Swap(array, lastLower, right);
return lastLower;
}
Zmienił się tylko sam początek. Reszta jest taka sama. Widzimy wywołanie magicznej funkcji FindPivotIndex, która zwraca nam indeks elementu dzielącego. Zamieniamy go jeszcze z ostatnim elementem, bo założyliśmy, że to ostatni element ma być tym dzielącym. No to zobaczmy jak wygląda FindPivotIndex.
public static int FindPivotIndex(int[] array, int left, int right) {
if (right - left < 2)
return right;
else {
int first = array[left];
int second = array[right];
int third = array[(right + left) / 2];
if (first <= second) {
if (second <= third)
return right;
if (first <= third)
return (right + left) / 2;
else
return left;
} else {
if (first <= third)
return left;
if (third <= second)
return right;
else
return (right + left) / 2;
}
}
return right;
}
Wielkiej filozofii tu nie ma. Dlaczego wybieramy elementy skrajne i środkowy? Jakbyśmy mieli tablicę posortowaną od początku, to taki dobór elementów sprawi, że będziemy mieli zawsze podział na dwie idealne połówki. Dalej mamy całą masę ifów, żeby wiedzieć który to środkowy element. Jeszcze uwaga do samej implementacji. Żeby użyć jednej lub drugiej wersji Partition wystarczy zmienić tylko nazwę (Z Partition na Partition2 lub odwrotnie) w metodzie Sort. To chyba tyle o Quicksorcie.
