Algoritmos de ordenação podem ser aplicados em vários tipos de estruturas, como vetores, matrizes e estruturas dinâmicas (por exemplo: listas, pilhas e filas). Sobre os algoritmos

Gabarito

A

Comentário do professor

Quicksort é um algoritmo de ordenação baseado na estratégia de divisão e conquista. Ele escolhe um elemento chamado pivô e reorganiza o conjunto pelo processo de particionamento: coloca ao lado esquerdo elementos menores ou iguais ao pivô e ao direito os maiores.

Após o particionamento, o Quicksort aplica recursivamente a mesma rotina às sublistas esquerda e direita até que cada parte esteja ordenada. Essa divisão reduz o problema em subproblemas menores, caracterizando a técnica de conquista.

Em termos de complexidade, a ordem média é \(O(n\log n)\), mas o pior caso chega a \(O(n^2)\) quando o pivô é escolhido de forma desfavorável. Estratégias como pivô aleatório ou mediana de três reduzem essa chance.

Normalmente é in-place (usa pouco espaço extra) e, por padrão, não é estável, ou seja, não preserva a ordem relativa de elementos iguais sem ajustes.