Questão 1561579

• Banca: Marinha
• Órgão: Quadro Complementar
• Ano: 2013
• Provas: Marinha - 2013 - Quadro Complementar - Segundo-Tenente - Engenharia da Computação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

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

• A. Ao terminar a primeira interação do método de ordenação bolha (BUBBLE SORT) pode-se garantir que as trocas realizadas posicionam o maior elemento na última posição .
  
• B. Uma solução para o problema da seleção do pivô no método de ordenação rápida (QUICKSORT) com bons resultados é a escolha da mediana dentre três elementos, sendo esses: o primeiro, o segundo e o terceiro.
  
• C. Uma interação do método de ordenação por intercalação (MERGESORT) se limita a percorrer a tabela do início ao fim, sem interrupção, trocando de posição dois elementos consecutivos sempre que estes se apresentem fora de ordem.
  
• D. Em algoritmos de ordenação rápida (QUICKSORT), a escolha do primeiro elemento como pivô, quando a tabela está ordenada na ordem inversa à desejada, provoca o melhor desempenho desse tipo de algoritmo.
• E. O método de ordenação por inserção consiste em dividir a lista original em duas metades e ordená-las, sendo o resultado duas listas ordenadas que podem ser concatenadas.

Gabarito: A

Comentários

• O 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.

  
  

  
  

  O 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;

  
  

  
  

  O 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.