Der QuickSort-Algorithmus ist ein effizienter, rekursiv arbeitender Algorithmus, der sich als Standard für Sortierprobleme etabliert hat. Er arbeitet nach dem Divide-and-Conquer-Prinzip (Teile und Herrsche) und teilt die zu sortierende Liste immer wieder in zwei kleinere Teillisten auf. Dabei enthält die linke Teilliste jeweils nur Elemente, die kleiner als oder gleich einem Vergleichselement (Pivot-Element) sind und die rechte nur Elemente, die größer als oder gleich dem Pivot-Element sind. Der gleiche Algorithmus wird nun auf diese beiden kleineren Teillisten angewandt. Wenn am Ende die Teillisten nur noch genau ein Element enthalten, dann ist die Sortierung fertig.

Eine Implementierung in C für int-Arrays.

/// @param values Zeiger auf erste das Element des zu sortierenden Arrays
/// @param left Linke Grenze des zu sortierenden "Teil-Arrays"
/// @param right Rechte Grenze des zu sortierenden "Teil-Arrays"
void QuickSort (int *values, size_t left, size_t right)
{
  size_t i = left, j = right;                  // Zählindizes
  int pivot = values[ (left + right) >> 1 ];   // Pivot-Element (Array-Mitte) bestimmen
  int tmp;                                     // Temporäre Variable zum Tauschen der Werte
 
  // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben
  do
  {
    // Paar finden, das getauscht werden muss
    while ( values[i] <= pivot ) ++i;
    while ( pivot <= values[j] ) --j;
 
    // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen
    // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife
    if (i < j)
    {
      tmp = values[i];
      values[i] = values[j];
      values[j] = tmp;
 
      ++i;
      --j;
    }
    else if (i == j)
    {
      ++i;
      --j;
      break;
    }
  } while (i <= j);
 
  // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an
  if (left < j) QuickSort(values, left, j);
  if (i < right) QuickSort(values, i, right);
}

Eine Implementierung in C++ für Arrays beliebiger Datentypen, die den kleiner als-Operator unterstützen.

// Tauschalgorithmus einbinden
#include <algorithm>
 
/// @param values Zeiger auf das erste Element des zu sortierenden Arrays
/// @param left Linke Grenze des zu sortierenden "Teil-Arrays"
/// @param right Rechte Grenze des zu sortierenden "Teil-Arrays"
template< typename T >
void QuickSort (T *values, size_t left, size_t right)
{
  size_t i = left, j = right;                // Zählindizes
  T pivot = values[ (left + right) >> 1 ];   // Pivot-Element (Array-Mitte) bestimmen
 
  // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben
  do
  {
    // Paar finden, dass getauscht werden muss
    while ( values[i] <= pivot ) ++i;
    while ( pivot <= values[j] ) --j;
 
    // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen
    // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife
    if (i < j)
    {
      std::swap( values[i], values[j] );
      ++i;
      --j;
    }
    else if (i == j)
    {
      ++i;
      --j;
      break;
    }
  } while (i <= j);
 
  // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an
  if (left < j) QuickSort(values, left, j);
  if (i < right) QuickSort(values, i, right);
}

Eine Implementierung eines QuickSort-Algorithmus für eine Integerliste in Haskell:

qs :: [Int] -> [Int]
qs [] = []
qs (x:xs) = qs [y | y <- xs , y < x] ++ [x] ++ qs[y | y <- xs , y >= x]

QuickSort weist im Gegensatz zu vielen anderen Sortieralgorithmen eine Eigenschaft auf, die sich Instabilität nennt. Nach außen hin gleiche Elemente im Array behalten nach dem Sortieren nicht unbedingt ihre Ausgangsreihenfolge. Diese Eigenschaft kann ein Problem darstellen, wenn man strukturierte Daten nach verschiedenen Kriterien Sortieren will. Dies lässt sich am besten anhand eines Beispielcodes verdeutlichen; der hier dargestellte Code könnte ein Ausschnitt aus einer Verwaltungssoftware sein.

