3   Lineares Sortieren

Literatur: Kapitel 9 [CLR90].

Inhalt O-Notation ·Einführung ·Vergleichssortieren ·Counting sort ·Bucket sort

• Bisher: die Algorithmen O(nlog n) oder O(n²)
• Gemeinsamkeit:

  Die Ordnung die die Algorithem bestimmen, beruht ausschließlich auf dem Vergleich zwischen Elementen

• Þ

  Vergleichssortieren

---

Verfahren	Tmin	Tmax	Tav
Auswahl	O(n2)	O(n2)	O(n2)
Einfügen	O(n)	O(n2)	O(n2)
Bubblesort	O(n)	O(n2)	O(n2)
Mischen	O(n log n)	O(n log n)	O(nlog n)
direktes Mischen	O(n log n)	O(n log n)	O(nlog n)
natürliches Mischen	O(n)	O(n log n)	O(nlog n)
Quicksort	O(nlog n)	O(n2)	O(nlog n)
Heapsort	O(n log n)

Table 1: Vergleich

---

• Vorraussetzung: Sortieren einer Sequenz (a₁,... a_n) (oBdA: alle Elemente verschieden, wichtig ist nur < oder das Gegenteil.)
• mögliche Eingaben der Länge n: alle Permutationen
• Entscheidungsbaum: Darstellung der Entscheidungen eines Sortieralgorithmusses
  • interner Knoten: a_i:a_j wobei 1£ i<j£ n, repräsentiert den Vergleich von a_i mit a_j, seine Unterbäume die Vergleiche, je nachdem wie sein Vergleich ausgefallen ist.
  • Blatt: Permutation
  • Lauf der Sortierung: Pfad durch den Baum
• Þ Höhe des Baumes @ worst-case der Vergleiche @ worst-case der Laufzeit
• Folie: insertion sort

• gegeben: Entscheidungsbaum für einen Algorithmus

• worst-case = Tiefe des Baumes

• Þ Abschätzung für die Laufzeit:

• Mischsortierung und Heapsort sind asymptotisch optimal.

• Es gibt ³ n! Blätter
• Eigenschaft eines binären Baumes: n! £ n^h, d.h., h³ lg(n!)
• mit Stirling-Approximation n! > ( n/e)ⁿ
• Þ h³ n lg n - nlg e
• Þ Untere Schranke O(nlg n).

• Beispiel für einen Algorithmus, der kein Vergleichssortieren ist
• man braucht zusätzliche Information
• Counting Sort: Information, daß der Wertebereich der Elemente endlich ist: 1..., k mit k =O(n).
• Þ Zählen der Elemente =i möglich (im Hilfsarray C[1... k])
• kein Vergleich im Algorithmus

Counting-Sort(A,B,k)
  for i := 1 to k do C[i] := 0;

  for j := 1 to length[A]
  do  C[A[j]] := C[A[j]] + 1  /* C[i]: Anzahl der Elemente = i */

  for i := 2 to k             /* Erlaubter Input von 1...k     */
  do  C[i] := C[i] + C[i-1];  /* C[i]: Anzahl Elemente <= i    */

  for j := length[A]  downto  1
  do
       B[C[A[j]]] :=   A[j];  /* C[A[j]] gibt Pos. in B        */
         C[A[j]]  := C[A[j]] - 1;   
  od;

1. erste Schleife: O(k)
2. zweite Schleife: O(n)
3. dritte Schleife: O(n)

• Insgesamt: O(k+n), und falls k =O(n) Þ lineare Laufzeit: O(n)

• Annahme von Bucketsort: uniforme Verteilung der Eingabe im Intervall I = [0, 1[
• Teilung von I in n Unterintervalle ( Buckets)
  1. Verteilen der Elemente in die Buckets
  2. Sortieren der Buckets
  3. Aneinanderhängen der sortierten Teillisten

BucketSort(A) 
  n := length(A);

  for i=1 to n
    do insert A[i] into list B[floor (n * A[i])];

  for i=0 to n-1
    do sort list B[i] with insertion sort;

  concatenate lists B[0], B[1], B[n-1] together;

• Alles linear bis auf Insertionsort = quadratisch
• Zufallsvariable n_i: Anzahl der Elemente in B[i].
• Insertionsort quadratisch Þ erwarteter Gesamtaufwand:

  n-1 å i=0

  O ( E(ni2)) = O

  æ ç ç è

  n-1 å i=0

  ( E(ni2))

  ö ÷ ÷ ø

• Verteilung von n_i: Binomialverteilung B(k,n,p=1/n)
  P(n_i = k) = n kp^k q^n-k
• E(n_i) = 1 und Var(n_i) = 1- 1/n.
• E(n_i²) = Var(n_i)+ E(n_i)² = 2 - 1/n = O(1)
• Þ
  T(n) = O(n)