Sortieren
-
Sortieren eines Arrays:
- Voraussetzung: Datenmenge passt in den
Speicher
- Eingabearray mit n Elementen (z.B. Zahlen)
- soll in aufsteigender Reihenfolge sortiert
werden
- Grundvoraussetzung zum schnellen Suchen in
großen
-
Bubblesort:
- einfachstes Sortierverfahren
-
Grundprinzip:
- Durchlaufe mehrmals das Array
- vertausche jedesmal aufeinanderfolgende
Elemente, falls verkehrt herum
- so viele Durchgänge, bis keine Elemente mehr
vertauscht wurden
- Sortierroutine für double-Array
-
Quicksort:
- sehr schnelles Sortierverfahren
- basiert auf Zerlegung der Eingabedaten und
rekursiver Verarbeitung der Teile
- Sortierroutine für
double-Array
-
Grundverfahren des Quicksort:
- wähle ein beliebiges Element x aus ("mittleres
Element")
- sortiere alle Elemente kleiner als x nach oben,
alle größer als x nach unten
- verwende das Verfahren rekursiv zum Sortieren der
beiden Teile
- höre auf, wenn eine Teilliste ein oder kein
Element enthält
-
Verfeinerung des Aufteilens:
- setze Markierung high nach oben, low nach
unten
- wiederhole
schiebe high nach unten, bis ein großes Element
kommt
schiebe low nach oben, bis ein kleines Element
kommt
falls high nicht schon unter low:
vertausche die beiden Elemente
bei high und low
setze high eins runter und low
eins rauf
solange high nicht unter low
-
Beispiele:
-
Aufteilen:
-
ganzer Quicksort, jeweils "mittleres Element" markiert