7
edições
Counting sort: diferenças entre revisões
Counting sort (editar)
Revisão das 00h06min de 4 de dezembro de 2016
, 00h06min de 4 de dezembro de 2016Adicionei o pseudocódigo do counting sort
m (Adicionei uma parte da explicação do livro Introducion to Algorithms de Thommas H. Cormen (et. all) para ajudar no entendimento do counting sort.) |
m (Adicionei o pseudocódigo do counting sort) |
||
|
A ideia básica do counting sort é determinar, para cada entrada x, o número de elementos menor que x. Essa informação pode ser usada para colocar o elemento x diretamente em sua posição no array de saída. Por exemplo, se há 17 elementos menor que x, então x pertence a posição 18. Esse esquema deve ser ligeiramente modificado quando houver vários elementos com o mesmo valor, uma vez que nós não queremos colocar eles na mesma posição.<ref>{{citar livro|titulo=Introduction to Algorithms|ultimo=Cormen|primeiro=Thomas|editora=MIT Press & McGraw-Hill|ano=2001|local=London, England|paginas=168|acessodata=03/12/2016}}</ref>
== Pseudocódigo do Counting sort ==
<syntaxhighlight>
for i ← 0 to k
do C[i]←0
for j ← 1 to lenght[A]
do C[A[j]] ← C[A[j]] + 1
//Agora C[i] contem o numero de elementos igual a i.
for i ← 1 to k
do C[i] ← C[i] + C[i - 1]
//Agora C[i] contem o numero de elementos menor que ou igual a i.
for j ← lenght[A] downto 1
do B[C[A[j]]] ← A[j]
C[A[j]] ← C[A[j]] -1
//Pseudocodigo do livro "Introduction to Algorithms"
//de Thomas H. Cormen...[et al.] - 2nd ed.
//The MIT Press (p. 168)
</syntaxhighlight>
== Implementações ==
| |||