No método insertsort, a cada passo, o menor elemento é procurado para que seja inserido na sequência já ordenada. Essa procura pode ser realizada sequencialmente ou por busca binária. Analise o desempenho de ambas as abordagens.

Passo 1

O exercício pede para comparar o desempenho do insertion sort quando a posição de inserção é encontrada por busca sequencial versus busca binária, analisando número de comparações e de deslocamentos de elementos.

Passo 2

Na busca sequencial, para inserir o elemento da posição i no prefixo já ordenado de tamanho i-1, fazemos até i-1 comparações (em média (i-1)/2). Somando para i=2 até n:
sumi=2^n (i-1) = n(n-1)2 = Theta(n^2)
Os deslocamentos também somam 1+2+cdots+(n-1)=Theta(n^2).

Passo 3

Na busca binária, para inserir o elemento da posição i no prefixo de tamanho i-1, precisamos de lceillog2 irceil comparações. Somando para i=2 até n:
sumi=2^n log2 i = Theta(nlog n)
Porém, após achar a posição, ainda deslocamos até i-1 elementos, totalizando Theta(n^2) deslocamentos.

Passo 4

Concluímos que buscar a posição por binária reduz as comparações de Theta(n^2) para Theta(nlog n), mas o tempo total continua dominado pelos deslocamentos Theta(n^2).

Resposta

Busca sequencial: comparações Theta(n^2), deslocamentos Theta(n^2). Busca binária: comparações Theta(nlog n), deslocamentos Theta(n^2). Complexidade geral permanece Theta(n^2).

Exercícios relacionados