Sortieren: Difference between revisions
No edit summary |
No edit summary |
||
Line 113: | Line 113: | ||
Aus Gründen der Einfachheit sei N = 2n | Aus Gründen der Einfachheit sei N = 2n | ||
C(N)= C(2^n)= C(<math>2^{n-1}) + 1 | C(N)= C(2^n)= C(<math>2^{n-1}) + 1 </math> +---+---+---+---+-|-+---+---+---+---+ | ||
| | | | | | | | | | | |||
= C(<math>2^{n-1}) + 1 + 1</math> +---+---+---+---+--|-+---+---+---+---+ | |||
= ... | = ... +---+---+---+---+ | ||
| | | | | | |||
= C(<math>2^0</math>) + n +---+---+---+---+ | |||
= | = n +---+---+ +---+ | ||
| | | -> | | | |||
= <math>log_2 N</math> +---+---+ +---+ | |||
= log_2 N</math> | |||
(iii) rekursives halbieren, lineare Bearbeitung, jedes Elements | (iii) rekursives halbieren, lineare Bearbeitung, jedes Elements | ||
'''(b) Stabilität''' | '''(b) Stabilität''' |
Revision as of 19:09, 25 May 2008
Laufzeitmesung in Python
Verwendung der timeit-Bibliothek für die Hausaufgabe.
- Importiere das timeit-Modul: import timeit
- Teile den Algorithmus in die Initialisierungen und den Teil, dessen Geschwindigkeit gemessen werden soll. Beide Teile werden in jeweils einen (mehrzeiligen) String eingeschlossen:
+--------+ +----+ setup = """ prog = """ | algo | --> |init| +----+ +----+ | | +----+ |init| |prog| | | +----+ +----+ | | +----+ """ """ | | --> |prog| +--------+ +----+
- aus den beiden Strings wird ein Timeit-Objekt erzeugt: t = timeit.Timer(prog, setup)
- Frage: Wie oft soll die Algorithmik wiederholt werden
- z.B. N = 1000
- Zeit in Sekunden für N Durchläufe: K = t.timeit(N)
- Zeit für 1 Durchlauf: K/N
3.Stunde am 16.04.2008
Sortierverfahren
1.Motivation
Def: Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren.
- Literatur, ride Sortierverfahren; Bubblesort 1956, Quicksort 1962. Liberysort 2004
Anwendungen
- Sortierte Daten sind häufig Vorbedingungen für Suchverfahren (Speziell für Algorithmen mit Log(N) Komplexität)
- Darstellung von Daten gemäß menschlicher Wahrnehmung
- Bemerkung: aus programmiertechnischer Anwendungssicht hat das Sortierproblem an Relevanz verloren da
- Festplatten / Hauptspeicher heute weniger limitierenden Charakter haben, so dass komplizierte, speicher-sparende Sortieralgorithmen nur noch in wenigen Fällen benötigt werden.
- gängige Programmiersprachen heute typunabhängige Algorithmen zur Verfügung stellen. Der Programmierer braucht sich deshalb in den meisten Fällen nicht mehr um die Implementierung von Sortieralgorithmen zu kümmern. In C/C++ sorgen dafür beispielsweise Methoden aus der STL
2. Vorraussetzungen/ Spielregeln
- Mengentheoretische Anforderungen a Elemente - Datenspeicherung Array / Liste - Charakterisierung von Algorithmen -- Komplexität (Speicher/ Laufzeit) -- Stabilität -- allg. Eigenschaften (Rekursivität/ Vergleich/ Methoden)
2.1 Mengentheoretische Anforderungen
Definition Totale Ordnung/ Total gordnete Menge:
Eine Totale Ordnung / Total geordnete Menge ist eine binäre Relation
<math>R \subseteq M \times M</math> über einer Menge <math>M</math>, die transitiv, antisymmetrisch und total ist.
<math>R</math> sei dargestellt als infix Notation <math>\le </math> dann, falls M total geordnet, gilt
<math> \forall a,b,c \ \epsilon M </math>
(1) <math>a \le b \bigwedge b \le a \Rightarrow a=b </math> (antisymmetrisch)
(2) <math>a \le b \bigwedge b \le c \Rightarrow a \le c </math> (transitiv)
(3) <math>a \le b \bigvee b \le a </math> (total)
Bemerkung: aus (3) folgt <math> a \le a </math> (reflexiv)
Hab in der Wiki eine gute Seite dazu gefunden Ordnungsrelation
2.2 Datenspeicherung
a) Array ---
+---+---+---+---+---+---+---+---+---+ |///| | | | | | | |///| Einfügen oder Löschen +---+---+---+---+---+---+---+---+---+ \________________ ____________________/ \/ N
b) Vekettete Liste
+---+ +---+ +---+ | |-> | |-> | |-> Z +---+ +---+ +---+
Datenelement zeigt auf das Nächste Nachteil: lineares array (Adressierung bsp: 10 > 9)
Charakterisierung der Effizienz von Algorithmen
- (a) Komplexität O( 1), O(n), etc. wird in Kapitel Effizienz erklärt.
- (b) Zählen der notwendigen Vergleiche
- (c) Messen der Laufzeit mit 'timeit' (auf identischen Daten)
Rekursive Beziehungen zerlegt die ursprünglichen Probleme in kleinere Probleme und wendet den Algorithmus auf die kleineren Probleme an; daraufhin werden die Teilprobleme zur Lösung des Gesamtproblems verwendet. d.h. Laufzeit (operativer Vergleich) für N Eingaben hängt von der Laufzeit der Eingaben für die Teilprobleme
Aufwand
(i) rekursives/ lineares Durchlaufen der Eingabedaten, Bearbeitung einzelner Elemente
C(N)= C(N-1)+ N ; N>1, C(1)= 1 +---+---+---+---+---+---+---+---+---+ = C(N-2) +(N-1)+ N | 7 | 3 | 2 | 5 | 6 | 8 | 1 | 4 | 2 | = C(N-3) + (N-2) + (N-1) + N +---+---+---+---+---+---+---+---+---+ = ... ________________________/ = C(1) + 2+...+(N-1) +N / +---+---+---+---+---+---+---+---+---+ N(N+1) N² | 1 | 3 | 2 | 5 | 6 | 8 | 7 | 4 | 2 | = ----- ~ -- +---+---+---+---+---+---+---+---+---+ 2 2
(ii) rekursives halbieren der Menge der Eingabedaten
C(N)= C(N/2)+1 ; N>1, C(1)=0 Aus Gründen der Einfachheit sei N = 2n C(N)= C(2^n)= C(<math>2^{n-1}) + 1 </math> +---+---+---+---+-|-+---+---+---+---+ | | | | | | | | | | = C(<math>2^{n-1}) + 1 + 1</math> +---+---+---+---+--|-+---+---+---+---+
= ... +---+---+---+---+ | | | | | = C(<math>2^0</math>) + n +---+---+---+---+
= n +---+---+ +---+ | | | -> | | = <math>log_2 N</math> +---+---+ +---+
(iii) rekursives halbieren, lineare Bearbeitung, jedes Elements
(b) Stabilität
Definition: stabiles Sortierverfahren
Ein Sortierverfahren heißt stabil falls die relative Reihenfolge gleicher Schlüssel M der Ausgangsdaten beibehält.
3. Sortierverfahren
4. Stunde, am 17.04.2008
(Fortsetzung der Stunde vom 16.04.2008)
Mergesort
a) Algorithmus
Zugrunde liegende Idee:
- "Teile und herrsche"-Prinzip (divide and conquer) zur Zerlegung des Problems in Teilprobleme.
- Zusammenführen der Lösungen über Mischen (merging): "two-way" oder "multi-way".
a.1) Algorithmus c ← merge(a,b)
c = merge(a,b) ← { # Kombination zweier sortierter Listen a[i] und b[j] # zu einer sortierten Ausgabeliste c[k] a[M+1] ← maxint b[N+1] ← maxint for k ← 1 to M+N if a[i] < b[j] c[k] > a[i] i ← i+1 else c[k] ← b[j] j ← j+1 }
a.2) rekursiver Mergesort
mergesort(m) ← { #m ist ein Array if |m| > 1 #True, wenn m mehr als 1 Element hat. a ← mergesort(m[1:<|m|/2]) b ← mergesort(m[(|m|/2)+1:|m|]) c ← merge(a,b) return(c) else return(m) }
(Eine In-place-Implementierung siehe bei Sedgewick.)
Bei der Sortierung mit Mergesort wird das Array immer in zwei Teile geteilt. → Es entsteht ein Binärbaum der Tiefe <math>lgN</math>.
Gegebene unsortierte Liste: [S,O,R,T,I,N,G] Die Teile werden bei jedem Schritt paarweise gemischt.
Schritt 0: S 0 R T I N G S O R T I N G #Arraylänge: N/8 Schritt 1: \ / \ / \ / / OS RT IN G OS RT IN / #Arraylänge: N/4 Vergleiche: N/4 * 4 Schritt 2: \ / \ / ORST GIN ORST GIN #Arraylänge: N/2 Vergleiche: N/2 * 2 \ / Schritt3: \ / GINORST GINORST #Arraylänge: N Vergleiche: N
Zeitkomplexität: <math>C(N) - N \cdot lgN</math>
b) Komplexität
Komplexität: <math>C(N) = 2 \cdot C \left( \frac{N}{2} \right) + N = N \cdot log_2 N </math> (für N = <math>2^n</math> )
Erklärungen zur Formel:
- <math> C \left(\frac{N}{2}\right) </math>: "für jede Hälfte des Arrays"
- <math> +N </math>: für das Zusammenführen
- N Vergleiche pro Ebene
- Insgesamt gibt es <math> log_2 N </math> Ebenen.
c) Weitere Eigenschaften von MergeSort
- Mergesort ist stabil, weil die Position gleicher Schlüssel im Algorithmus merge(a,b) nicht verändert wird - wegen „<” hat das linke Element Vorrang.
- Mergesort ist unempfindlich gegenüber der ursprünglichen Reihenfolge der Eingabedaten. Grund dafür ist
- die vollständige Aufteilung des Ausgangsarrays in Arrays der Länge 1 und
- dass merge(a,b) die Vorsortierung nicht ausnutzt, d.h. die Komplexität von merge(a,b) ist sortierungsunabhängig.
- Diese Eigenschaft ist dann unerwünscht, wenn ein Teil des Arrays oder gar das ganze Array schon sortiert ist. Es wird nämlich in jedem Fall das ganze Array neu sortiert.
Quicksort
- Quicksort wurde in den 60er Jahren von Charles Antony Richard Hoare [1] entwickelt. Es gibt viele Implementierungen von Quicksort, vgl. [2].
- Dieser Algorithmus gehört zu den "Teile und herrsche"-Algorithmen (divide-and-conquer) und ist der Standardalgorithmus für Sortieren.
a) Algorithmus für quicksort
quicksort(l,r) ← { #l: linke Grenze, r: rechte Grenze des Arrays #Das Array läuft also von l bis r (a[l:r]) if r > l i ← partition(l,r) #i ist das Pivot-Element quicksort(l,i-1) #quicksort auf beide Hälfte des Arrays anwenden quicksort(i+1,r) }
Dieser Algorithmus wird rekursiv für zwei Teilstücke links und rechts des Pivot-Elements aufgerufen. Das Pivot-Element ist nach diesem Schritt an der richtigen Position (d.h. links von der Stelle i stehen nur kleinere, rechts von i nur größere Elemente als das Pivot-Element). Die Methode partition sorgt dafür, dass diese Bedingung erfüllt ist.
b) Algorithmus für partition
Aufgabe: Ordne a so um, dass nach der Wahl von i (Pivot-Element) gilt:
- <math>a[i]</math> ist sortiert, d.h. dieses Element ist am endgültigen Platz.
- <math>\forall x \in \left\{ a \left[ l \right] , ... a \left[ i-1 \right] \right\} : x \leq a \left[ i \right]</math>
- <math>\forall x \in \left\{ a \left[ i+1 \right], ... a \left[ r \right] \right\} : x \geq a \left[ i \right]</math>
- a[i] heißt Pivot-Element (p)
l r +---+---+---+---+---+---+---+---+---+ Array: | | | | |\\\| | | | | +---+---+---+---+---+---+---+---+---+ \______ _____/ i \______ _____/ \/ \/ <=a[i] >=a[i] (a[i] ist das Pivot-Element)
i ← partition(l,r) ← { p ← a[r] #p: Pivot-Element. Hier wird willkürlich das rechteste # Element als Pivot-Element genommen. i ← l-1 #i und j sind Laufvariablen j ← r repeat repeat i ← i+1 #Finde von links den ersten Eintrag >= p until a[i] >= r repeat j ← j-1 #Finde von rechts den ersten Eintrag < p until a[j] <= r swap(a[i], a[j]) until j <= i #Nachteile: p steht noch rechts swap(a[i], a[j]) #Letzter Austausch zwischen i und j muss #zurückgenommen werden swap(a[i], a[r]) #Das Pivot-Element wird an die korrekte Position gesetzt. return(i) }
p +---+---+---+---+---+---+---+---+---+ Array: | | | | |\\\| | | | | +---+---+---+---+---+---+---+---+---+ -------> i>p j<p <------- | | +---------------+ Diese zwei Elemente werden ausgetauscht. p +---+---+---+---+---+---+---+---+---+ Array: | | | | |\\\| | | | | +---+---+---+---+---+---+---+---+---+ -----------------> <----------------- "repeat" bis sich die Zeiger treffen oder einander überholt haben.
l,i --> <-- j r +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | A | S | O | R | T | I | N | G | E | X | A | M | P | L | E | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ i j r +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | A | S | O | R | T | I | N | G | E | X | A | M | P | L | E | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ i j r +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | A | A | O | R | T | I | N | G | E | X | S | M | P | L | E | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ j i r +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | A | A | R | E | T | I | N | G | O | X | S | M | P | L | E | --> Hier wird die +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ Schleife verlassen. j i r +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | A | A | E | R | T | I | N | G | O | X | S | M | P | L | E | 1.swap +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ i r +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | A | A | E | E | T | I | N | G | O | X | S | M | P | L | R | 2.swap +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
- Bemerkungen zur gegebenen Implementierung:
- Die gegebene Implementierung benötigt ein Dummy-Minimalelement (für den Fall i=1).
- Dieses Element ist durch zusätzliche if-Abfrage vermeidbar, aber die if-Abfrage erhöht die Komplexität des Algorithmus (schlechte Performanz).
- Sie ist uneffizient für (weitgehend) sortierte Arrays, da sich folgende Aufteilung für die Partitionen ergibt:
- Erste Partition: [l,i-1], zweite Partition: [i+1,r]
- Die erste Partition umfasst N-1 Elemente. Die zweite Partition ist leer (bzw. sie existiert nicht), weil das Pivot-Element p = r gewählt wurde.
- Das Array wird elementweise abgearbeitet. → N einzelne Aufrufe ⇒ Zeitkomplexität: <math>\approx\frac{N^2}{2}</math>.
- Für identische Schlüssel sollten beide Laufvariablen stehen bleiben (daher "<math>\leq</math>"), um ausgeglichene Zerlegungen bei vielen identischen Schlüsseln zu gewährleisten.
- Bei der gegebenen Implementierung tauscht auch gleiche Elemente aus.
- Für identische Schlüssel können die Abbruchbedingungen verbessert werden (siehe Sedgewick, Seite 150).
c) Komplexität
<math>C(N) = (N+1) + \frac{1}{N} \sum_{k=1}^{N} \left[ C(k-1) + C(N-k) \right]</math> für <math> N>1;\, C_1 = C_0 =0 </math>
Anmerkungen zur Formel:
- <math>(N+1)</math>: Vergleiche für jeden Aufruf
- <math>k</math>: Teilungspunkt
- <math> \frac{1}{N} \sum_{k=1}^{N} \left[ C(k-1) + C(N-k) \right] = 2 \frac{1}{N} \sum_{k=1}^{N} C(k-1) </math> ist der mittlere Aufwand über alle möglichen Zerlegungen.
<math>
C(N) = (N+1) + \frac{2}{N} \sum_{k=1}^{N} C(k-1) </math> <math>\overset{\cdot N}{\longleftrightarrow} </math>
<math>
N \cdot C(N) = N \left[ (N+1) + \frac{2}{N} \sum_{k=1}^{N} C(k-1) \right] \overset{-\, (N-1) \cdot C(N-1)}{\longleftrightarrow} </math>
<math>
N \cdot C(N) - (N-1) \cdot C(N-1) = N(N+1) - (N-1) N + 2 \sum_{k=1}^{N} C(k-1) - 2 \sum_{k=1}^{N} C(k-1) </math>
<math>
= N(N+1) - (N-1) N + 2 \cdot C(N-1) \longleftrightarrow </math>
<math> N \cdot C(N) = N(N+1) - (N-1) N + 2 \cdot C(N-1) + (N-1) \cdot
C(N-1) = 2N + (N+1) \cdot C(N-1) \overset{/N(N+1)}{\longleftrightarrow} </math>
<math>
\frac{C(N)}{N+1} = \frac{C(N-1)}{N} + \frac{2}{N+1} </math>
<math>
= \frac{C(N-2)}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
<math>
= \frac{C(N-3)}{N-2} + \frac{2}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
<math>
= ... = </math>
<math>
= \frac{C(2)}{3} + 2 \sum_{k=3}^{N} \frac{1}{k+1} \approx 2 \sum_{k=3}^{N} \frac{1}{k+1} \approx 2 \int_1^N \frac{1}{k} dk = 2 \cdot ln N
</math>
Für sehr große N gilt:
<math>\approx 2 \sum_{k=1}^{N} \frac{1}{k}</math> beziehungsweise <math> \geq 2
\sum_{k=1}^{N} \frac{1}{k}</math>
Mittlere Komplexität:
<math>C(N) = 2(N+1) \cdot lnN \approx 2N \cdot lnN </math>
d) Verbesserungen des Quicksort-Algorithmus
Beseitigung der Rekursion
- Eine Verbesserung beseitigt die Rekursion durch Verwendung eines Stacks. Nach jeder Partitionierung wird das größere Teilintervall auf dem Stack abgelegt und das kleinere Teilintervall direkt weiterverarbeitet.
quickSort(l,r) ← { #initialize stack push([l,r]) repeat if r > l: i ← partition(l,r) if (i-l) > (r-i): push([l,i-1]) l ← i+1 else: push([i+1,r]) r ← i-1 else: [l,r] ← pop() until stackempty() }
+---+---+---+---+---+---+---+ | Q | U | I | C | K | S | O | +---+---+---+---+---+---+---+ +---+---+---+===+---+---+---+ | K | C | I |=O=| Q | S | U | +---+---+---+===+---+---+---+ \_________/ push +---+===+---+ | C |=I=| K | +---+===+---+ \_/ push +===+ |=C=| +===+ +===+ |=K=| +===+ +---+---+===+ | Q | S |=U=| +---+---+===+ +---+===+ | Q |=S=| +---+===+ +===+ |=Q=| +===+ +---+---+---+---+---+---+---+ | C | I | K | O | Q | S | U | +---+---+---+---+---+---+---+
Alternatives Sortieren kleiner Intervalle
- Für kleine Intervalle ist Insertion Sort effizienter als "Teile und herrsche"
- Modifikation:
if (r-l) <= K: insertion(l,r) else: #wie bisher
- für M = 3: explizites Sortieren von 3 Elementen. - Sortieren von 3 Datensätzen. Idee:
- Stelle sicher, dass a[1] und a[2] relativ zueinander sortiert sind.
- Falls a[1] jetzt noch größer als a[3] ist, so ist a[3] das kleinste Element und muss nach vorne geschrieben werden. Das heißt: swap(a[i], a[3]). Danach steht das kleinste Element in a[1].
- Jetzt kann es entweder sein, dass
- in 2. kein swap durchgeführt wurde und a[3] eventuell zwischen a[1] und a[2] liegen könnte, oder
- der swap durchgeführt wurde und die Reihenfolge von a[2] und a[3] jetzt falsch ist.
- Falls a[2] > a[3], dann swap(a[2], a[3]). Das löst beide in 3. genannten Probleme.
- Der Algorithmus zum Sortieren von drei Datensätzen:
a = sort2(a) ← { if a[1] > a[2]: swap(a[1], a[2]) if a[1] > a[3]: swap(a[1], a[3]) # Man könnte hier # swap(a[2],a[3]) # return # einfügen und eine if-Abfrage sparen. if a[2] > a[3]: swap(a[2], a[3]) }
Günstige Selektion des Pivot-Elements
- Das Pivot-Element könnte geschickter gewählt werden. Methode: Median von drei Elementen: Bestimme den Median der ersten, mittleren und letzten Elements eines Arrays und verwende der Median als Pivot-Element
- Diese Methode minimiert die Häufigkeit des Auftetens des ungünstigsten Falles.
147.142.207.188 19:31, 23 April 2008 (UTC)