count sort

Páginas: 2 (251 palavras) Publicado: 25 de agosto de 2014
Counting sort é um algoritmo de ordenação estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Seexistirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1.

Implementações[editar | editarcó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 fazcnt[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 cadaelemento de cnt o elemento somado ao elemento anterior: cnt[i] indica a posição ordenada do primeiro elemento de chave i.
Guarda em bos valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
Copia b para a.
Counting-Sort trabalha como uma contadora deocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos enúmeros que não existem um outro vetor indica a quantidade de ocorrências.
Esta implementação tem a desvantagem de precisar de vectoresauxiliares. O Counting Sort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor decontagem.

#include
#include

void count_sort (int *A, int n, int *B, int *C, int k){
int i;

//passo 1:
for(i=0; i
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • sort
  • sort
  • Merge Sort, Quick Sort e Heap Sort
  • Quick sort e shell sort
  • Heap Sort
  • selection sort
  • Radix sort
  • Selection sort

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!