UFSC-CTC-INE INE Estruturas de Dados - ppt carregar
PublicouThalita Prados Alterado mais de 6 anos atrás
Apresentação em tema: "UFSC-CTC-INE INE Estruturas de Dados"— Transcrição da apresentação:
1 UFSC-CTC-INE INE5384 - Estruturas de Dados
Ordenação de Dados Prof. Ronaldo S. Mello 2002/2
2 Ordenação de Dados Processo bastante utilizado na computação de uma estrutura de dados Dados ordenados garantem uma melhor performance de pesquisa a uma ED busca seqüencial evita a varredura completa de uma lista de dados busca binária só é possível se os dados estão ordenados apresenta baixa complexidade
3 Compromisso "A complexidade da ordenação da ED não deve exceder a complexidade da computação a ser feita na ED sem o processo de ordenação" Exemplo: deseja-se realizar uma única pesquisa a um vetor busca seqüencial  O(n) ordenação  O(n log n) Não vale a pena ordenar!
4 Considerações Dados estão mantidos em um vetor Elemento do vetor
objeto que possui um atributo chave que deve ser mantido ordenado Um método troca(x,y) realiza a troca dos elementos presentes nas posições x e y do vetor Para fins de exemplo, números inteiros serão utilizados como elementos
5 Implementação Classe Ordenador início vetor inteiro[ ];
n inteiro; /* tamanho do vetor */ construtor Ordenador (REF v[ ] inteiro); n  v.lenght; se n < 1 então Exceção VetorVazio(); vetor  v; ordena(); v  vetor; fim; método ordena();
6 Implementação Classe Ordenador início . . .
método troca(x inteiro, y inteiro); aux inteiro; aux  vetor[x]; vetor[x]  vetor[y]; vetor[y]  aux; fim;
7 Métodos de Ordenação Ordenação por troca Ordenação por inserção
8 Métodos de Ordenação Simples
9 "Revisão" de Somatória
Propriedade 1 (P1) Propriedade 2 (P2) n  i n (n + 1) = i = 1 2 n n   k i k i = i = 1 i = 1
10 BubbleSort BubbleSort é um método simples de troca Características
11 BubbleSort Simulação de funcionamento
12 BubbleSort - Complexidade
13 BubbleSort - Complexidade
14 BubbleSort - Implementação
Classe OrdenadorBubbleSort SubClasse de Ordenador início método ordena(); i, j inteiro; para i de 0 até n-2 faça /* n-1 varreduras */ para j de 1 até n-1-i faça /* desconsidera elementos */ se vetor[ j -1 ] > vetor[ j ] então /* a direita já ordenados */ troca( j - 1, j); /* a cada iteração */ fim;
15 InsertionSort InsertionSort é um método simples de inserção
16 segmento não-ordenado
17 InsertionSort realiza uma busca seqüencial no segmento ordenado para inserir corretamente um elemento do segmento não-ordenado nesta busca, realiza trocas entre elementos adjacentes para ir acertando a posição do elemento a ser inserido e5 e9 e8 . . . e2 e5 e8 e9 . . . e2
18 InsertionSort Simulação de funcionamento
19 InsertionSort - Complexidade
20 InsertionSort - Complexidade
21 InsertionSort X BubbleSort
22 SelectionSort SelectionSort é um método simples de seleção
23 SelectionSort Característica particular Simulação de funcionamento
24 SelectionSort - Complexidade
25 Comparação Melhor caso Pior caso InsertionSort O(n) O(n2) BubbleSort
26 Exercícios Implementar o método sort para uma subclasse OrdenadorInsertionSort da classe Ordenador Implementar o método sort para uma subclasse OrdenadorSelectionSort da classe Ordenador Melhore a complexidade do BubbleSort de modo que ele encerre a sua execução quando descobrir que o vetor já está ordenado