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
Sortierverfahren
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.
Vorraussetzungen/ Spielregeln
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 => 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)
Datenspeichen
a) Array (Grafik folgt noch)
b) Vekettete Liste
Nachteil Adressierung bsp: 10 > 9
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)
Mergesort
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>
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
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.
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.
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)
}
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 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).
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)
