Counting sort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Melhorar o português. |
m →top: manutênção refs. |
||
Linha 14:
'''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.
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 menores 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 que sejam colocados 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
== Pseudocódigo ==
| |||