Algorithme de tri rapide

Le tri rapide est l'un des algorithmes de tri les plus connus, car il est implémenté dans plusieurs langages de programmation au sein de la bibliothèque standard. Pourquoi cet algorithme est-il si utilisé ??
En raison de sa vitesse, l'algorithme de tri rapide est l'un des algorithmes de tri les plus rapides avec une complexité temporelle de O(n * log n) où n est la taille du tableau et log est la base du logarithme 2.

Comment ça marche?

Le concept principal nécessaire pour comprendre l'algorithme de tri rapide est la stratégie diviser pour régner.
La stratégie « diviser pour régner » est un terme militaire célèbre, qui signifiait autrefois que pour conquérir une grande nation, il fallait d'abord créer la nation, divisée, souvent par un conflit interne ou une guerre civile, puis balayer la nation entière pendant qu'elle était en guerre. occupé.
Ok, mais comment ce concept se traduit-il en informatique ? Le diviser pour régner, dans les algorithmes, signifie qu'il résout un problème en résolvant des problèmes plus petits, ceci est assez similaire au concept d'induction mathématique, dans lequel, on établit f(1), puis on établit f(n) et ensuite, nous montrons que f(n - 1) fonctionne, ce faisant, nous pouvons prouver un concept.
Les problèmes Diviser pour mieux régner fonctionnent de la même manière, d'abord nous résolvons le problème le plus simple, souvent appelé cas de base, puis nous formulons le cas récursif et, enfin, nous faisons en sorte que le problème soit décomposé en problèmes les plus simples, parce que ceux que nous savons résoudre.

L'algorithme

Je vais montrer une implémentation en C, puis je vais expliquer ligne par ligne comment cela fonctionne, car c'est une idée assez compliquée.

#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);
}

Donc, l'idée principale de l'algorithme est plutôt simple, divisez le tableau partitionnant la liste en deux parties, une dans laquelle tous les éléments sont plus petits que le pivot et une dans laquelle tous les éléments sont plus grands que le pivot.
Et puis, appliquez récursivement cet algorithme aux pièces elles-mêmes, jusqu'à ce que la pièce ne contienne aucun élément, dans ce cas, nous pouvons être sûrs qu'elle est correctement triée.

Il y a une nuance importante dans le choix d'un pivot dans l'algorithme de tri rapide : si nous choisissons de mauvais pivots, nous allons nous retrouver avec une terrible complexité, car chaque fois que nous divisons le tableau en deux tableaux, nous nous retrouvons avec de petits tableaux, dans ce cas, nous allons avoir n appels récursifs et nous devrons parcourir n éléments, donc le tri rapide a le pire des cas de O(n*n), ce qui est horrible, nous devons donc être prudents lorsque en choisissant un pivot, une bonne approche consiste à choisir un nombre aléatoire, ce faisant, nous sommes presque sûrs d'obtenir le cas médian, qui est O(n * log n), log n puisque dans le cas moyen, nous diviserons le tableau en deux tableaux qui ont la moitié des éléments du tableau initial, et comme il faut parcourir tous les éléments, il y a un facteur n.