Insertion Sort: Análise das afirmativas
Gabarito: Letra B. O Insertion Sort é, de fato, mais eficiente que o Quick Sort em listas pequenas ou quase ordenadas. Enquanto o Quick Sort possui alta sobrecarga recursiva e pior caso O(n²), o Insertion Sort é adaptativo, executando em O(n) no melhor caso (lista já ordenada) e com constante baixa, sendo ideal para esses cenários.
Alternativa A — ❌ Incorreta
Afirma que o Insertion Sort tem complexidade O(n) no pior caso. Na verdade, o pior caso ocorre quando a lista está em ordem inversa, resultando em O(n²). A complexidade O(n) é apenas para o melhor caso (lista já ordenada).
Alternativa B — ✅ Correta ⟵ GABARITO
O Insertion Sort é mais eficiente que o Quick Sort para listas pequenas (tipicamente n < 50) ou quase ordenadas. Seu baixo overhead e comportamento adaptativo (melhor caso O(n)) superam o Quick Sort, que tem custo de particionamento e recursão, sendo mais lento para entradas reduzidas ou já quase ordenadas.
Alternativa C — ❌ Incorreta
O Insertion Sort é um algoritmo de ordenação estável. Ele mantém a ordem relativa de elementos com chaves iguais, pois insere o elemento na posição correta deslocando os maiores para a direita, sem trocar elementos iguais.
Alternativa D — ❌ Incorreta
O Insertion Sort não utiliza a abordagem de divisão e conquista. Ele é um algoritmo incremental: constrói a sequência ordenada inserindo um elemento por vez na posição adequada. Divisão e conquista é característica de algoritmos como Merge Sort e Quick Sort.
Gabarito: letra B