5 de janeiro de 2024
Algoritmo: Quicksort
Algoritmos
Introdução
Quicksort é um algoritmo muito conhecido e pode ser usado para ordenar grandes amostras eficientemente. Ele foi desenvolvido em 1960 pelo cientista da computação britânico Charles Antony Richard Hoare. É provavelmente o algoritmo de ordenação mais utilizado no mundo.
Para criá-lo, primeiro precisamos do método de “partição”, esse método raramente vai ordenar de primeira, porém vai fazer algo muito importante: escolher um pivô (que pode ser qualquer número, mas é geralmente o último elemento) e separar os elementos menores que ele do lado esquerdo e os maiores do lado direito.
Como esse método faz isso? Para fazer essa divisão, vamos ter uma variável representando um índice “limite” do lado esquerdo separando os elementos menores (vamos chamá-la de i). Se a lista começa no índice 0, essa variável inicia em -1. Então i vai demarcar onde termina os elementos menores que o pivô. Ao achar um item menor que o pivô, somamos 1 a i e trocamos de posição o item atual com o item de posição i. Seguimos com a iteração. No final, pegamos o pivô e trocamos de lugar com o primeiro elemento da direita (maior que ele), ou seja, na posição i + 1. O limite dos elementos menores que o pivô é i, logo, i + 1 é o primeiro elemento maior ou igual ao pivô. Retornamos a posição final do pivô.
Tudo certo, essa é a função de partição. O algoritmo quicksort é outra parte, e assim como mergesort, utiliza da estratégia “dividir e conquistar”. Primeiro chama o método de partição para encontrar a posição final do primeiro pivô. Depois chama a si, recursivamente, para o subarray a sua esquerda, onde todos são menores e para o subarray a direita, onde todos os elementos são maiores que o pivô. Nesse momento não precisamos mais se preocupar com o primeiro pivô, pois temos certeza que sua posição já está correta: todos a direita são maiores e todos da esquerda menores.
No final da recursividade, com a implementação correta, vamos ter a lista devidamente ordenada.
A imagem abaixo, retirada do site do Khan Academy, demostra como os elementos se rearranjam em cada etapa. Os elementos em azul foram pivôs na iteração antecedente.
Repare que o primeiro pivô 6 tem todos seus elementos menores à esquerda, mesmo que não estejam ainda ordenados nessa fase. Na segunda recursão ele é ignorado pelo algoritmo.
Implementação
Vamos implementar quicksort em C:
1#include <stdio.h>
2#include <stdlib.h>
3
4int partition(int numbers[], int begin, int end)
5{
6 int pivot = numbers[end]; // {1}
7 int i = begin - 1; // {2}
8
9 for (int j = begin; j < end; j++) // {3}
10 {
11 if (numbers[j] < pivot) // {4}
12 {
13 i++; // {5}
14 swap(&numbers[i], &numbers[j]); // {6}
15 }
16 }
17
18 swap(&numbers[i + 1], &numbers[end]); // {7}
19 return (i + 1); // {8}
20};
21
22void quick_sort(int numbers[], int begin, int end)
23{
24 if (begin < end) // {9}
25 {
26 int partition_index = partition(numbers, begin, end); // {10}
27 quick_sort(numbers, begin, partition_index - 1); // {11}
28 quick_sort(numbers, partition_index + 1, end); // {12}
29 }
30};{1} Marcamos o último elemento da lista como pivô, mas poderia ser escolhido outro, até mesmo aleatoriamente.
{2} Variável que demarcar elementos menores que o pivô.
{3} Vamos iterar sobre a lista, do início ao fim, verificando se algum item é menor que o pivô {4}. Se for, aumentamos o limite de i em 1 {5} e permutamos esse item com o item da posição i {6}.
{7} No final da iteração, trocamos o pivô de posição com o primeiro item maior ou igual a ele. Por fim, retornamos essa posição {8}.
Agora no quicksort, enquanto o primeiro índice for menor que o último {9}, vamos chamar o método “partition” para encontrar o índice do pivô {10} e chamar a mesma função quicksort tanto para o lado esquerdo {11} quanto para o lado direito {13}.
Notação Assintótica
O tempo de execução para quicksort varia entre O(n log n) e O(n²). Mas seu tempo de execução médio é de O(n log n), que é muito eficiente. Quando a amostra é pequena, é mais lento que insertionsort ou selectionsort, mas para grandes amostras supera (extraordinariamente) esses algoritmos.