Considere o seguinte algoritmo de ordenação de elementos em uma lista: 1. Es...

Responda: Considere o seguinte algoritmo de ordenação de elementos em uma lista: 1. Escolha um elemento que será chamado o pivot da lista. 2. Reordene a lista de tal forma que os elementos...

1Q622776 | Informática, Analista de Planejamento, IBGE, CESGRANRIO

Considere o seguinte algoritmo de ordenação de elementos em uma lista:

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.
✂️ b) Quicksort, e faz, em média, O(n²) comparações para ordenar n itens.
✂️ c) Insertionsort, e faz, em média, O(n) comparações para ordenar n itens.
✂️ d) Insertionsort, e faz, em média, O(n log n) comparações para ordenar n itens.
✂️ e) Bublesort, e faz, em média, O(n²) comparações para ordenar n itens.

💬 Comentários

Confira os comentários sobre esta questão.

Por Camila Duarte em 31/12/1969 21:00:00

Gabarito: a)

O algoritmo descrito é o Quicksort, que funciona escolhendo um pivot, particionando a lista em elementos menores e maiores ou iguais ao pivot, e aplicando recursivamente o mesmo processo nas sublistas. Em média, o Quicksort realiza O(n log n) comparações para ordenar n itens, o que o torna eficiente para muitos casos. As outras opções mencionam algoritmos diferentes ou complexidades incorretas para o algoritmo descrito.

⚠️ Clique para ver os comentários

Visualize os comentários desta questão clicando no botão abaixo

Ver comentários