- Escolha um elemento que será chamado o pivot da lista.
- 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
b. a de maiores ou iguais ao pivot.
- 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,
comparações para ordenar
itens.
a. a de menores que o pivot
b. a de maiores ou iguais ao pivot.
a) Quicksort, e faz, em média,
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,
comparações para ordenar
itens. Essa afirmação está correta. Embora no pior caso o Quicksort possa ter uma complexidade de
, na média ele se comporta muito bem com uma complexidade de
, o que o torna eficiente para grandes conjuntos de dados.
Resposta
a) Quicksort, e faz, em média,
comparações para ordenar
itens.
Exercícios relacionados
Em uma Árvore Binária de Busca (BST) balanceada, qual das seguintes operações geralmente exibe uma complexidade de tempo média de
, considerando a estrutura balanceada da árvore?
a) A Inserção de um novo nó e remoção de um nó.
a) A Inserção de um novo nó e remoção de um nó.
Com relação às estruturas de dados em listas, analise as afirmativas a seguir.
I. Em uma lista não ordenada, os elementos devem estar organizados em ordem decrescente das respectivas chaves.
II. Uma lista encadeada é uma estrutura de dados, na qual os objetos estão organizados em ordem linear.
III. Em uma lista duplamente encadeada, cada elemento deve apontar para o elemento anterior e para o próximo.
Está correto o que se afirma em:
c) I e III, apenas.
I. Em uma lista não ordenada, os elementos devem estar organizados em ordem decrescente das respectivas chaves.
II. Uma lista encadeada é uma estrutura de dados, na qual os objetos estão organizados em ordem linear.
III. Em uma lista duplamente encadeada, cada elemento deve apontar para o elemento anterior e para o próximo.
Está correto o que se afirma em:
c) I e III, apenas.
Seja o seguinte vetor, ordenado de forma ascendente:
10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Caso se utilize um algoritmo de busca binária, quantas iterações serão necessárias para que o valor 80 seja encontrado?
b) 3
b) 3
Seja o seguinte vetor, ordenado de forma ascendente:
10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Caso se utilize um algoritmo de busca binária, quantas iterações serão necessárias para que o valor 80 seja encontrado?
c) 4
c) 4