Tutorial aed iii 005 - algoritmo de ordenação quicksort

  • Published on
    14-Jun-2015

  • View
    2.804

  • Download
    23

Embed Size (px)

Transcript

<ul><li> 1. ALGORITMOS E ESTRUTURAS DE DADOS III Tutorial 5 (usa o compilador de linguagem C Dev-C++ verso 4.9.9.2)Parte 2 de 3 sobre o algoritmo de ordenao quick (rpido) conhecido como Quicksort.</li></ul> <p> 2. 2 O ALGORITMO DE ORDENAO1 INTRODUOQUICKSORTEsta srie de tutoriais sobre Algoritmos eEstruturas de Dados III foi escrita usando oMicrosoft Windows 7 Ultimate, Microsoft 2.1 ANLISE DE COMPLEXIDADEOffice 2010, Bloodshed Dev-C++ verso 4.9.9.2 O tempo de execuo do Quicksort varia(pode ser baixado em http://www.bloodshed.net), conforme a partio balanceada1 ou no.referncias na internet e notas de aula doprofessor quando estudante. Ela cobre desde osalgoritmos de ordenao, passando pela pesquisaem memria primria e culminando com apesquisa em memria secundria.Ns entendemos que voc j conhece ocompilador Dev-C++. No caso de voc ainda no oconhecer, d uma olhada nos tutoriais Dev-C++001 a 017, comeando pelo Tutorial Dev-C++ -001 - Introduo.Se no tem problemas com a linguagem C/C++ eo compilador Dev-C++, ento o prximo passo saber ler, criar e alterar arquivos em discousando linguagem C/C++. Se ainda no sabecomo faz-lo, d uma olhada nos tutoriais Dev-C++ 001 e 002, comeando pelo Tutorial Dev-C++001 Criao, Leitura e Alterao de Arquivos.Se sabe todas as coisas anteriores, ento aprxima etapa conhecer os algoritmos maisbsicos de ordenao. Em minhas notas de aulavoc encontra um material bsico, pormdetalhado e com algoritmos resolvidos, dosA figura mostra sucessivas chamadas recursivas do Quicksort usando como pivotprincipais mtodos de ordenao existentes. sempre o primeiro elemento. Notar os constantes desbalanceamentos.Adotaremos o livro Projeto de Algoritmos comSe a partio balanceada o Quicksort roda toImplementao em Pascal e C, Editora Cengagerpido quanto o Mergesort, com a vantagem queLearning, de Nivio Ziviani, como livro-texto da no precisar de array auxiliar.disciplina. Nele voc encontrar os mtodos deO pior caso do Quicksort ocorre quando aordenao que iremos estudar.partio gera um conjunto com 1 elemento eSeu prximo passo ser estudar os algoritmos de outro com n-1 elementos para todos os passos doordenao por Insero, Seleo e Shellsort.algoritmo. Sua desvantagem ocorre quando aVoc pode usar os links anteriores (em ingls) ou diviso do arranjo (que baseada emfazer uso do livro-texto. comparao) fica muito desbalanceada (istoocorrequando oarranjoest quaseEm seguida, voc precisa conhecer o algoritmo ordenado/desordenado ou est completamenteQuicksort. Para isto, voc pode seguir o Tutorial ordenado/desordenado), mostraremos isso noAED 004, desta srie, e/ou ler o captulo grfico abaixo. Mesmo com essa desvantagem referente no livro-texto. provado que em mdia seu tempo tende a sermuito rpido [Cormen, 2002] 2, por isso o nome,Se voc estiver lendo este tutorial tenha certeza Ordenao-Rpida (ou Quicksort em ingls).de ter seguido o Tutorial AED 004. Agora quevoc seguiu todos os passos at aqui, est prontopara prosseguir com este tutorial.1 Diz-se que a partio balanceada quando aps opivoteamento, a quantidade de itens esquerda e direita dopivot so iguais.2 Voc pode encontrar uma edio mais recente em Th.H.Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Introduction toAlgorithms, 3rd edition, MIT Press, 20091 3. necessidade de desenvolver novos algoritmos para problemas que j tm soluo. A performance extremamente importante na informtica pelo que existe uma necessidade constante de melhorar os algoritmos. Apesar de parecer contraditrio, com o aumento da velocidade dos computadores, torna-se cada vez mais importante desenvolver algoritmos mais eficientes, devido ao aumento constante do tamanho dos problemas a serem resolvidos.A figura mostra um grfico do comportamento do Quicksort no pior caso. Eixo Vertical: segundos de 0 11 Devido a este fator surge a Complexidade Eixo Horizontal: nmero de elementos de 100.000 2.000.000.Computacional, pois e atravs dela que se torna possvel determinar se a implementao deDesde que a partio custa uma recorrncia, determinado algoritmo vivel.neste caso torna-se A importncia da complexidade pode ser( ) ( ) ( ) observada no exemplo abaixo, que mostra 5e como ( )( ) no difcil mostrar quealgoritmos A1 a A5 para resolver um mesmo problema, de complexidades diferentes. Supomos ( )( )que uma operao leva 1 ms para ser efetuada. A tabela seguinte d o tempo necessrio por cadaSe a partio gera dois subconjuntos de tamanhoum dos algoritmos.n/2 temos a recorrncia Tk(n) a complexidade do algoritmo. ( )( ) ( ) n A1 A2 A3 A4 A5que pelo teorema master nos dT1(n) = n T2(n) = n log n T3(n) = n2 T4(n) = n3 T5(n) = 2n 16 0,016 s0,064 s0,256 s 4s 1m4s( ) ( ) 32 0,032 s0,160 s 1s 33 s46 dPode ser mostrado que o caso mdio do 5120,512 s9s 4 m 22 s 1 d 13 h 10137 sc.Quicksort muito prximo ao caso acima, ouseja O(n ln n). Na implementao acima, oelemento pivot foi tomado como o elementointermedirio do conjunto. Outras escolhas 2.1.3 TIPOS DE C OMPLEXIDADE .podem ser obtidas para gerar um melhor ESPACIAL Este tipo de complexidade representa oparticionamento. Algumas verses do Quicksortespao de memria usado para executar oescolhem o pivot aleatoriamente e se demonstra algoritmo, por exemplo.que esta conduta gera resultados prximos do TEMPORAL Este tipo de complexidade o maisideal. usado podendo dividir-se em dois grupos:Mas como podemos chegar a valores como n ln n Tempo (real)necessrio execuodoe n2? E o que significam as notaes O (micron), algoritmo.(mega) e (teta), em O(n ln n) ou O(n2)? Nmero de instruesnecessrias execuo.2.1.1 O QUE A COMPLEXIDADE ?A Complexidade de um algoritmo consiste na Para o estudo da complexidade so usadas trsquantidade de trabalho necessria para a sua perspectivas: pior caso, melhor caso e o casoexecuo, expressa em funo das operaes mdio.fundamentais, as quais variam de acordo com oalgoritmo, e em funo do volume de dados. 2.1.3.1 P IOR C ASO Este mtodo normalmente representado por2.1.2 PORQU O ESTUDO DA O( ), por exemplo se dissermos que umCOMPLEXIDADE?determinado algoritmo representado por g(x) e aMuitas vezes as pessoas quando comeam a sua complexidade Pior Caso n, serestudaralgoritmosperguntam-se qual a representada por g(x) = O(n).2 4. Consiste basicamente em assumir o pior dosmundial o limite superior pode ser melhorado porcasos que pode acontecer, sendo muito usado e um algoritmo (atleta) mais veloz.sendo normalmente o mais fcil de determinar.2.1.5 LOWER B OUNDExemplo:s vezes possvel demonstrar que para um dadoSe por exemplo existirem cinco bas, sendo queproblema, qualquer que seja o algoritmo a serapenas um deles tem algo dentro e os outros usado, o problema requer pelo menos certoesto vazios a complexidade no pior caso ser nmero de operaes. Essa complexidade O(5) pois eu, no pior dos casos, encontro o ba chamada limite inferior (lower bound). Veja que ocorreto na quinta tentativa.limite inferior depende do problema, mas no doalgoritmo em particular. Usamos a letra em2.1.3.2 M ELHOR C ASO lugar de O para denotar um limite inferior.Representa-se por ( ).Para o problema de multiplicao de matrizes deMtodo que consiste em assumir que vaiordem n, apenas para ler os elementos das duasacontecer o melhor. Pouco usado. Tem aplicaomatrizes de entrada leva O(n2). Assim uma cotaem poucos casos.inferior trivial (n2).Exemplo:Na analogia anterior, um limite inferior de umaSe tivermos uma lista de nmeros e quisermosmodalidade de atletismo no dependeria mais doencontrar algum deles assume-se que a atleta. Seria algum tempo mnimo que acomplexidade Melhor Caso (1), pois modalidade exige, qualquer que seja o atleta. Umassumimos que o numero estaria logo na cabea limite inferior trivial para os 100 metros seria oda lista. tempo que a velocidade da luz leva a percorrer100 metros no vcuo.2.1.3.3 C ASO M DIORepresenta-se por ( ).Se um algoritmo tem uma complexidade que igual ao limite inferior do problema, ento oEste mtodo dos trs, o mais difcil de algoritmo timo.determinar, pois necessita de anlise estatstica ecomo tal muitos testes. No entanto muitoO algoritmo de Coppersmith e Winograd deusado, pois tambm o que representa mais ( ) , mas o limite inferior de (n2).corretamente a complexidade do algoritmo. Portanto, no timo. Pode ser que este limitesuperior possa ainda ser melhorado.2.1.4 UPPER BOUNDSeja dado umproblema,por exemplo, 2.1.6 COMPLEXIDADE DE TEMPOmultiplicao de duas matrizes quadradas de Pode ser medida empiricamente, com funesordem n (). Conhecemos um algoritmo parapara o clculo do tempo.resolver este problema (pelo mtodo trivial) decomplexidade O(n3). Sabemos assim que a Exemplo:complexidade deste problema no deve superar#include O(n3), uma vez que existe um algoritmo destatime_t t1, t2;complexidade que o resolve. Um limite superior(upper bound) deste problema O(n3). O limitetime(&amp;t1);superior de um algoritmo pode mudar se algum /* Algoritmo entra aqui */descobrir um algoritmo melhor. Isso de fato time(&amp;t2);aconteceu com o algoritmo de Strassen que ( ). Assim o limite superior do problema de double diferenca = difftime(t2, t1);multiplicao de matrizes passou a ser ().//diferena em segundosOutros pesquisadores melhoraram ainda esteresultado. Atualmente o melhor resultado o de 2.1.6.1 ANLISE ASSINTTICACoppersmith e Winograd de ( ).Deve-se preocupar com a eficincia de algoritmosquando o tamanho de n for grande.O limite superior de um algoritmo parecido como recorde mundial de uma modalidade deA eficincia assinttica de um algoritmo descreveatletismo. Ela estabelecida pelo melhor atletaa eficincia relativa dele quando n torna-se(algoritmo) do momento. Assim como o recordegrande. Portanto, para comparar 2 algoritmos,3 5. determinam-se as taxas de crescimento de cadaaps um certo tempo. Por isso dizemos que esteum. O algoritmo com menor taxa de crescimentoalgoritmo da ordem de n2 ou que temrodar mais rpido quando o tamanho do complexidade O(n2).problema for grande. 2.1.6.1.2 R EGRAS PARA O CLCULO2.1.6.1.1 C ALCULANDO O TEMPO DE RepetiesEXECUO O tempo de execuo de uma repetio o tempoSupondo que as operaes simples demoram dos comandos dentro da repetio (incluindouma unidade de tempo para executar, consideretestes) vezes o nmero de vezes que executada.o cdigo abaixo para calcular . Repeties aninhadasint soma;A anlise feita de dentro para fora. O tempo total de comandos dentro de um grupo desoma = 0;repeties aninhadas o tempo de execuo dosfor(i = 1; i (dir-i)) { return y-&gt;vitorias-x-&gt;vitorias; item.dir = j; item.esq = esq;//2 - sets, maior primeiro Empilha(item, &amp;pilha); if(x-&gt;sets!=y-&gt;sets) return y-&gt;sets-x-&gt;sets; esq = i; }//3 - pontos marcados, maior primeiro else { if(x-&gt;pontosmarcados != y-&gt;pontosmarcados) return y-&gt;pontosmarcados x - &gt; pontosmarcados; item.esq = i; item.dir = dir;//ordem alfabetica Empilha(item, &amp;pilha);return (strcmp(x-&gt;nome,y-&gt;nome)); dir = j;} } } else { Desempilha(&amp;pilha,&amp;item); dir = item.dir; esq = item.esq; }} while (!Vazia(pilha));}6 8. Exemplo simplificado de qsort:#include #include int values[] = {40, 10, 100, 90, 20, 25};int compare(const void * a, const void * b) { return(*(int*)a - *(int*)b);}int main () { int n; qsort(values, 6, sizeof(int), compare); for(n=0; n a e positivo se a &gt; b */}/* funo de impresso de vetor */void imprime_vetor_inteiros(const int *array, size_t qtd) { size_t i;for(i=0; ipreco - 100.f*ib-&gt;preco); /* comparao de float: retorna negativo se b &gt; a e positivo se a &gt; b. Ns multiplicamos o resultado por 100.0 para preservar a fraes decimais */}/* funo de comparao para struct (campo produto do tipo C-string) */int compara_struct_por_produto(const void *a, const void *b) { struct st_ex *ia = (struct st_ex *)a; struct st_ex *ib = (struct st_ex *)b; return strcmp(ia-&gt;produto, ib-&gt;produto); /* strcmp trabalha exatamente como esperado de uma funo de comparao */}9 11. /* exemplo de funo para impresso de vetor de struct */ void imprime_vetor_de_struct(struct st_ex *array, size_t qtd) {size_t i; for(i=0; i 0 &amp;&amp; (j &gt; left)) j--; um caractere a mais do que o comprimento if(i left)) j--; if(i</p>