Considere um arranjo (vetor) de inteiros com n ...

457941205134587

Ano: 2024Banca: IFMGOrganização: IFMGDisciplina: Estruturas de Dados e AlgoritmosTemas: Técnicas de Ordenação | Análise de Complexidade

Considere um arranjo (vetor) de inteiros com n elementos que está quase ordenado (isto é, apenas alguns elementos estão fora de ordem). Sabendo disso, você deseja escolher o algoritmo de ordenação que seja mais eficiente neste cenário. Qual das seguintes alternativas apresenta o melhor algoritmo de ordenação a ser escolhido para ordenar um arranjo (vetor) quase ordenado, em termos de desempenho esperado?

Utilizar o Quick Sort, pois, em média, tem complexidade O(n lg n). e funciona bem em dados quase ordenados, minimizando as trocas.

Utilizar o Heap Sort, pois garante complexidade O(n lg n). no pior caso e reorganiza eficientemente os elementos fora de ordem.

Utilizar o Insertion Sort, pois tem complexidade O(n) em um arranjo (vetor) quase ordenado e é eficiente em dados com pequenas desordens.

Utilizar o Merge Sort, pois é um algoritmo estável com complexidade O(n lg n) no pior caso e faz a ordenação em dois subarranjos(subvetor) para garantir uma ordenação eficiente.

Utilizar o Selection Sort, pois, apesar de sua complexidade O(n²), ele realiza o menor número de trocas possível, o que é ideal para arranjos (vetores) quase ordenados.

Gabarito comentado

Comentários

Anotações

Enviar para caderno

Reportar erro