Uma ordenação por contagem de um vetor
de tamanho
é executada da seguinte forma: declare um vetor count e defina count[i] como o número de elementos menores que
. Em seguida, coloque
consideração a possibilidade de elementos iguais). Escreva uma função para ordenar um vetor
de tamanho
usando esse método.
Passo 1
O enunciado pede para ordenar um vetor
de tamanho
usando a ideia de contar, para cada elemento
, quantos elementos são menores que ele e depois posicioná-lo de acordo com esse «ranking». Isso é um counting sort de complexidade
.
Passo 2
Vamos criar um vetor
e, para cada
até
, percorrer todo o vetor
incrementando
sempre que encontrarmos um elemento
menor que
.
Para tratar corretamente elementos iguais, no laço de comparação também fazemos: se e
, incrementamos
. Assim garantimos que cada cópia de um valor repetido ocupe uma posição distinta.
Para tratar corretamente elementos iguais, no laço de comparação também fazemos: se
Passo 3
Depois de termos todos os
, criamos um vetor de saída
e, para cada
, colocamos
em
.
Por fim, copiamos o vetor de volta para
, e então
estará ordenado em ordem não decrescente.
Por fim, copiamos o vetor
Resposta
função countingSort(x, n):
// 1) alocar e zerar o vetor de contagens
para i de 1 até n faça
count[i] := 0
fim para
// 1) alocar e zerar o vetor de contagens
para i de 1 até n faça
count[i] := 0
fim para
// 2) contar elementos menores (e iguais de índice menor)
para i de 1 até n faça
para j de 1 até n faça
se x[j] < x[i] ou (x[j] = x[i] e j < i) então
count[i] := count[i] + 1
fim se
fim para
fim para
para i de 1 até n faça
para j de 1 até n faça
se x[j] < x[i] ou (x[j] = x[i] e j < i) então
count[i] := count[i] + 1
fim se
fim para
fim para
// 3) distribuir os valores no vetor de saída
alocar output[1…n]
para i de 1 até n faça
output[count[i] + 1] := x[i]
fim para
alocar output[1…n]
para i de 1 até n faça
output[count[i] + 1] := x[i]
fim para
// 4) copiar de volta para x
para i de 1 até n faça
x[i] := output[i]
fim para
para i de 1 até n faça
x[i] := output[i]
fim para
retornar x