Classificação Ordenação de Dados

  • Published on
    01-Jan-2016

  • View
    23

  • Download
    0

Embed Size (px)

DESCRIPTION

Classificao Ordenao de Dados. Marco Antonio Montebello Jnior marco.antonio@aes.edu.br. Ordenao e Pesquisa de Dados. Ordenao dos dados. Facilitar e aumentar a eficincia das operaes de pesquisa sobre esses dados Pode ser crescente ou decrescente - PowerPoint PPT Presentation

Transcript

  • ClassificaoOrdenao de DadosMarco Antonio Montebello Jniormarco.antonio@aes.edu.brOrdenao e Pesquisa de Dados

  • Ordenao dos dadosFacilitar e aumentar a eficincia das operaes de pesquisa sobre esses dadosPode ser crescente ou decrescenteA seqncia de entrada, normalmente, um vetor com n elementosOutras possibilidades de estruturas de dados como por exemplo, uma lista encadeada

  • Ainda mais...Na prtica os nmeros a serem ordenados, raramente, so valores isoladosNormalmente, cada nmero componente de um conjunto de dados denominado registroE o conjunto de registros forma uma tabelaCada registro contm uma chave, que o valor a ser ordenado, e demais valores que sempre acompanham a chaveNuma operao de ordenao, sempre que for preciso trocar a posio de uma chave, ser necessrio alterar a posio de todos os elementos do registroNa prtica, quando os registros possuem uma grande quantidade de dados (alm da chave), a ordenao realizada sobre um vetor (ou lista) de ponteiros para os registros, com o objetivo de minimizar as operaes de movimentao de dados

  • ExemplosContigidade FsicaTabela no ordenadaTabela ordenadaAs entradas so fisicamente rearranjadas (todos os elementos de um registro so ordenados fisicamente)

    RegChaveOutros campos13xxxxxxxxx27yyyyyyyyy35zzzzzzzzz41kkkkkkkkk54ttttttttt62uuuuuuuuu

    RegChaveOutros campos11kkkkkkkkk22uuuuuuuuu33xxxxxxxxx44ttttttttt55zzzzzzzzz67yyyyyyyyy

  • ExemploVetor Indireto de OrdenaoAs entradas so mantidas nas posies originais. A seqncia dada por um vetor gerado durante o processo de classificao (no envolve movimentao dos registros em uma tabela).Tabela desordenadaVetor de ordenao

    ndice da tabela142631455362

  • ExemploEncadeamentoAs entradas so mantidas nas posies originais. formada uma lista encadeada com a ordenao. Utiliza-se um campo a mais na tabela para armazenamento da lista, e no mais o vetor adicional (vetor indireto de ordenao). preciso utilizar um ponteiro para o primeiro elemento4Ponteiro para o primeiro elemento da tabela (reg. 4 contm chave 1)

  • Ordenao Interna versus Ordenao ExternaA ordenao interna utilizada num conjunto de dados pequenoNeste caso a ordenao pode ser realizada inteiramente (ou quase inteiramente) na memria principalA ordenao externa utilizada num conjunto de dados grandesA conseqncia que a ordenao no pode ser realizada na memria principalNesse caso a ordenao realizada sobre dados armazenados na memria secundria (disco, fita, etc.)

  • Principais mtodos de ordenao internaOrdenao por InseroInsero DiretaIncrementos Decrescentes (Shell Sort)Ordenao por TrocaMtodo da Bolha (Bubble Sort)Mtodo da Troca e Partio (Quicksort)Ordenao por SeleoSeleo DiretaSeleo em rvore (Heapsort)

  • Ordenao por InseroNesse mtodo os elementos so inseridos em sua posio correta, em relao aos elementos j classificados

    Duas possibilidades : Insero DiretaMtodo Shell

  • Insero Direta o mtodo mais simplesUtilizado para um conjunto pequeno de dadosPossui baixa eficinciaNesse mtodo o vetor a ser ordenado dividido em dois segmentos: O primeiro segmento contm os elementos j ordenados; O segundo segmento contm os elementos a serem ordenados

  • Algoritmo Insero DiretaPrimeiro elemento est no vetor ordenado e os demais no vetor desordenado;Retirar o primeiro elemento do vetor desordenado e coloc-lo no vetor ordenado, na sua posio correta;Repetir o processo para todos os elementos do vetor desordenado.

  • Algoritmo Insero DiretaConstTAM = 10Tiposv = vetor[1..TAM] de inteiros+-------------------------+Var| Exemplo: |vet: v| | i, j, k, temp: inteiro| 5 | 2 3 4 8 7 | achei: lgico| 2 5 | 3 4 8 7 | | 2 3 5 | 4 8 7 | Incio| 2 3 4 5 | 8 7 | Para i = 1 at TAM Faa| 2 3 4 5 8 | 7 | leia (vet[i])| 2 3 4 5 7 8 || Fim-Para+-------------------------+Para i = 2 at TAM Faaj = 1achei = FALSOEnquanto (j < i) E (NO achei) Faa/* Compara o */Se vet[i] < vet[j] Ento/* vet[i] com */achei = VERDADEIRO/* os que esto */Seno/* sua */j = j + 1/* esquerda */Fim-SeFim-EnquantoSe achei Entotemp = vet[i]k = i - 1Enquanto k >= j Faa/* Desloca o */vet[k+1] = vet[k]/* vetor para */k = k 1/* a direita */Fim-Enquantovet[j] = tempFim-SeFim-ParaFim.

  • Algoritmo Outra versoConstTAM = 10Tiposv = vetor[1..TAM] de inteiros Var vet: v i, j, k, temp: inteiro achei: lgico Incio Para i = 1 at TAM Faa leia (vet[i]) Fim-ParaPara j = 2 at TAM Faachave = vet[j]i = j - 1Enquanto (i > 0) E (vet[i] > chave) Faa vet[i + 1] = vet[i]i = i - 1Fim-Enquantovet[i+1] = chaveFim-ParaFim.

  • Incrementos Decrescentes (Shell Sort)Proposto por Ronald L. Shell (1959) uma extenso do algoritmo de insero diretaA diferena com relao insero direta o nmero de segmentos do vetorNa insero direta considerado um nico segmento do vetor onde os elementos so inseridos ordenadamenteNo mtodo do Shell so considerados diversos segmentos

  • Descrio do Mtodo Shell SortA ordenao realizada em diversos passos. A cada passo est associado um incremento I, o qual determina os elementos que pertencem a cada um dos segmentos:segmento 1 - vet[1], vet[1 + I], vet[1 + 2I], ...segmento 2 - vet[2], vet[2 + I], vet[2 + 2I], ... ...segmento k - vet[k], vet[k + I], vet[k + 2I], ...

  • Descrio do Mtodo Shell SortA cada passo todos os elementos (segmentos) so ordenados isoladamente por insero direta.No final de cada passo o processo repetido para um novo incremento I igual a metade do anterior, at que seja executado um passo com incremento I = 1. O valor do incremento I sempre uma potncia inteira de 2. O valor do incremento inicial dado por 2**NP, onde NP o nmero de passos para ordenar o vetor (fornecido pelo usurio, NP uma aproximao inicial). Assim, para NP = 3 o valor do incremento em cada passo seria:I = 2 ** 3 = 8 (23)I = 2 ** 2 = 4 (22)I = 2 ** 1 = 2 (21)I = 2 ** 0 = 1 (20)

  • Exemplo: NP = 2Vetor original (Desordenado)Primeiro passo: I = 2 ** NP = 4 (22)Aplicando insero direta em cada segmentoObtm-se o vetor

    123456789101112152025101927401350414535

  • Exemplo: NP = 2Segundo passo: I = I DIV 2 = 2 (I/2) ou NP = NP - 1, I = 2 ** NP = 2 (21) Segmento 1 Segmento 2Aplicando insero direta em cada segmento:Obtm-se o vetor

  • Exemplo: NP = 2Terceiro passo: I = I DIV 2 = 1 ou: NP = NP - 1, I = 2 ** NP = 1 (20)Nesse ltimo passo os elementos esto prximos das suas posies finais, o que leva a um menor nmero de trocas.Aplicando insero direta ao vetor obtido no passo anterior obtm-se o vetor ordenado:

  • Algoritmo do Mtodo ShellConstTAM = 12Tiposv = vetor[1..TAM] de inteirosVarvet: vnp, i, j, inc : inteiro IncioPara i = 1 at TAM Faa Leia (vet[i]) Fim-Para

    Leia (np)

    Para i = np at 0 Passo -1 Faainc = 2 ** i //2iPara j = 1 at inc FaaMtodo_Shell (vet, inc, j, TAM)Fim-ParaFim-ParaFim.

  • Algoritmo do Mtodo ShellProcedimento Mtodo_Shell (Ref vet, r, s, n)IncioVari, j, k, temp: inteiroachei: lgicoPara i = (s + r) at n passo r Faaj = sachei = FALSOEnquanto (j < i) E (NO achei) FaaSe vet[i] < vet[j] Entoachei = VERDADEIROSenoj = j + rFim-SeFim-EnquantoSe achei Entotemp = vet[i]k = i + rEnquanto k > (j - r) Faavet[k + r] = vet[k]k = k - rFim-Enquantovet[j] = tempFim-SeFim-ParaFim-Mtodo_Shell

  • Ordenao por TrocaDurante o caminhamento no vetor, se dois elementos so encontrados fora de ordem, suas posies so trocadasSo realizadas comparaes sucessivas de pares de elementosA estratgia de escolha dos pares de elementos estabelece a diferena entre os dois mtodos de ordenao por troca.Dois mtodos principais: Mtodo da Bolha (Bubble Sort)Mtodo da Partio (Quick Sort)

  • Mtodo da Bolha (Bubble Sort) um mtodo bastante simples, porm lentoO nome bolha se deve ao fato de que os valores flutuam at a sua correta posio como bolhasO algoritmo o seguinte:A cada passo, cada elemento comparado com o prximo. Se o elemento estiver fora de ordem, a troca realizada;Realizam-se tantos passos quantos necessrios at que no ocorram mais trocas.Obs.: Logo no primeiro passo o maior valor vai para o fim

  • Exemplo do Mecanismo do Mtodo Bolha 500 85 515 60 910 170 890 275 650 430

    Passo 1: 85 500 60 515 170 910 890 910 275 910 650 910 430 910 85 500 60 515 170 890 275 650 430 910Passo 2: 85 60 500 170 515 275 650 430 890 910Passo 3: 60 85 170 500 275 515 430 650 890 910Passo 4: 60 85 170 275 500 430 515 650 890 910Passo 5: 60 85 170 275 430 500 515 650 890 910Passo 6: nenhuma troca

  • Algoritmo do Mtodo Bolha/*Nesse algoritmo, a cada passo, a varivel k contm a ltima posio trocada. Aps esta, todas j esto classificadas.*/ConstTAM = 20Tiposv = vetor[1..TAM] de inteirosVar vet: vi, temp, lim, k: inteirotroca: lgicoIncioPara i = 1 at TAM Faa Leia (vet[i]) Fim-Para troca = VERDADEIROlim = TAM - 1Enquanto troca Faatroca = FALSOPara i = 1 at lim FaaSe vet[i] > vet[i + 1] Entotemp = vet[i]vet[i] = vet[i + 1]vet[i + 1] = tempk = itroca = VERDADEIROFim-SeFim-paralim = kFim-EnquantoFim.

  • Mtodo da Troca e Partio (Quick Sort) o mais rpido entre os mtodos apresentados at o momentoE tambm o mais utilizadoFoi proposto por C. A. R. Hoare em 1962Parte do princpio que mais rpido classificar dois vetores com n/2 elementos cada

Recommended

View more >