- Dado um array com números variando entre 1 até
(
é o tamanho do array). É possível ordenar o array em tempo linear? Justifique sua resposta.
Passo 1
O enunciado dá um array
de tamanho
cujos elementos são inteiros no intervalo de
até
. Pergunta-se se é possível ordenar esse array em tempo
. O conteúdo envolvido é algoritmos de ordenação de inteiros, em particular counting sort e radix sort, e o limite inferior para ordenação baseada apenas em comparações.
Passo 2
Se usássemos apenas comparações, há o limite inferior
de comparações para ordenar
elementos, o que impede tempo linear. Logo, para alcançar
precisamos usar um algoritmo que aproveite o fato de os elementos serem inteiros em um intervalo conhecido.
Passo 3
O counting sort ordena
inteiros no intervalo
em tempo
. Aqui teríamos
, logo o tempo seria
o que não é linear em
.
Passo 4
O radix sort resolve isso quebrando cada número em dígitos em uma base
e aplicando counting sort em cada dígito. Precisamos de
dígitos. Se escolhermos
, então
e cada passo de counting sort leva
. Como são
passes, o tempo total é
Resposta
Sim. Basta usar radix sort com base
, em que cada um dos 6 passes de counting sort custa
, resultando em ordenação em tempo
.