Counting sort

Counting sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$O(n+k)$
complexidade caso médio	$O(n+k)$
complexidade melhor caso	$O(n+k)$
Algoritmos

Counting sort é um algoritmo de ordenação estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1.

Implementações

1. Cria cnt[M+1] e b[max N]
2. Inicializa todas as posições de cnt a 0.
3. Percorre o vector a e, para cada posição i de a faz cnt[a[i]-1]++ o que faz com que, no final, cada posição i de cnt contem o nº de vezes que a chave i-1 aparece em a.
4. Acumula em cada elemento de cnt o elemento somado ao elemento anterior: cnt[i] indica a posição ordenada do primeiro elemento de chave i.
5. Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
6. Copia b para a.
7. Counting-Sort trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos e números que não existem um outro vetor indica a quantidade de ocorrências.

Esta implementação tem a desvantagem de precisar de vectores auxiliares. O Counting Sort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor de contagem.

Características

• Estável
• Necessita de memória auxiliar. Logo, não é in-place
• Complexidade linear

Código em C++

template<class T>
std::vector<T> counting_sort( const std::vector<T> &op )
{
   if( op.empty() )
      return std::vector<T>{};

   auto min = *std::min_element( op.begin(), op.end() );
   auto max = *std::max_element( op.begin(), op.end() );

   std::vector<int> contagem( max - min + 1, 0 );

   for ( auto it = op.begin(); it != op.end(); ++it );
      ++contagem[ *it - min ];

   std::partial_sum( contagem.begin(), contagem.end(), contagem.begin() );

   std::vector<T> ordenado( op.size() );
   for ( auto = op.rbegin(); it2 != op.rend(); ++it2 )
      ordenado[ --contagem[ *it2 - min ] ] = *it2;

   return ordenado;
}

Código em C

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <ctype.h>
# define MAX 100001

struct data
{
 int number;
 char key[100];
}DataBase[MAX], VectorSort[MAX];

int CounterNum[MAX];
int size = 0;

int main (void)
{
 int i = 0;

 while(scanf("%d%s",&DataBase[size].number,DataBase[size].key) >= 1)
 size++;

 int aux[2] = {0,0};
 for(i = 0; i <= size;i++)
 aux[DataBase[i].number]++;

 aux[1] += aux[0];

 for(i = size - 1;i >= 0;i--)
 VectorSort[--aux[DataBase[i].number]] = DataBase[i];

 for(i = 0; i < size;i++)
 printf("Number: %d  ---  Key: %s\n",VectorSort[i].number,VectorSort[i].key);

 return 0;
}

Código em JAVA

public static void CountingSort(int[] a) {

// acha maior elemento
int maior = v[0];
for (int i = 1; i < v.length; i++) {
 if (v[i] > maior) {
 maior = v[i];
 }
}

// frequencia
int[] c = new int[maior];
for (int i = 0; i < v.length; i++) {
 c[v[i] -1] += 1;
 }

// cumulativa
for (int i = 1; i < c.length; i++) {
 c[i] += c[i-1];
 }

Integer[] b = new Integer[v.length];

for (int i = 0; i < b.length; i++) {
 b[c[v[i] -1] -1] = v[i];
 c[v[i] -1]--;
 }

// passando os elementos do array ordenado para o array recebido no parâmetro
for (int i = 0; i < b.length; i++) {
 v[i] = b[i];

Variação: ordenar números negativos

Apesar do Counting Sort ordenar apenas números inteiros. Pode-se também variá-lo para que ele ordene também números negativos.

Agora, na implementação, é preciso achar também o menor elemento do array. Assim, fazendo n = maior - menor + 1 temos o intervalo que os elementos do array estão inseridos. Em seguida, criamos o array auxiliar de tamanho n (maior - menor + 1). Segue-se a implementação de forma praticamente igual a do Counting Sort para os inteiros, exceto pelo fato de decrementar o valor do menor ao invés de 1 na alocação dos elementos do array recebido para o array auxiliar. Assim, os elementos são adicionados em posições válidas e de forma ordenada. Exemplo: Counting Sort -  c[v[i] -1] += 1; Counting Sort para Negativos - c[v[i] -menor] += 1.

Abaixo, segue-se a implementação da variação em JAVA.

public static void CountingNegativo(Integer[] v) {
    
// acha maior
	Integer maior = v[0];
	for (int i = 1; i < v.length; i++) {
		if (v[i] > maior) {
			maior = v[i];
		}
	}
	
// acha menor
	Integer menor = v[0];
	for (int i = 0; i < v.length; i++) {
		if (v[i] < menor) {
			menor = v[i];
		}
	}
	int n = maior - menor + 1;
	int[] c = new int[n];

// frequencia
	for (int i = 0; i < v.length; i++) {
		c[v[i] -menor] += 1;
	}
		
// cumulativa
	for (int i = 1; i < c.length; i++) {
		c[i] += c[i-1];
	}
		
	Integer[] b = new Integer[v.length];
	for (int i = 0; i < b.length; i++) {
		b[c[v[i] -menor] -1] = v[i];
		c[v[i] -menor]--;
	}
	
	for (int i = 0; i < b.length; i++) {
		v[i] = b[i];
}
	
}