Counting sort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
bot: revertidas edições de 200.175.132.220 ( erro : -25), para a edição 21573963 de Ricardo Ferreira de Oliveira |
|||
Linha 22: | Linha 22: | ||
#Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i] |
#Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i] |
||
#Copia b para a. |
#Copia b para a. |
||
#Counting-Sort trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem |
#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. |
Esta implementação tem a desvantagem de precisar de vectores auxiliares. |
||
Revisão das 20h53min de 20 de setembro de 2010
Counting sort | |
---|---|
classe | Algoritmo de ordenação |
estrutura de dados | Array, Listas ligadas |
complexidade pior caso | |
complexidade caso médio | |
complexidade melhor caso | |
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
- Cria cnt[M+1] e b[max N]
- Inicializa todas as posições de cnt a 0.
- 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.
- 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.
- Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
- Copia b para a.
- 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.
Código em C++
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;
}