Count sort

Origem: Wikipédia, a enciclopédia livre.

Este artigo precisa ser wikificado.

Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.
Remova este aviso somente depois de todo o texto estar wikificado.

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