Terminologi
Elementære metoder til sortering
- sortering ved udvælgelse
- sortering ved indsættelse
- Shellsort
- sortering ved tælling
- sortering ved adresseberegning
Hvorfor sortere?
(1) Det er lettere at søge i en en sorteret data-mæ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
i a: j b: k c: M 1 1 N 1 k = 0;
for (i = 1; i <= M; i++)
for (j = 1; j <= N; j++)
if (a[i] == b[j])
c[++k] = a[i];
Kompleksitet: O(M*N)
Bestemmelse af fællesmængden for to sorterede arrays
k = 0; i = j = 1;
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++; }
i a: j b: k c: M 1 1 N 1 < < < Kompleksitet: O(M + N)
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 (associativitet)
En sortering af en fil af poster er en permutation, p(1), p(2), ..., p(N), som ordner nøglerne i stigende rækkefølge, dvs. 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 lager-medium kaldes for ekstern sortering. [behandles ikke]
Elementære algoritmer
Sortering ved udvælgelse Sortering ved indsættelse Boble-sortering Shellsort Sortering ved tælling Sortering ved adresseberegning
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å algoritme-design og analyse
Sortering ved udvælgelse
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 udvælge det “minimale” element, (2) sætte det først blandt elementerne, og (3) sortere de sidste n-1 elementer. Problem: Givet et array a med elementerne a[1], a[2], ..., a[n]. 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 A O R T I N G E X S M P L E
A A E R T I N G O X S M P L E
A A E E T I N G O X S M P L R
A A E E G I N T O X S M P L R
A A E E G I N T O X S M P L R
A A E E G I L T O X S M P N R
A A E E G I L M O X S T P N R
A A E E G I L M N X S T P O R
A A E E G I L M N O S T P X R
A A E E G I L M N O P T S X R
A A E E G I L M N O P R S X T
A A E E G I L M N O P R S X T
A A E E G I L M N O P R S T X
A A E E G I L M N O P R S T X
Animering af sortering ved udvælgelse
void selection(int a[], int i, int n) {
if (i < n) {
int min = i;
for (int j = i+1; j <= n; j++)
if (a[j] < a[min])
min = j;
swap(a, min, i);
selection(a, i+1, n);
}
}
Sortering ved udvælgelse (rekursiv udgave) Metoden swap benyttes til at ombytte elementerne i arrayet:
void swap(int a[], int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
Sortering ved udvælgelse (iterativ udgave)
void selection(int a[], int n) {
for (int i = 1; i < n; i++) {
int min = i;
for (int j = i+1; j <= n; j++)
if (a[j] < a[min])
min = j;
swap(a, min, i);
}
}
Analyse af sortering ved udvælgelse
Sortering ved udvælgelse har et tidsforbrug, der stort set ikke afhænger af rækkefølgen i input.
Sortering ved udvælgelse er lineær for store poster og små nøgler. Antal sammenligninger:
Bedste tilfælde: (n-1) + ... + 2 + 1 = n(n-1)/2 = O(n2)
Værste tilfælde: (n-1) + ... + 2 + 1 = n(n-1)/2 = O(n2)
Gennemsnitlige tilfælde: n(n-1)/2 = O(n2)
Antal ombytninger:
Bedste tilfælde: n-1 (0, hvis ombytninger uden effekt udelades (min == i))
Værste tilfælde: n-1
Gennemsnitlige tilfælde: n-1
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[1], a[2], ..., a[n]. 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
Animering af sortering ved indsættelse
void insertion(int a[], int i) {
if (i > 1) {
insertion(a, i-1);
int v = a[i];
int j = i;
while (j > 1 && a[j-1] > v)
{ a[j] = a[j-1]; j--; }
a[j] = v;
}
} Sortering ved indsættelse (rekursiv udgave) i a: 1 j-1 j v:
Sortering ved indsættelse (iterativ udgave)
Løkketesten i den indre løkke kan forsimples til
while (a[j-1] > v)
hvis a[0] < a[1:n].
void insertionSort(int a[], int n) {
for (int i = 2; i <= n; i++) {
int v = a[i];
int j = i;
while (j > 1 && a[j-1] > v)
{ a[j] = a[j-1]; j--; }
a[j] = v;
}
}
Comments