SóProvas


ID
1561579
Banca
Marinha
Órgão
Quadro Complementar
Ano
2013
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Em relação aos Algoritmos de ordenação, assinale a opção correta.

Alternativas
Comentários
  • bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência.



    Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. 

     Os passos são:

    - Escolha um elemento da lista, denominado pivô;

    - Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;

    - Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;



    merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

    Sua ideia básica consiste em Dividir(o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar(após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas).Como o algoritmo do Merge Sort usa a recursividade em alguns problemas esta técnica não é muito eficiente devido ao alto consumo de memória e tempo de execução.

    Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

    - Dividir: Dividir os dados em subsequências pequenas;

    - Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;

    - Combinar: Juntar as duas metades em um único conjunto já classificado.

  • O gabarito é a letra A.

     

    O Bubble Sort percorre várias vezes o vetor de maneira sequencial. Em cada passo, compara cada elemento no vetor com o seu sucessor (p[i] com p[i+1]) e troca o conteúdo das posições em análise, caso não estejam na ordem desejada. Ao final da primeira iteração, apesar do vetor não estar ordenado ainda, o maior elemento fica na última posição.