Métodos de Ordenação Ordenação em memória primária

  • Published on
    18-Apr-2015

  • View
    142

  • Download
    27

Embed Size (px)

Transcript

<ul><li> Slide 1 </li> <li> Mtodos de Ordenao Ordenao em memria primria </li> <li> Slide 2 </li> <li> Objetivos Dado um vetor de tamanho n, com ndices de 0 a n-1, onde cada posio possui uma chave de ordenao Um algoritmo de ordenao deve rearranjar o vetor de forma a estabeler uma ordem entre os elementos onde, para quaisquer elementos v i-1, v i v i-1 &lt; v i, i = 1..n-1, considerando a chave de ordenao. 01234 732101 01234 1237 Vetor desordenado V de tamanho n = 5 Ordena(V,n) Vetor ordenado: </li> <li> Slide 3 </li> <li> Mtodo da Seleo (Selection Sort) Descrio: Seleciona sempre o menor elemento remanescente do conjunto no ordenado e move este elemento para sua posio correta Algoritmo 1. Encontrar o menor elemento e trocar com o elemento na primeira posio do vetor 2.Encontrar o segundo menor elemento e trocar com o elemento na segunda posio do vetor e assim sucessivamente... </li> <li> Slide 4 </li> <li> Mtodo da Seleo algoritmo seleo (int a[], int n){ Para i da primeira posio at a penltima faca mnimo = i para j da posio seguinte a i at a ultima posio faa se (a[j] &lt; a[mnimo] minimo =j; fim para troca(a[mnimo],a[i]); fim algoritmo Exemplo: {7,3,2,10,1} Para i =0, mnimo terminar com o valor 4, e o 1 ser trocado com o 7 {1,3,2,10,7} i=1, mnimo terminar com o valor 2, e o 2 ser trocado com o 3 {1,2,3,10,7} i= 2, mnimo terminar com o valor 4, e no haver troca i=3, mnimo terminar com o valor 4, e o 7 ser trocado com o 10 {1,2,3,7,10} </li> <li> Slide 5 </li> <li> Mtodo da Insero Descrio: Considera cada elemento uma vez inserindo- o em seu lugar correto entre os elementos que j esto em ordem. (Usado para ordenar cartas de um baralho na mo do jogador.) Algoritmo: 1.O elemento inserido entre os ordenados movendo-se os elementos maiores que ele uma posio para a direita e posteriormente inserindo-o na posio vaga. </li> <li> Slide 6 </li> <li> Mtodo da Insero (Insertion sort) Algoritmo insercao(int A[], int n) para j do segundo elemento at o ltimo faa x = A[j]; i=j-1; enquanto (i &gt;= 0 e A[i] &gt; x) faa A[i+1]=A[i]; i = i-1; fim enquanto A[i+1]=x; fim para fim algoritmo Exemplo: {7,3,2,10,1} Para j = 1, o 7 empurrado uma posio e o 3 colocado na posio (i+1) = 0 {3,7,2,10,1} Para j =2, { 3,7} so empurrados uma posio e o 2 colocado na posio 0 {2,3,7,10,1} Para j=3, ningum empurrado e o 10 colocado na mesma posio onde estava {2,3,7,10,1} Para j =4, {2,3,7,10} so empurrados uma posio e o 1 inserido na posio 0: {1,2,3,7,10} </li> <li> Slide 7 </li> <li> Mtodo da bolha (bouble sort) Descrio: Consiste em percorrer o vetor trocando os elementos adjacentes caso necessrio. O maior elemento vai subir (como um bolha) para a ltima posio do vetor. </li> <li> Slide 8 </li> <li> Mtodo da Bolha algoritmo bolha ( int a[],int n) Para i do ultimo elemento at o segundo faa para j do segundo elemento at i faa se (a[j-1]&gt;a[j]) troca(&amp;a[j-1],&amp;a[j]); } Exemplo ijA={7,3,2,10,1} 41{3,7,2,10,1} 2{3,2,7,10,1} 3 4{3,2,7,1,10} 31{2,3,7,1,10} 2 3{2,3,1,7,10} 21 2{2,1,3,7,10} 11{1,2,3,7,10} </li> <li> Slide 9 </li> <li> Exerccio Implementar os mtodos insero, seleo e bolha em C e fazer uma avaliao de desempenho dos mesmos Usar a funo abaixo para gerar vetores aleatrios: #include geravetor(int a[], int N){ int i; srand(time(NULL)); for (i=0;i</li></ul>