Quick Sort

Quicksort

QuicksortAlgoritmo de Ordenao Rpida

1

Tecnologia em Anlise e Desenvolvimento de Sistemas

Estrutura de DadosProf. Fernanda Pupo Larguesa

Douglas SantosEvertt ArimaJssica TeixeiraPedro GonalezPedro HenriqueDisciplina& EquipeAlgoritmo de Ordenao QuickSort2

IntroduoFuncionamentoCenriosMelhorPiorAlgoritmoAplicabilidadeDetalhes de ImplementaoMelhoriasFontesContedoAlgoritmo de Ordenao QuickSort

IntroduoProposto por Charles Antony Richard Hoare em 1960 e publicado em 1962; o algoritmo de ordenao interna mais rpido que se conhece para uma ampla variedade de situaes;Provavelmente o mais utilizado;Algoritmo de Ordenao QuickSort4

Algoritmo de Ordenao QuickSortQuicksort popular porque no difcil de implementar, funciona bem para uma variedade de tipos diferentes de entrada de dados, e substancialmente mais rpido que qualquer outro mtodo de ordenao em aplicaes tpicas. in-place (usa somente uma pequena pilha auxiliar), necessita tempo proporcional a N log N em mdia para ordenar N itens, e tem um loop interno extremamente pequeno.Introduo

IntroduoDividir o problema de ordenar um conjunto com N itens em dois problemas menores;Os problemas menores so ordenados independentemente;As parties so combinadas para produzir a soluo final;O algoritmo considerado instvel, pois h a possibilidade de elementos com mesma chave mudar de posio no processo de ordenaoAlgoritmo de Ordenao QuickSort6

Algoritmo de Ordenao QuickSortFuncionamentoA parte mais delicada do mtodo o processo de partio.O vetor A [Esq...Dir] rearranjado por meio da escolha arbitrria de um piv x.O vetor A particionado em duas partes:Parte esquerda: chaves x.Parte direita: chaves x.

Algoritmo de Ordenao QuickSortFuncionamentoAlgoritmo para o particionamento:

1. Escolha arbitrariamente um piv x.2. Percorra o vetor a partir da esquerda at que A[i] x.3. Percorra o vetor a partir da direita at que A[j] x.4. Troque A[i] com A[j].5. Continue este processo at os apontadores i e j se cruzarem.

Algoritmo de Ordenao QuickSortFuncionamentoAo final, do algoritmo de partio:o vetor A[Esq..Dir] est particionado de tal forma que:Os itens em A[Esq], (A[Esq + 1], ..., A[j]), so menores ou iguais a x;Os itens em A[i], (A[i + 1], ..., A[Dir]), so maiores ou iguais a x.

AlgoritmoAlgoritmo de Ordenao QuickSortAlgoritmo:

Se: O nmero de elementos a ordenar for zero ou um ento termine (no h o que ordenar);Seno:Escolha um elemento do conjunto para ser o piv;Organize os elementos de acordo com o pivos elementos menores ficam a esquerda do piv;os elementos maiores ficam a direita do piv;Chame recursivamente o algoritmo para ordenar o grupo de elementos a direita e a esquerda do piv.

Algoritmo de Ordenao QuickSort

(Algorithms Sedgewick and Wayne 4. Ed. Pg. 289)Algoritmo

CenriosAlgoritmo de Ordenao QuickSortAnliseMelhor caso:CN = 2 CN/2 + N = N log NEsta situao ocorre quando cada partio divide o arquivo em duas partes iguais.

CenriosAlgoritmo de Ordenao QuickSortMelhor caso:

Uma rvore de recurso para QUICKSORT em que o PARTICIONAMENTO sempre equilibra os dois lados igualmente (melhor caso). O tempo de execuo resultante O(n lg n).

CenriosAlgoritmo de Ordenao QuickSortAnliseCaso mdio de acordo com Sedgewick e Flajolet (1996, p. 17):CN 1,386 log N 2 ln NIsso significa que em mdia o tempo de execuo do Quicksort O(n log n).

CenriosAlgoritmo de Ordenao QuickSortCaso mdio:

Uma rvore de recurso para QUICKSORT em que o PARTICIONAMENTO sempre produz uma diviso de 9-para-1, tendendo a um tempo de execuo de O(n lg n). FONTE:

CenriosAlgoritmo de Ordenao QuickSortAnlisePior caso: CN = N2O pior caso ocorre quando, sistematicamente, o piv escolhido como sendo um dos extremos de um arquivo j ordenado.Isto faz com que o procedimento de ordenao seja chamado recursivamente N vezes, eliminando apenas um item em cada chamada.

CenriosAlgoritmo de Ordenao QuickSort

Pior caso:Uma rvore de recursividade para QUICKSORT em que o procedimento de PARTIO sempre coloca apenas um elemento de um lado da partio (pior caso). O tempo de execuo resultante O(n2).

AplicaesAlgoritmo de Ordenao QuickSortVantagens: Melhor opo para ordenar vetores grandes;Muito rpido por que o lao interno simples;Memria auxiliar para a pilha de recurso pequena;Complexidade no caso mdio O(n lg(n)).

Desvantagens:Perde eficincia em vetores pequenos;No estvel (no conhecida forma eficiente para tornar o quicksort estvel);Pior caso quadrtico.

Detalhes deImplementaoAlgoritmo de Ordenao QuickSortDetalhes de Implementao:

Particionamento interno (Partitioning inplace). Se usarmos um vetor extra, particionamento fcil de implementar, mas no to mais fcil que vale o custo de a verso particionada de volta no original. Permanea dentro dos limites (Staying in bounds). Se o menor ou maior valor do vetor for o piv, temos que tomar cuidado para os indicadores no ultrapassarem os limites esquerdo ou direito do vetor, respectivamente.