// Funktionen printf, memcpy und strncpy einbinden
#include <stdio.h>
#include <string.h>
 
// Legt fest, wie viele Zeichen eine Zeichenkette maximal haben soll
#define STRING_LENGTH 32
 
// Struktur, in der relevante Daten zu Personen zusammengefasst werden
struct Person
{
    char Name[STRING_LENGTH];      // Nachname
    char Forename[STRING_LENGTH];  // Vorname
};
 
// Sortiert ein Array von Personen nach Nachnamen
/// @param persons Zeiger auf erste das Element des zu sortierenden Arrays
/// @param left Linke Grenze des zu sortierenden "Teil-Arrays"
/// @param right Rechte Grenze des zu sortierenden "Teil-Arrays"
void QuickSort_Name (struct Person *persons, size_t left, size_t right)
{
  size_t i = left, j = right;  // Zählindizes
  char pivot[STRING_LENGTH];   // Pivotelement
  Person tmp;                  // Temporäre Variable zum Tauschen der Werte
 
  // Pivotelement bestimmen
  strncpy( pivot, persons[ (left + right) >> 1 ].Name, STRING_LENGTH );  
 
  // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben
  do
  {
    // Paar finden, dass getauscht werden muss
    while (strncmp( persons[i].Name, pivot, STRING_LENGTH ) <= 0) ++i;
    while (strncmp( pivot, persons[j].Name, STRING_LENGTH ) <= 0) --j;
 
    // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen
    // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife
    if (i < j)
    {
      memcpy( &tmp, &persons[i], sizeof(struct Person) );
      memcpy( &persons[i], &persons[j], sizeof(struct Person) );
      memcpy( &persons[j], &tmp, sizeof(struct Person) );
 
      ++i;
      --j;
    }
    else if (i == j)
    {
      ++i;
      --j;
      break;
    }
  } while (i <= j);
 
  // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an
  if (left < j) QuickSort_Name(persons, left, j);
  if (i < right) QuickSort_Name(persons, i, right);
}
 
// Sortiert ein Array von Personen nach Vornamen
/// @param persons Zeiger auf erste das Element des zu sortierenden Arrays
/// @param left Linke Grenze des zu sortierenden "Teil-Arrays"
/// @param right Rechte Grenze des zu sortierenden "Teil-Arrays"
void QuickSort_Forename (struct Person *persons, size_t left, size_t right)
{
  size_t i = left, j = right;  // Zählindizes
  char pivot[STRING_LENGTH];   // Pivotelement
  Person tmp;                  // Temporäre Variable zum Tauschen der Werte
 
  // Pivotelement bestimmen
  strncpy( pivot, persons[ (left + right) >> 1 ].Forename, STRING_LENGTH );  
 
  // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben
  do
  {
    // Paar finden, dass getauscht werden muss
    while (strncmp( persons[i].Forename, pivot, STRING_LENGTH ) < 0) ++i;
    while (strncmp( pivot, persons[j].Forename, STRING_LENGTH ) < 0) --j;
 
    // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen
    // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife
    if (i < j)
    {
      memcpy( &tmp, &persons[i], sizeof(struct Person) );
      memcpy( &persons[i], &persons[j], sizeof(struct Person) );
      memcpy( &persons[j], &tmp, sizeof(struct Person) );
 
      ++i;
      --j;
    }
    else if (i == j)
    {
      ++i;
      --j;
      break;
    }
  } while (i <= j);
 
  // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an
  if (left < j) QuickSort_Forename(persons, left, j);
  if (i < right) QuickSort_Forename(persons, i, right);
}
 
