3.2 Sortieren durch direktes Einfügen: Insertionsort
 - bekannt vom Sortieren beim Kartenspiel:
   * betrachte ein Element nach dem anderen
   * füge  es in die bereits sortierten ein, die Größeren rutschen nach rechts
   (am Overhead mit Münzen zeigen!)
 - Problem: v kleinestes Element => Schleife verläßt zulässigen Bereich
   Abhilfe: Sentinel Key a[0], mindestens so klein wie das kleinste Element

   Kurzanalyse: Zahl C[i] der Vergleiche beim i-ten Durchlauf: zwischen i-1 und 1
   im Mittel: i / 2
   insgesamt:	C[min] = n - 1
   C[mit] = (n2 + 3n - 4) / 4
   C[max] = (n2 + n - 2) / 2
   Zahl M[i] der Bewegungen beim i-ten Durchlauf: C[i] + 2
   insgesamt:	M[min] = 3 * (n-1)
   M[mit] = (n2 + 11n - 12) / 4
   M[max] = (n2 + 5n - 6) / 2
=> Komplexität von =(n2)		stabil
 - bester Fall bei geordneter Menge, schlechtester bei entgegengesetzt geordnet
 3.3 Shell-Metzner Sort
 - beruht auf Insertionsort
 - Vergleich der Elemente geschieht mit abnehmender Schritt- bzw. Spannweite
   * Elemente nicht nebeneinander, sondern um k auseinander
   * h absteigende Folge, muß gegen 1 konvergieren
   * bei h>1: wird das Feld h-sortiert
   => Elemente werden über große Strecken bewegt
   * bei h=1: Standart-Insertionsort kommt zum Zuge (Folie!)
   => durch Vorsortierung nur noch kleine Bewegungsanzahl notwendig
 - enormer Geschwindigkeitsgewinn
 - Analyse nicht möglich, da ungelöste Mathematische Probleme
 - nicht einmal Aussagen über h
 - für h[k-1] = 3 * h[k] + 1 gilt: O(n1.25)
 - bestes einfaches Verfahren

4. Quicksort
 - C.A.R. Hoare: Idee bei Projekt mechanischer Übersetzung Russisch -> Englisch
 - Wörter auf Magnetband gespeichert, schnellerer Zugriff -> Sortierung
 - Hoare hält autmat. Übersetzung für unpraktisch: Nebenprodukt Quicksort
 - Artikel von 1962, noch vor ALGOL-Entwicklung
 - später: Hoare's Vorhersagen über Geschwindigkeit werden bestätigt

4.1 Grundidee
    Problem in Teilprobleme zerlegen -> bis Teilprobleme lösbar werden
    Zahlenreihe in Teilreihen zerlegen: links kleiner Pivotelement
    rechts größer Pivotelement
    Rekursiv weiterzerlegen

4.2 Algorithmus
Partitionierung: (Folie!)
	1. Wert aus der Menge als Trennelement herausgreifen
	2. Reihe mit zwei Pfeilen durchlaufen:
	   unterer Pfeil startet: 	aktueller Wert kleiner Pivot: Pfeil geht weiter
`	   aktueller Wert größer Pivot: oberer Pfeil
	   oberer Pfeil startet:	aktueller Wert größer Pivot: Pfeil geht weiter
	   aktueller Wert kleiner Pivot:
	   Objekte tauschen, beide Pfeile weiter, unterer Pfeil startet
	3. Ende: beide Pfeile überkreuzen sich
	   - empfehlenswert: größer gleich  

Quicksort: - nach jeder Patitionierung: zwei neue Segmente
	   - leere oder 1-elementige werden nicht weiterpartitioniert
	   - rekursive Partitionierung sortiert das Feld
           - Quicksort arbeitet in situ, d.h. im Speicher
           - Nachteil: Rekursives Verfahren
           - implementierte Fehler schwerzufinden
           => Hoare muß sich einen Stack programmieren

4.3 Analyse von Quicksor
- Zahl C der Vergleiche für Partitionierung von N Elementen: ca. N

ungünstiger Fall: Pivotelement immer gerade größter oder kleinster Wert aus Feld
(Folie)	pro Rekursionsstufe findet ein Tausch statt, Ordnung O(n2)

 
- Zahl M der Bewegungen:
  Annahme: Wahl von Pivotelement zufällig: r-te Element
  Nach Partitionierung: 1..r-1, r, ..., N
  Zahl der Austausche = Anzahl der Element 1 bis r-1 > Pivotelement
  Wahrscheinlichkeit für ein Element größer Pivot: (N - r) / N
  => (N - r) * (r - 1) / N
  insgesamt: N / 6 + 5 / (6 * N)
- Vergleiche und Bewegungen: aN + b + c/N; a, b, c abhängig von Computer
  Tr Zeit, um r Elemente zu sortieren
  TN-r Zeit, um N-t Elemente zu sortieren
  also TN = Tr + TN-r + aN + b + c/N (vorausgesetzt: Pivot ist r-tes Element)
Erwartungswert: 2/N * Summe(1 bis N-1)Tr + aN + b + c/N;
- Lösung der Gleichung schwierig!
- größter Term entscheidend, setzte a = 1, b = c = 0
- 2N Summe(1 bis N)1/r ~ 2Nlog N (da ln(x+1) = Summe(xi/i! * (-1)i)
=>Quicksort ist von O(n * log(n))
  nach Informationstheorie:
  Entropie (=Entscheidungsgehalt) maximal zerstört bei 1 Tausch: - log 2
  Entropie der original Datenmenge: - log n!
  Entropie der sortierten Datenmenge: 0
=> minimale Vertauschung: - log n! / -log 2 = log2 n! ~ n log2 n

Quicksort ist nahe dran: 2n log / n log2 = 2 log 2, ca. 1.4