1
JADWIGA CHUDZICKA
Sortowanie szybkie (QuickSort)
Jest to dość szybki algorytm klasy
O(N log2N) / O(N logN).
W tym rozwiązaniu, dzięki odpowiedniej dekompozycji
sortowanego zbioru, osiąga się znaczną poprawę
szybkości sortowania.
Zakładamy, że sortowanym zbiorem jest
jednowymiarowa (z jednym indeksem) tablica liczb.
Algorytm przebiega następująco: dzielimy całą tablicę
na dwie części wg pewnej liczby działowej (osi
podziału (ang. pivot)) (zazwyczaj jest nią pierwszy
element analizowanego fragmentu tablicy).
2
JADWIGA CHUDZICKA
Wszystkie liczby mniejsze od osi podziału P są
przerzucane przed nią, a większe za nią.
Procedura podziału na wstępie odczytuje wartość
elementu P i analizowany fragment tablicy jest
dzielony tak, aby elementy < P znalazły się po lewej,
a pozostałe - po prawej stronie P, jak na rysunku:
< P P >= P
Kolejnym etapem jest zastosowanie tej samej
procedury sortowania do lewego i prawego
fragmentu tablicy.
Wywołania rekurencyjne kończą się w momencie,
gdy rozmiar fragmentu tablicy wynosi 1  wówczas
nie ma już czego sortować.
3
JADWIGA CHUDZICKA
Mówiąc inaczej:
Procedura wywołuje samą siebie dla liczb
mniejszych od liczby P (czyli od osi), a póz
niej dla
liczb większych od liczby P. Tablica ta jest dzielona
na coraz to mniejsze części przez kolejne
rekurencyjne wywołania procedury do czasu, gdy
w danym fragmencie tablicy zostanie tylko jedna
liczba.
4
JADWIGA CHUDZICKA
Dwa główne etapy algorytmu QuickSort
przedstawia poniższy rysunek:
QuickSort
P
QuickSort QuickSort
< P P >= P
Powtarzanie procedury QuickSort dla coraz mniejszych
fragmentów tablicy prowadzi do uporządkowania całej
tablicy.
5
JADWIGA CHUDZICKA
Algorytm jest zwięzły i np. w jęz. C++
wygląda następująco (część algorytmu
zastąpiona na razie komentarzami):
void qsort(int *tablica, int lewy, int prawy)
{
if (lewy < prawy)
{
int m;
// Podziel tablicę względem elementu osiowego P
// Jako P można przyjąć pierwszy element, czyli tablica[lewy]
// Pod koniec podziału elem. P zostanie przeniesiony do komórki nr m
qsort(tablica,lewy,m-1);
qsort(tablica,m+1,prawy);
}
}
6
JADWIGA CHUDZICKA
Najistotniejsza część przedstawionego algorytmu
kryje się za komentarzami. Można ten fragment
realizować na różne sposoby, dlatego powstało
wiele implementacji algorytmu QuickSort.
Elegancki i prosty sposób zostanie przedstawiony dalej
w języku C++. Zastosowano w nim następ. oznaczenia:
lewy, prawy  odpowiednio lewy/prawy skrajny indeks
aktualnego fragmentu tablicy;
P  wartość osiowa (zazwyczaj będzie to tablica[lewy]);
i  indeks przemieszczający się po indeksach od lewy
do prawy;
m  poszukiwany indeks elementu tablicy, w której
będzie umieszczony element osiowy.
7
JADWIGA CHUDZICKA
Przemieszczanie się po tablicy ma na celu
poukładanie elementów tak, aby po lewej stronie m
znajdowały się wartości mniejsze od P, a po
prawej >= P. W tym celu sprawdzamy
prawdziwość warunku tablica[ i ] < P.
P

= P Fragment niezbadany
lewy m prawy
i
Jeśli powyższy warunek jest spełniony, to zwiększamy
m i zamieniamy miejscami elementy tablica[ i ] i
tablica[ m ], ustalając w ten sposób właściwy porządek.
Po zakończeniu przeglądania tablicy stan będzie taki jak na rys.:
P

= P
lewy m prawy
8
JADWIGA CHUDZICKA
Widać, że elementem, który jeszcze nie jest na
właściwym miejscu jest P. Należy więc zamienić
miejscami tablica[ lewy ] z tablica[ m ], aby
otrzymać oczekiwany stan:

= P
lewy m prawy
Cała procedura w języku C++ na następnym
slajdzie.
9
JADWIGA CHUDZICKA
void qsort(Typ_elementu *tablica, int lewy, int prawy)
{
if (lewy < prawy)
Tu można wstawić
dowolny typ, np. int
{
int m=lewy;
for(int i=lewy+1; i<=prawy; i++)
if (tablica[ i ]przestaw(tablica[++m], tablica[ i ]);
przestaw(tablica[ lewy ], tablica[ m ]);
// powyższa funkcja zamienia argumenty miejscami
qsort(tablica, lewy, m-1);
qsort(tablica, m+1, prawy);
}
}
10
JADWIGA CHUDZICKA
Funkcja zamieniająca argumenty miejscami:
inline void przestaw(int& a, int &b) // inline ze
względów optymalizacji
{//przekazanie przez referencję gdyż będziemy
zmieniać zawartość argumentów
Typ_elementu temp=a;
a=b;
b=temp;
}
11
JADWIGA CHUDZICKA
 DZIEL I ZWYCI
ŻAJ
QuickSort stanowi dobry przykład techniki
programowania zwanej  dziel i zwyciężaj .
Chodzi w niej o taką dekompozycję
problemu, aby osiągnąć zysk czasowy
wykonywania programu, a przy okazji
również uproszczenie rozwiązania. Oba te
wymagania spełnia algorytm QuickSort.
12
JADWIGA CHUDZICKA


Wyszukiwarka