AED ordenação

  • Published on
    22-Oct-2015

  • View
    33

  • Download
    1

Embed Size (px)

Transcript

  • OrdenaoOrdenao

    Livro Projeto de Algoritmos Nvio ZivianiCaptulo 4http://www2.dcc.ufmg.br/livros/algoritmos/

  • Ordenao

    Introduo Conceitos Bsicos Introduo Conceitos Bsicos Ordenao Interna

    Ordenao por Seleo p Ordenao por Insero ShellSort QuickSort HeapSort MergeSort MergeSort Ordenao Digital Ordenao Parcial

    Algoritmos e Estrutura de Dados II

  • Ordenao

    Ordenao Externa Intercalao Balanceada de Vrios Caminhos Implementao por meio de Seleo por Substituio Consideraes Prticas Intercalao Polifsica

    Q i k t E t Quicksort Externo

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Ordenar: processo de rearranjar um conjunto de objetos em uma ordem ascendente oude objetos em uma ordem ascendente ou descendente.

    A ordenao visa facilitar a recuperao A ordenao visa facilitar a recuperao posterior de itens do conjunto ordenado. Dificuldade de se utilizar um catlogo telefnico Dificuldade de se utilizar um catlogo telefnico

    se os nomes das pessoas no estivessem listados em ordem alfabtica.

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Notao utilizada nos algoritmos:O l it t b lh b i t d Os algoritmos trabalham sobre os registros de um arquivo.

    Cada registro possui uma chave utilizada para Cada registro possui uma chave utilizada para controlar a ordenao.

    Podem existir outros componentes em um registro.

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Estrutura de um registro:typedef int ChaveTipo;typedef struct Item {

    Ch Ti ChChaveTipo Chave;/* outros componentes */

    } Item;} Item;

    Qualquer tipo de chave sobre o qual exista Qualquer tipo de chave sobre o qual exista uma regra de ordenao bem-definida pode ser utilizado.ser utilizado.

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Um mtodo de ordenao estvel se a ordem relativa dos itens com chaves iguaisordem relativa dos itens com chaves iguais no se altera durante a ordenao.

    Alguns dos mtodos de ordenao mais Alguns dos mtodos de ordenao mais eficientes no so estveis.

    A estabilidade pode ser forada quando o A estabilidade pode ser forada quando o mtodo no-estvel.

    Sedgewick (1988) sugere agregar um Sedgewick (1988) sugere agregar um pequeno ndice a cada chave antes de ordenar, ou ento aumentar a chave de alguma outra forma.

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Classificao dos mtodos de ordenao:O d i t i d d b Ordenao interna: arquivo a ser ordenado cabe todo na memria principal.

    Ordenao externa: arquivo a ser ordenado no Ordenao externa: arquivo a ser ordenado no cabe na memria principal.

    Diferenas entre os mtodos: Em um mtodo de ordenao interna, qualquer

    registro pode ser imediatamente acessadoregistro pode ser imediatamente acessado. Em um mtodo de ordenao externa, os

    registros so acessados seqencialmente ou emregistros so acessados seqencialmente ou em grandes blocos.

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    A i i d t d d d A maioria dos mtodos de ordenao baseada em comparaes das chaves.

    Existem mtodos de ordenao que utilizam o princpio da distribuioo princpio da distribuio.

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Exemplo de ordenao por distribuio: considere o problema de ordenar um baralhoconsidere o problema de ordenar um baralho com 52 cartas na ordem:

    A < 2 < 3 < ... < 10 < J < Q < Kee

    < < <

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Algoritmo:1 Di t ib i t b t t t1. Distribuir as cartas abertas em treze montes:

    ases, dois, trs, : : :, reis.2 Colete os montes na ordem especificada2. Colete os montes na ordem especificada.3. Distribua novamente as cartas abertas em quatro

    montes: paus, ouros, copas e espadas.4. Colete os montes na ordem especificada.

    Algoritmos e Estrutura de Dados II

  • Introduo Conceitos Bsicos

    Mtodos como o ilustrado so tambm conhecidos como ordenao digital radixsortconhecidos como ordenao digital, radixsort ou bucketsort.

    O mtodo no utiliza comparao entre chaves.O mtodo no utiliza comparao entre chaves. Uma das dificuldades de implementar este

    mtodo est relacionada com o problema de lidar com cada monte.

    Se para cada monte ns reservarmos uma rea, t d d i t dento a demanda por memria extra pode

    tornar-se proibitiva.O custo para ordenar um arquivo com n O custo para ordenar um arquivo com n elementos da ordem de O(n).

    Algoritmos e Estrutura de Dados II

  • Ordenao Interna

    Na escolha de um algoritmo de ordenao interna deve ser considerado o tempo gastointerna deve ser considerado o tempo gasto pela ordenao.

    Sendo n o nmero registros no arquivo, as g qmedidas de complexidade relevantes so: Nmero de comparaes C(n) entre chaves.

    N d i t M( ) d it d Nmero de movimentaes M(n) de itens do arquivo.

    O uso econmico da memria disponvel pum requisito primordial na ordenao interna.

    Mtodos de ordenao in situ so osf idpreferidos.

    Algoritmos e Estrutura de Dados II

  • Ordenao Interna

    Mt d tili li t d d Mtodos que utilizam listas encadeadas no so muito utilizados.

    Mtodos que fazem cpias dos itens a serem ordenados possuem menorserem ordenados possuem menor importncia.

    Algoritmos e Estrutura de Dados II

  • Ordenao Interna

    Classificao dos mtodos de ordenao interna:interna: Mtodos simples: Adequados para pequenos arquivos Adequados para pequenos arquivos. Requerem O(n2) comparaes. Produzem programas pequenos.

    Mtodos eficientes: Adequados para arquivos maiores. Requerem O(n log n) comparaes Requerem O(n log n) comparaes. Usam menos comparaes. As comparaes so mais complexas nos detalhes. Mtodos simples so mais eficientes para pequenos

    arquivos.Algoritmos e Estrutura de Dados II

  • Ordenao Interna

    Tipos de dados e variveis utilizados nos algoritmos de ordenao interna:algoritmos de ordenao interna:

    typedef int Indice;typedef Item Vetor[MaxTam + 1];typedef Item Vetor[MaxTam + 1];Vetor A;

    O ndice do vetor vai de 0 at MaxTam, devido s chaves sentinelas.devido s chaves sentinelas.

    O vetor a ser ordenado contm chaves nas posies de 1 at n.p

    Algoritmos e Estrutura de Dados II

  • Ordenao por Seleo

    Um dos algoritmos mais simples de ordenaoordenao.

    Al it Algoritmo: Selecione o menor item do vetor.

    Troque o com o item da primeira posio do vetor Troque-o com o item da primeira posio do vetor. Repita essas duas operaes com os n - 1 itens

    restantes, depois com os n - 2 itens, at que resterestantes, depois com os n 2 itens, at que reste apenas um elemento.

    Algoritmos e Estrutura de Dados II

  • Ordenao por Seleo

    O mtodo ilustrado abaixo:

    As chaves em negrito sofreram uma troca As chaves em negrito sofreram uma troca entre si.

    Algoritmos e Estrutura de Dados II

  • Ordenao por Seleo

    void Selecao (Item *A, Indice *n){ Indice i, j, Min;{ Indice i, j, Min;

    Item x;for (i = 1; i

  • Ordenao por Seleo

    AnliseC t h i t d Comparaes entre chaves e movimentaes de registros:

    C(n) = n2/2 n/2C(n) = n /2 n/2M(n) = 3(n - 1)

    A atribuio Min = j executada em mdia n log nvezes, Knuth (1973).vezes, Knuth (1973).

    Algoritmos e Estrutura de Dados II

  • Ordenao por Seleo

    Vantagens:C t li t h d t d Custo linear no tamanho da entrada para o nmero de movimentos de registros.

    o algoritmo a ser utilizado para arquivos com o algoritmo a ser utilizado para arquivos com registros muito grandes.

    muito interessante para arquivos pequenos. Desvantagens: O fato de o arquivo j estar ordenado no ajuda

    em nada, pois o custo continua quadrtico. O algoritmo no estvel.

    Algoritmos e Estrutura de Dados II

  • Ordenao por Insero

    Mt d f id d j d d t Mtodo preferido dos jogadores de cartas.

    Algoritmo: Em cada passo a partir de i=2 faa: Selecione o i-simo item da seqncia fonte. Coloque-o no lugar apropriado na seqncia destino de

    acordo com o critrio de ordenao.

    Algoritmos e Estrutura de Dados II

  • Ordenao por Insero

    O mtodo ilustrado abaixo:

    As chaves em negrito representam a As chaves em negrito representam a seqncia destino.

    Algoritmos e Estrutura de Dados II

  • Ordenao por Insero

    void Insercao(Item *A, Indice *n){ Indice i j;{ Indice i, j;Item x;for (i = 2; i

  • Ordenao por Insero

    Consideraes sobre o algoritmo:

    O processo de ordenao pode ser terminado pelas condies:pelas condies: Um item com chave menor que o item em considerao

    encontrado.O fi l d i d ti ti id d O final da seqncia destino atingido esquerda.

    Soluo: Soluo: Utilizar um registro sentinela na posio zero do vetor.

    Algoritmos e Estrutura de Dados II

  • Ordenao por Insero

    Anlise

    Seja C(n) a funo que conta o nmero de comparaescomparaes.

    No anel mais interno na i-sima iterao o valor No anel mais interno, na i sima iterao, o valor de Ci :

    melhor caso : Ci (n) = 1 pior caso : Ci (n) = i caso medio : Ci(n) = 1/i (1 + 2 + ... + i) = (i+1)/2( ) ( ) ( )

    Algoritmos e Estrutura de Dados II

  • Ordenao por Insero

    Assumindo que todas as permutaes de n so igualmente provveis no caso mdioso igualmente provveis no caso mdio, temos:

    melhor caso : C(n) = (1 + 1 + ... + 1) = n - 1 pior caso : C(n) = (2 + 3 + + n) = pior caso : C(n) (2 + 3 + ... + n)

    n2/2 + n/2 + 1 caso med