Elementare Sortierverfahren machen keine Annahmen bei der Datenstruktur. |
Sie haben daher eine hohe Komplexität, nämlich O(N²) |
|
Verfahren: Selection Sort, Insertion Sort, Shell Sort, Bubble Sort |
|
|
Spezielle Sortierverfahren nutzen bestimmte Eigenschaften von Datenstrukturen aus |
und erreichen dadurch geringere Komplexität, z.B. O(N * log(N)) |
|
Verfahren: Quick Sort, Heap Sort, Merge Sort, Radix Sort |
|
|
Die Laufzeitkomplexität messen wir durch |
die Anzahl C von Schlüsselvergleichen (Comparisons) und |
die Anzahl M von Item-Bewegungen (Movements) |
|
Sortverfahren heißen stabil, wenn sie die Reihenfolge von Items mit gleichem Schlüssel nicht
verändern. |
Wenn z.B. eine Notenliste zunächst nach Alphabet und dann nach Note sortiert wird, soll anschließend
Namen mit gleicher |
Note trotzdem noch alphabetisch geordnet sein (= stabil)- |