1. Escolha um elemento que será chamado o pivot da lista.
  2. Reordene a lista de tal forma que os elementos menores que o pivot venham antes dele e os elementos maiores ou iguais ao pivot venham depois dele. Essa operação é chamada de partição, e cria duas sublistas:
    a. a de menores que o pivot e
    b. a de maiores ou iguais ao pivot.
  3. Aplique recursivamente os passos 1 e 2 às sublistas de menores e maiores que o pivot. O algoritmo acima corresponde ao:
    a) Quicksort, e faz, em média, O(n log n) comparações para ordenar n itens.

Passo 1

Vamos começar entendendo o que a questão está pedindo. O enunciado descreve um algoritmo que escolhe um elemento chamado pivô, reorganiza a lista colocando os menores que o pivô antes dele e os maiores ou iguais depois. Depois, ele aplica esse processo de forma recursiva nas duas sublistas. Isso está relacionado ao conteúdo de algoritmos de ordenação, especificamente o Quicksort. Para resolver, vamos identificar qual algoritmo está sendo descrito e entender sua eficiência.

Passo 2

O algoritmo descrito no enunciado é o Quicksort. O Quicksort é um dos algoritmos de ordenação mais eficientes e é amplamente utilizado devido à sua boa performance na maioria dos casos. Ele funciona escolhendo um pivô, partindo a lista com base nesse pivô (como descrito no enunciado) e então ordenando recursivamente as sublistas resultantes.

Passo 3

A opção apresentada afirma que o Quicksort faz, em média, O(n log n) comparações para ordenar n itens. Essa afirmação está correta. Embora no pior caso o Quicksort possa ter uma complexidade de O(n^2), na média ele se comporta muito bem com uma complexidade de O(n log n), o que o torna eficiente para grandes conjuntos de dados.

Resposta

a) Quicksort, e faz, em média, O(n log n) comparações para ordenar n itens.

Exercícios relacionados