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/2–n/2
Das Verfahren hat im Hinblick auf die Anzahl der nötigen Schlüsselvergleiche eine Laufzeit von O(n^2)
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^2) 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.
Insertion Sort
Das Verfahren
- Unterteilung des unsortierten Feldes in sortierten und unsortierten Bereich
- erstes Element a1 wird als sortiert angesehen
- Schlüsselelement wird festgelegt
- Verschiebung der sortierten Elemente, die größer als Schlüsselelement sind, um jeweils eine Stelle nach rechts
- Einfügen des Schlüsselelementes in entstandene Lücke
Pseudocode
for j=2 bis n
key = A[j] // füge A[j] in sortierten Teil A[1…j-1] ein i = j-1 while i > 0 and A[i] > key A[i+1] = A[i] i = i-1 A[i+1] = key
Laufzeitverhalten
Die Laufzeit von Insertion Sort ist von der Anzahl der Schleifendurchläufe und von der Anzahl der im Schleifenkörper befindlichen Basisoperationen abhängig. Im Allgemeinen ergibt sich die Laufzeit aus der Summe der Produkte von Kosten und Anzahl der ausgeführten Basisoperationen. Unter Kosten versteht man die chronometrische Arbeitszeit zur Ausführung von Basisoperationen oder Auswertung von Bedingungen im Schleifenkopf. Dies stellt sich im Allgemeinen folgendermaßen dar.
Pseudocode
T(n) = …
Weiterhin ergeben sich bei Insertion Sort, durch die verschieden Instanzen einer Problemklasse, unterschiedliche Laufzeiten.
Best case
• alle Elemente des Eingabearrays sind bereits sortiert • keine Operationen zur Schaffung einer Ordnung erforderlich
T(n) = … …. an+b linear = O(n)
Worst Case
• alle Elemente sind absteigend sortiert • Platz zum einfügen wird erst am Anfang des sortierten Teils gefunden • n * (n + 1)/2 Schritte
T(n)….
Average case
Die Entscheidung, wie die durchschnittliche Eingabe eines Problems aussieht, ist schwer. Für Insertion Sort nehmen wir daher an, dass die Hälfte der Elemente im Teilarray A[1…j-1] kleiner und die andere Hälfte der Elemente größer als das jeweilige Schlüsselelement A[j] sind. Für die Ermittlung der richtigen Einfügeposition im Teilarray A[1…j-1] ist daher von tj = j/2 auszugehen. Daraus ergibt sich eine Laufzeit von O=(n²).
Bei Insertion Sort handelt es sich um ein in-place-Verfahren. Es benötigt daher wenig zusätzlichen Speicher. Aufgrund einer durchschnittlichen Laufzeit von O(n²) ist es nur für kleine n geeignet.