Counting sort: diferenças entre revisões

Sem alteração do tamanho ,  08h14min de 4 de agosto de 2021
m
Alterei o nome dos vetores para letras maiúsculas na sessão "Implementações", o que facilita a leitura
m (→‎top: manutênção refs.)
m (Alterei o nome dos vetores para letras maiúsculas na sessão "Implementações", o que facilita a leitura)
 
 
== Implementações ==
# Cria cntCNT[M+1] e bB[max N]
# Inicializa todas as posições de cntCNT a 0.
# Percorre o vector aA e, para cada posição i de a faz cntCNT[aA[i]-1]++ o que faz com que, no final, cada posição i de cntCNT contem o nº de vezes que a chave i-1 aparece em aA.
# Acumula em cada elemento de cntCNT o elemento somado ao elemento anterior: cntCNT[i] indica a posição ordenada do primeiro elemento de chave i.
# Guarda em bB os valores de aA ordenados de acordo com bB[cntCNT[aA[i]++]=aA[i]
# Copia bB para aA.
# 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.
6

edições