Questão EPO - Quicksort

Analise as afirmativas abaixo sobre Quicksort e assinale a alternativa correta:

I. Faz uso de um pivô aleatório e particiona o vetor em duas partes
II. Valores maiores ficam à esquerda do pivô e valores menores à direita do pivô
III. Após o particionamento da lista, o pivô estará na sua posição final
IV. Repete o procedimento dos passos I, II e III em cada sublista até que a ordenação esteja completa

a) I e II
b) I, II e III
c) I e III
d) Todas as alternativas
e) n.d.a

Questão EPO - Quicksort

Sobre Quick Sort é correto afirmar:

I. Sua implementação é muito delicada e difícil;
II. O método não é estável;
III. É extremamente eficiente para ordenar arquivos de dados;
IV. Como o Merge sort o Quick Sort é muito mais eficiente em vetores de tamanhos pequenos;

a) I, II, III
b) I, II, IV
c) II, III, IV
d) TODAS
e) NDA

Referencia:
http://homepages.dcc.ufmg.br/~rfortes/aeds/2/slides/aula17_quicksort.pdf

Questão EPO - Quicksort

 Sobre o Quicksort, é correto afirmar que:

a) Ordena comparando elementos adjacentes (dois a dois) e percorre o vetor em uma direção apenas;
b) Ordena de maneira adaptativa e compara os elementos das extremidades do vetor;
c) É um algoritmo de abordagem “Dividir para conquistar”, que divide usando um elemento pivô como referência e ordena recursivamente;
d) É um algoritmo com ótima performance para vetores com poucos elementos, pois  faz o número mínimo de comparações, mesmo no pior caso;
e) NDA.

Questão EPO - Quicksort

Assinale a alternativa incorreta

a) Mais rápido algoritmo de Ordenação (não paralelo)
b) Baseia-se na ordenação de sub-listas divididas por um pivô
c) O pivô é um elemento escolhido ao acaso, que é colocado na sua posição correta quando a lista estiver ordenada.
d) Implementação complexa, não muito melhor para listas de pequeno tamanho (<100 elementos)
e) N.D.A

Fonte:
http://www.comp.ita.br/~pauloac/ces10/quicksort.pdf

Questão EPO - Quicksort

Qual a sequencia de passos que o quick sort usa para ordenar?

a)    1) Escolha um elemento da lista, denominado pivô;
    2) 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 sub-listas não ordenadas. Essa operação é denominada partição;
    3) Recursivamente ordene a sub-lista dos elementos menores e a sub-lista dos elementos maiores;

b)    1) Recursivamente ordene a sub-lista dos elementos menores e a sub-lista dos   elementos maiores;
    2) 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 sub-listas não ordenadas. Essa operação é denominada partição;
    3) Escolha um elemento da lista, denominado pivô;

c)    1) Escolha um elemento da lista, denominado pivô;
    2) Recursivamente ordene a sub-lista dos elementos menores e a sub-lista dos elementos maiores;
    3) 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 sub-listas não ordenadas. Essa operação é denominada partição;

d)    1) Recursivamente ordene a sub-lista dos elementos menores e a sub-lista dos elementos maiores;
    2) Escolha um elemento da lista, denominado pivô;
    3) 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 sub-listas não ordenadas. Essa operação é denominada partição;

e) N.D.A

Retirado de http://pt.wikipedia.org/wiki/Quicksort

Questão EPO - Quicksort

p				j					r
<=c	<=c	<=c	<=c	=c	>c	>c	>c	>c	>c

Analise a figura acima assinale a alternativa correta:

a) Temos um vetor de n elementos e J é o elemento com conteúdo igual ao numero total de elementos;
b) J é o elemento escolhido como pivô;
c) J é o meio e somente isso, depois de divide tudo, ordena-se os lados e depois os une;
d) J é o pivô e ele troca os elementos ao seu lado primeiro e depois consecutivamente;
e) NDA

Fonte:
http://www.ime.usp.br/~pf/algoritmos/aulas/quick.html

Questão EPO - Quicksort

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". Como é realizada está divisão?

a) O quick elege um pivô, ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.
b) O quick sort não realiza divisões no método de ordenação.
c) Divide de maneira aleatória e após a junção das partes é realizada a ordenação do vetor.
d) O método quick ordena sem dividir em sublistas
e) Nda.

