Sobre algoritmos de ordenação

  • Published on
    13-Jul-2016

  • View
    2

  • Download
    0

Embed Size (px)

DESCRIPTION

Sobre algoritmos de ordenao

Transcript

<ul><li><p>Bubble Sort </p><p> No bubble sort analisado de duas em duas posies de um vetor, ordenando conforme seja determinada a lgica, crescente ou decrescente; </p><p> A ideia percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequncia. </p><p>Vantagem </p><p> A principal vantagem desse algoritmo que sua implementao fcil e conhecida. </p><p> Estvel </p><p>Desvantagem </p><p> um mtodo simples, porm lento. </p><p> No apresenta bons resultados quando a lista contm muitos itens. </p><p> O fato de o arquivo j estar ordenado no ajuda a reduzir o nmero de comparaes (o custo continua quadrtico), porm o nmero de movimentaes cai para zero. </p><p> void bubble (int vetor[],int tamanho){ </p><p>int aux; </p><p> for (int i=0; i</p></li><li><p> Heap Sort </p><p> uma rvore binria com seguintes propriedades: O valor de cada pai maior ou menor que os valores armazenados em cada filho; As folhas no ltimo nvel esto todas nas posies mais esquerda, podendo haver a falta de um elemento. </p><p>Vantagens </p><p> O Algoritmo heapsort apresenta o tempo mdio constante e satisfatrio (at nos piores cenrios); </p><p> Consumo de memria baixo (mesmo em comparao com outros algoritmos de ordenao); </p><p>Desvantagens </p><p> No recomendado para entrada com poucos elementos, por conta do heap ser muito complexo; </p><p> No to rpido quanto o quicksort ou outros mtodos em algumas situaes; </p><p> O Heapsort no estvel. </p><p>void max_heapify(int *a, int i, int n) </p><p>{ </p><p> int j, temp; </p><p> temp = a[i]; </p><p> j = 2*i; </p><p> while (j a[j]) </p><p> j = j+1; </p><p> if (temp &gt; a[j]) </p><p> break; </p><p> else if (temp </p></li><li><p> } </p><p> a[j/2] = temp; </p><p> return; </p><p>} </p><p>void heapsort(int *a, int n) </p><p>{ </p><p> int i, temp; </p><p> for (i = n; i &gt;= 2; i--) </p><p> { </p><p> temp = a[i]; </p><p> a[i] = a[1]; </p><p> a[1] = temp; </p><p> max_heapify(a, 1, i - 1); </p><p> } </p><p>} </p><p>void build_maxheap(int *a, int n) </p><p>{ </p><p> int i; </p><p> for(i = n/2; i &gt;= 1; i--) </p><p> { </p><p> max_heapify(a, i, n); </p><p> } </p><p>} </p><p>int main() </p><p>{ </p><p> int n, i, x; </p><p> coutn; </p><p> int a[20]; </p><p> for (i = 1; i </p></li><li> cout</li><li><p>Merge Sort </p><p>Vantagens </p><p> til para ordenao externa; </p><p> Pior caso: O(n log n); </p><p> Aplicaes com restrio de tempo; </p><p> Fcil implementao. </p><p>Desvantagens </p><p> Utiliza memria auxiliar; </p><p> Possui dependncia de outro vetor de tamanho idntico; </p><p> Alto consumo de memria. </p><p>VAZIO mergeSort(VETOR array) </p><p>SE TAMANHO(vetor) &gt; 1 ENTO </p><p>NUMERICO mid, i </p><p>mid TAMANHO(vetor) / 2) </p><p>VETOR esquerda[mid], direita[TAMANHO(vetor) - mid] </p><p>PARA i 0 AT TAMANHO(esquerda) </p><p>esquerda[i] array[i] </p><p>FIM </p><p>PARA i 0 AT TAMANHO(direita) </p><p>direita[i] array[i] </p><p>FIM </p><p>//Recurso para distribuio </p><p>mergeSort(esquerda) </p><p>mergeSort(direita) </p><p>intercala(array, esquerda, direita) </p><p>ELSE </p><p>ESCREVA Vetor j ordenado. </p><p>FIM </p><p>FIM </p></li><li><p>VAZIO intercala(VETOR array, VETOR esquerda, VETOR direita) </p><p>NUMRICO i1 0, i2 0, i </p><p>PARA i 0 AT TAMANHO(array) </p><p>// Verifica qual dos 2 valores menor e isnere no </p><p>vetor </p><p>SE( i1 &lt; TAMANHO(esquerda) E i2 &lt; TAMANHO(direita)) ENTO </p><p>SE(esquerda[i1] &lt; direita[i2]) ENTO </p><p>array[i] esquerda[i1] </p><p>i1 i1 + 1 </p><p>ELSE </p><p>array[i] direita[i2] </p><p>i2 i2 + 1 </p><p>FIM </p><p>FIM </p><p>//Caso os tamanhos dos vetores sejam diferentes, faz </p><p>a verificao individual de cada vetor </p><p>SENO SE (i1 &lt; TAMANHO(esquerda)) ENTO </p><p>array[i] esquerda[i1] </p><p>i1 i1 + 1 </p><p>SENO </p><p>array[i] direita[i2] </p><p>i2 i2 + 1 </p><p>FIM </p><p>FIM </p><p>FIM </p></li><li><p>Insertion Sort </p><p>Vantagens </p><p>Simplicidade </p><p> Bom desempenho em listas pequenas </p><p>Desvantagens </p><p>No funciona bem com listas grandes </p><p>N passos necessrios para funcionar </p><p>void InsertSort (int vet[]){ </p><p> int i,j,aux; </p><p> for (i = 1; i &lt; 5; i++){ </p><p> j = i; </p><p> while (j &gt; 0 &amp;&amp; vet[j-1] &gt; vet[j]) { </p><p> aux = vet[j]; </p><p> vet[j] = vet[j-1]; </p><p> vet[j-1] = aux; </p><p> j--; </p><p> } </p><p> } </p><p>} </p><p>int main(int argc, char** argv) { </p><p>int vet[5]; </p><p> coutvet[i]; </p><p> } </p><p> cout</p></li><li> cout</li><li><p>Bubble Sort </p><p>Vantagens </p><p>A principal vantagem desse algoritmo que sua implementao fcil e conhecida. </p><p> Estvel </p><p>Desvantagens </p><p> um mtodo simples , porm lento . </p><p>No apresenta bons resultados quando a lista contm muitos itens. </p><p>O fato de o arquivo j estar ordenado no ajuda a reduzir o nmero de comparaes (o custo continua quadrtico), porm o nmero de movimentaes cai para zero. </p><p>void cresc(int vetor[]){ </p><p>int aux; </p><p>for(int a=0;a</p></li><li><p>return EXIT_SUCCESS; </p><p>} </p></li><li><p>ShellSort </p><p>Vantagens: </p><p>Shellsort uma tima opo para arquivos de tamanho moderado; </p><p>Sua implementao simples e requer uma quantidade de cdigo pequena. </p><p>Desvantagens: </p><p>O tempo de execuo do algoritmo sensvel ordem inicial do arquivo; </p><p>O mtodo no estvel. </p><p>void shellSort(int *vet, int size) { //Vou assumir que o tamanho do vetor 8 ( size = vet[7]) int i , j , value; int gap = 1; while(gap &lt; size) { gap = 3*gap+1; //Aqui definido o espaamento entre a verificao } //das variveis atravs do gap while ( gap &gt; 1) { //Tendo nota que seu valor no pode ser maior que gap /= 3; //o tamanho do vetor que ser ordenado for(i = gap; i &lt; size; i++) { value = vet[i]; //Vai pegando o valor no vetor com o espaamento (Se gap for 4, pegar o ndex 4, na prox rodada do for, pega o ndex 5 etc.) j = i - gap; //Mesma coisa que em cima, s que vai passando os ndex 0,1,2,3 para o J (A varivel value pega os valores do ndex 4,5,6,7) while (j &gt;= 0 &amp;&amp; value &lt; vet[j]) { // Faz a verificao, basicamente se a varivel do ndex 4 for menor que a do ndex 0, vet [j + gap] = vet[j]; // eles trocam de posio (Alis, s um valor trocado por enquanto) j -= gap; // Aqui ele vai saindo do while depois de fazer as verificaes, deixando o J menor que 0 } vet [j + gap] = value; //Aqui o outro valor trocado, aquele que estava armazenado em value, note que o J s armazenou posio, } // enquanto o value armazenou o valor que estava na posio </p><p>} </p><p>} </p></li><li><p>QuickSort </p><p>Vantagens </p><p> extremamente eficiente para ordenar arquivos de dados. </p><p>Necessita de apenas uma pequena pilha como memoria auxiliar. </p><p>Funciona muito bem com listas grandes de itens. </p><p>Para dados bem bagunados o quicksort mais vantajoso por ser mais econmico. </p><p>Desvantagens </p><p>Sua implementao delicada e difcil. Um pequeno engano pode levar a efeitos inesperados para algumas entradas de dados. </p><p>O mtodo no estvel. </p><p> #include </p><p>void Quick(int vetor[10], int inicio, int fim); </p><p>int main(){ </p><p> int vetor[10] = {7, 9, 4, 3, 6, 1, 18, 2, 10, 5}; </p><p> int i; </p><p> printf("Vetor desordenado:\n"); </p><p> for(i = 0; i &lt; 10; i++){ </p><p> printf("%d ", vetor[i]); </p><p> } </p><p> printf("\n"); </p><p> Quick(vetor, 0, 9); </p><p> printf("Vetor ordenado:\n"); </p><p> for(i = 0; i &lt; 10; i++){ </p><p> printf("%d ", vetor[i]); </p><p> } </p><p> printf("\n"); </p><p>} </p><p>void Quick(int vetor[10], int inicio, int fim){ </p><p> int pivo, aux, i, j, meio; </p><p> i = inicio; </p></li><li><p> j = fim; </p><p> meio = (int) ((i + j) / 2); </p><p> pivo = vetor[meio]; </p><p> do{ </p><p> while (vetor[i] &lt; pivo) i = i + 1; </p><p> while (vetor[j] &gt; pivo) j = j - 1; </p><p> if(i i); </p><p> if(inicio &lt; j) Quick(vetor, inicio, j); </p><p> if(i &lt; fim) Quick(vetor, i, fim); </p><p>} </p></li></ul>