Kapitel 7. Sortier-Algorithmen
Klassifizierung von Sortiertechniken
Sortieren durch Auswahl (Selection Sort)
Funktion Selection_Sort
Insertion Sort (Sortieren durch (direktes ) Einfügen):
Funktion Insertion_Sort
Sortieren von Dateien mit großen Datensätzen
Beispiel: Umordnen eines sortierten Feldes
„Insertion sort“ unter Hinzufügung eines Indexfeldes
Funktion zum Umordnen einer Datei
„Insertion sort“ unter Verwendung eines Feldes von Zeigern
PPT-Folie
Bubblesort
Funktion bubblesort
Analyse:
Quicksort
Zerlegung:
Beispiel zu Quicksort:
Mit i sind wir anschließend auf das Element a[5] = 94 und mit j auf a[6] = 6 gestoßen. Wiederum werden beide vertauscht:
C-Programm zu Quicksort
Analyse Quicksort
Shellsort
Beispiel: Inkremente 4,2,1
Normalverfahren:
Heapsort
Beispiel:
Versickere
Mergesort
Funktion mergesort
Komplexität:
Natürliches 2-Wege-Mergesort
Anmerkung: wie läßt sich Grad der Vorsortierung einer Folge F = k1,...,kn von Schlüsseln messen?
Beispiele:
Zusammenfassung Sortierverfahren
E-Mail: der@informatik.uni-leipzig.de
Homepage: http://www.informatik.uni-leipzig.de/~der