ALGORYTMY SORTOWANIA DANYCH
W
zagadnieniu
sortowania
danych
rozpatrywa¢
b¦dziemy
n
liczb
caªkowitych, b¦d¡cych pierwotnie w losowej kolejno±ci, które nale»y upo-
rz¡dkowa¢ nierosn¡co.
Oczywi±cie sortowa¢ mo»emy te» inne typy danych ni» liczby caªkowite (np.
liczby zmiennoprzecinkowe, ci¡gi znaków alfanumerycznych, itp.), jednak
idea algorytmów nie zmienia si¦.
Podobnie, je±li chodzi o sortowanie w porz¡dku odwrotnym do zaªo»onego
(niemalej¡co) zmiany sprowadzaj¡ si¦ praktycznie do zamiany znaków
mniejszo±ci / wi¦kszo±ci na przeciwne.
Najprostszym jest algorytm
sortowania b¡belkowego,
który mo»na zaimplementowa¢ jako dwie zagnie»d»one p¦tle typu for, z któ-
rych ka»da wykonuje si¦ O(n) razy. Zadaniem tych p¦tli jest umieszczenie
ka»dego z elementów na wªa±ciwej pozycji.
O(n)
O(n)
= O(n
2
).
int B[n];
void bubble(int* B)
{ for(j=1; j<n; j++)
for(i=n-1; i>0; i--)
if(B[i-1]>B[i])
{ temp=B[i];
B[i]=B[i-1];
B[i-1]=temp;
};
};
Zªo»ono±¢ obliczeniowa sortowania b¡belkowego jest zawsze O(n
2
)
ka»da
z p¦tli wykona si¦ zawsze O(n) razy, chocia» np. w sytuacji wst¦pnego po-
sortowania danych wej±ciowych liczb¦ obiegów p¦tli wewn¦trznej mo»na by
zmniejszy¢.
Uwzgl¦dnia to algorytm
sortowania przez wstawianie,
gdzie wewn¦trzna p¦tla szuka wªa±ciwej pozycji dla bie»¡cego elementu,
ale tylko w±ród elementów wcze±niej posortowanych:
O(i)
O(n)
int B[n];
void insert(int* B)
{ for(i=2;i<n+1;i++)
{ j=i-1;
while(B[j]<B[j-1])
{ pom=B[j];
B[j]=B[j-1];
B[j-1]=pom;
j--;
if(j<1) break;
};
};
};
Czy takie usprawnienie przekªada si¦ na lepsz¡ zªo»ono±¢ obliczeniow¡?
Liczba iteracji p¦tli wewn¦trznej za pierwszym razem (tj. przy pierwszej
iteracji p¦tli zewn¦trznej) wynosi maksymalnie 1, za drugim razem 2,
potem 3, itd. Najwi¦cej razy wykona si¦ w ostatniej (
(n − 1)
-szej) iteracji
p¦tli zewn¦trznej
n − 1
razy.
Zatem, aby wyznaczy¢ zªo»ono±¢ obliczeniow¡ caªej procedury sortowa-
nia przez wstawianie, wystarczy policzy¢ sum¦ nast¦puj¡cego ci¡gu:
1 + 2 + 3 + . . . + (n − 2) + (n − 1) =
n−1
X
j=1
j,
n−1
X
j=1
j =
1
2
(n − 1)n =
1
2
n
2
−
1
2
n = O(n
2
).
Uzyskali±my wi¦c algorytm tego samego rz¦du co algorytm sortowania b¡-
belkowego.
Jednak rozwa»my przypadek, gdy liczby s¡ ju» posortowane.
(Przypomnijmy, »e w takiej sytuacji algorytm sortowania b¡belkowego wy-
kona tyle samo operacji, co w przypadku danych nieposortowanych).
W takim przypadku, w algorytmie sortowania przez wstawianie p¦tla we-
wn¦trzna nie wykona si¦ ani razu w ka»dej z n−1 iteracji p¦tli zewn¦trznej.
Zatem czas dziaªania algorytmu ograniczy si¦ do
O(n)
.
Sortowanie przez kopcowanie
Wykorzystajmy teraz struktur¦ kopca do skonstruowania algorytmu sorto-
wania.
Idea sprowadza si¦ do nast¦puj¡cych kroków:
1. Umie±¢ wszystkie dane wej±ciowe w kopcu. Utwórz pust¡ tablic¦
wyj±ciow¡ o dªugo±ci n.
2. Pobierz element z korzenia na pierwsz¡ woln¡ pozycj¦ w tablicy wyj-
±ciowej.
3. Umie±¢ w korzeniu (w miejsce pobranego elementu) ostatni element
z kopca
(rozmiar kopca zmniejsza si¦ o 1)
. Przywró¢ wªa±ciwo±¢ kopca
(analogicznie, jak w procedurze usuwania elementu z kopca)
.
4. Je±li kopiec nie jest pusty to skocz do Kroku 2; w przeciwnym wypadku
STOP posortowane dane s¡ w tablicy wyj±ciowej.
Wyznaczmy teraz zªo»ono±¢ obliczeniow¡ algorytmu sortowania przez kop-
cowanie.
Po pierwsze, nale»y zauwa»y¢, »e w algorytmie kroki 2-4 s¡ powtarzane
n
razy
(w ka»dej iteracji, kopiec pocz¡tkowo n elementowy zmniejsza si¦ o 1)
.
Zatem zªo»ono±¢ caªej procedury mo»na wyliczy¢ jako:
Zªo»ono±¢ Kroku 1 + n· Zªo»ono±¢ Kroków 2-4.
Wyznaczmy wi¦c zªo»ono±¢ poszczególnych kroków algorytmu.
Zªo»ono±¢ Kroku 1: Utworzenie kopca z n losowych danych to, jak ju»
wspomniano, n-krotne wykonanie operacji wstawienia elementu do kopca.
Wychodz¡c z zaªo»enia, »e wstawienie elementu do kopca n elementowego
zajmuje O(log n) czasu
(tyle, ile wynosi wysoko±¢ kopca)
, zªo»ono±¢ Kroku 1
mo»na oszacowa¢ jako
O(n log n)
.
Oczywi±cie 2-ga cz¦±¢ Kroku 1 utworzenie tabl. wyj±c. zajmuje
O(1)
.
UWAGA: Utworzenie kopca mo»na te» wykona¢ szybciej w sposób
wst¦puj¡cy.
W metodzie tej zakªadamy, »e od pocz¡tku kopiec jest wypeªniony loso-
wymi danymi. Rozpoczynaj¡c od elementu bn/2c przechodzimy przez ko-
lejne elementy a» do pierwszego i za ka»dym razem wykonujemy operacj¦
naprawy cz¦±ci kopca le»¡cego poni»ej (tj. poddrzewa, dla którego bie-
»¡cy element jest korzeniem), na podobnej zasadzie jak naprawa kopca po
usuni¦ciu elementu.
W takiej sytuacji mo»na wykaza¢, »e w kopcu jest najwy»ej dn/2
k+1
e
ele-
mentów maj¡cych poni»ej siebie k poziomów. Dla ka»dego takiego ele-
mentu operacja naprawy cz¦±ci kopca le»¡cego poni»ej zajmuje
O(k)
czasu.
Zatem zªo»ono±¢ Kroku 1 mo»na wyliczy¢ jako:
blog nc
X
k=0
n
2
k+1
O(k) = O
n ·
blog nc
X
k=0
k
2
k
.
Korzystaj¡c teraz z zale»no±ci
(patrz np. Cormen i in.)
∞
X
k=0
k
2
k
=
1/2
(1
− 1/2)
2
= 2,
otrzymamy
O
n ·
blog nc
X
k=0
k
2
k
= O
n ·
∞
X
k=0
k
2
k
= O(n).
Zªo»ono±¢ Kroków 2 i 4 to oczywi±cie
O(1)
,
natomiast Kroku 3
O(log n)
.
Zatem zªo»ono±¢ caªego algorytmu to
O(n) + n · (O(1) + O(log n) + O(1)) = O(n log n).
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
1
5
6
9
2
12
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
1
5
6
9
2
12
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
1
5
6
9
2
12
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
1
5
6
9
2
12
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
1
12
6
9
2
5
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
1
12
6
9
2
5
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
9
12
6
1
2
5
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
3
9
12
6
1
2
5
7
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
12
9
7
6
1
2
5
3
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
12
9
7
6
1
2
5
3
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
12
8
9
7
6
1
2
5
3
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
12
8
9
7
6
1
2
5
3
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
Tablica wyjściowa:
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
9
7
6
1
2
5
3
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12
Tablica wyjściowa:
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[10]
[9]
8
9
7
6
1
2
5
3
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12
Tablica wyjściowa:
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[9]
8
9
7
6
1
2
5
3
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12
Tablica wyjściowa:
[1]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[9]
8
4
7
6
1
2
5
3
9
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12
Tablica wyjściowa:
[1]
[8]
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
Tablica wyjściowa:
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[9]
8
4
7
6
1
2
5
3
[1]
[8]
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
Tablica wyjściowa:
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
[9]
8
4
7
6
1
2
5
3
[1]
3
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
Tablica wyjściowa:
[8]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
8
4
7
6
1
2
5
[1]
8
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
Tablica wyjściowa:
[8]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
7
4
5
6
1
2
3
[1]
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8
Tablica wyjściowa:
[8]
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
[8]
7
4
5
6
1
2
3
[1]
[8]
3
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8
Tablica wyjściowa:
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
7
4
5
6
1
2
[1]
3
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8
Tablica wyjściowa:
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
7
4
5
6
1
2
[1]
7
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8
Tablica wyjściowa:
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
6
4
5
3
1
2
[1]
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7
Tablica wyjściowa:
[3]
[2]
[6]
[4]
[7]
[5]
[6]
[4]
[5]
6
4
5
3
1
2
[1]
[3]
[6]
[7]
[5]
[6]
[5]
4
1
2
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7
Tablica wyjściowa:
[2]
[4]
[4]
6
5
3
[1]
[3]
[6]
[5]
[6]
[5]
4
1
2
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7
Tablica wyjściowa:
[2]
[4]
[4]
6
5
3
[1]
[3]
[6]
[6]
4
1
6
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7
Tablica wyjściowa:
[2]
[4]
[4]
5
2
3
[5]
[5]
[1]
[3]
[6]
[5]
[6]
[5]
4
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6
Tablica wyjściowa:
[2]
[4]
[4]
5
2
3
[5]
[5]
[1]
[3]
[6]
[6]
4
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6
Tablica wyjściowa:
[2]
[4]
[4]
5
2
3
[5]
[5]
[5]
[5]
[1]
[3]
4
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6
Tablica wyjściowa:
[2]
[4]
[4]
5
2
3
[5]
[5]
[5]
[5]
[1]
[3]
4
5
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6
Tablica wyjściowa:
[2]
[4]
[4]
3
2
1
[5]
[5]
[5]
[5]
[1]
[3]
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5
Tablica wyjściowa:
[2]
[4]
[4]
3
2
1
[5]
[5]
[5]
[5]
[1]
[3]
[5]
[5]
4
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5
Tablica wyjściowa:
[2]
[4]
[4]
2
3
[1]
[3]
[2]
[4]
[4]
3
4
2
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5
Tablica wyjściowa:
[1]
[3]
[2]
[4]
[4]
3
1
2
4
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5
Tablica wyjściowa:
[1]
[3]
[2]
[4]
[4]
3
1
2
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4
Tablica wyjściowa:
[1]
[3]
[2]
[4]
[4]
3
1
2
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4
Tablica wyjściowa:
[1]
[3]
[2]
3
1
2
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4
Tablica wyjściowa:
[1]
[3]
[2]
2
1
3
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4
Tablica wyjściowa:
[1]
[3]
[2]
2
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3
Tablica wyjściowa:
[1]
[3]
[2]
2
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3
Tablica wyjściowa:
[1]
[2]
2
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3
Tablica wyjściowa:
[1]
[2]
1
2
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3
Tablica wyjściowa:
[1]
[2]
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3 2
Tablica wyjściowa:
[1]
[2]
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3 2
Tablica wyjściowa:
[1]
1
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3 2
Tablica wyjściowa:
[1]
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3 2 1
Tablica wyjściowa:
Sortowanie przez kopcowanie:
przykład dla n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
12 9
8 7 6 5 4 3 2 1
Tablica wyjściowa:
KONIEC
Algorytm Quicksort
Zasad¦ dziaªania tego algorytmu najlepiej przedstawi¢ przy pomocy nast¦-
puj¡cej procedury rekurencyjnej:
int B[n];
void Quicksort(int* B,int p,int r)
{ if(p<r)
{ q=Partition(B,p,r);
Quicksort(B,p,q);
Quicksort(B,q+1,r);
};
};
Kluczowym elementem algorytmu jest procedura Partition.
Procedura ta ma za zadanie taki podziaª obszaru tablicy
B
od indeksu p
do indeksu q, aby przed elementem
q
znalazªy si¦ elementy nie wi¦ksze
od q-tego, a po tym elemencie nie mniejsze.
Aby posortowa¢ caª¡ tablic¦
B
, nale»y wywoªa¢ Quicksort(B,1,n).
Zatem caªa tablica dzielona jest na 2 cz¦±ci: w pierwszej z nich znajd¡ si¦
elementy nie wi¦ksze ni» w drugiej. Nast¦pnie ka»da z tych cz¦±ci dzielona
jest na dwie mniejsze o takiej samej wªasno±ci, itd.
Algorytm ko«czy dziaªanie, gdy osi¡gnie wyª¡cznie obszary 1- lub 2-
elementowe, i w ka»dym z 2-elementowych mniejszy element zostanie
ustawiony przed wi¦kszym
(oczywi±cie elementy równe mog¡ pozosta¢ w dowolnej
kolejno±ci)
.
Jedn¡ z decyzji, jak¡ nale»y podj¡¢ przy konstruowaniu procedury Partition
jest wybór elementu
q
, wzgl¦dem którego b¦dzie dokonany podziaª elemen-
tów B[p] . . . B[r]. Jednym z najprostszych sposobów jest wybór elementu
skrajnego, np.
B[r]
.
Nast¦pnie analizowane s¡ kolejno wszystkie pozostaªe elementy i umiesz-
czane w pierwszym albo w drugim obszarze (w zale»no±ci od tego, czy dany
element jest odpowiednio mniejszy czy wi¦kszy od q-tego). Najlepiej, je±li
powy»sz¡ operacj¦ wykonamy w miejscu.
Zilustrujmy powy»sze rozwi¡zanie na przykªadzie.
Partition (B, p, r )
2
8
7 1 3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
8
7 1 3 5 6 4
B:
[p]
[r]
q
Partition (B, p, r )
2
8
7 1 3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
8
7 1 3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
8
7 1 3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
8
7 1 3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
8
7
1
3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
1
7 8 3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
1
7 8 3 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
1
7
8
3
5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
1
3 8 7 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
1
3 8 7 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
1
3 8 7 5 6 4
B:
[p]
[r]
Partition (B, p, r )
2
1
3
8
7 5 6
4
B:
[p]
[r]
Partition (B, p, r )
2
1
3 4 7 5 6 8
B:
[p]
[r]
Zªo»ono±¢ obliczeniowa procedury Partition wynosi
O(n)
.
A jaka jest zªo»ono±¢ caªego algorytmu?
Zale»y to ±ci±le od dokonywanych podziaªów.
Je±li za ka»dym razem wybierany jest do podziaªu taki element, który
dzieli dany obszar na 2 równe cz¦±ci, to uzyskamy zªo»ono±¢
O(n log n)
,
co uzasadnia poni»szy rysunek.
n
n / 2
n / 2
n / 4
n / 4
n / 4
n / 4
n / 8
n / 8
n / 8
n / 8
n / 8
n / 8
n / 8
n / 8
log n
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
n
n
n
n
n
O(n log n)
czas pojedynczego wywołania Partition
Jednak je±li do podziaªu wybierany jest zawsze taki element, »e jedna
cz¦±¢ dzielonego obszaru zawiera 1 element, to uzyskamy wynik
O(n
2
)
.
n
1
n – 1
n
n
n
n – 1
3
2
O(n
2
)
n – 2
1
n – 3
1
2
1
1
n – 2
Na koniec nale»y zauwa»y¢, »e wystarczy, aby podziaª byª dokonywany
w proporcji 9/1, aby zªo»ono±¢ algorytmu Quicksort wynosiªa
O(n log n)
.
Czy mo»na skonstruowa¢ algorytm sortowania
o zªo»ono±ci mniejszej ni»
O(n log n)
?
Wszystkie dotychczas przedstawione algorytmy s¡ algorytmami dziaªaj¡cymi
na zasadzie porówna«. Mo»na wykaza¢, »e algorytmy tego typu nie mog¡
mie¢ zªo»ono±ci mniejszej ni»
O(n log n)
. Zatem konstruuj¡c algorytm
sortowania przez kopcowanie osi¡gn¦li±my doln¡ granic¦.
Jednak przy pewnych dodatkowych zaªo»eniach (np. odno±nie warto±ci
danych wej±ciowych) mo»na uzyska¢ lepszy rezultat.
Sortowanie przez zliczanie
W algorytmie tym mamy dodatkow¡ tablic¦,
C
, o rozmiarze równym
maksymalnej warto±ci spo±ród danych wej±ciowych, powiedzmy m. Wszyst-
kie komórki tej tablicy s¡ zainicjowane warto±ci¡ 0.
Dziaªanie algorytmu sprowadza si¦ do sprawdzenia ka»dej warto±ci ta-
blicy wej±ciowej i zwi¦kszenie o 1 tej komórki tablicy C, która odpowiada
warto±ci analizowanej danej (np., je±li w danej komórce tablicy wej±ciowej
odczytamy 5, to inkrementujemy komórk¦ C[5]).
Po przeanalizowaniu wszystkich n danych wej±ciowych, w tablicy C mamy
informacj¦, ile w±ród tych danych byªo warto±ci 1, ile warto±ci 2, itd. Tablic¦
wyj±ciow¡ wypeªniamy wi¦c tak, »e do pierwszych C[m] komórek wpisujemy
m
, do nast¦pnych C[m − 1] komórek m − 1, itd., a do ostatnich C[1]
komórek wpisujemy warto±¢ 1.
Zªo»ono±¢ obliczeniowa algorytmu wynosi
O(n + m)
:
•
ka»d¡ dan¡ wej±ciow¡ analizujemy 1 raz,
•
za ka»dym razem inkrementacja wybranej komórki tablicy C zajmuje
O(1)
,
•
na koniec wypeªnienie tablicy wyj±ciowej wymaga przej±cia po wszyst-
kich elementach tablicy C.
Dla m = O(n) algorytm ma wi¦c zªo»ono±¢
O(n)
.
Sortowanie pozycyjne
Sortowanie
n
liczb
d
-cyfrowych polega na wykonaniu d sortowa« naj-
pierw wg najmniej znacz¡cej cyfry, pó¹niej bardziej znacz¡cej, itd. Na ko«cu
sortujemy wg najbardziej znacz¡cej cyfry. Trzeba tylko uwzgl¦dnia¢ kolej-
no±¢ z poprzedniego sortowania, je±li cyfry na bie»¡cej pozycji s¡ jednakowe.
Poniewa» cyfry w systemie np. dziesi¦tnym maj¡ maksymalnie warto±¢
9, mo»emy z powodzeniem wykorzysta¢ do sortowania wg poszczególnych
pozycji algorytm sortowania przez zliczanie.
Zªo»ono±¢ obliczeniowa wynosi wtedy
O(dn + dm)
, gdzie m jest maksy-
maln¡ warto±ci¡ cyfr (np. m = 9 dla systemu dziesi¦tnego). Je±li d jest
staª¡, a m = O(n), to otrzymujemy zªo»ono±¢
O(n)
.
Sortowanie kubeªkowe
Przy zaªo»eniu, »e dane wej±ciowe s¡ z okre±lonego zakresu, np. [0,1),
dzielimy ten przedziaª na n obszarów o jednakowym rozmiarze (tworzymy
n
odpowiadaj¡cych im kubeªków). Ka»da dana wpada wi¦c do odpowied-
niego kubeªka (je±li dane wej±ciowe s¡ z rozkªadu jednostajnego, w ka»dym
kubeªku znajdzie si¦ mniej wi¦cej tyle samo elementów).
Nast¦pnie dane wewn¡trz ka»dego kubeªka sortujemy, np. algorytmem
przez wstawianie, i zª¡czamy kubeªki razem, otrzymuj¡c poprawny ci¡g
wynikowy.
Mo»na wykaza¢, »e zªo»ono±¢ obliczeniowa wynosi
O(n)
.
Document Outline
- Sort_Kopc.pdf
- Slajd 1
- Slajd 2
- Slajd 3
- Slajd 4
- Slajd 5
- Slajd 6
- Slajd 7
- Slajd 8
- Slajd 9
- Slajd 10
- Slajd 11
- Slajd 12
- Slajd 13
- Slajd 14
- Slajd 15
- Slajd 16
- Slajd 17
- Slajd 18
- Slajd 19
- Slajd 20
- Slajd 21
- Slajd 22
- Slajd 23
- Slajd 24
- Slajd 25
- Slajd 26
- Slajd 27
- Slajd 28
- Slajd 29
- Slajd 30
- Slajd 31
- Slajd 32
- Slajd 33
- Slajd 34
- Slajd 35
- Slajd 36
- Slajd 37
- Slajd 38
- Slajd 39
- Slajd 40
- Slajd 41
- Slajd 42
- Slajd 43
- Slajd 44
- Slajd 45
- Slajd 46
- Slajd 47
- Slajd 48
- Slajd 49
- Part.pdf
Wyszukiwarka
Podobne podstrony:
Napęd Elektryczny wykład
wykład5
Psychologia wykład 1 Stres i radzenie sobie z nim zjazd B
Wykład 04
geriatria p pokarmowy wyklad materialy
ostre stany w alergologii wyklad 2003
WYKŁAD VII
Wykład 1, WPŁYW ŻYWIENIA NA ZDROWIE W RÓŻNYCH ETAPACH ŻYCIA CZŁOWIEKA
Zaburzenia nerwicowe wyklad
Szkol Wykład do Or
Strategie marketingowe prezentacje wykład
Wykład 6 2009 Użytkowanie obiektu
wyklad2
wykład 3
więcej podobnych podstron