GabaritoD — Selection Sort
Gabarito: letra D (Selection Sort). Entre os algoritmos listados, o Selection Sort apresenta a maior complexidade de tempo de execução, pois seu pior caso, caso médio e melhor caso são todos O(n²), sem qualquer otimização que reduza o número de comparações em entradas parcialmente ordenadas. Os demais algoritmos (Quick Sort, Heap Sort) possuem complexidade O(n log n) no melhor/médio/pior caso (ou ao menos em média), enquanto Insertion Sort e Bubble Sort, embora também O(n²) no pior caso, podem ter desempenho O(n) em entradas já ordenadas, o que não ocorre com o Selection Sort.
A banca testa o conhecimento das complexidades assintóticas clássicas. A tabela abaixo resume o pior caso de cada um:
Algoritmo | Pior caso | Observação |
|---|---|---|
Quick Sort | O(n²) | Raro, evitável com boas escolhas de pivô |
Insertion Sort | O(n²) | Melhor caso O(n) (lista ordenada) |
Bubble Sort | O(n²) | Melhor caso O(n) (lista ordenada) |
Selection Sort | O(n²) | Sempre O(n²), independente da ordem |
Heap Sort | O(n log n) | Complexidade garantida |
Embora tanto Insertion Sort quanto Bubble Sort também sejam O(n²), eles podem executar em tempo linear em entradas já ordenadas, o que reduz a complexidade média em alguns cenários. O Selection Sort, por outro lado, realiza exatamente n(n-1)/2 comparações independentemente da ordem, tornando seu tempo de execução invariante e, portanto, o maior em termos de garantia de pior caso.
O Quick Sort tem complexidade média O(n log n) e, embora seu pior caso seja O(n²), isso é raro e pode ser evitado. Não é o maior entre os listados, pois Heap Sort e os O(n²) podem ser mais lentos no pior caso. A banca considera que o Selection Sort é superior em complexidade.
O Insertion Sort tem pior caso O(n²), mas no melhor caso é O(n). Na prática, não é o mais lento, pois pode se beneficiar de entradas quase ordenadas. O Selection Sort é mais lento de forma consistente.
O Bubble Sort também é O(n²) no pior caso, mas com melhor caso O(n). Assim como o Insertion Sort, não é o pior em todos os cenários.
O Selection Sort possui complexidade de tempo O(n²) no pior, médio e melhor caso, sendo o único que não apresenta melhora em entradas ordenadas. Isso o torna o algoritmo com a maior complexidade de tempo de execução entre as opções.
O Heap Sort tem complexidade O(n log n) no pior caso, sendo mais rápido que os algoritmos quadráticos.
Para questões que pedem o algoritmo de maior complexidade, lembre-se dos que são sempre O(n²), como Selection Sort, e dos que podem ser otimizados (Insertion, Bubble). Heap Sort e Merge Sort são O(n log n), e Quick Sort é O(n log n) na média. Memorize esses valores.
Gabarito: letra D (Selection Sort).
Link permanente: /questoes/ce124586