Sortieren und Suchen SS12
Inhaltsverzeichnis
|
Ordnungskriterium
Das Ordnungskriterium in einer Datensammlung bezieht sich nur auf wenige Elemente eines Datensatzes. Dies kann im Beispiel eines Telefonbuches eine lexikographische Anordnung der Namen sein. Die Suche in der Datensammlung orientiert sich an dem Ordnungskriterium, welches auch „Schlüssel“ genannt wird.
Datensatz hat den Aufbau: Schlüssel, Inhalt
Sortieren von Zahlen
Eine Eingabefolge von n Zahlen (a1; …. an) wird durch Umordnung in eine Ausgabefolge umgewandelt, für die gilt (a1 < a2 ….< an).
Einteilung von Sortierverfahren und Begriffsklärungen
- in-place-Sortierverfahren
- Sortierung erfolgt innerhalb des Eingabefeldes
- out-of-place-Sortierverfahren
- Sortierung erfolgt außerhalb des Eingabefeldes
- Interne Sortierverfahren
- Zu sortierende Elemente befinden sich im Hauptspeicher
- Externe Sortierverfahren
- Zu sortierende Elemente befinden sich auf der externem Speichermedium
- stabile Sortierverfahren
- Reihenfolge identischer Elemente bleibt nach Sortierung erhalten
- instabile Sortierverfahren
- Reihenfolge der Datensätze mit gleichem Sortierschlüssel bleibt nicht erhalten
Effizienz
- geringer Speicherplatzverbrauch
- geringe Laufzeit
Bei der Ermittlung einer aussagekräftigen Laufzeit treten folgende Probleme auf:
- Eigenschaften der Maschine auf der Algorithmus ausgeführt wird
- Qualität der Implementierung des Algorithmus
- Instanz der Problemklasse
- Größe der Eingabe
Die exakte chronometrische Arbeitszeit eines Algorithmus ist uninteressant. Es braucht eine Angabe, die weitgehend unabhängig von speziellen Ausprägungen der vorangegangenen Einflüsse ist.
Fallunterscheidungen
Um den Einfluss der Instanz der Problemklasse in eine praxistaugliche Aussage über die Laufzeit münden zu lassen, ist es erforderlich Fallunterscheidungen vorzunehmen.
Best case
Das Problem tritt in seiner geringsten Ausprägung auf und fordert die kürzeste Laufzeit und den wenigsten Speicherplatz.
Worst case
Das Problem tritt in seiner größten Ausprägung auf und fordert die längste Laufzeit und den meisten Speicherplatz.
Average case
Der durchschnittliche Fall ist schwer zu definieren.
Welcher Fall liefert eine praxistaugliche Aussage? Der best case scheidet aus. Die Aussage, dass die Laufzeit eines Algorithmus nicht besser als eine bestimmte Größe sein wird, ist von geringem Interesse. Der average case und der worst case sind aussagekräftiger und maßgeblicher für die Entscheidung über die Verwendung eines Algorithmus. Der worst case ist eine Garantie dafür, dass egal welche Instanz eines Problems auch immer auftreten mag, die Laufzeit niemals schlechter wird als im worst case. Er ist die obere Schranke für die Laufzeit. In Abhängigkeit mit welcher Häufigkeit der worst case in der Praxis auftritt, ist der average case von größerer Bedeutung. So hat Quicksort im ungünstigsten Fall eine Laufzeit von O(n²), findet aber durch sein günstiges Laufzeitverhalten im mittleren Fall häufig Anwendung.
Selection Sort (Auswahlsortieren)
Selection Sort ist ein instabiles in-place-Sortierverfahren. Die zu sortierenden Elemente werden in einen sortierten und einen unsortierten Bereich aufgeteilt.
Das Verfahren
- Ermittlung des kleinsten Elementes des unsortierten Feldes
- Tausch mit dem ersten Element des Feldes
- mit zweitem Element und Rest des unsortierten Teilfeldes ebenso verfahren
Laufzeitverhalten
Bei einigen Sortierverfahren ist die Anzahl der notwendigen Sortierschritte abhängig von einem Schlüsselelement, welches als Vergleichswert dient. Anhand des Schlüssels wird mittels Vergleichsoperatoren (<; >; oder =) die Position jedes Elementes im sortierten Feld bestimmt. Die Anzahl der Schritte bis zum sortierten Ergebnis, hängt bei Selection Sort nicht von der Auswahl eines Sortierschlüssels ab, sondern ist abhängig von der Elementanzahl. Somit existiert kein worst case oder best case. Zur Analyse des Laufzeitverhaltens genügt daher eine Grobanalyse.
- (n – 1) Schlüsselvergleiche im ersten Durchlauf
- (n – 2) Vergleiche im zweiten Durchlauf…..
T(n) = (n – 1) + (n – 2) + ….+ 2 + 1 T(n) = n * (n – 1) / 2 T(n) = n²/2 – n/2
Das Verfahren hat im Hinblick auf die Anzahl der nötigen Schlüsselvergleiche eine Laufzeit von O(n²)
Die Elemente sind (n – 1) mal zu vertauschen bis das Array sortiert vorliegt. Daraus ergibt sich eine Ordnung von n.
Begründet durch die asymptotische Laufzeitkomplexität von O(n²) ist Selection Sort ein für große n ungünstiges Sortierverfahren.
Da es sich bei Selection Sort um ein in-place Verfahren handelt, wird nur für das unmittelbare Vertauschen von zwei Elementen zusätzlicher Speicherplatz benötigt. Soll beispielsweise das Element X und das Element Y vertauscht werden, bedarf es eines zusätzlichen Speicherplatzes Z, der den Wert von X aufnimmt. Nun kann der Wert von Y auf X geschrieben werden und im Anschluss Z auf Y.