Algoritmos de ordenação são responsáveis por ordenar elementos de uma estrutura de dados de forma completa ou parcial. Sobre a complexidade dos algoritmos de ordenação, assinale, a seguir, o algoritmo de ordenação que, no pior caso, tem complexidade igual a O(n log n).
- A)Quick sort.
Errada, porque o Quick sort tem pior caso O(n²), apesar de ser muito eficiente na prática e no caso médio.
- B)Merge sort.
Certa, porque o Merge sort mantém O(n log n) no pior caso ao dividir o problema e depois combinar as partes em tempo linear.
- C)Bubble sort.
Errada, porque o Bubble sort tem pior caso O(n²), já que compara e troca repetidamente elementos adjacentes.
- D)Insertion sort.
Errada, porque o Insertion sort também pode chegar a O(n²) no pior caso, especialmente com dados em ordem inversa.
- E)Selection sort.
Errada, porque o Selection sort tem pior caso O(n²), pois faz várias varreduras para selecionar o menor elemento.
Gabarito: B
Quando a banca pergunta a complexidade de algoritmos de ordenação, ela quer que voce saiba não só "quem ordena", mas também quanto custa ordenar quando o cenário complica. Em geral, os algoritmos mais simples, como Bubble, Insertion e Selection, costumam ficar em O(n²) no pior caso, então não são os favoritos de questões de complexidade. Já os algoritmos mais eficientes usam a estratégia de dividir para conquistar, reduzindo bastante o trabalho total. O ponto central aqui é o pior caso. O algoritmo pedido no enunciado deve manter complexidade O(n log n) mesmo quando os dados estão em uma situação desfavorável. Esse é exatamente o caso do Merge sort, que divide o vetor em partes menores, ordena cada parte e depois faz a fusão. Como a divisão acontece logaritmicamente e cada nível faz trabalho linear, o total fica em O(n log n). O Quick sort costuma ser muito rápido na prática, mas seu pior caso pode cair para O(n²) quando a escolha do pivô é ruim. Ou seja, ele não atende ao que a questão pediu. Já Bubble, Insertion e Selection são os clássicos da dor de cabeça em prova quando a banca quer comparar ordens de crescimento: eles são simples, mas pouco eficientes para grandes volumes. Então, o gabarito B está correto porque o Merge sort tem complexidade O(n log n) no pior caso. Se voce lembrar da lógica "divide e conquista + fusão linear", praticamente mata esse tipo de questão sem sofrimento.