Schnellsortierungsalgorithmus

Die Schnellsortierung ist einer der bekanntesten Sortieralgorithmen, da sie in mehreren Programmiersprachen innerhalb der Standardbibliothek implementiert ist. Warum wird dieser Algorithmus so verwendet??
Aufgrund seiner Geschwindigkeit ist der Schnellsortierungsalgorithmus einer der schnellsten Sortieralgorithmen mit einer zeitlichen Komplexität von O(n * log n), wobei n die Größe des Arrays und log der Logarithmus zur Basis 2 ist.

Wie funktioniert es?

Das Hauptkonzept, das zum Verständnis des Schnellsortierungsalgorithmus erforderlich ist, ist die Divide-and-Conquer-Strategie.
Die „Teile-und-Herrsche-Strategie“ ist ein berühmter militärischer Begriff, der früher bedeutete, dass man zur Eroberung einer großen Nation zunächst die Nation teilen sollte, oft durch interne Konflikte oder Bürgerkriege, und dann die ganze Nation zerstören sollte, während sie gerade ist beschäftigt.
Ok, aber wie lässt sich dieses Konzept auf die Informatik übertragen? Das Teilen und Herrschen in Algorithmen bedeutet, dass er ein Problem löst, indem er kleinere Probleme löst. Dies ähnelt eher dem Konzept der mathematischen Induktion, bei der wir f(1) festlegen, dann f(n) und dann Wir zeigen, dass f(n - 1) funktioniert. Auf diese Weise können wir ein Konzept beweisen.
Teile-und-Herrsche-Probleme funktionieren auf die gleiche Weise: Zuerst lösen wir das einfachste Problem, das oft als Basisfall bezeichnet wird, dann formulieren wir den rekursiven Fall und schließlich zerlegen wir das Problem in die einfachsten Probleme. denn diese wissen wir zu lösen.

Der Algorithmus

Ich werde eine Implementierung in C zeigen und dann Zeile für Zeile erklären, wie das funktioniert, da es sich um eine ziemlich komplizierte Idee handelt.

#include 
#include 
#include 

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i  i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] = high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index   1, high);
}

Die Hauptidee des Algorithmus ist also ziemlich einfach: Teilen Sie die Array-Partitionierung der Liste in zwei Teile auf, einen, in dem alle Elemente kleiner als der Pivot sind, und einen, in dem alle Elemente größer als der Pivot sind.
Und dann wenden Sie diesen Algorithmus rekursiv auf die Teile selbst an, bis der Teil keine Elemente mehr hat. In diesem Fall können wir sicher sein, dass er richtig sortiert ist.

Es gibt eine wichtige Nuance bei der Auswahl eines Pivots im Schnellsortierungsalgorithmus: Wenn wir schlechte Pivots auswählen, erhalten wir eine schreckliche Komplexität, denn jedes Mal, wenn wir das Array in zwei Arrays aufteilen, erhalten wir kleine Arrays, in diesem Fall werden wir n rekursive Aufrufe haben und wir müssen n Elemente durchlaufen, daher hat die schnelle Sortierung ein Worst-Case-Szenario von O(n*n), was schrecklich ist, also mussten wir vorsichtig sein, wann Bei der Auswahl eines Pivots besteht ein guter Ansatz darin, eine Zufallszahl auszuwählen. Auf diese Weise erhalten wir mit ziemlicher Sicherheit den mittleren Fall, nämlich O(n * log n), log n, da wir im Durchschnittsfall aufteilen Teilen Sie das Array in zwei Arrays auf, die die Hälfte der Elemente des ursprünglichen Arrays enthalten, und da wir alle Elemente durchgehen müssen, gibt es einen Faktor von n.