Acerca das estruturas de dados multimídias e dos algoritmos de ordenação e busca, julgue o item a seguir. O algoritmo Bubble Sort é considerado ineficiente para ordenar grandes vol

Gabarito

Errado

Comentário do professor

Bubble Sort foi considerado ineficiente, e a afirmação está errada porque atribui a ele a complexidade de tempo equivocada.

No pior caso, quando a lista está na ordem inversa, o algoritmo realiza trocas sucessivas de elementos adjacentes em múltiplas passagens, gerando aproximadamente \((n-1) + (n-2) + ... + 1 = O(n^2)\) operações. Logo, a correta complexidade no pior caso é \(O(n^2)\), não \(O(n \log n)\).

No caso médio também vale \(O(n^2)\). Apenas uma versão otimizada com verificação de troca pode ter melhor caso \(O(n)\) quando o vetor já está ordenado.

Algoritmos eficientes que alcançam \(O(n \log n)\) no pior caso são, por exemplo, Merge Sort e Heap Sort, o que explica por que Bubble Sort é considerado inadequado para grandes volumes de dados.