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
no prefixo já ordenado de tamanho
, fazemos até
comparações (em média
). Somando para
até
:
Os deslocamentos também somam
.
Passo 3
Na busca binária, para inserir o elemento da posição
no prefixo de tamanho
, precisamos de
comparações. Somando para
até
:
Porém, após achar a posição, ainda deslocamos até
elementos, totalizando
deslocamentos.
Passo 4
Concluímos que buscar a posição por binária reduz as comparações de
para
, mas o tempo total continua dominado pelos deslocamentos
.
Resposta
Busca sequencial: comparações
, deslocamentos
. Busca binária: comparações
, deslocamentos
. Complexidade geral permanece
.