Questão EPO - Quicksort

Sobre quick sort é correto afirmar que:

a) O Quicksort é um algoritmo de ordenação por comparação não-estável.

b) O Quicksort é um algoritmo de ordenação do tipo dividir-para-conquistar.

c) Ela é composta por células que apontam para o próximo elemento da lista

d) Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado.

e) nda

Questão EPO - Quicksort

Sobre o Quick  Sort é correto afirmar que:

I. Usa do mesmo método do Merge sort “Dividir e conquistar”, o que o difere que usa um elemento da lista que é denomidado Pivô;
II. Os elementos menores do que o Pivô vão para a direita do mesmo e o maiores a esquerda;
III. Como o Merge sort o Quick Sort é muito mais eficiente em vetores de tamanhos pequenos;
IV. A cada iteração, localiza a posição final de um elemento aleatório (pivô) e subdivide o vetor em duas partes para prosseguir a ordenação.

a) I,II e IV
b) I,III e IV
c) II e IV
d) I e IV
e) NDA

Retirado do material:
http://www.deinf.ufma.br/~csalles/ed2/aula06_07.pdf
http://pt.wikipedia.org/wiki/Quicksort

Questão EPO - Quicksort

Qual a melhor definição para Quick Sort?

a) Definir um numero -> Ordenar menores antes deste maiores depois -> ordenar numeros maiores -> ordenar numeros menores,

b) Definir um numero -> Ordenar menores antes deste maiores depois -> Definir outro numero para cada sublista -> Repetir o processo para todas as sublistas até que a sequencia esteja ordenada.

c) Encontrar menor numero -> Entcontrar maior numero -> Encontrar numero medio -> ordenar numeros entre menor e medio -> ordenar numeros entre medio e maior,

d) Separar todos os numeros em pares -> ordenar pares -> juntar todos os pares -> Repetir até que todos estejam ordenados;

e) N.D.A.

Fonte:
Bolada com o conhecimento adquirido em sala.

Questão EPO - Quicksort

Quais alternativas estão CORRETAS sobre QuickSort

I. É o mais lento de todos algoritimos de ordenação.
II. A pior situação ocorre se o pivô escolhido é o menor ou o maior numero do conjunto de dados.
III. Não divide o veto em subvetores para a ordenação.
IV. Ele pode ser muito eficiente caso o pivô escolhido tenha um valor mediano no conjunto de dados.

a) I e II
b) II e III
c) I, II e IV
d) II e IV
e) N.D.A.

Questão EPO - Quicksort

O QuickSort, como o MergeSort, é baseado em uma estratégia de dividir para conquistar e é um dos algoritmos de ordenação mais populares. O QuickSort é baseado no método de ordenação por trocas.

O algoritmo QuickSort pode ser dividido nos seguintes passos:

O array A[p..r] é subdividido em dois arrays A[p..q] e A[q+1..r] não vazios tal que cada elemento de A[p..q] é menor ou igual a cada elemento de A[q+1..r]. O índice q é calculado como parte deste particionamento.

Os dois subarrays A[p..q] e A[q+1..r] são ordenados por recursivas chamadas do QuickSort.

Dado o array  f e d h a c g b, e tomando o valor “d” para partição, o primeiro passo do quicksort rearranja o array da seguinte forma:

a) a b c d e f g h
b) f e d h a c g b
c) b c a d h e g f
d) b c f a h e g f
e) NDA

Questão EPO - Quicksort

Considere a figura abaixo e assinale a alternativa correta

a) Se ao invés do 5, o 9 fosse tomado como primeiro pivô, o  subgrupo particionado dos elementos menores teria todos os outros elementos do grupo a ser ordenado.
b) A figura contém um erro no subgrupo dos elementos menores que o primeiro pivô
c) A figura contém um erro no subgrupo dos elementos maiores que o primeiro pivô
d) O procedimento na figura é ineficiente, pois esta utilizando mais passos que o algoritmo Quick sort realmente precisa para ordenar um vetor de 9 posições.
e) N.D.A

Questão Quick sort baseada em :
"ALGORITMOS E ESTRUTURAS DE DADOS - Quinto Trabalho Prático - Análise de Desempenho de Algoritmos de Ordenação por Comparação e suas Variações e Otimizações" - Luiz Henrique Santos - Universidade Federal de Ouro Preto- Instituto de Ciências Exatas e Biológicas - Departamento de Computação

