Quais das razões seguintes são válidas para se utilizar o insertionSort em vez do selectionSort, na ordenação dessa lista por ordem decrescente?

Alternativa D - Apenas I e II

A questão apresenta um cenário clássico de análise de algoritmos de ordenação, focando na eficiência quando o conjunto de dados já possui uma ordem parcial (quase ordenado).

Para decidir entre Insertion Sort (Ordenação por Inserção) e Selection Sort (Ordenação por Seleção), precisamos analisar como cada um se comporta com dados quase ordenados.

Análise das Afirmações

• Afirmação I (Menos comparações): Correta. O Insertion Sort tem complexidade de tempo de O(n) no melhor caso (quando a lista já está ordenada). Como 95% da lista está ordenada, ele realiza poucas comparações para encontrar a posição correta de cada elemento. Já o Selection Sort sempre realiza aproximadamente O(n^2) comparações, independentemente da ordem inicial. Portanto, há menos comparações no Insertion Sort.
• Afirmação II (Menos mudanças de posição): Correta. Em listas quase ordenadas, o Insertion Sort realiza muito poucos deslocamentos (shifts) de elementos, pois eles já estão próximos de suas posições finais. O Selection Sort, por outro lado, força trocas (swaps) em cada passo para colocar o menor (ou maior) elemento na posição correta, mesmo que a lista esteja quase completa. Isso resulta em menos movimentações de dados no Insertion Sort neste contexto específico.
• Afirmação III (Menos necessidade de espaço): Incorreta. Ambos os algoritmos são classificadores in-place (em lugar). Isso significa que ambos utilizam O(1) de memória auxiliar adicional. Não há diferença significativa na necessidade de espaço entre eles; ambos ocupam o mesmo espaço de memória constante.

Resumo Comparativo

Como apenas as afirmações I e II apresentam vantagens reais do Insertion Sort sobre o Selection Sort para este tipo de dado, a opção correta é a letra D.