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 mit Analyse
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
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.
Mergesort (sortieren durch zusammenführen)
Divide and Conquer
Ist ein Problem zu groß, um es direkt lösen zu können, zerlege es in beherrschbare Instanzen des selben Problems und löse diese. Die Teillösungen werden abschließend zur Gesamtlösung zusammengefügt. Das ist das Prinzip von „Teile und Herrsche“. Mergesort arbeitet nicht in-place und ist ein stabiles Verfahren. Es eignet sich besonders zum sortieren von Daten auf Sekundärspeichern (externes Sortieren).
Das Verfahren
• Teilung der Folge A in zwei Teilfolgen A1 und A2 jeweils der Länge n/2 • rekursive Zerlegung des Eingabefeldes in Teilfelder, bis Wert in jedem Feld atomar vorliegt (die Länge 1 hat) • Zusammenführung der Teilfelder bei gleichzeitiger Sortierung • Zusammenführung der sortierten Teilfelder im Reißverschlussverfahren zum Gesamtergebnis
Pseudocode
Instert Pseudocode Here !
Laufzeitverhalten
Mergesort hat einen höheren Speicherplatzbedarf als beispielsweise Selection Sort. Dies ist durch die Verwendung von Hilfs-Arrays bedingt, welche für die Teilung des Eingabearrays erforderlich sind.
Ist T(n) die Zeit zur Lösung eines Problems und n die Eingabegröße, so kann das Problem für den Elementarfall (Eingabe besteht nur aus einem Element) n <= c für eine Konstante c in konstanter Zeit gelöst werden. Es ergibt sich daraus eine Laufzeit von O=(1). In diesem Fall gehen wir davon aus, dass die Aufteilung des Eingabearrays zu a Teilproblemen mit der Länge 1/b führt. Ist D(n) die Zeit um das Problem zu zerlegen und C(n) die Zeit um die Teilprobleme zur Gesamtlösung zu vereinigen, ergibt sich die folgende Rekursionsgleichung.
T(n) = {O(1)für n <= c}
- {aT(n/b) + D(n) + C(n)}sonst}
Abbildung::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Der Aufwand zur Aufteilung des Eingabearrays ist immer gleich und nicht von der Eingabegröße abhängig, somit ist D(n) = O(1). Ist der gesamte Zeitaufwand zur Herstellung einer Ordnung in der gesamten Eingabe gleich T(n), dann beträgt er für zwei Teilfolgen der Länge n/2 der Eingabe gleich 2T(n/2). Diesen Beitrag leistet die Sortierung der Teilfolgen zur gesamten Laufzeit. Das Zusammenführen der sortierten Teilfolgen zur Gesamtlösung hat einen zeitlichen Aufwand, der in Abhängigkeit von der Eingabegröße steht. Er trägt für C(n) = O(n) zur gesamten Laufzeit bei. Addiert man die einzelnen Beiträge zusammen, so ergibt sich für den schlechtesten Fall die folgende Rekursionsgleichung.
T(n) = {O(1) für n = 1} {2T(n/2) + O(n)} für n > 1}
Zur Beantwortung der Frage nach der Laufzeit für den schlechtesten Fall, ziehen wir das Mastertheorem heran. Diese Methode unterscheidet drei Fälle zur Bestimmung der Laufzeit, beim Vorliegen von Rekursionsgleichungen. Sie muss der folgenden Form entsprechen.
T(n) = aT(n/b) + f(n)
f(n) ergibt sich aus der Summe von D(n) und C(n). Bei Merge Sort findet der zweite Fall des Mastertheorems Anwendung, da sich für f(n) = n log b a aus f(n) = n log 2 2 gleich f(n) = O(n) ergibt. Die Laufzeit ergibt sich somit aus T(n) = n log 2 2 lg n und ist von der Ordnung n lg n.
Quicksort
Quicksort ist ein auf das divide and conquer Prinzip basierendes Sortierverfahren, unterscheidet sich aber bezüglich seiner Arbeitsweise von Mergesort. Es arbeitet in-place und benötigt nur zum Vertauschen zweier Elemente zusätzlichen Speicherplatz.
Das Verfahren
- beliebiges Pivot-Element X (Schlüssel) aus unsortiertem Array wählen
- durchsuchen des Array, beginnend von links, nach Element größer X
- durchsuchen des Array, beginnend von rechts, nach Element kleiner X
- vertauschen der beiden Elemente
- fortfahren bis man sich aus beiden Richtungen trifft
- Array ist nun in Elemente kleiner X und größer X zerlegt
- X befindet sich an richtiger Position
- rekursive Anwendung des Verfahrens auf alle entstehenden Teilarrays
Ein Zusammenführen der Teilarrays nach dem letzten Durchlauf ist nicht erforderlich, da nur im Eingabearray gearbeitet wurde und das Gesamtarray bereits im sortierten Endzustand vorliegt.
Laufzeitverhalten
Die Laufzeit von Quicksort hängt unter anderem von der Auswahl des Pivot-Elementes ab. Quicksort arbeitet besonders effizient, wenn Teilarrays gleicher Größe entstehen.
Best case
In diesem Fall wird das Pivot - Element bei jedem Durchlauf zufällig so gewählt, dass jeweils ein Teilarray der Größe n/2 und eines der Größe n/2 - 1 durch den rekursiven Aufruf übergeben wird, sofern die Größe des Eingabearrays eine Zweierpotenz ist. Das Ergebnis eines jeden Zerlegeprozesses ist, dass sich jeweils das gewählte Schlüsselelement an der richtigen Position im Array befindet. Da dies für jedes Element im Eingabearray festzustellen ist, ergibt sich dafür eine Laufzeit von O(n). Dies kann in folgender Rekurrenzgleichung dargestellt werden.
T(n) = 2T(n/2) + O(n)
Da die Form der Gleichung, der für die Anwendung des Mastertheorems entsprechenden Form genügt, kann dieses zur Lösung der Gleichung herangezogen werden. Daraus ergibt sich eine Laufzeit von O (n log n).
Worst case
Im ungünstigsten Fall wird das Schlüsselelement bei jedem Durchlauf so gewählt, dass jeweils ein Teilarray mit nur einem Element und eines mit dem Rest der Eingabe entsteht. Dies ist der Fall, wenn eine Eingabe erfolgt, die bereits sortiert ist. Das Element, welches allein steht, ist das Schlüsselelement. Es befindet sich an der richtigen Stelle im Array und muss daher nicht Teil des rekursiven Aufrufs sein. Die Laufzeit ergibt sich in diesem Fall aus folgender Gleichung. Sie ist für den schlechtesten Fall von der Ordnung n².
T(n) = T(n-1) + O(n)
Average case
Mit Hilfe eines Rekursionsbaumes lassen sich auch die entstehenden Kosten für eine unbalancierte Aufteilung des Eingabearrays sehr einfach ermitteln. Jede Ebene des Baumes erzeugt in Summe cn Kosten. Die Baumtiefe ergibt sich aus dem Logarithmus von n, zur Basis des Kehrwertes des größeren Anteils von n, in der zweiten Ebene des Baumes. Sie ist log n. Da log n Ebenen zu je cn Kosten vorhanden sind, ergibt sich daraus eine Laufzeit von O(n lg n). Im Mittel wechseln sich gute und schlechte Aufteilungen ab. Auch hier kann eine Laufzeit von O(n lg n) nachgewiesen werden. In der Praxis bewegt sich die Laufzeit näher am günstigsten Fall.