Questão FC266055
No contexto de estruturas de dados e algoritmos, a escolha de métodos eficientes para ordenação, pesquisa e hashing é crucial para o desempenho de muitas aplicações. Dentre os méto
Algoritmos e Lógica de Programação
IDECAN · 2024
No contexto de estruturas de dados e algoritmos, a escolha de métodos eficientes para ordenação, pesquisa e hashing é crucial para o desempenho de muitas aplicações. Dentre os métodos de ordenação, destaca-se uma técnica que utiliza um pivô para particionar o vetor em duas partes, garantindo que todos os elementos menores que o pivô fiquem à sua esquerda, e os elementos maiores, à direita. De acordo com a descrição apresentada, assinale a alternativa que contém o método de ordenação destacado.
- QuickSort
- MergeSort
- BubbleSort
- InsertionSort
Mostrar resposta e comentário
Gabarito
A
Comentário do professor
Quicksort é um algoritmo de ordenação que usa o conceito de pivô para dividir o problema: escolhe-se um elemento e rearranja-se o vetor de modo que todos os valores menores que o pivô fiquem à sua esquerda e os maiores à direita.
Essa técnica segue a estratégia de divisão e conquista: após a partição, aplica-se recursivamente o mesmo procedimento às sublistas até que todas tenham tamanho 0 ou 1 (caso base).
Em termos de desempenho, a complexidade média é \(O(n \log n)\), enquanto o pior caso é \(O(n^2)\) quando a escolha do pivô é desfavorável. O algoritmo costuma ser in-place (uso extra de memória baixo) e, normalmente, não é estável.
A escolha do pivô (ex.: elemento aleatório, mediana de três) e a implementação da partição influenciam fortemente a eficiência prática do Quicksort.
Conteúdo do catálogo FC Concursos · Atualizado em