Sortieren

---

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

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(N) Komplexität)
• Darstellung von Daten gemäß menschlicher Wahrnehmung
• Bemerkung: aus programmiertechnischer Anwenwendungssicht 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 typenabhängige Algorithmen zur Verfügung stellen. Der Programmierer braucht deshalb sich in den meisten Fällen nicht mehr um die Implementierung von Sortieralgorithmen kümmern. In C/C++ sorgen dafür beispielsweise Methoden aus der STL

Vorraussetzungen/ Spielregeln

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

Datenspeicherung

a) Array (Grafik folgt noch)

b) Vekettete Liste

  Nachteil 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 Zerlegung zerlegt Ursprüngliche Probleme in kleinere Probleme und wendet sie auf die kleineren Probleme an; daraufhin werden die Teilprobleme zur Lösung des Gesamtproblems verwendet. Aufwand für N Eingaben, hängt ab vom Aufwand der Eingaben geringeren Umfangs ab. (Teilprobleme)

----

---

4. Stunde, am 17.04.2008
(Fortsetzung der Stunde vom 16.04.2008)

3.3 Mergesort

a) Algorithmus

1. Zugrunde liegende Idee:

• "Teile und herrsche"-Prinzip (divide and conquer) zur Zerlegung in Teilprobleme
• Zusammenführen der Lösungen über Mischen (merging)
  • two-way
  • 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.

3.4 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:

1. <math>a[i]</math> ist sortiert, d.h. dieses Element ist am endgültigen Platz.
2. <math>\forall x \in \left\{ a \left[ l \right] , ... a \left[ i-1 \right] \right\} : x \leq a \left[ i \right]</math>
3. <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)

Abbildung fehlt noch

 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)
 }

Abbildung fehlt noch

Beispiel fehlt noch

Bemerkungen zur gegebenen Implementierung:

1. 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).

1. Sie ist ineffizient für (weitgehend) sortierte Arrays, da sich folgende

Aufteilung für die Partitionen ergibt:

1. Erste Partition: [l,i-1], zweite Partition: [i+1,r]
2. Die erste Partition umfasst N-1 Elemente
3. Die zweite Partition ist leer (bzw. sie existiert nicht), weil das Pivot-Element p = r gewählt wurde. Das Array wird also elementweise abgearbeitet.
4. → N einzelne Aufrufe ⇒ Zeitkomplexität: <math>\approx

\frac{N^2}{2}</math> (siehe Berechnung vom 16.04.2008)

1. Für identische Schlüssel sollten beide Laufvariablen stehen bleiben.
2. Bei der gegebenen Implementierung tauscht auch gleiche Elemente aus.
3. 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:

1. <math>(N+1)</math>: Vergleiche für jeden Aufruf
2. <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

1. Eine Verbesserung beseitigt die Rekursion durch Verwendung eines Stacks.
2. "r" wird immer kleiner → Der rekursive Aufruf lohnt sich nicht mehr. → Explizites Sortieren einsetzen.
3. Das Pivot-Element könnte geschickter gewählt werden: Median.

147.142.207.188 19:31, 23 April 2008 (UTC)