count sort

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]
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. O Counting Sort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor de contagem.

#include
#include

void count_sort (int *A, int n, int *B, int *C, int k){ int i; //passo 1: for(i=0;