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