Bucket 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.

Suponha que lhe seja fornecida uma lista de números distintos, todos contidos no intervalo . 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:

  1. Crie um arranjo com posições, todas preenchidas com False.
  2. Percorra a lista de números e, para cada número da lista, faça .
  3. Percorra o arranjo e, para cada índice , se for igual a True, imprima .

O Bucket Sort funciona muito bem e é eficiente. Entretanto, convém fazer algumas observações sobre seus usos e as restrições que ele possui:

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 Bucket Sort, você teria que criar um arranjo de 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 Bucket 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 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 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.