Dzisiaj przedstawiony zostanie
kolejny algorytm sortowania, konkurencyjne rozwiązanie względem sortowania
przez scalanie. Szybkie sortowanie (ang. quick sort) zostało obmyślone przez
Tony'ego Hoare i jest uważane za najlepsze w swojej dziedzinie. Podobnie jak
sortowanie przez scalanie przeciętna złożoność obliczeniowa tego algorytmu to O(n*log(n)). Odpowiednia implementacja
tego algorytmu pozwala zużyć znacznie mniej pamięci niż scalanie: O(log(n) zamiast O(n).
Algorytm
ten również działa na zasadzie "dziel i rządź" - z ciągu elementów
wejściowych wybierany jest element
osiowy (ang. pivot) względem którego będzie się odbywał podział. Polega ono na
przeniesieniu wszystkich elementów mniejszych od osi na lewo od niej a
większych na prawo. Po takim przetasowaniu element osiowy znajduje się na
odpowiedniej dla niego pozycji w ciągu wyjściowym. Następnie, zgodnie z regułą
"dziel i rządź" ta sama czynność jest wykonywania na dwóch częściach
ciągu wejściowego aż do uzyskania posortowania elementów. Przykład działania
znajduje się na obrazku poniżej:
 |
| From Wikipedia, the free encyclopedia |
Implementacja:
Najlepszym sposobem implementacji
algorytmów działających na zasadzie dziel i rządź jest rekurencja. Główna pętla
prezentuje się następująco:
void quickSort(int[] arr, int p, int q)
{
if
(q <= p)
return;
int
pivotIndex = p + (q - p) / 2;
if
(arr[p] > arr[q])
{
if(arr[q]
> arr[pivotIndex])
{
pivotIndex = q;
}
else
if(arr[p] > arr[pivotIndex])
{
pivotIndex = p;
}
}
else
{
if(arr[p]
> arr[pivotIndex])
{
pivotIndex = p;
}
else
if (arr[q] < arr[pivotIndex])
{
pivotIndex = q;
}
}
pivotIndex = distribute(arr, p, q,
pivotIndex);
quickSort(arr, p, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, q);
}
Argumenty
wejściowe funkcji to: tablica z elementami do posortowania, indeks pierwszego
elementu tablicy oraz indeks ostatniego elementu. Najpierw sprawdzamy czy
możemy dalej dzielić tablicę - jeśli nie, przerywamy rekursję i "wracamy
wyżej". Dalej wybierany jest element osiowy - jest on wartością środkową
trzech elementów: pierwszego, środkowego i ostatniego. Ten sposób wyboru
elementu pivot zwiększa szanse na najbardziej optymalne działanie algorytmu.
Dzielenie ciągu następuje poprzez wywołanie funkcji distribute, którą omówimy zaraz a następnie funkcja wywołuje samą
siebie aby posortować dalszą część tablicy.
Sposób
implementacji funkcji decyduje o ilości zasobów jaką zużywać będzie sortowanie,
omówiony tutaj sposób nie potrzebuje żadnych dodatkowych tablic, gdyż operuje
on tylko na tablicy wejściowej.
int
distribute(int[] arr, int
p, int q, int
pivot)
{
int
pivotValue = arr[pivot];
int
store = p;
swap(arr, pivot, q);
for
(int i = p; i < q; i++)
{
if
(arr[i] < pivotValue)
{
swap(arr, i, store);
store++;
}
}
swap(arr, store, q);
return store;
}
Argumenty
wejściowe to: tablica na której będą odbywać się operacje, pozycja początku,
końca tablicy oraz indeks elementu osiowego. Następnie elementy zostają
poprzestawiane zgodnie z regułą: mniejsze na lewo i zostaje zwrócona pozycja
środka tego podziału która w późniejszych wywołaniach posłuży jako wskaźnik
końca lub początku nowej tablicy.
Podsumowanie
Sortowanie
szybkie jest niewątpliwie demonem szybkości i oszczędności zasobów ale jest
również niezwykle podatne sposób ułożenia danych wejściowych. Quick sort
sprawdza się najlepiej gdy dane są czysto losowe schody zaczynają się gdy są
one częściowo lub całkowicie posortowane - złożoność obliczeniowa sięga w tych
przypadkach nawet O(n2)
czyli równie wolno co proste algorytmy pokroju sortowania bąbelkowego. Również
wybór elementu osiowego nie jest bez znaczenia: najlepiej gdy ten element jest
medianą wszystkich wartości w tablicy, im bliżej wartości minimalnej bądź
maksymalnej tym gorzej.
Brak komentarzy:
Prześlij komentarz