Vamos analisar detalhadamente a questão proposta e entender porque a alternativa correta é a D, ou seja, todas as afirmativas estão corretas.

Afirmativa I: Quicksort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independente, e depois os resultados são combinados para produzir a solução de ordenação do conjunto maior.

O Quicksort é um dos algoritmos de ordenação mais eficientes e amplamente utilizados. Ele usa a estratégia de "divisão e conquista," onde um pivô é escolhido e o conjunto de dados é particionado em dois sub-conjuntos: um com elementos menores que o pivô e outro com elementos maiores. Esses sub-conjuntos são então ordenados independentemente. Portanto, a afirmativa está correta.

Afirmativa II: Seleção é um método que consiste em selecionar o menor item de um vetor e substituí-lo pelo item que estiver na primeira posição. Essas duas operações são repetidas com os itens restantes até o último elemento.

O método de Seleção (ou Selection Sort) funciona exatamente como descrito: ele encontra o menor elemento na lista e o coloca na posição inicial, repetindo este processo para os elementos subsequentes. Portanto, esta afirmativa também está correta.

Afirmativa III: Shellsort é uma extensão do algoritmo de ordenação por Inserção, contornando o problema que ocorre quando o menor item de um vetor está na posição mais à direita.

O Shellsort é realmente uma generalização do algoritmo de Inserção, mas ele melhora a eficiência ao permitir a troca de elementos que estão distantes entre si. Isso é feito usando uma sequência de espaçamentos que diminui ao longo do tempo. Portanto, a descrição está correta.

Assim, todas as afirmativas I, II e III estão corretas, levando-nos à alternativa D como a correta.

Alternativa D: As afirmativas I, II e III estão corretas.

Quicksort

O problema desta página é o mesmo das três páginas anteriores:  rearranjar um vetor v[0..n-1] (ou seja, permutar os elementos do vetor) de modo que ele fique em ordem crescente, isto é, de modo que tenhamos v[0] ≤ ... ≤ v[n-1].

O algoritmo Quicksort, inventado por C.A.R. Hoare [Computer Journal, 5, pp.10-15, 1962], resolve o problema.  O algoritmo é muito rápido em geral, mas é lento em algumas raras instâncias especiais.  O algoritmo consome tempo proporcional a  n log(n)  em média e proporcional a  n²  no pior caso.

Usaremos duas abreviaturas ao discutir o algoritmo.  A expressão  "v[h..j] ≤ x"  será usada como abreviatura de  "v[i] ≤ x para todo i no conjunto de índices h..j".  Analogamente, a expressão  "v[h..j] ≤ v[k..m]"  será interpretada como "v[i] ≤ v[l] para todo ino conjunto h..j e todo l no conjunto k..m".

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

Ordenação: algoritmos elementares

Esta página trata do seguinte problema:  Permutar (ou seja, rearranjar) os elementos de um vetor  v[0..n-1]  de tal modo que eles fiquem em ordem crescente, ou seja, de tal forma que tenhamos  v[0]   ≤   v[1]   ≤   . . .   ≤   v[n-1] .

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

 

Shell sort

Criado por Donald Shell em 1959,^[1] publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.^[2] O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles.^[3] Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção.

http://pt.wikipedia.org/wiki/Shell_sort

 

Sempre achei que quicksort primeiro fazia o processo para a lista inteira, e depois repetia o processo recursivamente para as chaves a esquerda e a direita do pivot. Alguém poderia comentar sobre isso por favor?

I. Quicksort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independe, e depois os resultados são combinados para produzir a solução de ordenação do conjunto maior. (Correto)

a) Algoritmo Quicksort é do tipo dividir para conquistar.
b) Ideia do algoritmo: efectuar partição dos dados e ordenar as várias partes independentemente (de forma recursiva)
c) Processo de partição é crítico
d) Uma vez efectuada a partição, cada uma das partes pode ser ordenada pelo mesmo algoritmo.

II. Seleção é um método que consiste em selecionar o menor item de um vetor e substituí-lo pelo item que estiver na primeira posição. Essas duas operações são repetidas com os itens restantes até o último elemento. (Correto)

a) A idéia é sempre procurar o menor elemento do vetor e inseri-lo no início do vetor.
b) Procuramos o menor valor do vetor e colocamos ele em vetor[1]. Procuramos o menor valor do vetor excluindo o já colocado e colocamos ele em   vetor[2]. E assim vamos indo até termos todo o vetor ordenado.

III. Shellsort é uma extensão do algoritmo de ordenação por Inserção, contornando o problema que ocorre quando o menor item de um vetor está na posição mais à direita. (Correta)

a) Extensão do algoritmo de ordenação por inserção
b) Ordenação por inserção só troca itens adjacentes para determinar o ponto de inserção.
c) São efetuadas n-1 comparações e movimentações quando o menor item está na última posição

Essa afirmativa tá com muito mais cara de merge sorte que quick sort não acham? Apesar de serem parecidos pelo fato de dividir e conquistar, é característica do merge ir "juntando" novamente os sub-vetores e os ordenar um com o outro. No quick vai se fragmentando cada vez mais o vetor total separando-o por um pivô. Ao final, cada sub -vetor já está disposto de forma ordenada, não existe essa "volta" reordenando um com o outro. O GABARITO deveria ser a letra C.

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

Seleção - encontra o menor elemento e o troca com a primeira posição, depois o segundo menor com a segunda posição, e assim sucessivamente (n-1 vezes). Número de com,parações (N2 − N)/2, sendo muito lento e inadequado para valores grandes de N. 
 

Shellsort - é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. Os itens separados de h posições são earranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é dita estar h-ordenada.
 

 

 

 

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