Sortieren in linearer Zeit

under construction

Wir kehren an dieser Stelle nochmals zum Sortierproblem zurück und stellen uns die Frage, ob wir noch schnellere Algorithmen finden können, die eventuell sogar in O(N) statt in O(N*log(N))zum Ziel kommen. Mit Hilfe der gerade eingeführten Suchbäumen werden wir zeigen, dass dies nicht möglich ist, solange für die Sortierschlüssel nur eine paarweise Vergleichsfunktion definiert ist. Besitzen wir jedoch zusätzliche Informationen über die Schlüssel, die uns die Anwendung des Bucket-Prinzips erlauben, ist das Sortieren in linearer Zeit möglich.

Sortieren und Permutationen

Bevor wir die Grenzen des Sortierens mit Paarvergleichen analysieren, wollen wir noch etwas näher beleuchten, was beim Sortieren eigentlich geschieht. Dazu gehen wir noch einen Schritt zurück und schauen uns an, was beim Mischen eines zunächst sortierten Arrays passiert. Wir betrachten das Array mit den drei Element A, B, C sowie ein korrespondierendes Indexarray, das angibt, an welcher Position im sortierten Array die drei Elemente gehören. Solange das Hauptarray noch sortiert ist, enthält das Indexarray einfach die aufsteigende Folge 0, 1, 2:

  L = A B C     # Hauptarray sortiert (0. Permutation)
  I = 0 1 2     # Indexarray

Es gibt jetzt 5 weitere Anordnungsmöglichkeiten (imsgesamt also 6 = 3! Permutationen) für die drei Elementa A, B und C. Immer, wenn wir diese drei Elemente umordnen, ordnen wir das Indexarray so, dass das Element I[k] in jedem Indexarray uns angibt, wo sich der Buchstabe jetzt befindet, der ursprünglich (also in der sortierten Anordnung) an Position k stand:

  L = A C B     # 1. Permutation
  I = 0 2 1 

  L = B A C     # 2. Permutation
  I = 1 0 2

  L = B C A     # 3. Permutation
  I = 2 0 1

  L = C A B     # 4. Permutation
  I = 1 2 0

  L = C B A     # 5. Permutation
  I = 2 1 0

In der 5. Permutation sagt beispielsweise I[0] = 2, dass der ursprünglich 0. Buchstabe (das A) jetzt an Position 2 ist. Daraus folgt, dass wir ein permutiertes Array in linearer Zeit sortieren können, wenn uns das Indexarray bekannt ist. Wir müssen einfach einmal durch das Indexarray gehen und jedes Element von Position I[k] wieder an Position k verschieben:

  def sortByIndexArray(L, I):
      R = [None]*len(L)        # zunächst leeres Ergebnisarray
      for k in xrange(len(L)):
          R[k] = L[I[k]]       # Elemente sortiert in R einfügen
      return R

Da man nur einmal über den Bereich k = 0 ... len(L)-1 gehen muss, ist der Aufwand dieser Funktion O(len(L)), also linear. Dieser Algorithmus ist z.B. nützlich, wenn man mehrere Arrays in der gleichen Weise sortieren muss, z.B. die Liste der Studentennamen und die Liste der dazugehörigen Übungspunkte. Man kann dann einfach einmal die Permutation des Indexarrays bestimmen, und dann alle Listen entsprechend sortieren. Wie man das Indexarray mit dem Standard-Sortieralgorithmus array.sort() bestimmen kann, ist Aufgabe im Übungsblatt 9.

Sortieren als Suchproblem

