Teste sobre Insertion sort (ordenação por inserção)

Pergunta 1: No melhor caso da ordenação por inserção, quando a lista de entrada já está completamente ordenada, o algoritmo atinge uma complexidade de tempo linear O(n).

A. Sim

B. Não

Explicação: O material de estudo afirma que 'O melhor caso para a ordenação por inserção ocorre quando a lista de entrada já está completamente ordenada. ... o número de operações é diretamente proporcional ao número de elementos na lista, resultando em uma complexidade de tempo linear, denotada como O(n).'

Pergunta 2: Considerando o exemplo passo a passo da ordenação por inserção para a lista inicial `[5, 2, 4, 6, 1, 3]`, qual é o estado da lista após a conclusão do 'Passo 4'?

A. [1, 2, 3, 4, 5, 6]

B. [2, 4, 5, 6, 1, 3]

C. [1, 2, 4, 5, 6, 3]

D. [2, 5, 4, 6, 1, 3]

Explicação: No 'Passo 4', o elemento no índice 4 (valor 1) é selecionado como a chave. A sublista ordenada é `[2, 4, 5, 6]`. A chave `1` é comparada com `6`, `5`, `4` e `2`, fazendo com que todos sejam deslocados uma posição para a direita. O `1` é então inserido na primeira posição, resultando na lista `[1, 2, 4, 5, 6, 3]`.

Pergunta 3: A ordenação por inserção é considerada um algoritmo eficiente para processar grandes conjuntos de dados não ordenados.

A. Sim

B. Não

Explicação: A ordenação por inserção é ineficiente para grandes listas devido à sua complexidade de tempo quadrática (O(n²)), o que a torna impraticável para grandes conjuntos de dados não ordenados.

Pergunta 4: No pior caso da ordenação por inserção, a complexidade de tempo é O(n), pois o algoritmo requer menos deslocamentos e comparações do que o esperado em listas grandes.

A. Sim

B. Não

Explicação: O material afirma claramente que, no pior caso, a complexidade de tempo da ordenação por inserção é O(n²). Isso ocorre porque a lista de entrada está ordenada em ordem inversa, exigindo que cada elemento seja comparado e desloque múltiplos elementos, levando a uma complexidade quadrática, não linear (O(n)).

Pergunta 5: Apesar de ter complexidade de tempo O(n²) no pior caso, assim como a Ordenação por Seleção e a Ordenação por Bolha, a Ordenação por Inserção possui um mecanismo de operação distinto. Qual das seguintes afirmações descreve corretamente a diferença fundamental no mecanismo da Ordenação por Inserção em comparação com os outros dois algoritmos mencionados?

A. A Ordenação por Inserção encontra o menor elemento restante e o troca para a posição correta, similar à Ordenação por Seleção.

B. A Ordenação por Inserção compara e troca elementos adjacentes repetidamente, como faz a Ordenação por Bolha.

C. A Ordenação por Inserção pega um elemento e o insere na posição correta dentro da sublista já ordenada, envolvendo deslocamentos em vez de trocas diretas com elementos distantes.

D. A Ordenação por Inserção é o único algoritmo estável entre os três, sendo os outros dois instáveis.

Explicação: O material de estudo enfatiza que, apesar de todos terem complexidade O(n²) no pior caso, seus mecanismos são distintos. A Ordenação por Inserção distingue-se por pegar um elemento e inseri-lo na posição correta dentro da sublista já ordenada, o que envolve 'deslocamentos' em vez de trocas diretas com elementos distantes. As opções que descrevem as operações da Ordenação por Seleção e Ordenação por Bolha estão incorretas, pois atribuem essas características à Ordenação por Inserção. A estabilidade é uma vantagem da Ordenação por Inserção, mas não é o ponto principal da diferença *mecânica* abordada na seção de erros comuns.