Schnelle Sortierung

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 Schnellsortieralgorithmus 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 <stdlib.h>
#include <stdio.h>
#include <stdint.h>

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 < 11; ++i)
    {
        printf("%u ", list[i]);
    }

    return EXIT_SUCCESS;
}

// Just a helper to have a cleaner interface
void quick_sort(uint32_t *arr, size_t size)
{
    // Note: here we are passing the high bound as the size - 1,
    // so in here we are having an inclusive range
    // this is important because it makes the algorithm slightly simpler
    // and it requires less -1's which usually causes a lot of off-by one mistakes
    _quick_sort(arr, 0, size - 1);
}

size_t partition(uint32_t *arr, size_t low, size_t high)
{
    // Partition is the operation that puts all the elements smaller than the pivot
    // We are picking the last element as the pivot always,
    // I guess we could be more clever and pick a random element
    // or the median of the first, middle and last elements
    // but this is just a simple example
    size_t pivot_index = high;
    uint32_t pivot = arr[pivot_index];

    // This is going to be the index of the pivot at the end
    // of the loop
    size_t i = low;
    for (size_t j = low; j <= high; ++j)
    {
        // If the current element is less than the pivot,
        // we swap it with the element at index i
        // and increment i,
        // doing this we will know exacyly where the pivot
        // should be placed after the iteration is done
        // because all the elements of index < i are less than the pivot
        // and all the elements of index > i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] < pivot)
        {
            uint32_t temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;

            ++i;
        }
    }

    // putting the pivot at the right spot, remember, it could've been anywhere
    arr[pivot_index] = arr[i];
    arr[i] = pivot;

    return i;
}

void _quick_sort(uint32_t *arr, size_t low, size_t high)
{
    // The main idea of this function, is to use a window, that has the bounds
    // [low, high] inclusive, so if the window has length 0, low = high
    // it means we reached our base case, and the list is already sorted
    // since an array without elements is always going to be sorted
    // I guess
    if (low >= 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 das Teil keine Elemente mehr hat. In diesem Fall können wir sicher sein, dass es richtig sortiert ist.

Es gibt eine wichtige Nuance bei der Auswahl eines Pivots im Schnellsortierungsalgorithmus: Wenn wir schlechte Pivots auswählen, erhalten wir am Ende eine schreckliche Komplexität, denn jedes Mal, wenn wir das Array in zwei Arrays aufteilen, erhalten wir am Ende 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.

Das obige ist der detaillierte Inhalt vonSchnelle Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!