Questão FC266062
Na computação existem algoritmos que utilizam diferentes técnicas de ordenação para organizar um conjunto de dados. Selecione o algoritmo de ordenação que usa um método eficiente c
Algoritmos e Lógica de Programação
IDECAN · 2022
Na computação existem algoritmos que utilizam diferentes técnicas de ordenação para organizar um conjunto de dados. Selecione o algoritmo de ordenação que usa um método eficiente com complexidade C(n) = O(n2) no pior caso, e C(n) = O(n log n) no melhor e médio caso, com o seguinte funcionamento:
➢ Escolhe um elemento da lista chamado pivô.
➢ Reorganiza a lista de forma que os elementos menores que o pivô fiquem de um lado, e os maiores fiquem de outro.
➢ Recursivamente ordena a sub-lista abaixo e acima do pivô.
Assinale a alternativa correta.
- Selection Sort
- Insertion Sort
- Quick Sort
- Merge Sort
- Shell Sort
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
Quick Sort é um algoritmo de ordenação baseado em divisão e conquista que escolhe um elemento chamado pivô e reorganiza o vetor de modo que elementos menores que o pivô fiquem à esquerda e os maiores, à direita.
Essa etapa chama-se particionamento e tem custo \(O(n)\) para um segmento de tamanho n. Após particionar, o algoritmo recursa sobre as duas sublistas geradas até que cada sublista tenha tamanho 0 ou 1.
Na prática isso produz complexidade média e melhor caso \(C(n)=O(n\log n)\), enquanto o pior caso ocorre quando o pivô é sistematicamente extremo, resultando em \(C(n)=O(n^2)\). Estratégias como escolha aleatória do pivô ou "median-of-three" reduzem a chance do pior caso.
Implementações típicas são in-place (baixo uso extra de memória, aproximadamente \(O(\log n)\) para a pilha de chamadas) e o algoritmo não é estável por padrão.
Conteúdo do catálogo FC Concursos · Atualizado em