Algoritmo de classificação rápida

O quick sort é um dos algoritmos de ordenação mais famosos, pois é implementado em diversas linguagens de programação dentro da biblioteca padrão. Por que esse algoritmo é tão usado??
Devido à sua velocidade, o algoritmo de classificação rápida é um dos algoritmos de classificação mais rápidos, com uma complexidade de tempo de O (n * log n), onde n é o tamanho da matriz e log é o logaritmo de base 2.

Como funciona?

O principal conceito necessário para entender o algoritmo de classificação rápida é a estratégia de dividir para conquistar.
A estratégia de dividir para conquistar é um termo militar famoso, que costumava significar que para conquistar uma grande nação você deveria primeiro fazer a nação, dividida, muitas vezes por conflito interno ou guerra civil, e então você vai e ataca toda a nação enquanto eles estão ocupado.
Ok, mas como esse conceito se traduz na ciência da computação? O dividir e conquistar, em algoritmos, significa que ele resolve um problema resolvendo problemas menores, isso é bastante semelhante ao conceito de indução matemática, no qual estabelecemos f(1), depois estabelecemos f(n) e então, mostramos que f(n - 1) funciona, fazendo isso podemos provar um conceito.
Os problemas de dividir para conquistar funcionam da mesma maneira, primeiro resolvemos o problema mais simples, muitas vezes chamado de caso base, depois formulamos o caso recursivo e, por fim, fazemos com que o problema seja dividido nos problemas mais simples, porque esses a gente sabe resolver.

O algoritmo

Vou mostrar uma implementação em C, e depois vou explicar linha por linha como isso funciona, já que é uma ideia 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);
}

Portanto, a ideia principal do algoritmo é bastante simples, dividir o array e particionar a lista em duas partes, uma em que todos os elementos são menores que o pivô e outra em que todos os elementos são maiores que o pivô.
E então, aplique recursivamente esse algoritmo às próprias partes, até que a parte não tenha mais elementos, neste caso, podemos ter certeza de que está ordenada corretamente.

Há uma nuance importante na escolha de um pivô no algoritmo de classificação rápida, se escolhermos pivôs ruins, acabaremos com uma complexidade terrível, porque toda vez que dividirmos o array em dois arrays, acabaremos com pequenos arrays, neste caso, teremos n chamadas recursivas e teremos que percorrer n elementos, portanto a classificação rápida tem o pior cenário de O (n * n), o que é horrível, então precisamos ter cuidado ao escolhendo um pivô, uma boa abordagem é escolher um número aleatório. Ao fazer isso, temos certeza de que obteremos o caso intermediário, que é O(n * log n), log n, pois no caso médio, iremos dividir o array em dois arrays que possuem metade dos elementos do array inicial, e como temos que passar por todos os elementos, há um fator de n.