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 algorítimo de CountingSort 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 do Algoritmo de Counting Sort em Java

public static void ordena(int[] a, int m){
		int n = a.length;
		
		int vetorAuxiliar[] = new int[m];
		
		//1ª - (Inicializar com zero)
		for(int i = 0; i < m; i++){
			vetorAuxiliar[i] = 0;
		}
		
		//2ª - Contagem das ocorrencias
		for(int i = 0; i < n; i++){
			vetorAuxiliar[a[i]]++;
		}

		//3ª - Ordenando os indices do vetor auxiliar
		int sum = 0;				
		for(int i = 1; i < m; i++){
			int dum = vetorAuxiliar[i];
			vetorAuxiliar[i] = sum;
			sum += dum;
		}		
		int vetorOrdenado[] = new int[n];
		for(int i = 0; i < n; i++){
			vetorOrdenado[vetorAuxiliar[a[i]]] = a[i];
			vetorAuxiliar[a[i]]++;
		}
		
		//4ª Retornando os valores ordenados para o vetor de entrada
		for (int i = 0; i < n; i++){
			a[i] = vetorOrdenado[i];
		}
	}

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.

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

exemplo_vetor_bs-pequeno

Referencia:
http://en.wikipedia.org/wiki/Counting_sort
http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/countingSort/count.html
http://freevideolectures.com/Course/2501/COMP1927-Data-Structures-and-Algorithms/10
Estrutura de Dados e Algoritmos: Padrões de Projetos Orientados a Objetos Com Java – Livro