Sortowanie „szybkie”
Quick_Sort
Tony Hoare (1960)
Algorytm sortowania
QuickSort
Cechy algorytmu:
Przeciętna złożoność obliczeniowa O(nlgn),
Pesymistyczna złożoność O(n
2
),
Sortowanie „w miejscu”,
Niestabilny,
Zastosowanie techniki „dziel i zwyciężaj”,
Algorytm rekurencyjny.
Rozproszone sortowanie,
Wpływ danych wejściowych na złożonoość obliczeniową,
Łatwa implementacja,
Sprawdza się w sortowaniu średnich i dużych zbiorów danych.
ASD
LJ
S
Algorytm sortowania
QuickSort
Podstawowy etap algorytmu:
1.
Wybór elementu osiowego (dzielącego) (
pivotpoint
) v=A[q],
2.
Pogrupowanie elementów tablicy A[lewy.. prawy] w sposób następujący:
żaden z elementów A[lewy], ..., A[q-1] „nie większy” niż v,
żaden z elementów A[q+1], ..., A[prawy] „nie mniejszy” niż v,
ASD
LJ
S
Warianty schematu algorytmu:
Rekurencyjny, nierekurencyjny
Wybór elementu osiowego:
pierwszy, środkowy lub ostatni,
losowy,
mediana z 3.
Algorytm
QuickSort
Zakładając, że wybierany jest element osiowy jako pierwszy element tablicy tj.
v=A[lewy] otrzymujemy podział:
v
lewy
prawy
i
j
elementy ≤ v
elementy ≥ v
v
lewy
prawy
prawy
lewy
Dzielenia tablicy dokonuje procedura podziału (
partition
).
ASD
LJ
S
Algorytm sortowania
QuickSort
Działanie procedury podziału (element osiowy A[lewy]):
1.
Wybór elementu osiowego np. v=A[lewy] dzielącego tablicę A[lewy..prawy],
2.
Przeglądanie A[lewy+1],;,A[prawy] od strony lewej, dopóki nie zostanie
znaleziony element „większy równy” od v,
3.
Przeglądanie A[lewy+1],;,A[prawy] od strony prawej, dopóki nie zostanie
znaleziony element „mniejszy równy” od v,
4.
Dwa elementy, na których się zatrzymują się indeksy, wymieniane są
miejscami. Przeszukiwanie kontynuuowane jest od lewej a później od prawej,
5.
Kiedy indeksy się spotkają proces podziału kończy się,
6.
Element osiowy v zamieniany jest z ostatnim elementem lewej części tablicy.
ASD
LJ
S
Algorytm sortowania
QuickSort
Mechanizm sortowania:
3
7
4
8
5
2
9
i
∞
∞
∞
∞
6
j
3
2
4
5
7
9
∞
∞
∞
∞
8
6
3 2
9
8
7
5
4
4
3
2
2
3
wartownik
ASD
LJ
S
Algorytm sortowania
QuickSort
Partition(A,lewy,prawy)
{//uŜycie wartownika A[prawy+1]=
+∞ ;
v=A[lewy];
i=lewy;
j=prawy+1;
DO{
DO i=i+1; WHILE (A[i]<v);
DO j=j-1; WHILE (A[j]>v);
IF (i<j) swap(A[i],A[j]);
} WHILE(i<j)
A[lewy]=A[j];
A[j]=v;
return(j);
}
QuickSort(A,lewy,prawy)
{
q=Partition (A,lewy,prawy);
IF(q-1>lewy)QuickSort(A,lewy,q-1);
IF(q+1<prawy)QuickSort(A,q+1,prawy);
}
ASD
LJ
S
Mechanizm sortowania:
Algorytm sortowania
QuickSort
QuickSort(A,lewy,prawy)
{
q=Partition (A,lewy,prawy);
IF(q-1>lewy)QuickSort(A,lewy,q-1);
IF(q+1<prawy)QuickSort(A,q+1,prawy);
}
ASD
LJ
S
Partition(A,lewy,prawy)
{
v=A[prawy];
i=lewy-1;
FOR (j=lewy; j≤prawy-1; j=j+1)
IF (A[j]≤v){
i=i+1;
swap(A[i],A[j]);
}
swap(A[i+1],A[prawy]);
return(i+1);
}
Złożoność algorytmu
QuickSort
Złożoność obliczeniowa algorytmu zależy od zrównoważenia podziałów tablicy:
Podział niezrównoważony
Podział zrównoważony
Podział niezrównoważony (przypadek najgorszy) - żaden element nie zostaje
umieszczony po lewej stronie elementu osiowego przez procedurę podziału.
Podział zrównoważony (przypadek najlepszy) - gdy element osiowy dzieli tablicę
na dwie równe części.
ASD
LJ
S
Złożoność algorytmu
QuickSort
Pesymistyczna złożoność (podział niezrównoważony).
Podział niezrównoważony - gdy procedura Partition tworzy dwie podtablice:
1-elementową
(n-1) elementową
Po prawej stronie, elementu osiowego otrzymujemy tablicę pomniejszoną tylko o
jeden element.
Zakładamy, że podziały niezrównoważone będą wykonywane w każdym kroku
algorytmu.
ASD
LJ
S
Złożoność algorytmu
Sortowanie tablicy
n -elementowej
Podział tablicy
T(n) = T(1) + T(n-1) + T
part
(n)
Sortowanie
tablicy (n-1)-elementowej
Sortowanie tablicy
1-elementowej
T(1)=0
Złożoność pesymistyczna
:
ASD
LJ
S
Złożoność procedury Partition.
Rozmiar danych wejściowych n=prawy–lewy +1
T
part
(n) = n-1 = Θ(n)
Złożoność algorytmu
Złożoność czasowa procedury Partition.
T(n) = T(n-1) + Θ(n) = T(1) + ∑
n-1
k=1
Θ(k) =
Θ
(1) + ∑
n -1
k=1
Θ(k) = Θ(∑
n-1
k=1
k) = Θ(n
2
)
0
n = 1
T(n-1) + (n-1)
n > 1
T(n) =
Rozmiar danych wejściowych n=prawy–lewy +1
T
part
(n) = n-1 = Θ(n)
Pesymistyczna złożoność sortowania (podział niezrównoważony).
Θ(1)
n = 1
T(n-1) + Θ(n)
n > 1
T(n) =
ASD
LJ
S
Podział niezrównoważony
Drzewo rekurencji:
1
n-2
1
n-1
1
2
1
n
1
(n-1)
(
n-2
)
(
n-3
)
1
T(n) = 1+ 2+ ... +(n-1) = n(n-1)/2 = Θ(n
2
)
Θ(n
2
)
ASD
LJ
S
Podział zrównoważony
Zrównoważone drzewo podziału:
T(n) = lgn Θ(n) = Θ(n lgn)
n
n/2
n/2
n/4
n/4
n/4
n/4
1
1
1
1
1
1 1
11
1
1 1
1
1
1
lgn
podziałów
Θ(n)
Θ(n)
Θ(n)
Θ(1)
n = 1
2T(n/2) + Θ(n)
n > 1
T(n) =
Rozwiązaniem równania jest T(n) = Θ(n lgn)
ASD
LJ
S
Złożoność algorytmu
QuickSort
0
dla n = 1
T(n) =
2 T(n/2) + (n – 1)
dla n > 1
T(n) = 2
k
T(n/2
k
) + 2
k-1
(n/2
k-1
-1) + 2
k-2
(n/2
k-2
-1) + ... + 2
1
(n/2 -1) + 2
0
(n -1) =
= (n - 2
k-1
) + (n - 2
k-2
) + ...+ (n - 2
-1
) + (n -1) =
= k n – (1+2+...+2
k-1
) = kn – ((2
k
-1) / (2-1)) = kn – (2
k
– 1) =
= nlgn – (n-1)
T(n) = O(nlgn)
Złożoność algorytmu (podział zrównoważony).
ASD
LJ
S
Złożoność algorytmu
QuickSort
Poprawność rozwiązania:
T(n) = nlgn – n+1
T(2n) = 2n lg(2n) - 2n + 1 = 2n(lg2 + lgn) – 2n + 1 =
= 2nlgn + 1 = 2(nlgn – n +1)+ 2n -2 +1 =
= 2T(n) + 2n -1
T(2n) = 2T(n) + 2n - 1
T(n) = Θ(n lgn)
ASD
LJ
S
Złożoność algorytmu QuickSort
Przeciętna złożoność obliczeniowa algorytmu.
partition
procedury
realizacji
czas
j
n
T
j
T
n
n
n
T
ave
ave
n
j
ave
↑
−
+
−
+
−
=
∑
=
))
(
)
1
(
(
1
)
1
(
)
(
1
Równanie rekurencyjne:
- prawdopodobieństwo tego, że zwracana przez procedurę partition
wartość jest równa j.
n
1
)
(
log
log
2
)
(
n
O
n
n
e
n
T
ave
+
=
log ≡ log
10
ASD
LJ
S
Wrażliwość algorytmu QuickSort
Pesymistyczna wrażliwość czasowa algorytmu:
∆(n)=O(n
2
- nlgn) = O(n
2
)
Oczekiwana wrażliwość czasowa:
68
.
0
)
(log
)
3
2
7
(
)
(
2
↓
+
−
=
n
O
n
n
π
σ
ASD
LJ
S
Sortowanie przez scalanie
Merge_Sort
John von Neumann
Sortowanie przez scalanie
ASD
LJ
S
Cechy algorytmu:
Złożoność obliczeniowa O(nlgn),
Stabilny,
Sortowanie ekstensywne,
Zastosowanie techniki „dziel i zwyciężaj”,
Algorytm rekurencyjny,
Sortowanie przez scalanie
5
2
4
6
1
3
2
6
5
2
4
6
1
3
2
6
5
2
4
6
1
3
2
6
5
2
4
6
1
3
2
6
2
5
4
6
1
3
2
6
2
4
5
6
1
2
3
6
1
2
2
3
4
5
6
6
1
2
2
3
4
5
6
6
2
4
5
6
1
2
3
6
2
5
4
6
1
3
2
6
5
2
4
6
1
3
2
6
Idea algorytmu mergeSort.
ASD
LJ
S
Sortowanie przez scalanie
Merge (A,lewy,q,prawy)
{ // B-tablica pomocnicza
i=lewy;
j=q+1;
k=1;
WHILE(i≤q and j≤prawy) {
IF(A[i]<A[j]){
B[k]=A[i];
i=i+1;
}ELSE{
B[k]=A[j]);
j=j+1;
}
k=k+1;
}
IF(i>q )
Kopiuj A[j],...,A[prawy] do B[k],...,B[prawy];
ELSE
Kopiuj A[i],...,A[q] do B[k],...,B[prawy];
Kopiuj B[lewy],...,B[prawy] do A[lewy],...,A[prawy];
}
MergeSort (A, lewy, prawy)
{
IF(lewy<prawy){
q:= (lewy+prawy)/2
MergeSort (A,lewy,q)
MergeSort (A,q+1,prawy)
Merge (A,lewy,q,prawy)
}
}
ASD
LJ
S
Złożoność algorytmu
MergeSort
16
8
8
4
4
4
4
1
1
1
1
1
1 1
11
1
1
1
1
1
1
1
1
10
5
5
3
2
3
2
1
1
1
1
1
2
2
1
1
1
1
1
Drzewa podziału algorytmu Merge_sort.
ASD
LJ
S
Złożoność algorytmu
MergeSort
Θ(1)
dla n = 1
T(n) =
2 T(n/2) + Θ(n)
dla n > 1
0
dla n = 1
T(n) =
2 T(n/2) + (n – 1)
dla n > 1
ASD
LJ
S
Złożoność algorytmu
MergeSort
Θ(1)
dla n = 1
T(n) =
2 T(n/2) + Θ(n)
dla n > 1
0
dla n = 1
T(n) =
2 T(n/2) + (n – 1)
dla n > 1
T(n) = 2
k
T(n/2
k
) + 2
k-1
(n/2
k-1
-1) + 2
k-2
(n/2
k-2
-1) + ... + 2
1
(n/2 -1) + 2
0
(n -1) =
= (n - 2
k-1
) + (n - 2
k-2
) + ...+ (n - 2
-1
) + (n -1) =
= k n – (1+2+...+2
k-1
) = kn – ((2
k
-1) / (2-1)) = kn – (2
k
– 1) =
= nlgn – (n-1).
T(n) =
Θ
(nlgn)
ASD
LJ
S
Złożoność algorytmu
MergeSort
Poprawność rozwiązania:
T(n) = nlgn – n+1
T(2n) = 2n lg(2n) - 2n + 1 = 2n(lg2 + lgn) – 2n + 1 =
= 2nlgn + 1 = 2(nlgn – n +1)+ 2n -2 +1 =
= 2T(n) + 2n -1
T(2n) = 2T(n) + 2n - 1
T(n) = Θ(n lgn)
ASD
LJ
S