MO417 - Questão para a prova oral

Número: 2003-069

Enunciado: Sobre o COUNTING-SORT é correto afirmar que:

A) Se os inteiros a serem ordenados estão no intervalo de 1 a n, tem ordem de crescimento Θ(n). Escapa do limite inferior de Ω(n lg n) porque não realiza ordenação por comparação.

B) É estável porque utiliza ordenação local, ou seja, utiliza espaço adicional constante.

C) Realiza ordenação sobre cada dígito dos elementos, assim como era usado antigamente na ordenação de cartões perfurados.

D) Divide o intervalo [0, 1) em n subintervalos de igual tamanho e depois distribui os n elementos de entrada entre os subintervalos. Então conta-se o número de elementos em cada subintervalo e redistribui os elementos no arranjo de forma ordenada.

E) NDA

Ideia original de: Fabio Batista Gomes