Questão 459298

• Banca: FCC
• Órgão: INFRAERO
• Ano: 2011
• Provas: FCC - 2011 - INFRAERO - Analista de Sistemas - Desenvolvimento e Manutenção
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

O método de ordenação QuickSort (ordenação rápida) é um método sofisticado de ordenação de vetores que

• A. considera em cada passo somente um único elemento sucessor na sequência fonte e todos os elementos do vetor destino para encontrar o ponto correto da inserção.
• B. ordena todos os elementos que estiverem a intervalos de 4 posições entre si na sequência corrente.
• C. é baseado nos princípios de ordenação por inserção direta através de incrementos decrescentes.
• D. é baseado no fato de que as permutações devem ser preferencialmente empregadas para pares de elementos que guardem entre si distâncias grandes, com a finalidade de se conseguir uma eficiência maior.
• E. é baseado nos princípios de ordenação por seleção direta que consiste na seleção repetitiva da menor dentre as chaves de n elementos, e depois dentre os n-1 elementos restantes, e assim por diante.

Gabarito: D

Comentários

• a) INSERTION SORT: considera em cada passo somente um único elemento sucessor da seqüência fonte e todos os elementos do vetor destino para encontrar o ponto correto de inserção
  
  b) SHELL SORT:ordena todos os elementos que estiverem a intervalos de 4 posições entre si na sequência corrente.
  
  c) SHELL SORT: é baseado nos princípios de ordenação por inserção direta através de incrementos decrescentes.
  
  d) QUICK SORT: é baseado no fato de que as permutações devem ser preferencialmente empregadas para pares de elementos que guardem entre si distâncias grandes, com a finalidade de se conseguir uma eficiência maior.
  
  e) SELECTION SORT: é baseado nos princípios de ordenação por seleção direta que consiste na seleção repetitiva da menor dentre as chaves de n elementos, e depois dentre os n-1 elementos restantes, e assim por diante.

• Gabarito D

  Quicksort - Escolhe-se um pivot e particiona-se a lista em duas sublistas: uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivot, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio é de O(n log n).
   

   

   

   

  "Retroceder Nunca Render-se Jamais !"
  Força e Fé !
  Fortuna Audaces Sequitur !

• O método Quicksort é do tipo divide and conquer. Para a ordenação, o vetor é dividido em uma sublista da direita e esquerda, de modo que todo elemento da sublista da esquerda seja menor que o da direita. Em seguida, ordenam-se, pelo mesmo processo, as duas sublistas de forma recursiva.