-
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 n2 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
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
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 !
-
Força Guerreiro!!!!!!
-
Força Guerreiro!!!!!!