Questão EPO - Quicksort

Observe as sentenças:

I.  Ele escolhe o primeiro elemento aleatoriamente
II.  Subdivide a lista de forma que os menores que o pivô fique do lado esquerdo e os maiores do lado direito
III.  Ordena as sub listas recursivamente
   
Indique a correta:   
a) II e III estão corretas
b) I e II estão corretas
c) Somente a II está correta
d) Todas estão corretas
e) NDA

Fonte:
Slides vistos em apresentação
http://pt.wikipedia.org/wiki/Quicksort

Questão EPO - Quicksort

O Quicksort é uma estrutura de dados de ordenação que possui as seguintes características na utilização de um vetor:

a) Varre o vetor  da esquerda para a direita ordenando em ordem decrescente.
b) Escolha de um pivô no início do vetor e de uma função que parte o vetor ao meio, ordenando os valores menores a esquerda e os maiores a direita.
c) Escolha de um pivô que compara índice a índice os valores maiores e menores, ordenando os valores menores a esquerda e os maiores a direita.
d) Divide ao meio o vetor, ordena e depois une para exibição.
e) N.D.A

Questão EPO - Quicksort

Quais dos seguintes algoritmos de ordenação são instáveis?

I. BubbleSort (ordenação por bolha);
II. InsertionSort (ordenção por inserção);
III. Merge sort;
IV. Quick sort;

a) Somente II.
b) Somente I e II.
c) Somente I, II e III.
d) Somente IV
e) NDA

Fonte:
http://www.allgoritmos.com/2009/08/poscomp-2005-q33-algoritmos-de.html

Questão EPO - Quicksort

Assinale as afirmativas corretas:

I. O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960.
II. O Quicksort é um algoritmo de ordenação por comparação não-estável.
III. 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".
IV. São um tipo de estruturas de dados cujos objetos estão ligados duma maneira linear.

a) Todas estão corretas.
b) I, II e III.
c) I e II
d) Somente II.
e) NDA.

Referência:
http://pt.wikipedia.org/wiki/Quicksort

Questão EPO - Quicksort

Analise as afirmativas sobre Quicksort e marque a alternativa correta:

I. Quicksort randômico não é um método adaptivo
II. Não foi criado nenhuma adaptação pois seu desempenho sempre foi excelente.
III. Muito bom tanto para ordenação de poucos quanto para muitos valores.
IV. Muito usado em universidades pela difícil implementação, sendo assim aguçando as habilidades dos programadores.

a) I e III estão corretas.
b) I, III e IV estão incorretas.
c) II, III e IV estão incorretas.
d) Todas estão corretas.
e) N.D.A

Questão EPO - Quicksort

Em relação ao método de ordenação Quick Sort clássico, julgue os itens à seguir:

I. Por ser um método de ordenação estável, é igualmente rápido em quaisquer tipos de cenários de elementos.
II. Uma das técnicas usadas é a recursividade.
III. A cada subdivisão do array escolhe-se um elementos central (pivô) onde os maiores valores passarão a sua direita e os menores a sua esquerda.

a) Todas as alternativas estão corretas.
b) Apenas uma alternativa está incorreta.
c) Duas afirmativas estão incorretas.
d) Nenhuma das afirmativas são corretas.
e) N. D. A.

Questão EPO - Quicksort

O QuickSort é um algoritmo que se utiliza da técnica dividir-para-conquistar,  efetuando a partição do vetor desordenado em sub-vetores menores e escolhendo um vetor aleatório pra servir de parâmetro pra a ordenação interna. Tendo em vista essa definição, qual alternativa está incorreta:

a) O QuickSort necessita apenas de uma pequena pilha como memória auxiliar para conter os sub-vetores já parcialmente ordenados
b) O pior caso de ordenação do QuickSort ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos arquivos já ordenados
c) O QuickSort possui uma implementação extremamente simples, já que pequenos erros cometidos no código não influem na entrada de dados
d) O QuickSort é um método de ordenação não estável e que possui seu pior caso em O(n2) comparações.
e) N.D.A.

Fonte:
http://www.decom.ufop.br/toffolo/site_media/cms_page_media/27/T-15.%20Ordenacao%20(Parte%202).pdf