Quick Sort

Considerando um dos algoritmos de ordenação eficientes, o Quick Sort é um algoritmo recursivo, que implementa o princípio dividir para conquistar. Embora seja mais eficiente em termos de custo computacional, o processo de compreensão desse algoritmo é um pouco mais complexo do que os anteriores.

Assim, recomendo que vocês leiam atentamente essa explicação, assim como tentem resolver o algoritmo linha a linha no papel, simulando o processo que apresentarei logo mais. Ao final, também há vídeos que explicam a ideia do algoritmo.

Apesar disso, nada é mais eficiente que a execução linha a linha no papel, para que você execute e compreenda o objetivo de cada linha apresentada no algoritmo.

Vamos lá!

🤯 Entendendo a ideia

A ideia é que um vetor seja dividido sucessivas vezes, até que reste apenas um elemento. A ordenação acontece durante esse processo.

Vamos entender o processo inicial:

🔁 A parte recursiva

1. Ao chamarmos o algoritmo de ordenação QuickSort, informamos os seguintes parâmetros:
   • Qual é o vetor a ser ordenado;
   • Qual é a posição inicial do vetor;
   • Qual é a última posição válida do vetor;
2. Ao iniciar, o algoritmo verificará se o início do vetor é menor que o fim. Se inicio for igual ou superior ao fim, nada será executado.
3. O algoritmo baseia-se na ideia de dividir para conquistar. Assim, ele precisa efetuar a partição do vetor em dois. Reforçando: a partição do vetor é uma abstração, ele não será fisicamente divido em dois.
4. A função de particao retornará um índice do vetor que indica a posição do meio.
5. Em seguida, o algoritmo QuickSort fará duas chamadas recursivas (para si mesmo), passando metade do vetor em cada uma delas.

✂️ A partição do vetor

Agora, vamos entender como funciona a função de partição:

A função particao recebe o vetor a ser ordenado, além de duas variáveis de controle: inicio e fim. Já na sua primeira linha, é definido um elemento, chamado pivô, que será utilziado para basear a ordenação do algoritmo.

Observe que, logo no início do processo, o vetor é

1. A função de partição escolhe um elemento no meio do vetor, chamado pivô. Observe que o pivô não é a posição do meio, mas sim o valor armazenado naquela posição.
2. Duas variáveis adicionais, a e b, serão criadas:

• a percorrerá o vetor da esquerda para a direita;
• b percorrerá o vetor da direita para a esquerda;

3. A inicialização das variáveis é um pouco curiosa:

• a será inicializada como inicio-1;
• b será inicializada como fim+1 ;

Realizado esse processo, o algoritmo entra em um loop que compara os elementos nas posições a e b com o valor do pivô. O objetivo é posicionar os elementos menores que o pivô à esquerda e os elementos maiores à direita.

Enquanto a posição de a for menor que a de b:

1. Incremente a enquanto o valor do item na posição a do vetor for menor que o pivô;
2. Decremente b enquanto o valor do item na posição b do vetor maior que o pivô;
3. Se a for menor que b, troque os elementos dessas posições.

Esse processo continua até que a e b se cruzem, momento em que a partição está finalizada. Ao final da função de partição, o índice de b é retornado. Esse índice será utilizado pela função Quick Sort para identificar o meio do vetor.

👩🏾‍💻 A implementação

int particao(int vet[], int inicio, int fim){
    int pivo = vet[(inicio + fim)/2];
    int a = inicio-1;
    int b = fim+1;

    while(a<b){
        do{
            a++;
        } while(vet[a] < pivo);
        do{
            b--;
        } while(vet[b] > pivo);
        if(a<b) trocar(&vet[a], &vet[b]);
    }
    return b;
}

void quickSort(int vet[], int inicio, int fim){
    if(inicio<fim){
        int meio = particao(vet,inicio,fim);
        quickSort(vet,inicio,meio);
        quickSort(vet,meio+1,fim);
    }
}

🚀 Execução

Acompanhe, na imagem a seguir, o processo de execução passo-a-passo do algoritmo Quick Sort para a ordenação de um vetor {14,7,2}. Recomendo fortemente que, antes de acompanhar a figura, você observe o fragmento de código acima.

Na figura, tentei mesclar os trechos de código com os seus efeitos num esquema visual.

.

🎬 Vídeos de apoio

Outra opção de material:

⚠️ Dicas importantes

• Ao procurar outros materiais sobre algoritmos de ordenação, atente-se: há outras estratégias para a escolha do pivô no algoritmo QuickSort. A apresentada neste material seleciona o elemento do meio como pivô.