Avancerede sorteringsmetoder:
• Metoder med kompleksitet O(n logn):
- Quicksort (ekskurs: udvælgelse)
- Sortering ved fletning
----------------------------------------------------------
- Hob-sortering (prioritetskøer)
• En metode med kompleksitet O(n): - Radixsortering
Quicksort (Hoare, 1960)
venstre del højre del ≤ Sorter derefter den venstre del og den højre del rekursivt. Quicksort er i praksis den hurtigste algoritme til intern sortering.
Desuden er den forholdsvis let at implementere.
Ide: For at sortere et array, så del det i en venstre og en højre del, således at alle elementer i den venstre del er mindre end alle elementer i den højre del.
Deling (partition)
Delingen af et array a kan foretages således:
(1) Vælg en delingsværdi, v, blandt værdierne i a.
(2) Gennemløb a fra venstre mod højre, indtil der findes et element a[i] ≥ v.
(3) Gennemløb a fra højre mod venstre, indtil der findes et element a[j] ≤ v.
(4) Ombyt a[i]og a[j].
(5) Fortsæt med at gennemløbe og ombytte, indtil de to gennemløb “krydser” hinanden.
v: delingsværdien
i: venstre-mod-højre-pegeren
j: højre-mod-venstre-pegeren i j ≤ v ≥ v a[i] ≥ v a[j] ≤ v X Y i j ≤ v ≥ v Y X ≤ v ≥ v
Implementering
Resultat: a[l:j] ≤ a[i:r] og i > j.
Kan bevises ved at påvise gyldigheden af løkkeinvarianten { a[l:i-1] ≤ v ≤ a[j+1:r] } for den yderste løkke. Deling af a[l:r] med hensyn til v:
i = l; j = r;
while (i <= j) {
while (a[i] < v) i++;
while (a[j] > v) j--;
if (i <= j)
{ swap(a, i, j); i++; j--; }
}
Quicksort
Delingsværdien v kan være værdien af et vilkårligt
element blandt a[l:r], f.eks. a[(l+r)/2].
void quicksort(int a[], int l, int r) {
if (l < r) {
int v = a[(l+r)/2];
int i = l, j = r;
while (true) {
while (a[i] < v) i++;
while (a[j] > v) j--;
if (i >= j) break;
swap(a, i, j); i++; j--;
}
quicksort(a, l, j);
quicksort(a, i, r);
}
}
int partition(int a[], int l, int r) {
int v = a[r];
int i = l-1, j = r;
while (true) {
while (a[++i] < v) ;
while (a[--j] > v)
if (j == l) break;
if (i >= j) break;
swap(a, i, j);
}
swap(a, i, r);
return i;
} Sedgewicks implementation Sætningen ‘if (j == l) break’ kan fjernes ved brug af “stopklods” (eng. sentinel), a[l-1] ≤ a[l..r]. Sedgewick anvender a[r] som delingsværdi.
a[l:r-1] deles, hvorefter a[r] ombyttes med a[i].
int quicksort(int a[], int l, int r) {
if (l < r) {
int i = partition(a, l, r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
}
Metoden quicksort
Animering af Quicksort
Antal sammenligninger
Lad C(N) betegne antallet af sammenligninger ved kald af quicksort med N elementer (N = r-l+1).
Ved delingen foretages cirka N sammenligninger.
Herefter sorteres den venstre del og den højre del hver for sig.
I gennemsnit består hver del af cirka N/2 elementer, og får vi derfor rekursionsrelationen: C(N) = N + 2*C(N/2) for N ≥ 2, og C(1) = 0.
som har løsningen C(N) = Nlog2N.
Antal sammenligninger i gennemsnit
2N ln N ≈ 1.39 N log2N
Det gennemsnitlige antal sammenligninger er altså kun 39% højere end antallet af sammenligninger i det bedste tilfælde.
Mere præcise beregninger giver
Quicksort bruger i gennemsnit cirka 2N lnN
sammenligninger.
hvor ln betegner den naturlige logaritme.
Antal sammenligninger i værste tilfælde
Det værste tilfælde optræder, når delingen for hvert N resulterer i en del med 1 element og en del med N-1 elementer.
Vi få da C(N) = N + C(N-1), for N ≥ 2, og C(1) = 0.
som har løsningen C(N) = N(N+1)/2.
Det værste tilfælde optræder med Sedgewicks implementation, når filen er sorteret (eventuelt i omvendt orden).
Valg af tilfældigt delingselement (eller “median af 3”) reducerer chancen for, at det værste tilfælde optræder.
Quicksort med median af 3
l m r r-1 void quicksort(int a[], int l, int r) {
if (l < r) {
if (a[l] > a[r]) swap(a, l, r);
int m = (l+r)/2;
if (m == l) return;
if (a[l] > a[m]) swap(a, l, m);
if (a[m] > a[r]) swap(a, m, r);
swap(a, m, r-1);
int i = partition(a, l+1, r-1);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
}
Pladskrav
if (i-l > r-i) {
quicksort(a, i+1, r);
quicksort(a, l, i-1);
}
else {
quicksort(a, l, i-1);
quicksort(a, i+1, r);
} Dog kun under forudsætning af, at der automatisk
foretages elimination af halerekursion. Kravet til ekstra plads er proportionalt med den maksimale stakdybde for de rekursive kald af quicksort.
I værste fald kan stakdybden blive N. Nemlig når enhver deling bevirker, at den højre del består af 1 element.
Kravet til stakplads kan mindskes (til log2N) ved altid først at sortere den mindste af de to dele:
Fjernelse af rekursion
void quicksort(int a[], int l, int r) {
Stack s = new Stack(50);
while (true) {
while (l < r) {
int i = partition(a, l, r);
if (i-l > r-i)
{ s.push2(l, i-1); l = i+1; }
else
{ s.push2(i+1, r); r = i-1; }
}
if (s.empty())
return;
r = s.pop(); l = s.pop();
}
} Quicksort er relativt langsom for små filer, bl.a. på grund af de rekursive kald.
Rekursionen kan helt fjernes (ved brug af eksplicit stak).
Benyt en simpel metode for små delfiler
Langt mere effekt har anvendelse af ‘sortering ved indsættelse’ for “relativt små” delfiler.
if (r-l <= M) insertion(a, l, r); else indsættes i stedet for if (l < r) i starten af quicksort, hvor M f.eks. er 10.
Bedre er dog at vente med insertion-sorteringen: quicksort(a, 1, N); insertion(a, 1, N);
Animering af quicksort (ignorering af små delfiler)
Empirisk undersøgelse af Quicksort (PowerBook G3, 400 MHz, Metrowerks)
Tid i sekunder:
Metode N = 32000 64000 128000 256000 512000 1024000
quicksort1 0.03 0.05 0.09 0.19 0.39 0.85
quicksort2 0.03 0.05 0.09 0.20 0.42 0.90
quicksort3 0.03 0.05 0.09 0.18 0.39 0.85
quicksort4 0.03 0.05 0.09 0.17 0.36 0.76
shellsort 0.04 0.08 0.18 0.41 1.03 2.37
insertion 6.59 27.24 114.14 ≈ 8 min ≈ 32 min ≈ 2 timer
quicksort1: Min version
quicksort2: Sedgwicks version
quicksort3: insertion-sort for små delfiler (M = 10).
quicksort4: quicksort3 med median af 3
Udvælgelse Problem: Find det k’te mindste element blandt en mængde af N elementer. Eksempel: Det 3. mindste tal blandt {3, 6, 5, 2, 8, 4} er 4. Løsningsmulighed 1: Sorter elementerne i stigende orden. Det k´te element i den sorterede rækkefølge er løsning på problemet. Kompleksitet: afhænger af sorteringsmetode - med quicksort: O(N log N).
Comments