Preservar a aleatoriedade (Preserving randomness).O embaralhamento aleatrio desordena o vetor. Desde que trate todos os termos nos sub-vetores uniformemente, este recurso tem a propriedade de que estes tambm estejam aleatoriamente desordenados. Este fato crucial para a previsibilidade do algoritmo. Uma forma alternativa para preservar a aleatoriedade escolher um termo aleatrio para piv na partio. Finalizando o loop (Terminating the loop). Teste apropriadamente se os indicadores cruzaram um pouco mais difcil do que pode parecer primeira vista. Um erro comum esquecer de considerar que o vetor possa ter termos de mesmo valor que o piv.


Manipulando termos com valores iguais ao piv (Handling items with keys equal to the partitioning item's key). melhor para as varreduras esquerda para valores maiores ou iguais ao piv e direita para valores menores ou iguais ao piv. Apesar desta poltica possa parecer criar trocas desnecessrias envolvendo termos de mesmo valor, crucial para evitar tempo de execuo quadrtico em certas aplicaes tpicas. Finalizando a recurso (Terminating the recursion).Um erro comum na implementao do quicksort envolve no se assegurar que determinado termo seja sempre colocado em posio, gerando um loop recursivo infinito quando o piv o menor ou maior valor no vetor.

MelhoriasAlgoritmo de Ordenao QuickSortMelhorias:

Mudar para Insertion Sort. Como na maioria dos algoritmos recursivos, uma forma fcil de melhorar a performance do quicksort baseada nas seguintes duas observaes:Quicksort mais devagar que insertion sort para pequenos sub-vetores.Se for recursivo, quicksort certamente chamar a si mesmo para pequenos sub-vetores. O melhor valor para mudar para Insertion Sort dependente do Sistema, mas qualquer valor entre 5 e 15 provvel de ser eficiente para maioria das situaes.


Particionamento Mediana-de-trs.Uma segunda forma fcil de melhorar performance do quicksort usar a medianda de uma amostra pequena de termos retirada do sub-vetor como sendo o piv. Tal ao resultar em uma partio melhor, mas ao custo de computar a mediana. Na prtica, a maior parte das melhorias vm da escolha de uma amostra de tamanho 3 e particionando no item central. Como um bonus, pocemos usar a amostra como sentinelas nas extremidades do vetor e remover ambos dos testes de partio.


Entropy-optimal sorting. Vetores com grandes quantidades de valores duplicados aparecem com frequncia em aplicaes. Por exemplo, podemos querer ordenar um grande arquivo de colaboradores por ano de nascimento, ou talvez separ-los por gnero. Nestas situaes, implementar o quicksort tem uma performance considervel, mas pode ser melhorado de forma substancial. Por exemplo, um sub-vetor que consiste apenas de termos de mesmo valor no precisa ser processado novamente, mas nossa implementao continua a particion-los em sub-vetores menores. Em uma sitao onde h um grande nmero de valores duplicados, a natureza recursiva do quicksort se assegura que sub-vetores compostos inteiramente de termos de mesmo valor ocorrer com frequncia. H potencial para uma melhora significativa.

FontesAlgoritmo de Ordenao QuickSortSedgewick, Robert & Wayne, KevinAlgorithms - 4th. EditionPrinceton University Pearson Education, Inc.Chapter 2.3 page 288Cormen, Leiserson, Rivest & SteinIntroduction to Algorithms 3rd. EditionThe MIT Press Massachusetts Institute of TechnologyChapter 7 page 170Sedgewick, RobertAlgorithmsBrown University Addison-Wesley Publishing Co.Chapter 9 page 103Princeton University Dept. of Computer ScienceHanson, David R.Lecture 11 Quicksorthttps://www.cs.princeton.edu/courses/archive/spr97/cs126University of North Carolina Dept. of Computer Sciencehttp://cs.unc.eduJordan University of Science and TechnologyChapter 7 Quicksortwww.just.edu.jo/~basel/algorithms/.../algo_ch7_quick_sort.pdf

FontesAlgoritmo de Ordenao QuickSortUniversity of Science and Technology of Chinahttp://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap08.htmSouza, Jairo Francisco deUniversidade Federal de Juiz de Fora - UFJFEstrutura de Dados II Quicksorthttp://www.ufjf.br/jairo_souza/ensino/material/ed2Boniati, Bruno B.Universidade Federal de Santa MariaEstrutura de dados Quicksort & Mergesorthttp://www.cafw.ufsm.br/~brunoMenotti, DavidUniversidade Federal de Ouro Preto - UFOPEstrutura de Dados I Quicksorthttp://www.decom.ufop.br/menotti/Feofiloff, Paulohttp://www.ime.usp.br/~pf/algoritmos/http://www.ime.usp.br/~pf/analise_de_algoritmos/

Algoritmo de Ordenao QuickSort

Apndice

ApndiceAlgoritmo de Ordenao QuickSort// Esta funo rearranja qualquer vetor// v[p..r] em ordem crescente.

void quicksort (int v[], int p, int r) { int j; // 1 if (p < r) { //ou while(p < r) {// 2j = separa (v, p, r); // 3 quicksort (v, p, j-1); // 4 quicksort (v, j+1, r); // 5}} Cdigo Quicksort Bsico:

ApndiceAlgoritmo de Ordenao QuickSortAlgoritmo de Separao:// Recebe vetor v[p..r] com p

Documents

Quick Sort