(Questão 02-03 pontos)
Qual método executa mais rápido em um vetor com chaves idênticas: seleção ou inserção? Justifique sua resposta.
Passo 1
O enunciado pergunta qual algoritmo de ordenação — seleção ou inserção — é mais rápido quando todas as chaves de um vetor são idênticas. O conteúdo aqui é análise de complexidade de algoritmos de ordenação, e vamos precisar dos custos de comparações e movimentações de cada método em função da entrada.
Passo 2
A complexidade do método de seleção independe da ordem das chaves: ele sempre varre o vetor procurando o mínimo em cada uma das
passadas, fazendo cerca de
comparações e exatamente
trocas. Logo, mesmo que todas as chaves sejam iguais, a seleção permanece em
.
Passo 3
O método de inserção, por outro lado, tem complexidade proporcional ao número de inversões do vetor. Em um vetor cujas chaves já estão “ordenadas” (inclusive todas iguais), não há inversões. Assim, em cada iteração o elemento já se encaixa na posição correta sem precisar deslocar nada, resultando em cerca de
comparações e nenhum movimento extra. Portanto, no melhor caso (ou neste caso especial) a inserção roda em
.
Passo 4
Comparando os custos: seleção faz
de qualquer jeito, enquanto inserção em vetor de chaves idênticas faz
. Logo, inserção é assintoticamente mais rápida.
Resposta
O método de inserção, pois em vetor de chaves idênticas ele executa em
, enquanto seleção permanece em
.