View source for Sortieren in linearer Zeit

===Sortieren als Suchproblem===

Stellt man systematisch Fragen, die nur mit True oder False beantwortet werden können, kann dieses Vorgehen auch als Entscheidungsbaum dargestellt werden.<br> [[Image:penka.png|400px]]

Als Beispiel verwenden wir den Algorithmus zum Sortieren von drei Elementen aus der Vorlesung über [[Sortieren]]. Als Eingabe sind drei Zahlen vorgegeben a={1,2,3}, deren Reihenfolge (Permutation) nicht bekannt ist. Wie die Illustration für den linke Hälfte des Entscheidungsbaumes zeigt, können wir die Reihenfolge mit nur 3 Fragen herausbekommen.
[[Image:trueFalseBeisp.png|700px]]<br> (Die Reihenfolge der Antworten ''True, False, True'' kann allerdings gar nicht auftreten, weil sie widersprüchlich ist ('''<font color=red>bitte aus der Graphik löschen!</font>''')<br>Die allgemeine Regel lautet: Wenn es N mögliche Lösungen gibt, muss der Baum N Blätter haben. Wie wir oben gezeigt haben, hat ein Baum mit N Blättern mindestens die Tiefe log(N).

{| border="0" cellspacing="0" cellpadding="5" 
|-valign="center" 
|[[Image:vollbaum.png|left]]
| vollständiger Baum [http://hci.iwr.uni-heidelberg.de/alda/index.php/Suchen#Balance_eines_Suchbaumes]<br>2<sup>d+1</sup>  Knoten<br>2<sup>d</sup> Blätter
|}

Im Fall des Sortierens von n Elementen gilt, dass es N = n! mögliche Permutation gibt. Ein Baum mit n! Blättern hat mindestens die Tiefe log(n!). Im obigen Beispiel für n=3 gilt 3! = 1*2*3 = 6 und damit für die Tiefe d
:::<math>d = \lceil \log_2(6)\rceil \approx \lceil 2.6\rceil = 3</math>
Im ungünstigsten Fall braucht man bei dem Frage-Baum drei Schritte. Weil aber <math>\log(6)\approx 2.6 < 3</math> muss nicht jeder Pfad zu Ende durchlaufen werden, um die Lösung zu bekommen.

Allgemein gilt
::<math>d \ge \log_2(n!) = \log_2(1\cdot 2\cdot ... \cdot n) = \log_2(1) + \log_2(2) + ... + \log_2(n) = \sum_{k=1}^n \log_2(k) = \frac{1}{\ln(2)}\sum_{k=1}^n \ln(k) = \frac{1}{\ln(2)}\sum_{k=2}^n \ln(k)</math>
Die letzte Identität gilt, weil <math>\ln(1) = 0</math> in der Summe weggelassen werden kann. Eine untere Schranke für die Tiefe kann man explizit bestimmen durch die Methode der
 
====Abschätzung von Summen durch Integrale====

Gegeben sei eine monoton wachsende Funktion f(x) (blaue Kurve). Das bestimmte Integral über die Funktion sei
:::<math>\int_{x_1}^{x_2} f(x)dx</math>. 
Wenn wir das Funktionsargument x abrunden (schwarze Kurve), entsteht ein Integral, das einen kleineren Wert als das ursprüngliche Integral hat. Runden wir auf (rote Kurve), entsteht ein Integral mit einem größeren Wert:

{| border="0" cellspacing="0" cellpadding="5" 
|-valign="center" 
|[[Image:integralGraph.png|400px|left]]
| <math>\int_{x_1}^{x_2} f(\lfloor x \rfloor)dx \le \int_{x_1}^{x_2} f(x)dx \le \int_{x_1}^{x_2} f(\lceil x \rceil)dx</math>
|}
In unserem Zusammenhang sind x<sub>1</sub> und x<sub>2</sub> positive ganze Zahlen. Deshalb gilt
:::<math>f(\lfloor x \rfloor)_{x_1}^{x_1+1}= f(x_1),</math>
:::<math>f(\lfloor x \rfloor)_{x_1+1}^{x_1+2}= f(x_1+1)</math>
:::<math>...</math>
:::<math>f(\lfloor x \rfloor)_{x_2-1}^{x_2}= f(x_2-1)</math>
Wir können die obigen Integrale daher folgendermaßen vereinfachen:
:::<math>\begin{array}{lcl}
\int_{x_1}^{x_2} f(\lfloor x \rfloor) dx &=& \int_{x_1}^{x_1 + 1} f(\lfloor x \rfloor) dx + ...+ \int_{x_2-1}^{x_2} f(\lfloor x \rfloor) dx \\
& = & \int_{x_1}^{x_1 + 1} f(x_1) dx + ...+ \int_{x_2-1}^{x_2} f(x_2-1) dx \\
& = & f(x_1) \int_{x_1}^{x_1 + 1} dx + ...+ f(x_2-1) \int_{x_2-1}^{x_2} dx \\
& = & f(x_1)  + ...+ f(x_2-1) \\
& = & \sum_{k=x_1}^{x_2-1} f(k)
\end{array}</math>
für die Fläche unter den schwarzen Rechtecken sowie
:::<math>\begin{array}{lcl}
\int_{x_1}^{x_2} f(\lceil x \rceil) dx &=& \int_{x_1}^{x_1 + 1} f(\lceil x \rceil) dx + ...+ \int_{x_2-1}^{x_2} f(\lceil x \rceil) dx \\
& = & \int_{x_1}^{x_1 + 1} f(x_1+1) dx + ...+ \int_{x_2-1}^{x_2} f(x_2) dx \\
& = & f(x_1+1) \int_{x_1}^{x_1 + 1} dx + ...+ f(x_2) \int_{x_2-1}^{x_2} dx \\
& = & f(x_1+1)  + ...+ f(x_2) \\
& = & \sum_{k=x_1+1}^{x_2} f(k)
\end{array}</math>
für die Fläche unter den roten Rechtecken. Zusammenfassend gilt also
<math> \sum_{k=x_1}^{x_2-1} f(k) \le \int_{x_1}^{x_2} f(x)dx</math> und 
<math> \sum_{k=x_1+1}^{x_2} f(k) \ge \int_{x_1}^{x_2} f(x)dx</math>
Für unser Problem setzen wir f(k) = ln(k), x<sub>1</sub>+1 = 2, und x<sub>2</sub> = n. Also können wir abschätzen
:::<math>\sum_{k=x_1+1}^{x_2} f(k) = \frac{1}{\ln(2)}\sum_{k=2}^{n} \ln(k) \ge \frac{1}{\ln(2)}\int_1^n \ln(x) dx</math>
Das Integral ist leicht zu lösen, und wir erhalten
:::<math>\frac{1}{\ln(2)}\sum_{k=2}^{n} \ln(k) \ge \frac{1}{\ln(2)}\left[x\ln(x)-x\right]_{x=1}^{n} = \frac{1}{\ln(2)}(n\ln(n)-n+1)=n\log_2(n) - \frac{n-1}{\ln(2)} \in \Omega(n \log(n))</math>
Folglich gilt:
:::<math>d\ge\log_2(n!) = \frac{1}{\ln(2)}\sum_{k=2}^{n} \ln(k) \in \Omega(n \log(n))</math>
Mit anderen Worten: '''Kein Sortieralgorithmus auf Basis paarweise Vergleiche ist asymptotisch schneller als Mergesort, denn die Anzahl der Vergleiche (= Tiefe des Entscheidungsbaumes) ist <math>\Omega(n \log(n))</math>'''. Falls man einen schnelleren Sortieralgorithmus benötigt, muss man ein anderes algorithmisches Prinzip verwenden, siehe dazu Übungsaufgabe 6.2.

==Bucket Prinzip==

Mit dem Bucket Prinzip verteilt man die Schlüssel geschickt auf die "Fächer" (buckets) und arbeitet dann mit jedem Bucket einzeln. 

1) Die Schlüssel sind bereits ganze Zahlen von [0, M)

   def integerSort(a, M):
      buckets = [[] for k in xrange(M)]          #leere buckets
      for k in xrange(len(a)):
         b[a[k].key].append(a[k]) 		#verteilen
      i = 0
      for k in xrange(M):
         a[i : i+len(b[k])] = b[k]
         i += len(b[k])


2) Schlüssel sind keine integer
:-> umwandeln in [0, M)
::- entweder Ordnung erhalten key1 <= key2
:::::::::bucketMap(key1) <= bucketMap(key2)
:::-> "Quantisierung"
				
::- oder Ordnung nicht erhalten
:::-> "Hashing"
		
===Bucket Sort===

<tt>Bucket Sort</tt> sortiert die keys in die buckets.

   def bucketSort(a, bucketMap, c):
      M = int(c * len(a))
      b = [[] for k in xrange(M)]
      for k in xrange(len(a)):
         index = bucketMap(a[k].key, M)
         b[index].append(a[k])
      i = 0
      for k in xrange(M):
         insertionSort(b[k])
         a[i : i + len(b[k])] = b[k]
         i+= len(b[k])


'''Beispiel:'''
keys sind reelle Zahlen in [0, 1)
	
   def bucketMap(key, M):
      return int(key + M)



[[Korrektheit|Nächstes Thema]]