Algoritmos de busca e ordenação - Ordenação Bolha e Ordenação de Seleção Direta

  • Published on
    08-Aug-2015

  • View
    34

  • Download
    1

Embed Size (px)

Transcript

<ol><li> 1. INSTITUTO FEDERAL RIO GRANDE DO SUL Campus Osrio 1 </li><li> 2. Ao final desta Aula: Conhecer o mtodo de ordenao bublesort e seleo direta. Desenvolver os seus respectivos algoritmos 2 </li><li> 3. Lembre-se Sempre que tiver dvidas, pergunte. Muita ateno nas explicaes; Utilize as referncias para estudar em casa. 3 </li><li> 4. Estruturas de seleo Estruturas de repetio Vetores; Algoritmos, em geral Caso tenha diculdades na resoluo do exerccio, revise o seguinte contedo: 4 </li><li> 5. Como ordenamos nossas coisas? 5 </li><li> 6. Algoritmos de Ordenao Troca Seleo Bubble Sort Cocktail Sort Comb Sort Gnome Sort Odd-even Sort Quicksort Selection Sort HeapSort 6 Insertion Sort Shell Sort Insero </li><li> 7. Ordenao bolha 7 Mtodo de ordenao simples; Entendimento e implementao fceis; um dos mais conhecidos mtodos de ordenao; No um algoritmo eficiente; Objetivo desenvolver o raciocnio. O Princpio do Bubble sort a troca entre posies consecutivas, fazendo com que os valores mais altos (ou mais baixos) borbulhem para o final do conjunto </li><li> 8. Ordenao bolha 8 Considere o conjunto abaixo: 5 3 1 4 2 Como poderamos orden-lo? </li><li> 9. Ordenao bolha 9 Passo 1: Comparar os dois primeiros valores. 5 3 1 4 2 Esto desordenados entre si? &lt; </li><li> 10. Ordenao bolha 10 Passo 1: Comparar os dois primeiros valores. 3 5 1 4 2 Est ordenado, agora? &lt; </li><li> 11. Ordenao bolha 11 Passo 2: Repetir o procedimento at o final. 3 5 1 4 2 Esto desordenados entre si? &lt; </li><li> 12. Ordenao bolha 12 Passo 2: Repetir o procedimento at o final. 3 1 5 4 2 E agora? &lt; </li><li> 13. Ordenao bolha 13 Passo 2: Repetir o procedimento at o final. 3 1 5 4 2 5 menor que o 4? &lt; </li><li> 14. Ordenao bolha 14 Passo 2: Repetir o procedimento at o final. 3 1 4 5 2 inverte &lt; </li><li> 15. Ordenao bolha 15 Passo 2: Repetir o procedimento at o final. 3 1 4 5 2 5 menor que o 2? &lt; </li><li> 16. Ordenao bolha 16 3 1 4 2 5 Agora, 0 5 "borbulhou" at a ltima posio, que a correta. O Prximo passo repetir o processo desde o incio, sem comparar o penltimo elemento com o ltimo. </li><li> 17. Ordenao bolha 17 3 1 4 2 5 Comparar os valores: 3 menor que 1? &lt; </li><li> 18. Ordenao bolha 18 1 3 4 2 5 3 menor que 4? &lt; Comparar os valores: </li><li> 19. Ordenao bolha 19 1 3 4 2 5 4 menor que 2? &lt; Comparar os valores: </li><li> 20. Ordenao bolha 20 1 3 2 4 5 Agora, o 4 est na posio final. Devemos continuar comparando do incio, sem utilizarmos o 4 e o 5. </li><li> 21. Ordenao bolha 21 1 3 2 4 5 1 menor que 3? Comparando: &lt; </li><li> 22. Ordenao bolha 22 1 3 2 4 5 3 menor que 2? Comparando: &lt; </li><li> 23. Ordenao bolha 23 1 2 3 4 5 Basta agora, realizar o mesmo processo do incio, ignorando o 3 em diante. Continuando: &lt; </li><li> 24. Ordenao bolha 24 1 2 3 4 5 Como s temos um ltimo elemento... 2 Est na sua posio final: </li><li> 25. Ordenao bolha 25 1 2 3 4 5 A ordenao acabou! </li><li> 26. Bolha.c 26 #include int main(void) { int vetor[5] = {5, 3, 1, 4, 2}; int tamanho = 5; int aux; for(int i=tamanho-1; i &gt;= 1; i--) { for( int j=0; j &lt; i ; j++) { if(vetor[j] &gt; vetor[j + 1]) { aux = vetor[j]; vetor[j] = vetor[j+1]; vetor[j + 1] = aux; } } } for( int r = 0; r &lt; tamanho; r++){ printf("%dn",vetor[r]); } } </li><li> 27. Seleo Direta 27 Ao comparar, caso o primeiro elemento esteja desordenado em relao ao outro, feita a troca; Ao alcanar o final do conjunto, teremos o menor valor ou o maior, conforme feita a primeira comparao. Este algoritmo, embora contenha o mesmo nmero de comparaes que o bubble sort, o numero mdio de trocas menor. O Mtodo de ordenao seleo direta consiste em varrer o conjunto comparando todos os elementos com o primeiro. </li><li> 28. Seleo Direta 28 Considere o conjunto abaixo: 5 3 1 4 2 Como poderamos orden-lo pela seleo direta? </li><li> 29. Seleo Direta 29 Passo 1: Comparar o primeiro com o segundo. 5 3 1 4 2 Esto desordenados entre si? &lt; </li><li> 30. Seleo Direta 30 Passo 2: Comparar o primeiro com os prximos. 3 5 1 4 2 Esto desordenados entre si? &lt; </li><li> 31. Seleo Direta 31 Passo 2: Comparar o primeiro com os prximos. 1 5 3 4 2 Esto desordenados entre si? &lt; </li><li> 32. Seleo Direta 32 Passo 2: Comparar o primeiro com os prximos. 1 5 3 4 2 Esto desordenados entre si? &lt; </li><li> 33. Seleo Direta 33 O menor elemento foi deslocado para sua posio correta! 1 5 3 4 2 O Primeiro eleento no precisa ser mais comparado </li><li> 34. Seleo Direta 34 Passo 3: Comparar o os restantes. 1 5 3 4 2 Esto desordenados entre si? &lt; </li><li> 35. Seleo Direta 35 Passo 3: Comparar o os restantes. 1 3 5 4 2 Esto desordenados entre si? &lt; </li><li> 36. Seleo Direta 36 Passo 3: Comparar o os restantes. 1 3 5 4 2 Esto desordenados entre si? &lt; </li><li> 37. Seleo Direta 37 Segundo item completo. 1 2 5 4 3 Assim por diante. </li><li> 38. Seleo Direta 38 Continuando as comparaes. 1 2 5 4 3 Assim por diante. &lt; </li><li> 39. Seleo Direta 39 Continuando as comparaes. 1 2 4 5 3 Assim por diante. &lt; </li><li> 40. Seleo Direta 40 Mais um item em sua posio. 1 2 3 5 4 Assim por diante. </li><li> 41. Seleo Direta 41 Continuando. 1 2 3 5 4 Assim por diante. &lt; </li><li> 42. Seleo Direta 42 Mais um item em sua posio. 1 2 3 4 5 Assim por diante. </li><li> 43. Seleo Direta 43 Mais um item em sua posio. 1 2 3 4 5 S sobrou o ltimo item, e j est na posio correta. </li><li> 44. Seleo Direta 44 Finalizou a ordenao. 1 2 3 4 5 </li><li> 45. Selecao.c 45 #include intmain(intargc,constchar*argv[]){ intvetor[5]={5,3,1,4,2}; inttamanho=5; inti,j,menor,aux; for(i=0;i</li></ol>