Questão 163060

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2010
• Provas: CESGRANRIO - 2010 - Petrobrás - Analista de Sistemas Júnior - Processos de Negócios
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação; Conceitos Básicos e Algoritmos

O quicksort é um algoritmo que funciona usando o paradigma de dividir e conquistar, usando uma rotina de particionamento que divide o vetor de estruturas em dois pedaços em torno de um pivô. O pedaço da esquerda só contém elementos com chaves menores ou iguais que o elemento corrente e o pedaço da direita, só elementos com chaves maiores que o elemento corrente. O algoritmo procede, então, para o subproblema de ordenar cada um dos pedaços e seu desempenho total é um dos mais eficientes para ordenação de estruturas de dados. Qual das seguintes descrições representa uma correta característica do algoritmo quicksort?

• A. O algoritmo de particionamento é o ponto fraco do quicksort, podendo exigir até n² operações de trocas em cada iteração, o que faz com que ele precise ser fortemente otimizado.
  
• B. O algoritmo de particionamento só funciona nos casos em que o número de elementos no vetor é par, pois é necessário, para o correto cálculo do pivô, que o lado esquerdo e o direito tenham exatamente o mesmo tamanho.
  
• C. Seu tempo de execução, no pior caso, é ,que ocorre no caso especial em que a rotina de particionamento gera subproblemas com n-1 elementos e outro com 0 elemento.
  
• D. Seu tempo de execução de melhor caso é , que ocorre no caso especial em que o vetor de estruturas já está ordenado.
  
• E. Seu tempo de execução é de no caso do particionamento ser desbalanceado na proporção de 2 elementos para um lado, para cada elemento do outro lado.

Gabarito: C

Comentários

• Método da Troca e Partição (QuickSort): é o mais rápido entre os métodos
  apresentados até o momento, e também o mais utilizado. Esse método foi
  proposto por C. A. R. Hoare em 1962 e parte do princípio que é mais rápido
  classificar dois vetores com n/2 elementos cada um, do que um com n
  elementos (dividir um problema maior em dois menores).
  A parte mais delicada do método é o particionamento do vetor. O vetor é
  particionado em três segmentos:
  V[1], ..., V[i - 1]           V[i]                V[i + 1], ..., V[n]
  (segmento 1)   (segmento 2)   (segmento 3)
  A partição é realizada através da escolha arbitrária de um elemento (V[i])
  de modo que os elementos no segmento 1 sejam menores, e os elementos
  no segmento 3 sejam maiores do que o elemento escolhido V[i].
  Após a ordenação dos segmentos 1 e 3, tem-se o vetor original
  classificado. O processo de partição pode ser repetido para os segmentos
  1 e 3.
  Obs. Quando um segmento apresenta um número de elementos menor ou
  igual a M (um número pré-estabelecido), aplica-se um método simples de
  ordenação.

• • Complexidade de tempo: θ(n lg₂ n) no melhor caso e no caso médio e θ(n²) no pior caso;
  • Complexidade de espaço: θ(lg₂ n) no melhor caso e no caso médio e θ(lg₂ n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n²) no pior caso.
• Essa questão deveria ter sido anulada, pois apresenta erro de notação.
  
  teta(n): caso médio
  ômega(n): pior caso
  O(n): pior caso
  
  Como a questão utiliza teta(n) para falar de pior caso, há erro de notação. Alguém comenta?

• Olá galera, dica rápida, simples e free!!!!

   

                        PIOR     MÉDIO     MELHOR
  QUICK SORT:      O(n2)      O(nlogn)      O(nlogn)

   

  A técnica de particionamento é uma arma poderosa que o quicksort possui.

   

  Para maiores detalhes: https://pt.wikipedia.org/wiki/Quicksort

   

   

  Go ahead!!!

• Gabarito C

  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 !

• c-

  O método Quicksort é uma aplicação do princípio divide and conquer. Para a ordenação, inicialmente o vetor é dividido em uma sublista da direita e uma da 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. o pior caso é n². normal é nlogn