Questão de Algoritmos e Estrutura de Dados — Algoritmos — IBADE 2025

QuickSort e sua eficiência em grandes conjuntos

Gabarito: letra B. O QuickSort é eficiente para grandes volumes de dados porque adota a estratégia de divisão e conquista: o problema é dividido recursivamente em subproblemas menores (particionamento em torno de um pivô), e cada subarray é ordenado independentemente. Essa abordagem oferece complexidade média O(n log n), superando algoritmos quadráticos como Bubble Sort ou Insertion Sort para entradas grandes.

A banca testa o conhecimento do paradigma central do QuickSort. A alternativa correta é a única que descreve esse mecanismo — as demais ou contradizem a definição do algoritmo ou atribuem características que não lhe pertencem.

Alternativa A — ❌ Incorreta

Afirma que o QuickSort usa "comparações sequenciais sem divisões". Na verdade, o QuickSort realiza divisões (particionamento) e não é meramente sequencial: ele depende da recursão para dividir o array em partes menores. Essa descrição se aproxima mais de algoritmos simples como Selection Sort ou Bubble Sort, que fazem apenas comparações adjacentes sem subdividir.

Alternativa B — ✅ Correta ⟵ GABARITO

Exatamente a característica-chave: "Divisão recursiva em subproblemas menores". O QuickSort escolhe um pivô, particiona o array em elementos menores e maiores que o pivô, e então chama a si mesmo recursivamente para ordenar cada partição. Esse processo de divisão e conquista reduz drasticamente o número de comparações totais, conferindo eficiência assintótica.

Alternativa C — ❌ Incorreta

Diz que o QuickSort elimina trocas entre elementos adjacentes. Na verdade, o QuickSort realiza trocas (swap) entre elementos, inclusive entre posições não adjacentes, durante o particionamento. A afirmação é falsa porque o algoritmo faz trocas e não as elimina. A eliminação de trocas adjacentes é uma característica do Shell Sort (com gaps) ou do Counting Sort (não baseado em comparação).

Alternativa D — ❌ Incorreta

Afirma que o QuickSort ordena "diretamente sem memória auxiliar". Embora o QuickSort seja um algoritmo in-place (ordena no próprio array, exceto pela pilha de recursão), ele usa memória auxiliar implícita — a pilha de chamadas recursivas — que, no pior caso, pode ter profundidade O(n). Além disso, a descrição "sem memória auxiliar" é imprecisa e não é uma característica que define sua eficiência. Algoritmos como Merge Sort, embora não in-place, também são eficientes.

Alternativa E — ❌ Incorreta

"Processamento exclusivo de dados ordenados" é absurdo: o QuickSort é um algoritmo de ordenação geral, usado para desordenar dados (no sentido de colocá-los em ordem). Ele não exige que a entrada esteja ordenada; pelo contrário, seu desempenho piora quando os dados já estão ordenados (caso o pivô seja mal escolhido). Essa frase não corresponde a nenhuma característica do algoritmo.

Conclusão: A alternativa que descreve corretamente a razão da eficiência do QuickSort é a letra B — a estratégia de divisão recursiva em subproblemas menores.

Gabarito: letra B.