Questão de Informática

Considere os algoritmos clássicos de ordenação: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort e Quick Sort. Analise as afi rmativas a seguir com base em suas propriedades formais de complexidade, estabilidade e uso de memória na implementação tradicional apresentada na literatura clássica. I. O Insertion Sort possui complexidade de tempo O(n²) no pior caso e pode apresentar complexidade O(n) no melhor caso, quando o vetor já se encontra ordenado. II. O Merge Sort apresenta complexidade O(n log n) nos casos melhor, médio e pior, é estável e, em sua implementação tradicional, requer espaço adicional proporcional a O(n). III. O Quick Sort apresenta complexidade média O(n log n) e pior caso O(n²), podendo este ocorrer quando o pivô escolhido produz partições altamente desbalanceadas. IV. O Selection Sort possui complexidade O(n²) nos casos melhor, médio e pior e, em sua implementação tradicional, não é considerado um algoritmo estável. Assinale a alternativa CORRETA: