Algorytm Quicksort w JAVA
W tym przykładzie zaimplementujemy wersję jednego z najlepszych algorytmów: Quicksort. Twórcą algorytmu i jego nazwy jest C.A.R. Hoare. Quicksort jest obecnie najlepszym z dostępnych uniwersalnych algorytmów sortowania. Nie mogłem jednak przedstawić go w rozdziale 5., ponieważ najlepsze jego implementacje wykorzystują rekurencję. Wersja, którą zaimplementujemy w tym rozdziale, będzie sortować tablicę znaków, ale tę samą logikę możesz zastosować dla dowolnych obiektów.
Algorytm Quicksort bazuje na idei podziału. Ogólna procedura polega na wybraniu pewnej wartości, a następnie podziale tablicy na dwie części. W jednej umieszczamy elementy, których wartość jest równa bądź większa od wybranej wartości, a w drugiej te, których wartość jest mniejsza. Proces ten powtarzamy dla każdej części tablicy, aż uzyskamy całkowicie posortowaną tablicę. Na przykład dla tablicy fedacb możemy wybrać wartość d, wtedy wynikiem pierwszego przebiegu algorytmu Quicksort będzie tablica bcadef.
Pierwszy przebieg b c a d e f
Następnie powtarzamy proces dla każdej części tabeli, czyli dla bca i def. Jak łatwo zauważyć, proces ten jest z natury rekurencyjny i rzeczywiście najlepsza jego implementacja wykorzystuje rekurencję.
Wartość, z którą porównujemy pozostałe elementy tablicy, możemy wybrać na dwa sposoby. Albo w sposób losowy, albo jako średnią z pewnego podzbioru wartości tablicy. Optymalne działanie algorytmu wymaga wybrania wartości znajdującej się dokładnie pośrodku zakresu. Jednak dokonanie takiego wyboru nie jest łatwe dla większości sortowanych zbiorów danych. W najgorszym przypadku musimy liczyć się z wyborem wartości będącej ekstremum sortowanego zbioru. Jednak nawet w takim przypadku algorytm Quicksort nadal działa poprawnie. W naszej wersji algorytmu Quicksort będziemy wybierać element leżący pośrodku tabeli.
1. Utwórz plik o nazwie QSDemo.java.
2. Najpierw utwórz klasę Quicksort pokazaną poniżej:
class Quicksort {
// Konfiguruje wywołanie właściwej metody algorytmu Quicksort.
static void qsort(char items[]) {
qs(items, 0, items.length-1);
}
// Rekurencyjna wersja Quicksort sortująca tablicę znaków.
private static void qs(char items[], int left, int right)
{
int i, j;
char x, y;
i = left; j = right;
x = items[(left+right)/2];
do {
while((items[i] < x) && (i < right)) i++;
while((x < items[j]) && (j > left)) j--;
if(i <= j) {
y = items[i];
items[i] = items[j];
items[j] = y;
i++; j--;
}
} while(i <= j);
if(left < j) qs(items, left, j);
if(i < right) qs(items, i, right);
}
}
Aby uprościć interfejs, klasa Quicksort dostarcza metodę qsort(), która konfiguruje wywołanie metody qs() stanowiącej właściwą implementację algorytmu. Dzięki temu można wywołać algorytm, dostarczając jedynie nazwy tablicy do posortowania bez konieczności wstępnego jej podziału na części. Ponieważ metoda qs() jest używana tylko wewnątrz klasy Quicksort,
została zadeklarowana jako private.
3. Aby wykonać sortowanie, wystarczy wywołać metodę Quicksort.qsort(). Ponieważ została ona zadeklarowana jako static, to wywołujemy ją z nazwą klasy. Zwróć więc uwagę, że użycie algorytmu sortowania nie wymaga utworzenia obiektu klasy Quicksort. Po wywołaniu metody qsort() tablica zostanie posortowana. Ta wersja algorytmu sortuje jedynie tablice znaków, ale możesz zaadaptować ją dla tablic dowolnego typu.
4. Na listingu 6.20 przedstawiłem program demonstrujący użycie algorytmu Quicksort.
Listing 6.20. QSDemo.java
class Quicksort {
// Konfiguruje wywołanie właściwej metody algorytmu Quicksort.
static void qsort(char items[]) {
qs(items, 0, items.length-1);
}
// Rekurencyjna wersja Quicksort sortująca tablicę znaków.
private static void qs(char items[], int left, int right)
{
int i, j;
char x, y;
i = left; j = right;
x = items[(left+right)/2];
do {
while((items[i] < x) && (i < right)) i++;
while((x < items[j]) && (j > left)) j--;
if(i <= j) {
y = items[i];
items[i] = items[j];
items[j] = y;
i++; j--;
}
} while(i <= j);
if(left < j) qs(items, left, j);
if(i < right) qs(items, i, right);
}
}
class QSDemo {
public static void main(String args[]) {
char a[] = { 'd', 'x', 'a', 'r', 'p', 'j', 'i' };
int i;
System.out.print("Tablica przed posortowaniem: ");
for(i=0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
// sortuje tablicę
Quicksort.qsort(a);
System.out.print("Tablica posortowana: ");
for(i=0; i < a.length; i++)
System.out.print(a[i]);
}
}
