Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Fundamentos da Compuação Inteligente * Métodos de Ordenação EDII 2010.1 Fundamentos da Compuação Inteligente Fundamentos da Compuação Inteligente * * Métodos de Ordenação Ordenação corresponde ao processo de rearranjar um conjunto de objetos em uma ordem crescente ou decrescente Tem como objetivo facilitar a recuperação dos itens do conjunto Recuperação de nomes em um lista telefônica Atividade relevante e fundamental em processamento de dados, sobretudo aqueles armazenados em arquivos Fundamentos da Compuação Inteligente * * Ordenação Num processo de ordenação escolhe-se uma determinada chave (campo) comum da massa de dados sobre o qual o processo acontecerá Registros são usados para representar os elementos a serem ordenados struct TipoItem { TipoChave chave; //outras declarações desejadas... }; Os demais campos dos registros, em geral não influenciam no processo de ordenação Fundamentos da Compuação Inteligente * * Processo de Ordenação Sejam os itens a1, a2, . . . , an. Ordenar consiste em permutar estes itens em uma ordem: ak1 , ak2 , . . . , akn tal que, dada uma função de ordenação f , tem se a seguinte relação: f (ak1 ) ≤ f (ak2 ) ≤ . . . ≤ f (akn ) Função de ordenação é definida sobre o campo chave. Qualquer tipo sobre o qual exista uma regra de ordenação bem definida pode ser utilizado omo chave Fundamentos da Compuação Inteligente * * Classificação – Quanto à Estabilidade Métodos Instáveis: a ordem relativa dos itens com chaves iguais é alterada durante o processo de ordenação Métodos Estáveis: se a ordem relativa dos itens com chaves iguais mantém-se inalterada durante o processo Alguns dos métodos de ordenação mais eficientes não são estáveis Fundamentos da Compuação Inteligente * * Estabilidade - Exemplo Estável: Instável: Fundamentos da Compuação Inteligente * * Classificação: Quanto ao conjunto de registros Ordenação Interna: o conjunto de registros cabe todo em na memória principal Ordenação Externa: o conjunto de registros não cabe completamente em memória principal, e deve ser armazenado em memória auxiliar. Alguns autores utilizam ordenação de vetores (ordenação interna) e ordenação de registros (ordenação externa) Fundamentos da Compuação Inteligente * Ordenação Interna Fundamentos da Compuação Inteligente Fundamentos da Compuação Inteligente * * Ordenação Interna Medidas de complexidade levam em conta: O número de comparação entre as chaves O número de trocas entre os itens São classificados em dois tipos: Métodos Simples: mais recomendados para conjuntos pequenos de dados. Usam mais comparações, mas produzem códigos menores e mais simples; Métodos Eficientes ou Sofisticados: adequados para conjuntos maiores de dados. Usam menos comparações, porém produzem códigos mais complexos e com muitos detalhes. Fundamentos da Compuação Inteligente * * Alguns Algoritmos de Ordenação Interna Ordenação por Seleção (Selection Sort) Ordenação por Inserção (Insertion Sort) Ordenação por Seleção e Troca (Bubble Sort) Ordenação por Inserção através de incrementos decrescentes (ShellSort) Ordenação por Particionamento (QuickSort) Ordenação de Árvores (HeapSort) Fundamentos da Compuação Inteligente * Ordenação Interna Métodos Simples Fundamentos da Compuação Inteligente Fundamentos da Compuação Inteligente * Selection Sort Ordenação por Seleção Fundamentos da Compuação Inteligente Fundamentos da Compuação Inteligente * * Ordenação por Seleção (Selection Sort) Um dos algoritmos mais simples Mais recomendado para conjuntos pequenos Procedimento: Selecione o menor item do conjunto e troque-o com o item que está na posição i Repita essas operações com os demais itens até que reste apenas um elemento Fundamentos da Compuação Inteligente * * Ordenação por Seleção (Selection Sort) Chaves Iniciais: i=1: i=2: i=3: i=4: i=5: Fundamentos da Compuação Inteligente * * Ordenação por Seleção void SelectionSort(int vet[10]) { int i, j, min, aux; for(i=0;i<10;i++) { min = i; //Posição a ser ordenada for(j=i+1;j<10;j++) { if (vet[j] < vet[min]) { min = j; //Posição a ser trocada } } aux = vet[min]; vet[min] = vet[i]; vet[i] = aux; } } Troca Fundamentos da Compuação Inteligente * * Ordenação por Seleção (Selection Sort) Desvantagens O fato de o conjunto já estar ordenado não ajuda em nada (o número de comparações continua o mesmo) O algoritmo não é estável, isto é, os registros com chaves iguais nem sempre irão manter a mesma posição relativa de antes do início da ordenação Fundamentos da Compuação Inteligente * Insertion Sort Ordenação por Inserção Fundamentos da Compuação Inteligente Fundamentos da Compuação Inteligente * * Ordenação por Inserção (Insertion Sort) Também um algoritmo simples Procedimento Os elementos são divididos em uma seqüência de destino a1, ..., ai-1 e em uma seqüência fonte ai, ..., an. Em cada passo, a partir de i =2, o i-ésimo item da seqüência fonte é retirado e transferido para a seqüência destino sendo inserido na posição adequada Fundamentos da Compuação Inteligente * * Ordenação por Inserção (Insertion Sort) A O R D E N 6 2 3 4 5 1 Chaves Iniciais O R A O R D E N i = 2 Fundamentos da Compuação Inteligente * * Ordenação por Inserção (Insertion Sort) A inserção do item em uma posição adequada na seqüência de destino é realizada com a movimentação das chaves maiores para a direita e então é feita a inserção do item na posição vazia Vantagens: O número mínimo de comparações e movimentos ocorre quando os itens já estão originalmente ordenados O número máximo ocorre quando os itens estão originalmente em ordem reversa, o que indica um comportamento natural para o algoritmo Fundamentos da Compuação Inteligente * * Ordenação por Inserção void InsertSort(int v[10]) { int i, j, key; for(j = 0; j < 10; j++) { key = v[j]; for(i = j - 1; (i >= 0) && (v[i] > key); i--) // Valores menores movidos para cima { v[i+1] = v[i]; } v[i+1] = key; //Pondo a chave em sua localização correta } } Fundamentos da Compuação Inteligente * * Ordenação por Seleção e Troca (Bubblesort) Um dos algoritmos mais simples Princípio: As chaves Item[1].Chave e Item[2].Chave são comparadas e trocadas se estiverem fora de ordem; Repete-se o processo de comparação e troca com Item[2] e Item[3], Item[3] e Item[4], ... Por que Bolha? Se o vetor a ser ordenado for colocado na vertical, com Item[n] em cima e Item[1] embaixo, durante cada passo o menor elemento “sobe” até encontrar um elemento maior ainda, como se uma bolha subisse dentro de um tubo de acordo com sua densidade Fundamentos da Compuação Inteligente * * Ordenação pelo Método da Bolha i = 1 i = 4 i = 6 i = 7 Chaves Iniciais i = 3 i = 2 i = 5 i = 8 Fundamentos da Compuação Inteligente * * Implementação: Ordenação pelo Método da Bolha void BubbleSort(int L[10]) { int i,j, aux; for(i=0;i<10;i++) { for(j=i+1;j<10;j++) { if(L[i] > L[j]) { aux=L[i]; L[i]=L[j]; L[j]=aux; } } } } Fundamentos da Compuação Inteligente * * Ordenação pelo Método da Bolha Note que no exemplo, as três últimas iterações não afetam a ordem do vetor; assim o algoritmo pode ser melhorado! Técnica óbvia: manter uma indicação para saber se houve ou não troca na última iteração: se não houve, o vetor já está ordenado Fundamentos da Compuação Inteligente * * Observações Método extremamente lento: só faz comparações entre posições adjacentes É o método mais ineficiente entre os simples Melhor caso: vetor já ordenado Pior caso: vetor de entrada em ordem reversa Cada passo aproveita muito pouco do que foi “descoberto” em relação à ordem das chaves no passo anterior (exibe informações redundantes)
Compartilhar