View
102
Download
0
Category
Preview:
Citation preview
G.Heyer Algorithmen und Datenstrukturen1
5. Sortier-AlgorithmenVorbemerkungen:
Sortierproblem: Gegeben Folge von Datensätzen (items) s1, s2, ... sn
Jedes si besitzt Schlüssel ki (meist vom Typ integer).
Gesucht: Permutation , so daß k(1) k(2) ... k(n)
Interne Sortierverfahren: alle Datensätze im Hauptspeicher, sonst Nutzung des Externspeichers
Maße für die Laufzeit: Anzahl der Schlüsselvergleiche C (Comparisons) und Anzahl der Zuweisungen von Datensätzen M (Moves).C min, C max, C mit jeweilsM min, M max, M mit minimale, maximale, mittlere Anzahl
G.Heyer Algorithmen und Datenstrukturen2
Klassifizierung von SortiertechnikenSortieren durch
1. Auswählen
2. Einfügen
3. Austauschen
4. Mischen
5. Streuen und Sammeln
6. Fachverteilen
G.Heyer Algorithmen und Datenstrukturen3
Sortieren durch Auswahl
Methode: Finde zuerst das kleinste Element im Feld und tausche es gegen das an erster Stelle befindliche Element aus, finde danach das zweitkleinste Element und tausche es gegen das an zweiter Stelle befindliche Element aus und fahre in dieser Weise fort bis das gesamte Feld sortiert ist.
Für jedes i von 1,..., N-1 tauscht es a[i] gegen das kleinste Element in a[i] , ... , a[N] aus:
G.Heyer Algorithmen und Datenstrukturen4
selection ( int a [ ] , int N ){
int i, j, min, t ;
for ( i = 1 ; i < N ; i++ )
{
min = i;
for ( j = i+1; j <= N ; j++ )
if ( a [ j ] < a [ min ] ) min = j;
t = a [ min ] ; a [ min ] = a [ i ] ; a [ i ] = t;
}
}Analyse:Anzahl Schlüsselvergleiche: i = N(N-1) / 2 = (N2)Anzahl Bewegungen von Sätzen: 3(N-1)
G.Heyer Algorithmen und Datenstrukturen5
Insertion Sort (Sortieren durch (direktes ) Einfügen):(Beispiel: Einsortieren der Karten beim Kartenspiel)
Methode:
Betrachte die Elemente eines nach dem anderen und füge jedes an seinen richtigen Platz zwischen den bereits betrachteten ein (wobei diese sortiert bleiben).
Das gerade betrachtete Element wird eingefügt, indem die größeren Elemente einfach um eine Position nach rechts bewegt werden und das Element dann auf dem frei gewordenen Platz eingefügt wird.
Für jedes i von 2 bis N werden die Elemente a [1] ,..., a [i] sortiert, indem a [ i ] an die entsprechende Stelle in der sortierten Liste von Elementen in a[1] ,..., a[i-1] gesetzt wird.
G.Heyer Algorithmen und Datenstrukturen6
insertion (int a[ ] , int N ){
int i, j, v ;
for ( i = 2 ; i <= N ; i++ )
{
v = a [ i ] ; j = i;
while ( a [ j-1 ] > v )
{ a [ j ] = a [ j-1 ] ; j--; }
a [ j ] = v ;
}
}
/* Programm läuft nur, wenn j>1*/
G.Heyer Algorithmen und Datenstrukturen7
Sortieren von Dateien mit großen DatensätzenZiel: Jedes Sortierverfahren so einzurichten, dass es nur N Austauschoperationen von vollständigen Datensätzen ausführt, indem man den Algorithmus indirekt (unter Verwendung eines Feldes von Indizes) mit der Datei arbeiten und das Umordnen dann nachträglich vornehmen lässt.
Insbesondere, wenn das Feld a [ 1 ] , ... , a [ N ] aus umfangreichen Datensätzen besteht, zieht man es vor, mit einem „Indexfeld“ p [ 1 ] , ... , p [ N ] zu arbeiten, wobei ein Zugriff auf das Originalfeld nur für Vergleiche erfolgt.
In C ist es zweckmäßig, eine auf dem gleichen Prinzip beruhende Implementierung zu entwickeln, die ein Feld von Maschinenadressen (Zeigern) verwendet.
G.Heyer Algorithmen und Datenstrukturen8
Beispiel: Umordnen eines sortierten FeldesVor dem Sortierenk
a [k]
p [k]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A O R T I N G E PS MAX L E
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Nach dem Sortierenk
a [k]
p [k]
k
a [k]
p [k]
Nach dem Permutieren
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 11 9 15 8 6 14 12 7 3 13 4 2 5 10
A E E G I L M N SA RPO T X
A O R T I N G E PS MAX L E
G.Heyer Algorithmen und Datenstrukturen9
„Insertion sort“ unter Hinzufügung eines Indexfeldesinsertion ( int a [ ] , int p [ ], int N )
{
int i, j, v ;
for ( i = 0 ; i <= N ; i ++ ) p [ i ] = i ;
for ( i = 2 ; i <= N ; i ++ )
{
v = p [ i ]; j = i ;
while ( a [ p [j - 1]] > a [ v ])
{ p [ j ] = p [j - 1] ; j-- ; }
}
}
G.Heyer Algorithmen und Datenstrukturen10
Funktion zum Umordnen einer Dateiinsitu ( int a [ ], int [ p ], int N )
{
int i , j , k , t ;
for ( i = 1 ; i <= N ; i ++ )
if ( p [ i ] != i )
{
t = a [ i ] ; k = i;
do
{ j = k ; a [ j ] = a [p [j ] ] ;
k = p [ j ] ; p [ j ] = j ; }
while ( k != i ); a [ j ] = t;
}
}
G.Heyer Algorithmen und Datenstrukturen11
„Insertion sort“ unter Verwendung eines Feldes von Zeigerninsertion ( int a [ ], int *p [ ], int N)
{
int i, j, *v;
for (i = 0 ; i <= N ; i++ ) p [ i ] = & a [ i ] ;
for (i = 2 ; i <= N ; i++ )
{
v = p [ i ]; j = i ;
while ( *p[ j -1 ] > *v )
{ p [ j ] = p [ j - 1 ] ; j -- ; }
p [ j ] = v ;
}
}
G.Heyer Algorithmen und Datenstrukturen12
Cmin(N) = N-1 Cmax(N) = i=2..N i = (N2)Mmin(N) = 2(N-1) Mmax(N) = i=2..N i+1 = (N2)
Für die Abschätzung der Werte C mit und M mit kann man davon ausgehen, daß im Mittel die Hälfte der maximalen Vergleiche/Bewegungen ausgeführt werden müssen. Auch hier erhält man also (N2).
Analyse
G.Heyer Algorithmen und Datenstrukturen13
Bubblesort
Methode:Jeweils 2 benachbarte Schlüssel werden verglichen.Ist a[i].key > a[i+1].key, so werden items vertauscht.
Größtes Element steigt in jedem Durchgang ans Ende (wie Blase, engl. bubble, nach oben).
Terminierung wenn keine Vertauschung mehr erfolgt ist, oder spätestens nach N-1 Durchläufen.
G.Heyer Algorithmen und Datenstrukturen14
bubblesort
bubble (int a[], int N)
{
int i, j, t;
for ( i = N ; i >= 1 ; i--)
for (j = 2; j <= i; j++ )
if ( a [j-1] > a [j] )
( t = a [j-1] ; a [j-1] = a [j] ; a [j] = t; )
}
G.Heyer Algorithmen und Datenstrukturen15
Analyse:
Cmin(N) = N-1Cmax(N) = (N-1) + (N-2) + ... + 1 = N*(N-1) / 2 = (N2)Mmin(N) = 0Mmax(N) = 3 * Cmax(N) = (N2)
Dieselbe Abschätzung erhält man für die mittlere Laufzeit.
Bubblesort asymmetrisch: gut, wenn viele Elemente in der richtigen Reihenfolge sind, schlecht sonst.
G.Heyer Algorithmen und Datenstrukturen16
Leistungsparameter der Sortierverfahren (Durchschnitt)Algorithmus Vergleiche Bewegungen
Selection Sort N2 /2 N
Insertion Sort N2 /4 N2 /8
Bubble Sort N2 /2 N2 /2
G.Heyer Algorithmen und Datenstrukturen17
Quicksort erfahrungsgemäß eine der schnellsten Methoden
Divide and Conquer-Verfahren:
• Zerlege die Folge F= a[1],...,a[n] in zwei Folgen F1 und F2, so daß gilt:
Für jeden Schlüsselwert ki1 der Folge F1 und jeden Schlüsselwert ki2 der Folge F2 gilt die Beziehung ki1 < ki2 ,
d. h. jedes Element der ersten Teilfolge ist kleiner als jedes Element der zweiten Teilfolge.
• Führe diese Zerlegung wiederum für beide Folgen F1 und F2
durch, usw.• Das Verfahren bricht für eine Teilfolge ab, wenn diese einelementig ist.Nach dem Abbruch des Verfahrens ist dann die gesamte Folge sortiert. Wir beschreiben den Vorgang des Zerlegens und Zusammensetzens etwas genauer:
G.Heyer Algorithmen und Datenstrukturen18
Zerlegung:(i) Wähle ein Element x aus der Folge a[1],...,a[n], etwa x:=A[1];(ii) Durchsuche die Folge von links, bis ein Element a[i] mit
x < a[i] gefunden wurde.(iii) Durchsuche die Folge von rechts, bis ein Element a[j] mit
a[j] < x gefunden wurde.(iv) Vertausche beide Elemente(v) Wiederhole (ii), (iii) und (iv) so lange, bis i >= j gilt.
Anschließend wird das Element x = a[1] mit a[j] vertauscht und es gilt für die neue Folge a[1],...,a[j-1], x, a[j+1],...,a[n]:
a[i1] < x < a[i2], für alle i1 {1,...,j-1}, i2 {j+1,...,n}
Daraufhin wird der gesamte Prozeß für die Teilfolgen a[1],...,a[j-1] und a[j+1],..., a[n] durchgeführt, und es ist kein Zusammensetzen der Ergebnisse mehr erforderlich.
G.Heyer Algorithmen und Datenstrukturen19
Beispiel zu Quicksort:Wir betrachten die Folge
44 55 12 42 94 6 18 67
ji
und sortieren sie bezüglich der Ordnung <= . Zuerst haben wir das Vergleichselement x = a[1] = 44 gewählt. Mit der Variablen i sind wir von links so weit gelaufen, bis wir auf ein Element gestoßen sind, das größer ist als 44. Das gleiche geschah von rechts mit der Variablen j, bis ein Element gefunden wurde, das kleiner ist als x, a[i] und a[j] werden nun vertauscht und wir erhalten:
i j
1844 12 42 94 556 67
G.Heyer Algorithmen und Datenstrukturen20
Mit i sind wir anschließend auf das Element a[5] = 94 und mitj auf a[6] = 6 gestoßen. Wiederum werden beide vertauscht:
44 18 12 42 6 675594
ij
Nachdem wir mit Hilfe von i und j die Folge weiter durchsucht haben, gilt jetzt i >= j, und damit ist das Abbruchkriterium der Zerlegung erreicht. Jetzt werden a[1] und a[j] vertauscht, und wir erhalten:
4212186 679444 55
Jetzt gilt: Alle Elemente der linken Teilfolge sind kleiner oder gleich x, und jedes Element der rechten Teilfolge ist größer oder x. Das Verfahren wird nun auf beide Teilfolgen angewendet:
6 18 12 42 5594 67und
G.Heyer Algorithmen und Datenstrukturen21
C-Programm zu Quicksortquicksort ( int a [ ] , int l , int r )
/* ausgewähltes Element steht rechts */ {
int v, i, j, t ; if ( r > l)
{ v = a [ r ] ; i = l - 1; j = r ; for ( ; ; )
{while ( a [ i++] < v) ;while ( a [ --j] > v );if ( i >= j ) break;t = a[i] ; a[i] = a[j] ; a[j] = t;}
t = a [ i ] ; a [ i ] = a [ r ]; a [ r ] = t; quicksort ( a , l , i -1 ) ; quicksort ( a , i+1 , r ) ; }
}
G.Heyer Algorithmen und Datenstrukturen22
Analyse:
worst case: sowohl Vergleiche wie Bewegungen quadratisch. Schlechtester Fall tritt ein, wenn Array bereits sortiert.
(N + 1) + (N) + ( N - 1) + ... + 3 Vergleiche
best case: Folgen werden in gleichlange Teilfolgen aufgeteilt, Aufrufbaum hat Tiefe log N, auf jeder Ebene maximal N Vergleiche, damit Laufzeit (N log N).
Mittlere Laufzeit fast so gut wie beste Laufzeit!!
Annahmen: Schlüssel 1, ..., N, alle Permutationen gleich wahrscheinlich
Average case Komplexität: O(N log N)
Recommended