Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCC 2018
Algoritmos e Estrutura de DadosAlgoritmos
- Código
- fc044547
- Banca
- FCC
- Órgão
- DPE-AM
- Ano
- 2018
- Cargo
- Assistente Técnico de Defensoria - Programador
Considerando que N é número de elementos do vetor a ser ordenado, a estratégia de ordenação apresentada em Java
- Atambém é conhecida como método de ordenação por intercalação e possui uma versão para unir dois vetores já ordenados.
- Btem complexidade O(N²) no pior caso e no caso médio, mas apresenta complexidade O(N) no melhor caso.
- Cfaz um número fixo de comparações dado por log₂N, independente dos valores do vetor original. Isso é garantido pelas chamadas recursivas ao método ordena().
- Dutiliza o método separar() para dividir o vetor original em 2 sublistas de igual tamanho. Isso garante que mesmo no pior caso o método realize Nlog₂N comparações.
- Eutiliza o método separar() para fazer a partição do vetor, por meio da seleção de um elemento chamado pivô. A escolha do pivô é crucial para o bom desempenho do método, já que a fase de partição é a parte crítica do algoritmo.