Elementære metoder til sortering
- sortering ved indsættelse
- Shellsort
Sorteringsmetoder baseret på rekursion
quicksort
flettesortering
Randomisering
Hvorfor sortere?
(1) Det er lettere at søge i en en sorteret datamængde end i en usorteret datamængde, såvel for maskiner som for mennesker. Tænk f.eks. på opslag i en telefonbog.
(2) Mange problemer kan løses mere effektivt, hvis inddata er sorteret. Eksempel: Hvis to filer er sorteret i samme orden, er det muligt i blot ét gennemløb at finde alle de poster, der findes i begge filer.
Uformel definition: Ved sortering forstås en proces, hvorved elementerne i en datamængde ordnes i rangfølge.
Bestemmelse af fællesmængden for to usorterede arrays
k = 0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
if (a[i] == b[j])
c[k++] = a[i];
Kompleksitet: O(M * N) i a: M 0 j b: 0 N k c: 0
Bestemmelse af fællesmængden for to sorterede arrays
i = j = k = 0;
while (i < M && j < N)
if (a[i] < b[j]) i++;
else if (a[i] > b[j]) j++;
else { c[k++] = a[i]; i++; j++; }
Kompleksitet: O(M + N) i a: M 0 < j b: 0 N < k c: 0 <
Permutationer
En permutation af en mængde af objekter er en ordning af objekterne.
For eksempel er p = (2 3 1) en permutation af {1, 2, 3}. p(1) = 2 p(2) = 3 p(3) = 1
Der er 6 permutationer af {1, 2, 3}, nemlig (1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)
Antallet af permutationer af n objekter er n!.
Lad der desuden være defineret en ordningsrelation ‘<’ på mængden af nøgleværdier, som er total, dvs. for vilkårlige tre nøgleværdier a, b og c opfylder følgende to betingelser:
(1) Præcis et af følgende 3 udsagn er sandt: a < b, a = b eller b < a (3-delelighed)
(2) Hvis a < b og b < c, så a < c (transitivitet)
En sortering af en fil af n poster er en permutation, p, af mængden {1, 2, ..., n}, som ordner nøglerne i stigende rækkefølge: Kp(1) ≤ K p(2) ≤ ... ≤ Kp(N). Lad der være givet N emner R1, R2, ..., RN, der skal sorteres. Vi kalder dem poster, og hele samlingen kaldes for en fil. Hver post Ri indeholder en nøgle, Ki, til styring af sorteringen. Herudover kan en post indeholde anden information.
Terminologi
En sortering af en fil i det indre lager (f.eks. et array), kaldes for intern sortering.
En sortering af en fil på et eksternt lagermedium (f.eks. en disk) kaldes for ekstern sortering.
Elementære algoritmer
Sortering ved indsættelse Shellsort
Hvorfor studere elementære algoritmer?
(1) De er lette at kode
(2) De er (tilstrækkeligt) hurtige for små filer
(3) I specielle situationer er de hurtigst
(4) Udgør illustrative eksempler på algoritmedesign og -analyse
Sortering ved indsættelse
Løsning (ved induktion):
Basistilfælde: Vi ved, hvordan 1 element sorteres.
Induktionshypotese: Vi ved, hvordan n-1 elementer sorteres.
Vi kan opnå en sortering af n elementer ved (1) at sortere de første n-1 elementer, (2) indsætte det n´te element korrekt blandt disse. Problem: Givet et array a med elementerne a[0], a[1], ..., a[n-1]. Sorter elementerne i stigende orden.
A S O R T I N G E X A M P L E
A S O R T I N G E X A M P L E
A O S R T I N G E X A M P L E
A O R S T I N G E X A M P L E
A O R S T I N G E X A M P L E
A I O R S T N G E X A M P L E
A I N O R S T G E X A M P L E
A G I N O R S T E X A M P L E
A E G I N O R S T X A M P L E
A E G I N O R S T X A M P L E
A A E G I N O R S T X M P L E
A A E G I M N O R S T X P L E
A A E G I M N O P R S T X L E
A A E G I L M N O P R S T X E
A A E E G I L M N O P R S T X
void insertionSort(Comparable[] a, int i) {
if (i > 0) {
insertionSort(a, i - 1);
for (int j = i;
j > 0 && a[j].compareTo(a[j - 1]) < 0; j--)
swap(a, j, j - 1);
}
} Sortering ved indsættelse (rekursiv udgave) void swap(Object[] a, int i, int j) {
Object tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
void insertionSort(Comparable[] a) {
for (int i = 1; i < a.length; i++)
for (int j = i;
j > 0 && a[j].compareTo(a[j - 1]) < 0; j--)
swap(a, j, j - 1);
} Sortering ved indsættelse (iterativ udgave)
void insertionSort(Comparable[] a, int i) {
for (int i = 1; i < a.length; i++){
Comparable tmp = a[i];
int j = i;
for ( ; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
} Sortering ved indsættelse (iterativ udgave med flytninger) tmp: i a: 0 j-1 j
Animering af sortering ved indsættelse
Analyse af sortering ved indsættelse
Tidsforbruget er lineært for “næsten sorterede” filer.
Antal sammenligninger:
Bedste tilfælde: n-1
Værste tilfælde: 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n2)
Gennemsnitlige tilfælde: n(n-1)/4 = O(n2)
Antal flytninger:
Bedste tilfælde: 0
Værste tilfælde: 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n2)
Gennemsnitlige tilfælde: n(n-1)/8 = O(n2)
Shellsort (D. L. Shell, 1959)
Ide: Sortering ved indsættelse er meget effektiv, når filen er “næsten sorteret”. Men for “meget usorterede” filer er den langsom, da den kun tillader ombytning af naboelementer.
Spørgsmål: Kan vi sørge for at ombytte elementer, der ligger langt fra hinanden i starten, for så derefter at foretage en sædvanlig sortering ved indsættelse?
Svar: Ja, vi kan sortere de delfiler, der fås ved at tage hvert h´te element i den oprindelige fil, hvor h > 1.
4-sortering
1. Opdel filen i 4 delfiler: hvert 4. element startende i det første, hvert 4. element startende i det andet, hvert 4. element startende i det tredje, hvert 4. element startende i det fjerde,
2. Sorter hver af disse.
Filen siges da at være 4-sorteret.
På tilsvarende måde kan vi definere en h-sortering.
Bemærkning: En fil, der er 1-sorteret, er sorteret.
4-sortering ved indsættelse
Benyt sortering ved indsættelse med “skridtlængde” 4. A S O R T I N G E X A M P L E
A S O R T I N G E X A M P L E
A I O R T S N G E X A M P L E
A I N R T S O G E X A M P L E
A I N G T S O R E X A M P L E
A I N G E S O R T X A M P L E
A I N G E S O R T X A M P L E
A I A G E S N R T X O M P L E
A I A G E S N M T X O R P L E
A I A G E S N M P X O R T L E
A I A G E L N M P S O R T X E
A I A G E L E M P S N R T X O
h-sortering
void h_sort(Comparable[] a, int h) {
for (int i = h; i < a.length; i++) {
Comparable tmp = a[i];
int j = i;
for ( ; j >= h && tmp.compareTo(a[j - h]) < 0; j -= h)
a[j] = a[j - h];
a[j] = tmp;
}
}
I forhold til insertionSort er 1 blot erstattet med h.
Comments