GabaritoA — Bubble Sort.
Gabarito: letra A (Bubble Sort). Em uma lista já ordenada em ordem crescente, o Bubble Sort não realiza nenhuma troca (movimentação), mas seu número de comparações é da ordem de O(n²), o maior entre os algoritmos listados, resultando em maior tempo de execução. Os demais algoritmos ou realizam movimentações (Merge Sort, Quick Sort) ou fazem menos comparações (Insertion Sort).
A questão testa o conhecimento do comportamento específico de cada algoritmo diante de uma entrada já ordenada. Vamos analisar cada alternativa:
O Bubble Sort tradicional percorre o vetor comparando pares adjacentes e trocando-os se estiverem fora de ordem. Em uma lista já ordenada, nenhuma troca é necessária, portanto o número de movimentações é zero. No entanto, o algoritmo ainda executa todas as comparações do laço mais externo e interno, totalizando aproximadamente n²/2 comparações, resultando em complexidade O(n²) – a maior entre as opções, gerando o maior tempo.
O Merge Sort baseia-se no paradigma de divisão e conquista: ele divide recursivamente o vetor em metades até ter subvetores de tamanho 1 e depois intercala (merge) as metades ordenadas. Mesmo que a lista já esteja ordenada, o algoritmo ainda realiza a etapa de intercalação, que envolve movimentações de elementos para o vetor auxiliar. Portanto, há movimentações e o número de comparações é O(n log n), não sendo o maior.
O Quick Sort escolhe um pivô e particiona o vetor em elementos menores e maiores que ele. Em uma lista já ordenada, dependendo da escolha do pivô (por exemplo, o primeiro elemento), o particionamento resulta em subvetores altamente desbalanceados, gerando o pior caso com O(n²) comparações e muitas movimentações (trocas). Assim, ele tanto realiza movimentações quanto tem tempo comparável ou maior, mas não é o único sem movimentações.
O Insertion Sort percorre o vetor da esquerda para a direita, inserindo cada elemento na posição correta entre os já ordenados. Em uma lista já ordenada, cada elemento já está em seu lugar, então não há movimentações (deslocamentos de elementos) e apenas uma comparação por iteração, totalizando aproximadamente n comparações (complexidade O(n)). Portanto, ele não tem o maior tempo ou número de comparações – é o mais eficiente nesse cenário.
Algoritmo | Movimentações em lista ordenada | Complexidade de comparações no melhor caso | Complexidade de comparações no pior caso |
|---|---|---|---|
Bubble Sort | Nenhuma | O(n²) | O(n²) |
Merge Sort | Sim (intercalação) | O(n log n) | O(n log n) |
Quick Sort | Sim (trocas no particionamento) | O(n log n) | O(n²) |
Insertion Sort | Nenhuma | O(n) | O(n²) |
Muitos candidatos confundem e pensam que o Insertion Sort também se encaixa na descrição, mas ele faz apenas O(n) comparações, não sendo o de maior tempo. A banca explora justamente a diferença entre o número de comparações do Bubble Sort (sempre O(n²)) e do Insertion Sort (O(n) em lista ordenada).
Gabarito: letra A (Bubble Sort).
Link permanente: /questoes/qq664111