Sortieralgorithmen: Quick sort

In den letzten Beiträgen wurden 3 "einfache" Sortieralgorithmen vorgestellt. Es musste lediglich eine Liste durchlaufen und die Indizes nach einer Prozedur überprüft und gegebenenfalls vertauscht werden.

Der Quick sort ist zunächst auch nur ein Sortieralgorithmus. Ein großer Unterschied zum z.B. Bubble sort ist, dass dieses Verfahren auf eine Rekursion basiert. Das heißt, die Funktion ruft sich selber innerhalb der eigenen Funktion auf. Dies passiert solange bis eine geeignete Abbruchbedingung erfüllt wird.

Ein weiterer Unterschied ist das divide and conquer-Prinzip (Teile und herrsche). Dazu wird die zu sortierende Liste in zwei Teile aufgeteilt. Diese zwei Teillisten werden dann wieder in Teillisten aufgeteilt usw. Der Index, wo die Liste aufgeteilt wird nennt sich Pivotelement. Alle Elemente die kleiner sind als das Pivotelement kommen auf die linke Seite und die restlichen Elemente auf die rechte Seite.

Nun werden alle Teillisten rekursiv sortiert. Sobald eine Teilliste nur noch ein Element hat, wird die Rekursion für diese Teilliste abgebrochen. Nach dem sortieren werden alle Teillisten noch zusammengefügt bis man die Ursprügliche Liste hat nur mit dem Unterschied, dass alle Elemente sortiert sind.

• Quick sort (c++)

#include <iostream>

void quickSort(int *list, unsigned int left, unsigned int right){
    unsigned int i = left;
    unsigned int j = right;
    unsigned int temp;
    
    // initial splitelement
    int pivot = list[((right + left) / 2)];

    while( i <= j ){
        while( list[i] < pivot ){
            i++;
        }

        while( list[j] > pivot ){
            j--;
        }

        if( i <= j ){
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            i++;
            j--;
        }
    }

    if( left < j){
        quickSort(list, left, j);
    }
    if( i < right ){
        quickSort(list, i, right);
    }
}

int main(){
    const unsigned int SIZE = 10;
    int list[SIZE] = {5,3,8,1,14,4,7,11,3,2};
    quickSort(list,0,SIZE-1);
    
    for(unsigned int res = 0; res < SIZE; res++){
        std::cout << list[res] << "\n";
    }
    
    return 0;
}

Abbildung 1: Prinzip beim Divide and Conquer

Quelle
Abbildung 1: https://qph.fs.quoracdn.net/main-qimg-34e9fa71e56b7e2656b7925bf072f327-c
https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf, pp. 4ff. [letzter Zugriff: 05.02.2020, 18:45]