Tri rapide

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, en faisant cela, 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 <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);
}

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 n'ait plus d'éléments, 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 complexité terrible, 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.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!