Quicksort

"Grundlagen der Programmierung"

Folie 1

1. Geschichte und Hintergründe des Sortierproblems
 - erste Entwicklungen in Amerika Ende 19.Jh (Volkszählung alle 10 Jahre üblich)
 - Interesse an versch. Statistiken => Sortierverfahren (bisher: Handarbeit)
 - Hollerith: batteriebetriebene Sortiermaschine mit Lochkarten
   * Loch: Kontakt zwischen Nadel und Unterlage => Klappe öffnen
   * 1 Angestellter kann in 6,5h 19071 Karten bearbeiten
 - steigende Bevölkerung: Sortiermaschinen mit autom. Papierzuführung (1901/04)
 - 1930 erste programmierbare Computer => eröffnet neue Dimensionen
 - Interesse an Sortierproblem unweigerlich mit Computerentwicklung verbunden
 - so alt wie Computer selbst
   => unzählig viele Sortier-Algorithmen


2. Theoretische Grundlagen

2.1 Das Sortierproblem
 - Sortieren (lat. sors, -tis Rang, Ordnung) = "in Ordnung bringen"
 - Ordnung: in bezug auf Größe (opt. Ordnung), Zahlenwerte (PLZs), Alphabet
 - soll späteres Suchen vereinfachen 
 - exakte Darstellung:
   Sei A Alphabet oder eine geordnete Menge von Elementen
   Sei v = v1,, v2, ..., vn E An
   nach Ordnung soll gelten: vi <= vi+1 für i = 1, 2, ..., n-1.
   Ges.: Permutation Pi: {1, 2, ..., n} -> {1, 2, ..., n},
   so daß vPi(1), vPi(2), ..., vPi(n) geordnet (in Bezug auf A)


2.2 Definition einiger Fachbegriffe
 - zur Bewertung von Algorithmen einige Fachbegriffe notwenig
   Schlüssel (engl. key) = Wert eines Elementes der zu sortierenden Menge
   Stabilität = Maß für die Beibehaltung der Reihenfolge gleicher Schlüssel
   Inversionszahl = Maß der Unordnung einer Permutation
   Beispiel: Folge v = (25 58 01 08 76 06 24)
           Pi = ( 5  6  1  2  7  3  4); (zugehörige ordnende Permutation)
           Alpha (25 58 01 08 76 06 24) = 11;
   Ordnungsverträglichkeit = Ausnutzung bestehender Teilordnung(en)

3. Elementare Sortieralgorithmen
 - wichtig, da mit komplexeren Algorithmen kombinierbar
 - für kleine Datenmengen oft ausreichend (weniger Fehler Sedgewick)

3.1 Bubblesort
 - einer der bekanntentesten Algorithmen
 - Prinzip des direkten Austausches:
   * aufeinander folgende Paare werden verglichen, ggf. vertauscht
   * Feld N-1 durchlaufen
   (am Overhead mit Münzen zeigen!)
 - Feld senkrecht: Zahlen steigen, wie Blasen (engl. Bubbles), nacheinander auf
 - Tracetabelle (Folie!)
   * letzten drei Durchläufe unnötig
   * FOR-NEXT-Schleife wird stur durchlaufen
 - Verbesserung: prüfen, ob überhaupt noch Vertauschungen stattfinden


  Kurzanalyse: Zahl C[i] der Vertauschungen im i-ten Durchlauf: (n-i)
  insgesamt: C = (n2 - n) / 2
  Zahl M[i] der Beweungen im i-ten Durchlauf: zwischen 3*(n-i) und 0
  im Mittel: 3 * (n - i) / 2
  insgesamt:M[min] = 0
	    M[mit] = 3 * (n2 - n) / 4
	    M[max] = 3 * (n2 - n) / 2
=> Komplexität von O(n2)
 - instabil