Uma ordenação por contagem de um vetor x de tamanho n é executada da seguinte forma: declare um vetor count e defina count[i] como o número de elementos menores que x [ i ]. Em seguida, coloque x [ i ] n a p o s i c ̧ a ̃ o c o u n t [ i ] d e u m v e t o r d e s a i ́ d a ( l e v e e m ̧ consideração a possibilidade de elementos iguais). Escreva uma função para ordenar um vetor x de tamanho n usando esse método.

Passo 1

O enunciado pede para ordenar um vetor x de tamanho n usando a ideia de contar, para cada elemento x[i], quantos elementos são menores que ele e depois posicioná-lo de acordo com esse «ranking». Isso é um counting sort de complexidade O(n^2).

Passo 2

Vamos criar um vetor count[1dots n] e, para cada i=1 até n, percorrer todo o vetor x incrementando count[i] sempre que encontrarmos um elemento x[j] menor que x[i].
Para tratar corretamente elementos iguais, no laço de comparação também fazemos: se x[j]=x[i] e j, incrementamos count[i]. Assim garantimos que cada cópia de um valor repetido ocupe uma posição distinta.

Passo 3

Depois de termos todos os count[i], criamos um vetor de saída output[1dots n] e, para cada i, colocamos x[i] em output[count[i]+1].
Por fim, copiamos o vetor output de volta para x, e então x estará ordenado em ordem não decrescente.

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
// 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
// 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
// 4) copiar de volta para x
para i de 1 até n faça
x[i] := output[i]
fim para
retornar x

Exercícios relacionados