Assinale a opção que apresenta a técnica que tem a maior co...
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
A alternativa correta é a alternativa D - Selection Sort.
Vamos discorrer sobre o tema da questão, que aborda a complexidade de tempo de execução de diversos algoritmos de ordenação. Para responder corretamente, é necessário compreender os conceitos de complexidade de tempo, frequentemente expressos na notação Big O (O(N)), que determina o desempenho de um algoritmo em termos de tempo de execução conforme o tamanho da entrada cresce.
Agora, justificaremos a resposta correta e as razões pelas quais as outras alternativas estão incorretas:
Alternativa D - Selection Sort:
O Selection Sort possui uma complexidade de tempo de execução de O(N²) tanto no pior caso quanto no caso médio. Isso ocorre porque, para cada elemento no array, ele percorre o restante do array para encontrar o menor elemento, resultando em um comportamento quadrático. Dessa forma, entre as alternativas, o Selection Sort é o algoritmo que tem a maior complexidade de tempo de execução.
Alternativa A - Quick Sort:
O Quick Sort, na média, apresenta uma complexidade de tempo de O(N log N). No pior caso, sua complexidade é O(N²), mas esse caso é raro e pode ser evitado com técnicas de escolha de pivô. De qualquer forma, na maioria das implementações e casos práticos, ele é mais eficiente do que o Selection Sort.
Alternativa B - Insertion Sort:
O Insertion Sort possui uma complexidade de O(N²) no pior e no caso médio. Porém, ele é eficiente para conjuntos de dados pequenos ou quase ordenados, onde sua complexidade pode se aproximar de O(N) no melhor caso. Apesar de ser quadrático no pior caso, ele é geralmente mais rápido que o Selection Sort em muitos cenários práticos.
Alternativa C - Bubble Sort:
O Bubble Sort também tem uma complexidade de tempo de O(N²) no pior caso e no caso médio. Contudo, similar ao Insertion Sort, ele é menos eficiente em comparação com outros algoritmos quadráticos devido ao seu maior número de trocas.
Alternativa E - Heap Sort:
O Heap Sort opera com uma complexidade de O(N log N) no pior caso. Ele é mais eficiente do que os algoritmos quadráticos e é usado em aplicações que requerem eficiência garantida no pior cenário.
Portanto, a resposta correta é a alternativa D, pois o Selection Sort tem a maior complexidade de tempo de execução.
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Comentários
Veja os comentários dos nossos alunos
A ordenação por seleção é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os n-1 elementos restantes, até os últimos dois elementos. Portanto tem a maior complexidade de tempo de execução. Fonte:
Complexidade O(n²) > O(n log n) > O(n)
ALGORITMO MELHOR CASO CASO MÉDIO PIOR CASO
BubbleSort O(n) O(n²) O(n²)
InsertionSort O(n) O(n²) O(n²)
SelectionSort O(n²) O(n²) O(n²)
QuickSort O(n log n) O(n log n) O(n²)
ShellSort O(n log n) Depende do gap O(n²)
MergeSort O(n log n) O(n log n) O(n log n)
HeapSort O(n log n) O(n log n) O(n log n)
GABARITO: D
https://s3.ap-south-1.amazonaws.com/afteracademy-server-uploads/comparison-of-sorting-algorithms-compare1-18082c14f960abf3.png
Boa Sorte
Selection Sort complexidade O(n²)
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo