Quick-Sort

aus www.iwiki.de, der freien Wissensdatenbank

Quick-Sort ist eines der schnellsten und zugleich einfachsten Sortierverfahren, es arbeitet rekursiv nach dem Teile-und-Herrsche-Prinzip.

Inhaltsverzeichnis

1 Prinzip
2 Beispiel
3 Implementierung
4 Weblink

[bearbeiten]

Prinzip

Die Folge der zu sortierenden Daten wird in zwei Bereiche getrennt. Dies erfolgt durch Auswahl des mittleren Elements (Pivotelement p) durch ganzzahlige Division der Listenlänge. Ein Bereich befindet sich rechts (R) vom mittleren Element, der andere links (L).

L soll nur Elemente enthalten, die < p sind. R soll nur Elemente enthalten, die >= p sind.

Zähler i durchläuft L von links nach rechts, bis er einen Wert findet, der > p ist. Zähler j durchläuft R von rechts nach links, bis er eine Wert findet, der < p ist.

Sind beide Werte gefunden, werden diese miteinander vertauscht. Die beiden Zähler laufen solange, bis sie beim Mittelwert angelangt sind. Anschließend wird in L und R das mittlere Element bestimmt. Die Teilfolgen werden ihrerseits in zwei Bereiche unterteilt. Die Zähler werden gestartet.

Das Aufsplittern der Bereiche und Vertauschen der Elemente wird solange ausgeführt, bis die Elementfolge sortiert ist.

(das Pivotelement muss sich nicht unbedingt in der Mitte der zu sortierenden Elementenfolge befinden)

[bearbeiten]

Beispiel

[bearbeiten]

Implementierung

Quicksort (int data[],int left,int right) {
  int mid,tmp,i,j;
  i = left;
  j = right;
  mid = data[(left + right)/2];
  do {
       while(data[i] < mid)
          i++;
      while(mid < data[j])
          j--;
      if (i <= j) {
          tmp = data[i];
          data[i] = data[j];
          data[j] = tmp;
          i++;
          j--;
      }
  } while (i <= j);
  if (left < j) Quicksort(data,left,j);
  if (i < right) Quicksort(data,i,right);
}

[bearbeiten]