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
• (binärer) Heap: vollständiger, geordneter, binärer Wurzelbaum
  • Binär: Anzahl der Kinder £ 2.
  • vollständiger (``complete'') Binärbaum: alle Blätter haben die selbe Tiefe + alle internen Knoten mit exakt 2 Kindern²
  • geordnet: Reihenfolge der Kinder spielt eine Rolle, d.h. man kann linkes und rechtes Kind unterscheiden.³
• + Heap-Eigenschaft: Für alle Teilbäume t gilt: t = Node(l, a, r) Þ l = Leaf oder a ³ Key(l) (und genauso für den rechten: r = Leaf oder 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 (nochmal 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 unter Ausnutzung: das maximale Element des Heaps ist fest
• 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]   // finde das maximum
     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  // bottom-up
  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);                       // build initial heap
   for i = length(A) downto 2           
   do  exchange A[1] A[i];              // extract maximum
       heapsize[A] := heapsize[A] - 1;  // decrease size of heap
       Heapify(A,1);                    // repair heap condition

• 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.8 2001/11/11 12:40:19 softtech Exp $ *)

(* A functional implementation of quicksort. The divide-and-conquer
   approach is visible in the recursive inner $\ocwlowerid{sort}$-function:
   It chooses as pivot the first element. Using the auxiliary function
   $\ocwlowerid{filter}$,\footnote{The function is directly available from
   the standard-library. It's included here for sake of reference.} it
   splits the remainder of the list into two halves, the elements less or
   equal the pivot and those larger than the pivot.  The sublists are
   sorted and, together with the pivot in the middle, put together to the
   sorted list.

*)

(*i*)
open Basic;;
open Sort;;
(*i*)



module QuicksortFun (E: ORDERED) : (SORT with type elem = E.t) =
    struct
      type elem = E.t 
     
      let rec filter p l = match l with  (* auxiliary function *)
     []     -> []
      | 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  ->                                   (* x = pivot *)
     sort (filter (function y -> E.lt(y,x)) tl)
     @ [x] @                                     
     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                          /* invariant I_2    */
  do     repeat j := j-1
           until A[j] <= x;           /* non-strict comp. */
         repeat i := i+1
           until A[i] >= x;
         if   i < j                   /* invariant I_1    */
         then exchange A[i] <-> A[j]  /* invariant I_2    */
         else return   j;             /* j <= i           */
  od;
  
         

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