Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CESGRANRIO 2013
Algoritmos e Estrutura de DadosEstrutura de Dados
- Código
- cg000859
- Banca
- CESGRANRIO
- Órgão
- IBGE
- Ano
- 2013
- Nível
- Superior
- Cargo
- Analista - Análise e Desenvolvimento de Aplicações
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
- AQuicksort, e faz, em média, O(n log n) comparações para ordenar n itens.
- BQuicksort, e faz, em média, O(n² ) comparações para ordenar n itens.
- Cnsertionsort, e faz, em média, O(n) comparações para ordenar n itens.
- DInsertionsort, e faz, em média, O(n log n) comparações para ordenar n itens.
- EBublesort, e faz, em média, O(n² ) comparações para ordenar n itens.