Algoritmo de clasificación rápida

La clasificación rápida es uno de los algoritmos de clasificación más famosos, porque está implementado en varios lenguajes de programación dentro de la biblioteca estándar. ¿Por qué se utiliza tanto este algoritmo?
Debido a su velocidad, el algoritmo de clasificación rápida es uno de los algoritmos de clasificación más rápidos y tiene una complejidad temporal de O(n * log n) donde n es el tamaño de la matriz y log es el logaritmo en base 2.

¿Como funciona?

El concepto principal necesario para comprender el algoritmo de clasificación rápida es la estrategia de divide y vencerás.
La estrategia de dividir y conquistar es un término militar famoso, que solía significar que para conquistar una gran nación primero se debe dividir la nación, a menudo por un conflicto interno o una guerra civil, y luego ir y arrasar con toda la nación mientras ellos están. ocupado.
Bien, pero ¿cómo se traduce este concepto en la informática? El divide y vencerás, en algoritmos, significa que se resuelve un problema resolviendo problemas más pequeños, esto es bastante similar al concepto de inducción matemática, en el que establecemos f(1), luego establecemos f(n) y luego, demostramos que f(n - 1) funciona y, al hacer esto, podemos probar un concepto.
Los problemas de dividir y conquistar funcionan de la misma manera, primero resolvemos el problema más simple, a menudo llamado caso base, luego formulamos el caso recursivo y, por último, hacemos que el problema se descomponga en los problemas más simples. porque esas las sabemos resolver.

el algoritmo

Mostraré una implementación en C, y luego voy a explicar línea por línea cómo funciona esto, ya que es una idea bastante complicada.

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

Entonces, la idea principal del algoritmo es bastante simple: dividir la matriz y dividir la lista en dos partes, una en la que todos los elementos son más pequeños que el pivote y otra en la que todos los elementos son más grandes que el pivote.
Y luego, aplique recursivamente este algoritmo a las partes mismas, hasta que la parte no tenga elementos; en este caso, podemos estar seguros de que está ordenada correctamente.

Hay un matiz importante al elegir un pivote en el algoritmo de clasificación rápida: si elegimos malos pivotes, terminaremos con una complejidad terrible, porque cada vez que dividimos la matriz en dos matrices, terminamos con pequeñas matrices, en este caso, vamos a tener n llamadas recursivas y tendremos que recorrer n elementos, por lo tanto, la clasificación rápida tiene el peor de los casos O(n*n), lo cual es terrible, por lo que debemos tener cuidado al Al elegir un pivote, un buen enfoque es elegir un número aleatorio; al hacerlo, estamos bastante seguros de que obtendremos el caso medio, que es O(n * log n), log n ya que, en el caso promedio, dividiremos el arreglo en dos arreglos que tienen la mitad de los elementos del arreglo inicial, y como tenemos que recorrer todos los elementos, hay un factor de n.