Count sort
Origem: Wikipédia, a enciclopédia livre.
As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as 1ªs k0 posições do array final: de 0 a k0-1. Necessita de vectores auxiliares para guardar contagens e para construir o array ordenado.
Passos:
• 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.
Tem a desvantagem de precisar de vectores auxiliares.
[editar] Implementações
[editar] Código em C++
template<class T>
std::vector<T> count_sort( std::vector<T> &lista )
{
std::vector<T> resultado( lista.size() );
std::vector<T>::iterator elem;
for( elem = lista.begin(); elem != lista.end(); ++elem )
{
resultado.at( count_if( lista.begin(), lista.end(), bind2nd(less<T>(), *elem ) ) ) = *elem;
}
return resultado;
}
[editar] Código em Java
public static void CountSort(int[] v) {
int num = v.length;
int valor; int[] result = new int[num];
// percorre com o valor que terá sua posicao procurada
for ( int i = 0; i < num; i++) {
valor = v [i];
// Encontra a posição e coloca o valor lá
result [(EncontraPosicao(v, valor))] = valor;
}
}
public static int EncontraPosicao(int [] v, int valor) {
int cont = 0;
// percorre o vetor a procura da posicao
for ( int i = 0; i < v.length; i++ )
if (valor > v [i])
cont ++;
return cont;
}
