2   Sortieren

Literatur: Kapitel 7 und 8 aus [CLR90]. Knuth [Knu73b] enthält mehr über Sortieren als man wissen will. Heapsort stammt von Williams [Wil64], Quicksort von Tony Hoare [Hoa62]

Inhalt Heaps ·Heapsort ·Quicksort

• (gerichteter) Graph G = (V,E):
  • V: Menge von Knoten (vertices),
  • E: Kanten, binäre Relation auf V (edges)
• ungerichteter Graph: E: Menge ungeordneter Paare {u,v} von Knoten mit u¹v (keine self-loops)
• Wurzelbaum: (rooted tree): verbundener, azyklischer, ungerichteter Graph mit einem ausgezeichnetem Knoten = Wurzel
• Heap: voller, geordneter, binärer Wurzelbaum.
  • Binär: Anzahl der Kinder £ 2.
  • voll: entweder Blatt oder genau zwei geordnete Kinder
  • geordnet: Reihenfolge der Kinder spielt eine Rolle, d.h. hier man kann linkes und rechtes Kind unterscheiden.²
• + Heap-Eigenschaft: Für alle Teilbäume t gilt: t = Node(l, a, r) Þ l = Leaf (und r = Leaf) oder a ³ Key(l) und a ³ Key(r)
• Bild: Heap als Baum

• Implementierung von Heaps als Array: Knoten als Arrayelemente
• Þ weitere Zusatzbedingung: alle Ebenen des Baums gefüllt bis auf evtl. die letzte, diese kann von links nach rechts teilgefüllt sein.³
• Füllung des Arrays von 1 bis heapsize (Bild)
• Repräsentierung des Binärbaumes:

  Parent(i) = ë i 2 û Left(i) = 2 i Right(i) = 2 i + 1

• Ein weiteres Mal das Bild: Heap + Implementierung

• Ausgangspunkt: Unsortierter Array
• zwei Schritte:
  1. "` Teilsortierung"': Bilden eines Heaps
  2. inkrementelle Sortierung des Heaps
• unsortiert ¾® Heap ¾® sortiert

• Heapify: Einfügen, Erhalt der Heapbedingung
• Annahme: der rechte und der linke Teilbaum erfüllen die Heapbedingung!
• rekursive Prozedur: `` Einsickern'' des neuen Elementes

Heapify (A, i)                  
  l := Left(i); r := Right(i);  // Left(i), Right(i) are heaps   

  if l <= heapsize(A) and A[l] > A[i]
     then largest := l  else largest := i;
  if r <= heapsize(A) and  A[r] > A[largest]
     then largest := r;

  if largest != i                 // Verletzung der Heapbedingung?
     then exchange (A[i] , A[largest]);
          Heapify(A, largest);

• repariere alle Verletzungen der Heapbedingung mit Heapify
• Bottom-up mittels Heapify
• Blätter erfüllen Heap-Eigenschaft Þ Start bei den untersten nicht-Blatt Knoten (ë length(A)/2 û).

Build-Heap(A)  
  heapsize[A]  := length[A];
  for i= floor(length(A)/2)) downto 1
      do 
         heapify(A,i);

• Heap als unsortiertes, aber teilsortiertes Reservoir, der Rest des Arrays ist bereits sortiert
• Wurzel des Heaps: Maximum
• Þ Aufbau der sortierten Elemente von hinten
• Entfernen aus dem Heap ist billig (Heapify log₂(n))

Heapsort(A)

   build_heap(A);
   for i = length(A) downto 2
   do  exchange A[1] A[i];
       heapsize[A] := heapsize[A] - 1;
       Heapify(A,1);

• Divide & Conquer
• im Gegensatz zu Mergesort: Verschmelzen trivial, investiere dafür mehr in das Divide
• D&C-Schritte:
  1. Divide: Teile die Sequenz s in zwei Teilsequenzen s₁ und s₂, sodaß s₁£ s₂ (punktweise)
  2. Sortiere Teilsequenzen s₁ und s₂
  3. Conquer: Zusammenfügen trivial

(* $Id: quicksort.ml,v 1.6 1999/11/11 10:43:28 ms Exp $ *)

open Basic;;
open Sort;;

module QuicksortFun (E: ORDERED) : (SORT with type elem = E.t) =
    struct
      type elem = E.t 
     
      let rec filter p l = match l with 
     []     -> []
      | x :: tl ->  
   if   (p x) 
   then  x::(filter p tl)
   else  filter p tl
     
      let rec sort (l : elem list) =   match l with  
        []  -> []
      | x :: tl  -> 
   sort (filter (function y -> E.lt(y,x)) tl)
   @ [x] @                                     (* Pivot *)
   sort (filter (function y -> E.geq(y,x)) tl)
    end

• Zwei rekursive Aufrufe
• das Divide: Partition liefert den Index für die Trennung in die kleinere und größere Hälfte

Quicksort(A,p,r)
if  p < r 
    then   q := Partition(A,p,r)   
           Quicksort(A,p,q);
           Quicksort(A,q+1,r);

• Wähle ein Element des Arrays: das Pivot x
• Partitionieren: trenne/ordne A in 2 Hälften, links alle £ x, rechts alle ³ x.
• Invariante:

• Abbruch: (i ³ j) & I₁, d.h., A[p... i-1] £ x £ A[j+1... r], daraus folgt A[p... j] £ x £ A[j+1... r]

Partition(A,p,r)                      /* p <= r         */
  x := A[p];
  i := p-1;
  j := r+1;
 
  while true                          /* Invariante I_2 */
  do     repeat j := j-1
           until A[j] <= x;
         repeat i := i+1
           until A[i] >= x;
         if   i < j                   /* Invariante I_1 */
         then exchange A[i] <-> A[j]  /* Invariante I_2 */
         else return   j;             /* j <= i         */
  od;
  
         

• Schlechtester Fall: Partitionierung trennt den Ausschnitt [p... r] der Länge n = r-p+1 in einen Teile der Größe 1 und n-1.
• Kosten der Partitionierung: O(n)
• Rekurrenz: T(n) = T(n-1) +O(n) Þ T(n) = å_k=1ⁿ O(k) = O(n²)
• Schlimmster Fall: Falls A bereits sortiert