MO417 - Questão para a prova oral

Número: 2003-062

Enunciado: Abaixo encontram-se duas versões do algoritmo "Bubble Sort".

BUBBLE-SORT1(A)                          BUBBLE-SORT2(A)
1 for i := length[A]-1 downto 1          1 for i := length[A]-1 downto 1 
2   for j := 1 to i                      2   for j := 1 to i
3     if (A[j] > A[j+1])                 3     if (A[j] >= A[j+1])
4       troca A[j] <-> A[j+1]            4       troca A[j] <-> A[j+1]

Note que a única diferença entre as duas versões é a comparação na linha 3. Qual destas duas versões pode ser usada na implementação do algoritmo "Radix Sort" para obtermos complexidade de tempo linear no número de elementos?

A) Ambas as versões podem ser usadas na implementação do "Radix Sort".
B) Somente a versão "Bubble-Sort1" pode ser usada na implementação do "Radix Sort".
C) Somente a versão "Bubble-Sort2" pode ser usada na implementação do "Radix Sort".
D) Nenhuma das versões pode ser usada na implementação do "Radix Sort".
E) NDA

Ideia original de: José Augusto Amgarten Quitzau