DVG1 - 12 - Sortierverfahren Sortierverfahren Vortrag: Ingo Gensch, Mathias Reich am: 11.12.2000

DVG1 - 12 - Sortierverfahren

Sortierverfahren

Vortrag: Ingo Gensch, Mathias Reicham: 11.12.2000


Was sind Sortieralgorithmen Das Sortieren ist ein Verfahren zum Herstellen einer definierten

(geordneten) Sequenz von Objekten entsprechend einer Ordnung bzw. der Vorgang des Anordnens von Objekten zu einer definierten Sequenz entsprechend einer Ordnung

Zielsetzung: Vereinfachung des Findens von Objekten mit Hilfe einfacher

Suchverfahren


Wo braucht man Sortierverfahren? wenn große Datenmengen vorhanden sind und sortiert werden

sollen Wenn zu einer bereits bestehenden, sortierten Datenmenge

neue Elemente hinzugefügt werden müssen

Sortierte Datenbestände sind z.B.: Telefonbuch Register Kataloge usw.


Was sortieren wir? Elektronische Daten

Zahlen Zeichenketten Adressen Datenbänke usw.


Was sind gute Algorithmen?

Oder gibt es einen besten Sortieralgorithmus für alle Datensätze? Die Effektivität der Sortieralgorithmen ist abhängig von der Art

der bestehenden Daten vorsortierte Daten? Steht die Menge der zu sortierenden Daten im Verhältnis zum

Programmierumfang? Geschwindigkeit der Sortierung der Daten wichtig?


Geschwindigkeit der Sortierung Abhängig vom Sortierverfahren Abhängig von der Anzahl der arithmetischen Funktionen Das theoretisch schnellste Sortierverfahren:

Jeder Wert der Datenmenge muss mit jedem anderen Wert der Datenmenge verglichen werden

d.h. wenn n die Anzahl der Werte ist, dann hat das effizienteste Sortierprogramm genau n*(n-1) Vergleiche und maximal n Vertauschungen


Computer und Sortieren Sortieralgorithmen haben sich parallel zur Entwicklung der

Computer weiterentwickelt

Früher: Computer waren zu langsam, Technik noch nicht ausgereift. => Hauptaugenmerk auf neue/bessere Algorithmen

Gegenwart: Prozessorentwicklung boomt => Weniger Interesse an guten Algorithmen, da Prozessoren immer schneller werden

Zukunft: Maximale (physikal.) Prozessorgeschwindigkeit? => wieder bessere Algorithmen?


Prinzipien des Sortierens Vorsortierte Menge neuer Datensatz

Sortierprinzip: Vergleich und sofortiger Austausch (z.B. BubbleSort)

?


Sortierprinzip: Vergleich solange bis der neue Datensatz an der richtigen Stelle ist und dann wird erst der neue Datensatz eingefügt (z.B. InsertSort)

?


Arten von SortieralgorithmenEinfache

SortierverfahrenMittlere

SortierverfahrenHöhere

Sortierverfahren

RandomSort (zufälliges Verändern der Reihenfolge bis es stimmt)

InsertSort (Sortieren durch Einfügen)

QuickSort (Sortieren durch Zerlegen)

PermSort (Sortieren durch Permutation)

MergeSort (Sortieren durch Mischen)

BubbleSort (Sortieren durch Austauschen)

HeapSort (Sortieren im Baum)


BubbleSort


Bubblesort (Theorie) Es gibt eine unsortierte Datenmenge der Größe n Man vergleicht das erste Feld mit dem Zweiten

wenn erstes Feld größer ist als das Zweite, dann Vertauschung der beiden Feldern

Man vergleicht die nächsten beiden Felder analog Wenn die letzten beiden Felder verglichen sind, Wiederholung

mit der Feldgröße (n-1) Wenn keine Vertauschungen dabei stattgefunden haben, ist die

Menge sortiert

Anzahl der maximalen Vergleiche und Vertauschungen: (n*(n-1))/2 + (n*(n-1))/2 = n^2-n


Quelltext von BubbleSort

for (int i = a.length-1; i>0;i--) { boolean getauscht = false; for (int j = 0; j<i; j++) {

if (a[j] > a[j+1]) {int h = a[j];a[j] = a[j+1];a[j+1] = h;getauscht = true;

} } if (!getauscht) return;}


InsertSort


InsertSort (Theorie) Vergleich der ersten beiden Werte kleinerer Wert wird sich gemerkt Der Wert wird mit dem Nächsten verglichen Am Ende der Datenmenge wird der gemerkte (kleinste) Wert an

die erste Stelle geschrieben Wiederholung mit der Feldgröße (n-1)

Anzahl der Vergleiche und Vertauschungen : (n*(n-1))/2 + n = (n^2+n)/2


Quelltext von InsertSort

int min_index; int anz = a.length-1; int minimum;for(int i=0;i<anz;i++) {

min_index = i;for(int j=min_index+1;j<anz; j++); {

if (a[j]<a[min_index]) min_index=j;}if min_index>i {

minimum=a[min_index];for (int j=min_index; j>i; j--) a[j]=a[j-1];a[i]=minimum;

}}


QuickSort


Quicksort (Theorie) Prinzip: „Teile und herrsche!“ Aufteilung der Datenmenge in zwei beliebig große Blöcke

kleinere Werte auf eine Seite, größere auf die andere Seite vorsortieren

Jeden einzelnen Unterblock wiederum unterteilen Wenn Blockgröße auf 1 geschrumpft ist, ist die Menge sortiert

Anzahl der Vergleiche und Vertauschungen

Abhängig von den Werten : ca. n*log(n)


Struktogramm von QuickSort (rekursive Programmierung) Siehe Blatt

Documents

DVG1 - 12 - Sortierverfahren Sortierverfahren Vortrag: Ingo Gensch, Mathias Reich am: 11.12.2000