Wir haben gesehen, dass wir in linearer Zeit sortieren können, wenn uns die Permutation bzw. das zugehörige Indexarray bekannt ist. Die nächste Frage lautet deshalb: Wie viele Schritte brauchen wir, um die Permutation zu finden? Dabei ist es nur erlaubt, Schlüssel paarweise zu vergleichen, und man erhält jeweils eine ja/nein Antwort. Ein solches Vorgehen kann als Entscheidungsbaum dargestellt werden. Jeder Knoten ist eine Frage, und wir gehen zum linken Kind weiter, wenn die Frage mit "ja" beantwortet wurde, ansonsten zum rechten Kind. An jeder Kante stehen die jetzt noch in Frage kommenden Permutationen, und der jeweilige Kindknoten gibt uns die nächste Frage vor. Die Blätter enthalten das Indexarray, das der Permutation entspricht:

                                 (L[0] < L[1])
                         ja     /             \  nein
                       ABC     /               \    BAC
                       ACB    /                 \   CAB
                       BCA   /                   \  CBA
                            /                     \
                     (L[0] < L[2])           (L[0] < L[2])
                    /            \           /            \
              ja   /        nein  \         /  ja          \  nein
            ABC   /          BCA   |       |   BAC          \   CAB
            ACB  /                 |       |                 \  CBA
                /               (2 0 1) (1 0 2)               \
         (L[1] < L[2])                                   (L[1] < L[2])
         /            \                                 /             \
    ja  /              \  nein                    ja   /               \  nein
  ABC  /                \   ACB                 CAB   /                 \   CBA
      /                  \                           /                   \
   (0 1 2)             (0 2 1)                   (1 2 0)               (2 1 0)

Der Suchaufwand im sclechtesten Fall entspricht offensichtlich der Tiefe des Baumes. Bei Arrays mit drei Elementen ist die Tiefe gerade 3, wir benötigen maximal 3 Fragen bis zum Ziel. Für Arrays der Länge n gilt allgemein: Es gibt N = n! verschiedene Permutationen, der Baum muss also n! Blätter haben. Wir haben im Abschnitt Suchen gesehen, dass die Tiefe eines Baumes minimal wird, wenn der Baum perfekt balanciert ist, und dass der balancierte Baum mit den meisten Blättern der vollständige Baum ist. Die Tiefe des vollständigen Baums mit n! Blättern gibt uns also eine untere Schranke für die minimale Anzahl der Vergleiche im schlechtesten Fall.

Ein vollständiger Baum der Tiefe d hat 2^d+1-1 Knoten und 2^d Blätter:

vollständiger Baum 2d+1-1 Knoten 2d 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!)</math>

Wir können die Tiefe am einfachsten durch die Stirlingsche Näherungsformel für die Fakultät abschätzen:

<math>n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n</math>,

die asymptitisch für große n gilt. Einsetzen liefert

<math>d \ge \log_2(n!) \in \Omega\left(\log_2\left(\sqrt{2\pi n} \left(\frac{n}{e}\right)^n\right)\right)</math>

Der Logarithmus eines Produkts ist gleich der Summe der Logarithmen der einzelnen Faktoren:

<math>\Omega\left(\log_2\left(\sqrt{2\pi n} \left(\frac{n}{e}\right)^n\right)\right) = \Omega(\log_2(\sqrt{2\pi})) + \Omega(\log_2(\sqrt{n})) + \Omega(\log_2(n^n)) - \Omega(\log_2(e^n))</math>

Wir vereinfachen die rechte Seite nach den Regeln der O-Notation: nur der am schnellsten wachsende Term bleibt übrig:

<math>\Omega\left(\log_2\left(\sqrt{2\pi n} \left(\frac{n}{e}\right)^n\right)\right) = \Omega(\log_2(n^n))</math>.

Den Exponenten in nⁿ kann man vor den Logarithmus ziehen, und die Basis des Logarithmus spielt keine Rolle. Wir erhalten somit:

<math>d \in \Omega(n \log n)</math>.

Somit braucht man im schlechtesten Fall mindestens <math>\Omega(n \log n)</math> Vergleiche, und Merge Sort ist somit optimal und kann nicht weiter verbessert werden, solange man sich auf paarweise Vergleiche von Schlüsseln beschränkt.

Eine exakte Herleitung dieser Tatsache, ohne Verwendung der Stirlingschen Formel, ist möglich durch

Abschätzung von Summen durch Integrale

Schreibt man die Fakultät als Produkt aus, und transformiert den Logarithmus des Produkts in eine Summe von Logarithmen, erhalten wir:

<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

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:

<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₁ und x₂ 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₁+1 = 2, und x₂ = 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.

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

Bucket Sort 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)

Nächstes Thema