QuickSort QuickSort

Prinzip: Teile und herrsche!

Algorithmus Beispiel
  1. Ein Trennelement wird ausgewählt.
    (z.B.: das erste Element, das letzte Element oder das in der Mitte stehende Element)

  2. Von oben (o) wird begonnen und eine Element gesucht, dass kleiner oder gleich dem Trennelement ist.
    Von unten (u) wird ein Element gesucht, dass größer oder gleich dem Trennelement ist.
    Diese Elemente werden getauscht.
    Falls sich der ober und der untere Zeiger kreuzen, wird an dieser Stelle die Reihung in zwei neue Teilfelder geteilt.
    (Im unteren Teilfeld sind nun alle Elemente, die kleiner oder gleich dem Trennelement sind. Im oberen Teilfeld sind diejenigen, die größer oder gleich dem Trennelement sind.)

  3. Die Schritte 1 und 2 werden so lange rekursiv auf die Teilfelder angewendet, bis in jedem nur noch ein Element ist.
 Trennelement = 3
u o
1 8 4 3 4 7 0

Trennelement = 3
u o
1 8 4 3 4 7 0

Trennelement = 3
u o
1 0 4 3 4 7 8

Trennelement = 3
o u
1 0 3 4 4 7 8

Der untere Zeiger (u) und der obere Zeiger (o) haben sich gekreuzt, es entstehen neue Teilfelder.

Sortiere weiter:

Teilfolge 1 mit
Trennelement = 0
u o
1 0 3

und Teilfolge 2 mit
Trennelement = 4
u o
4 4 7 8



Zeitabhängigkeit:
  • schlechtester Fall: quadratisch
  • mittlerer und bester Fall: n*log(n)
Quelltext (Auszug):


   /**
    Durch diese Methode wird das Sortieren gestartet.
   */

   public void sort()

   { 

      sort(0, a.length - 1);

   }


/* Diese Methode sort ist u.a. für das Auslösen des Sortiervorganges in den entstehenen Teilfelder verantwortlich. Sie ist rekursiv! */

   public void sort(int from, int to)

   {

      if (from < to)
    {
      int p = partition(from, to);

      sort(from, p);

      sort(p + 1, to);

    }
   }

/* Die Methode partition realisiert Schritt zwei: Durchlaufen einer gegebenen Reihung und eventuell notwendige Tauschoperationen. */

   private int partition(int from, int to)

   {

      int pivot = a[from];

      int i = from - 1;

      int j = to + 1;

      while (i < j)

      {

         i++; while (a[i] < pivot) i++;

         j--; while (a[j] > pivot) j--;

         if (i < j) swap(i, j);

      }

      return j;

   }



   /**

      Die Methode swap tauscht zwei Elemente der Reihung.

   */

   private void swap(int i, int j)

   {

      int temp = a[i];

      a[i] = a[j];

      a[j] = temp;

   }

}


Quelltexte im Zip-Format zum herunter laden

Aufgaben:
  1. Erläutern Sie, wie Teilfolge 1 weiter sortiert wird!
  2. Stellen Sie die Methoden sort(int from, int to) und partition(int from, int to) in je einem Struktogramm dar!
  3. Untersuchen Sie das Zeitverhalten des Algorithmus experimentell!