int main (void)
{
  // Array für Personen anlegen und ausgeben
  struct Person persons[4];
  strncpy( persons[0].Name,     "Mueller", STRING_LENGTH );
  strncpy( persons[0].Forename, "Heinrich", STRING_LENGTH );
  strncpy( persons[1].Name,     "Schulze", STRING_LENGTH );
  strncpy( persons[1].Forename, "Walter", STRING_LENGTH );
  strncpy( persons[2].Name,     "Mueller", STRING_LENGTH );
  strncpy( persons[2].Forename, "Maria", STRING_LENGTH );
  strncpy( persons[3].Name,     "Schmidt", STRING_LENGTH );
  strncpy( persons[3].Forename, "Johanna", STRING_LENGTH );
  for (int i = 0; i < 4; ++i)
    printf( "%d --- %s, %s\n", i, persons[i].Name, persons[i].Forename );
  printf("\n");
 
  // Nach Vornamen sortieren und ausgeben
  QuickSort_Forename(persons, 0, 3);
  for (int i = 0; i < 4; ++i)
    printf( "%d --- %s, %s\n", i, persons[i].Name, persons[i].Forename );
  printf("\n");
 
  // Nach Nachnamen sortieren und ausgeben
  QuickSort_Name(persons, 0, 3);
  for (int i = 0; i < 4; ++i)
    printf( "%d --- %s, %s\n", i, persons[i].Name, persons[i].Forename );
  printf("\n");
 
  // positiven Statuscode zurückgeben
  return 0;
}

Bei Ausführung gibt das Programm folgendes aus:

0 - Mueller, Heinrich
1 - Schulze, Walter
2 - Mueller, Maria
3 - Schmidt, Johanna

0 - Mueller, Heinrich
1 - Schmidt, Johanna
2 - Mueller, Maria
3 - Schulze, Walter

0 - Mueller, Maria
1 - Mueller, Heinrich
2 - Schmidt, Johanna
3 - Schulze, Walter

Wie man sieht werden Heinrich und Maria, die den gleichen Nachnamen haben, beim ersten Sortieren (Vorname) in die richtige Reihenfolge gebracht. Allerdings geht diese Reihenfolge beim zweiten Sortiervorgang (Nachname) verloren. Mit einem Sortieralgorithmus à la BubbleSort oder SelectionSort hat man dieses Problem nicht.

Da der QuickSort-Algorithmus erfahrungsgemäß nicht immer auf Anhieb zu verstehen ist folgt hier ein Beispieldurchlauf. Auch hier wird noch einmal das Problem Instabilität gezeigt. Dazu werden die beiden äußerlich identischen Elemente „66“ jeweils mit einer Zahl versehen, die auf das Sortieren an sich allerdings keinen Einfluss hat.

Die fiktive Liste

Pivotelement suchen

Zu tauschendes Paar suchen

Tauschen und Zählindizes weiterzählen

Fortsetzen bis sich die Zählindizes „getroffen“ haben

Mit Teilliste 1 fortfahren (Elemente 0 bis 2)

Teilliste 1.1 enthält nur Element 0
Mit Teilliste 1.2 fortfahren (Elemente 1 und 2)

Teilliste 1.2.1 enthält nur Element 1 Teilliste 1.2.2 enthält nur Element 2
Mit Teilliste 2 fortfahren (Elemente 3 bis 8)

Mit Teilliste 2.1 fortfahren (Elemente 3 und 4)

Teilliste 2.1.1 enthält nur Element 3 Teilliste 2.1.2 enthält nur Element 4
Mit Teilliste 2.2 fortfahren (Elemente 5 bis 8)

Mit Teilliste 2.2.1 fortfahren (Elemente 5 und 6)

Teilliste 2.2.1.1 enthält nur Element 5 Teilliste 2.2.1.2 enthält nur Element 6
Mit Teilliste 2.2.2 fortfahren (Elemente 7 und 8)

Teilliste 2.2.2.1 enthält nur Element 7 Teilliste 2.2.2.2 enthält nur Element 8
Zusammensetzen aller Teillisten bzw. Einzelelemente

Mit dem Layout bin ich total unzufrieden.

Animation

Autorendiskussion