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.

A ideia básica do counting sort é determinar, para cada entrada x, o número de elementos menor que x. Essa informação pode ser usada para colocar o elemento x diretamente em sua posição no array de saída. Por exemplo, se há 17 elementos menores que x, então x pertence a posição 18. Esse esquema deve ser ligeiramente modificado quando houver vários elementos com o mesmo valor, uma vez que nós não queremos que sejam colocados na mesma posição.

Pseudocódigo

//k é o maior valor do vetor A

//Criar vetor auxiliar com k+1 elementos e inicializar com zeros
for i ← 0 to k
    do C[i]←0
    
for j ← 1 to length[A]
    do C[A[j]] ← C[A[j]] + 1
//Agora C[i] contem o numero de elementos igual a i.

for i ← 1 to k
    do C[i] ← C[i] + C[i - 1]
//Agora C[i] contem o numero de elementos menor que ou igual a i.

for j ← length[A] downto 1
    do B[C[A[j]]] ← A[j]
        C[A[j]] ← C[A[j]] - 1
        
//Pseudocodigo do livro "Introduction to Algorithms" 
//de Thomas H. Cormen...[et al.] - 2nd ed.
//The MIT Press (p. 168)

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 it2 = 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 1.0

public Integer[] CountingSort(Integer[] v) {
	
//encontra o maior valor em v[]	
	int maior = v[0];
	for (int i = 1; i < v.length; i++) {
		if (v[i] > maior) {
			maior = v[i];
		}
	}
		
//conta quantas vezes cada valor de v[] aparece
	int[] c = new int[maior+1];//+1 pois se 10 for o maior valor, ele iria apenas de 0 a 9
	for (int i = 0; i < v.length; i++) {
		c[v[i]] += 1;
	}
		
//acumula as vezes de cada elemento de v[] com os elementos anteriores a este
	for (int i = 1; i < c.length; i++) {
		c[i] += c[i-1];
	}
		
//adiciona os elementos em suas posições conforme o acumulo de suas frequencias
	Integer[] b = new Integer[v.length];
	for (int i = b.length-1; i >= 0; i--) {//percorre do fim para o inicio para manter estavel, mas não haveria problema em i = 0; i < b.lenght; i++
		b[c[v[i]] -1] = v[i];
		c[v[i]]--;
	}
	
	return b;
}

Código em Java 1.1

public void CountingSort(Integer[] array, int leftIndex, int rightIndex) {
		
		//Encontrar o maior valor 
		int k = 0;
		for(int m = leftIndex; m < rightIndex; m++){
			if(array[m] > k){
				k = array[m];
			}
		}
		
		//Cria vetor com o tamanho do maior elemento
		int[] vetorTemporario = new int[k];
		
		//Inicializar com zero o vetor temporario
		for(int i = 0; i < vetorTemporario.length; i++){
			vetorTemporario[i] = 0;
		}
		
		//Contagem das ocorrencias no vetor desordenado
		for(int j = leftIndex; j < rightIndex; j++){
			vetorTemporario[array[j]] += 1;
		}
		
		//Fazendo o  complemento do numero anterior 
		for(int i = leftIndex; i < k; i++){
			vetorTemporario[i] = vetorTemporario[i] + vetorTemporario[i - 1];
		}
		
		//Ordenando o array da direita para a esquerda
		int[] vetorAuxiliar = new int[array.length];
		for(int j = rightIndex; j > leftIndex; j--) {
			vetorAuxiliar[vetorTemporario[array[j]]] = array[j];
			vetorTemporario[array[j]] -= 1; 
		}
		
		//Retornando os valores ordenados para o vetor de entrada
		for (int i = leftIndex; i < rightIndex; i++){
			array[i] = vetorAuxiliar[i];
		}
	}