Técnico Informática

ALGORITMOS DE ORDENAÇÃO COUNTING SORT, BUCKET SORT E RADIX SORT

Método de Ordenação Counting Sort

Explicação:
O Counting Sort é um tipo de algoritmo utilizado para ordenar vetores de tipos inteiros onde os valores estão entre 0 e M-1. A ideia é utilizar recipientes para organizar e classificar os dados e então retorna-los. Este tipo de algoritmo faz uso de um vetor auxiliar, onde é feito a separação e numeração das ocorrências dos dados de entrada, a qual os valores do vetor são usados como índices em um outro vetor.
A implementação de um algoritmo de Counting Sort requer varias operações, em geral são usados as seguintes etapas:

1 – Inicializar os elementos do vetor auxiliar com zeros
2 – Jogar os valores do vetor de entrada como índice no vetor auxiliar
3 – Ordenar o vetor auxiliar não vazios
4 – Transferir os valores do vetor auxiliar para o vetor de entrada

Exemplo:

O algoritmo acima tem complexidade linear O(m+n) para valores inteiros, mesmo tendo acesso constante aos índices do vetor o algoritmo é eficiente para este tipo de problema. Note que o código acima não utiliza nenhum comando ‘if’ para ordenar o vetor. Concluo que o poder do algoritmo esta no fato de utilizar os próprios valores do vetor como índice em um outro vetor, desta forma que os valores ficam ordenados, porem a forma mais eficiente deste tipo de algoritmo se dá apenas com valores do tipo inteiro e que devem estar uniformemente espalhados no vetor de entrada para poder ser usado como índice.

Lógica do Algoritmo:

Considerando um vetor com os dados {6,8,1,0,4,1,9,8,2,7}, o algoritmo apresentado realizará as seguintes operações:

Método de Ordenação Bucket Sort

Explicação:
Bucket Sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente. O bucket sort tem complexidade