Questão de Algoritmos e Estrutura de Dados — Algoritmos — UFCG 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq557458
Banca
UFCG
Órgão
UFCG
Ano
2019
Nível
Superior
Cargo
Analista de Tecnologia da Informação - Desenvolvimento de Sistemas
Sobre o algoritmo de ordenação Quick Sort, escolha a assertiva correta.
AFoi inventado após 1970.
BTem O(n log n) no pior caso.
CQuick Sort, assim como Bubble Sort, é um algoritmo recomendado apenas para finalidades didáticas, não sendo bem aplicável em ambientes de produção.
DNão é um algoritmo de ordenação estável.
ENão é um algoritmo que permite paralelismo.
Revelar gabarito e comentário▾
GabaritoD — Não é um algoritmo de ordenação estável.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Quick Sort
Gabarito: letra D. O Quick Sort não é um algoritmo de ordenação estável, pois a troca de elementos durante as partições pode alterar a ordem relativa de elementos iguais. Essa característica é conhecida e contrasta com algoritmos estáveis como Merge Sort e Insertion Sort.
Quick Sort (Hoare, 1960)
1Características
Caso médio: O(n log n)
Pior caso: O(n²) (pivô extremo)
Não é estável
Permite paralelismo
Usado em produção (com otimizações)
2Estabilidade
Estáveis
Merge Sort
Insertion Sort
Bubble Sort
Não estáveis
Quick Sort
Heap Sort
Selection Sort
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O Quick Sort foi inventado por Tony Hoare em 1960, ou seja, antes de 1970. A afirmação de que foi inventado após 1970 é falsa.
Alternativa B — ❌ Incorreta
No pior caso (por exemplo, quando o pivô é sempre o menor ou o maior elemento), o Quick Sort apresenta complexidade O(n²). O caso médio é O(n log n), mas não o pior caso.
Alternativa C — ❌ Incorreta
Diferentemente do Bubble Sort, que realmente é mais usado para fins didáticos, o Quick Sort é amplamente utilizado em sistemas reais devido ao seu bom desempenho médio e à possibilidade de otimizações (escolha de pivô, introsort).
Alternativa D — ✅ Correta ⟵ GABARITO
Estabilidade, em algoritmos de ordenação, significa que elementos iguais mantêm a ordem relativa original. O Quick Sort, por realizar trocas de elementos distantes (particionamento), não garante essa propriedade. Portanto, não é estável.
PEGA ESSA DICA!
Decore a estabilidade dos principais algoritmos: Estáveis → Merge Sort, Insertion Sort, Bubble Sort; Não estáveis → Quick Sort, Heap Sort, Selection Sort.
Alternativa E — ❌ Incorreta
O Quick Sort permite paralelismo, pois as chamadas recursivas para as duas partições podem ser executadas em paralelo, e há implementações paralelas eficientes. A afirmação contrária é falsa.