Alternativa E - Apenas a afirmativa I está incorreta.
Introdução ao Algoritmo Quicksort
O algoritmo Quicksort é um método de ordenação baseado na estratégia Dividir e Conquistar. Sua principal característica é a alta eficiência em média, com complexidade temporal de O(n \log n). O funcionamento central depende da escolha de um elemento especial chamado pivô, que serve para particionar o conjunto de dados.
Para responder corretamente, devemos analisar cada afirmação considerando a teoria clássica de estruturas de dados e algoritmos, focando no pedido da questão: identificar as informações INCORRETAS.
Análise Detalhada das Afirmações
- Afirmação I (Incorreta):
- Estabilidade: Um algoritmo de ordenação é considerado estável se mantém a ordem relativa de elementos com chaves iguais após a ordenação.
- O Quicksort clássico é um algoritmo instável. Durante o processo de troca de elementos (particionamento), a posição relativa de valores iguais pode ser alterada sem garantia de preservação.
- Logo, dizer que ele é "considerado um método de ordenação estável" é falso.
- Afirmação II (Correta):
- A escolha do pivô impacta diretamente a performance. Se o pivô for consistentemente o menor ou maior valor (como em vetores já ordenados), a complexidade degrada para O(n^2) no pior caso.
- Estratégias heurísticas como a mediana de três (escolher a mediana entre o primeiro, o meio e o último elemento) são técnicas válidas para aumentar a probabilidade de escolher um bom pivô.
- Afirmação III (Correta):
- Não existe uma regra fixa sobre onde o pivô deve estar inicialmente. Ele pode ser o primeiro, o último, um elemento aleatório ou o elemento do meio do vetor. Todas essas opções são estratégias legítimas de implementação.
- Afirmação IV (Correta):
- Esta frase descreve perfeitamente a etapa de particionamento. O objetivo é reorganizar o vetor de modo que todos os elementos menores que o pivô fiquem à sua esquerda e todos os maiores fiquem à sua direita.
Conclusão
Dentre as quatro afirmações apresentadas, apenas a número I contém uma informação falsa, pois o Quicksort é tradicionalmente classificado como um algoritmo instável. As demais afirmativas descrevem corretamente a importância do pivô, suas possíveis posições e a lógica de divisão.
Portanto, a alternativa que aponta apenas a informação incorreta é a letra E.