O algoritmo counting sort tem larga aplicabilidade pelo seu desempenho linear na ordenação de dados em memória. No entanto, o maior consumo de espa...

O algoritmo counting sort tem larga aplicabilidade pelo seu desempenho linear na ordenação de dados em memória. No entanto, o maior consumo de espaço em memória pode restringir seu uso em determinados cenários. Outra característica é sua estabilidade quanto ao posicionamento de elementos com o mesmo valor. Considerando que um vetor A de n posições é passado como parâmetro para o algoritmo counting sort e que dois elementos nas posições i e j têm o mesmo valor k (A[ i ] = A[ j ] = k), assinale a alternativa correta quanto ao funcionamento do algoritmo. Assuma que um vetor B é retornado pelo algoritmo.
O algoritmo é estável, porque a posição C[ k ] do vetor auxiliar C é decrementada após a alocação de k em B, e não é mais incrementada.
Se existirem outros elementos com valor k, o vetor auxiliar terá armazenado em sua posição k o valor p.
O algoritmo é estável, porque a posição C[ k ] do vetor auxiliar C é decrementada após a alocação de k em B, e não é mais incrementada.
Como A[ i ] = A[ j ] no vetor de origem, então as posições relativas entre esses elementos podem ser alteradas no vetor de saída B.
Supondo que i < j, neste caso, o último laço do algoritmo vai examinar A[ i ] antes que A[ j ].
Se o vetor C tem na sua posição k o valor m, então o elemento k é alocado na posição n – m do vetor de saída B.