Sortieren
Headline text
Nebenbemerkung für die Hausaufgabe über die timeit-Bibliothek:
+--------+ +----+ setup = """ prog = """ | | --> |init| +----+ +----+ | | +----+ |init| |prog| | | +----+ +----+ | | +----+ """ """ | | --> |prog| +--------+ +----+
- Timeit-Objekt erzeugen: 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
Sortieralgorithmen
Sortierverfahren
1. Motivation
Def: Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren.
Anwendungen
- Sortierte Daten sind häufig Vorbedingungen für Suchverfahren
(Speziell für Algorithmen mit Log Komplexität)
- Darstellung menschl. Wahrnehmung
- Bemerkungen
aus Programmiertechnischer Anwenwendungssicht hat das Sortierproblem an Relevanz verloren da
- Festplatten / Hauptspeicher heute weniger limitierenden Charakter haben
- gängige Proprammiersprachen haben typenabhängige Algorithmen zur Verfügung stellen.
2. Vorraussetzungen/ Spielregeln
2.1 Mengentheoretische Anforderungen
- Def
- Totale Ordnung/ Total gordnete Menge
Eine Totale Ordnung/ Total geordnete Menge ist eine binäre Relation
R \subseteq M \times M über einer Menge M.
Eigenschaften transitiv, antisymmetrisch und total
Hab in der Wiki eine gute Seite dazu gefunden Ordnungsrelation
Konkret
R sei dargestellt als infix Notation <math>\le </math> dann, falls M total geordet, gilt <math> \forall a,b,c \ \epsilon M </math>
(1) <math>a \le b \bigwedge b \le a \Rightarrow a=b </math> (anitsymmetrisch)
(2) <math>a \le b \bigwedge b \le c => 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)
2.2 Datenspeichen a) Array (Grafik folgt noch)
b) Vekettete Liste
Nachteil Adressierung bsp: 10 > 9
2.3 Charakterisierung von Algorithmen
(a) Komplexität O(1), O(n), O(.), \Omega (.)
Rekursive Zerlegung zerlegt Ürsprüngliche Probleme in kleinere Probleme und wendet sie auf die kleineren Probleme an; daraufhin werden die Teilrobleme zur Lösung des Gesamtproblems verwendet. Aufwand für N Eingaben, hängt ab vom Aufwand der Eingaben geringeren Umpfangs ab. (Teilprobleme)
----
4. Stunde, am 17.04.2008
(Fortsetzung der Stunde vom 16.04.2008)
a) Algorithmus
- c ← merge(a,b) (Siehe Mitschrift der Stunde am 16.04.2008)
- 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)
}
Bei der Sortierung mit Mergesort wird das Array immer in zwei Teile geteilt. → Es
entsteht ein Binärbaum der Tiefe <math>lgN</math>.
Zeitkomplexität: <math>C(N) - N \cdot lgN</math>
b) Komplexität
Komplexität: <math>C(N) = 2 \cdot \left( \frac{N}{2} \right) + N = N \cdot log_2 N
\cdot 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
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 Reihenfolge der Eingabedaten.
Grund dafür ist die vollständige Aufteilung des Ausgangsarrays in Arrays der Länge
1.
- 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.
3.4 Quicksort
- Quicksort wurde in den 60er Jahren von Charles Antony Richard Hoare [1] entwickelt. Es gibt viele Implementierungen von Quicksort, siehe vgl. [2].
- Dieser Algorithmus gehört zu den "Teile und herrsche"-Algorithmen (divide-and-conquer) und ist der Standardalgorithmus für Sortieren.
a) Algorithmus
quiksort(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)
}
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>
Abbildung fehlt noch a[i] heißt Pivot-Element (p)
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] >= p
repeat
j ← j+1 #Finde von rechts den ersten Eintrag <= p
until a[j] <= p
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])
return(i)
}
Bemerkungen zur gegebenen Implementierung:
- Sie benötigt ein Dummy-Minimalelement.
- Dieses Element ist durch zusätzliche if-Abfrage vermeidbar, aber die
if-Abfrage erhöht die Komplexität des Algorithmus (schlechte Performanz).
- Sie ist ineffizient 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
- Erste Partition: [l,i-1], zweite Partition: [i+1,r]
Pivot-Element p = r gewählt wurde. Das Array wird also elementweise
abgearbeitet.
- → N einzelne Aufrufe ⇒ Zeitkomplexität: <math>\approx
\frac{N^2}{2}</math> (siehe Berechnung vom 16.04.2008)
- Für identische Schlüssel sollten beide Laufvariablen stehen bleiben.
- Bei der gegebenen Implementierung tauscht auch gleiche Elemente aus.
- Für identische Schlüssel können die Abbruchbedingungen verbessert werden (siehe
Sedgewick).
c) Komplexität
<math>C(N) = (N+1) + \frac{1}{N} \sum_{m=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_{m=1}^{N} \left[ C(k-1) + C(N-k) \right] = 2 \frac{1}{N}
\sum_{k=1}^{N} C(k-1)
</math>
<math>
C(N) = (N+1) + \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k) \right]
\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) \cdot N + 2 \sum_{k=1}^{N}
C(k-1) - 2 \sum_{k=1}^{N} C(k-1) </math>
<math>
= N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) \longleftrightarrow </math>
<math> N \cdot C(N) = N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) + (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>
Verbesserungen des Algorithmus:
- Eine Verbesserung beseitigt die Rekursion durch Verwendung eines Stacks.
- "r" wird immer kleiner → Der rekursive Aufruf lohnt sich nicht mehr. →
Explizites Sortieren einsetzen.
- Das Pivot-Element könnte geschickter gewählt werden: Median.
147.142.207.188 19:31, 23 April 2008 (UTC)
