Counting sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes fiáveis e independentes. (desde agosto de 2012). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
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[editar | editar código-fonte]

  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.

Código em C++[editar | editar código-fonte]

template<class T>
std::vector<T> counting_sort( const std::vector<T> &op )
{
   if( op.empty() )
      return std::vector<T>();
 
   T min = *std::min_element( op.begin(), op.end() );
   T max = *std::max_element( op.begin(), op.end() );
 
   std::vector<int> contagem( max - min + 1, 0 );
 
   for( std::vector<T>::const_iterator 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( std::vector<T>::const_reverse_iterator it2 = op.rbegin(); it2 != op.rend(); ++it2 )
      ordenado[ --contagem[ *it2 - min ] ] = *it2;
 
   return ordenado;
}

Código em C[editar | editar código-fonte]

# 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;
}