Algorítimo de ordenação

  • Published on
    30-Jun-2015

  • View
    715

  • Download
    0

Embed Size (px)

Transcript

<ul><li> 1. Faculdade de Tecnologia de Presidente PrudenteAlgortmo de OrdenaoAnlise e Desenvolvimento de Sistemas 3 Mdulo</li></ul> <p> 2. O que ?Algoritmo que coloca os elementos de umadada sequncia em uma certa ordem onde asmais usadas so a numrica e a lexicogrfica. 3. Lexigrfica Analisa a entrada de linhas de caracteres eproduz uma seqncia chamada de "smboloslxicos" (lexical tokens), ou somente "smbolos"(tokens). 4. Shellsort(Diminuio de incrementos) Criado por Donald Shell em 1959, publicadopela Universidade de Cincinnati. Mais eficiente algoritmo de classificaodentre os de complexidade quadrtica. um refinamento do mtodo de inserodireta. 5. Cdigo em Cvoid shellSort(int * vet, int size) {int i , j , value;int gap = 1;do { gap = 3*gap+1;} while(gap &lt; size);do {gap /= 3;for(i = gap; i &lt; size; i++) {value =vet[i];j = i - gap;while (j &gt;= 0 &amp;&amp; value &lt; vet[j]) {vet [j + gap] =vet[j];j -= gap;}vet [j + gap] = value; }} while ( gap &gt; 1);} 6. Exemplo de execuoDado o vetor de entrada: 12, 43, 1, 6, 56, 23, 52, 9 12, 43, 1, 6, 56, 23, 52, 9 12, 43, 1, 6, 56, 23, 52, 9 1, 43, 12, 6, 56, 23, 52, 9 1, 6, 12, 23, 56, 43, 52, 9 1, 6, 12, 23, 52, 43, 56, 9 1, 6, 12, 23, 52, 9, 56, 43 1, 6, 12, 9, 52, 23, 56, 43 1, 6, 9, 12, 52, 23, 56, 43 1, 6, 9, 12, 23, 52, 56, 43 1, 6, 9, 12, 23, 52, 43, 56 1, 6, 9, 12, 23, 43, 52, 56Obtemos o vetor ordenado: 1, 6, 9, 12, 23, 43, 52, 56. 7. Mergesort (Fuso) um exemplo de algoritmo de ordenao do tipodividir-para-conquistar. Criar uma sequncia ordenada a partir de duasoutras tambm ordenadas dividindo a sequnciaoriginal em pares de dados, ordena-as; depois asagrupa em sequncias de quatro elementos, eassim por diante, at ter toda a sequnciadividida em apenas duas partes. (resumir estetpico) Os trs passos teis do algoritmo so: dividir,conquistar e combinar. 8. VantagemAlgoritmo de ordenao de simplesimplementao e fcil entendimento utilizandochamadas recursivas. 9. DesvantagemAlto consumo de memria, devido a srie dechamadas recursivas. 10. Cdigo em Cvoid mergesort(int begin, int end)for(i = begin;i end ||= 0;(left</p>