Bucket Sort e Radix Sort
A ideia por trás do Bucket Sort é simples: crie um número suficiente de "caixas" (buckets, em Inglês) e coloque cada elemento dentro da caixa correspondente. Depois percorra as caixas em ordem. É isso. Simples, não?
Um exemplo de uso do Bucket Sort é a ordenação de cartas de um baralho, separadas por naipe. A ideia aqui é criar quatro caixas, uma para cada naipe, e colocar as cartas de cada naipe em sua respectiva caixa. Após isso, basta ordenar as cartas dentro de cada naipe.
Apesar de a ideia do Bucket Sort ser simples, ela pode parecer um pouco abstrata no início. Vamos agora ilustrá-la com um exemplo para tentar tornar as coisas mais concretas. Um algoritmo que segue a mesma ideia do Bucket Sort é o chamado Counting Sort. Na verdade, o Counting Sort é o Bucket Sort quando há uma "caixa" para cada valor possível da entrada. Nosso exemplo focará nele, por questões de simplicidade.
Suponha que lhe seja fornecida uma lista de números distintos, todos contidos no intervalo $[0, 10.000]$. Sua tarefa é imprimir os números dessa lista em ordem crescente.
Como fazer isso com complexidade linear no tamanho da lista de números? A solução é simples:
-
Crie um arranjo $A$ com $10.000$ posições, todas preenchidas com
False. -
Percorra a lista de números e, para cada número $i$ da lista, faça $A[i] = True$.
-
Percorra o arranjo $A$ e, para cada índice $i$, se $A[i]$ for igual a
True, imprima $i$.
O Counting Sort funciona muito bem e é eficiente. Entretanto, convém fazer algumas observações sobre seus usos e as restrições que ele possui:
-
O Counting Sort pode ser usado somente se soubermos previamente em que intervalo os números estão. Em nosso exemplo acima, fomos capazes de usar Counting Sort somente porque sabíamos que todos os números da lista de entrada estavam no intervalo inicial, $[0, 10.000]$.
-
Se o intervalo dos números na lista de entrada for muito grande, pode ser inviável usar o Counting Sort, por causa do elevado consumo de memória extra necessária para armazenar as "caixas" (buckets).
No exemplo anterior, suponha que em vez de ter que ordenar uma lista de números, lhe fosse fornecida uma lista de CEPs (oito dígitos) e você tivesse que imprimir os CEPs da lista de entrada em ordem crescente. Como você faria?
Note que, para usar o Counting Sort, você teria que criar um arranjo de $10.000.000$ de posições. A pergunta é: Seria possível resolver o problema sem ter que criar um arranjo tão grande? A resposta é: Sim, use Radix Sort em vez de usar Counting Sort.
Radix Sort
Considere novamente o problema apresentado acima, de se ordenar uma lista de CEPs. Como dissemos, gostaríamos de resolver o problema sem ter que alocar um vetor de $10.000.000$ de posições. Para isso, podemos usar o Radix Sort, cuja ideia principal é processar a lista de entrada em etapas. Primeiro, criamos 10 "caixas" e ordenamos todos os números de acordo com o primeiro dígito do CEP. Agora, cada "caixa" contém $1.000.000$ de CEPs. Seguindo a mesma ideia, podemos ordenar os números em cada "caixa" de acordo com cada um dos dígitos, usando para isso o Bucket Sort.
Playground
# Use este espaço para praticar o que você aprendeu nesta seção.
# Basta digitar o código no espaço abaixo e clicar 'run'.