of 38 /38
Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort ASN Universidade Federal de Ouro Preto, UFOP Departamento de Computação, DECOM Material elaborado com base nos slides do Prof. Reinaldo Fortes (curso de 2016/01).

BCC202 - Estrutura de Dados I - Aula 12: Ordenação: Bubble ... · PDF fileBCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (24) Introdução

  • Author
    dominh

  • View
    222

  • Download
    4

Embed Size (px)

Text of BCC202 - Estrutura de Dados I - Aula 12: Ordenação: Bubble ... · PDF fileBCC202...

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    BCC202 - Estrutura de Dados IAula 12: Ordenao: Bubble, Selection e Insertion Sort

    ASN

    Universidade Federal de Ouro Preto, UFOPDepartamento de Computao, DECOM

    Material elaborado com base nos slides do Prof. Reinaldo Fortes (curso de 2016/01).

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Contedo

    1 IntroduoConceitos Bsicos de Ordenao

    2 BubbleSort

    3 SelectionSort

    4 InsertionSort

    5 Concluso

    6 Exerccios

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (2)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Contedo

    1 IntroduoConceitos Bsicos de Ordenao

    2 BubbleSort

    3 SelectionSort

    4 InsertionSort

    5 Concluso

    6 Exerccios

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (3)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    O que um mtodo de ordenao?

    Ordenar: processo de rearranjar um conjunto de objetosem uma ordem ascendente ou descendente.

    A ordenao visa facilitar a recuperao posterior de itens doconjunto ordenado.

    Dificuldade de se utilizar um catlogo telefnico se os nomesdas pessoas no estivessem listados em ordem alfabtica.

    Em cincia da computao um mtodo de ordenao colocaos elementos de uma dada sequncia em uma certa ordem,ou seja, efetua sua ordenao completa ou parcial.

    As ordens mais usadas so a numrica e a lexicogrfica.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (4)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    Notao

    Os mtodos trabalham sobre os registros de um arquivo.

    Cada registro possui uma chave utilizada para controlar aordenao.

    Podem existir outros componentes em um registro.

    Estrutura de um registro:1 typedef int TChave ;23 typedef struct {4 TChave Chave ;5 /* outros componentes */6 } TItem ;

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (5)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    Caractersticas

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

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

    Alguns dos mtodos mais eficientes no so estveis.

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

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (6)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    Caractersticas

    Os mtodos de ordenao podem ser classificados como:Ordenao Interna: o arquivo a ser ordenado cabe todo namemria principal.

    Qualquer registro pode ser imediatamente acessado.

    Ordenao Externa: o arquivo a ser ordenado no cabe todona memria principal.

    Registros so acessados seqencialmente ou em blocos.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (7)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    Caractersticas

    A maioria dos mtodos de ordenao baseada emcomparaes das chaves.

    Existem mtodos de ordenao que utilizam o princpio dadistribuio.

    Exemplo: ordenar um baralho com 52 cartas, pelo valor dacarta e pelo nipe.

    Primeiro separe as cartas em treze montes (valores das cartas).

    Em seguida, colete os montes na ordem desejada.

    Distribua cada monte em quatro montes (naipes das cartas).

    Colete os montes na ordem desejada.

    Qual o custo deste algoritmo?

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (8)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    Critrios de anlise

    Sendo n o nmero registros no arquivo, as medidas decomplexidade relevantes so:

    Nmero de comparaes C(n) entre chaves.

    Nmero de movimentaes M(n) de registros do arquivo.

    O uso econmico da memria disponvel um requisitoprimordial na ordenao interna.

    Mtodos de ordenao in situ so os preferidos.

    Mtodos que utilizam listas encadeadas no so muitoutilizados.

    Mtodos que fazem cpias dos itens a serem ordenadospossuem menor importncia.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (9)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    Ordenao Interna por Comparao

    Mtodos simples:Adequados para pequenos arquivos.

    Requerem O(n2) comparaes.

    Produzem programas pequenos.

    Mtodos eficientes:Adequados para arquivos maiores.

    Requerem O(n log n) comparaes.

    As comparaes so mais complexas nos detalhes.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (10)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    O melhor algoritmo

    AtenoNo existe um mtodo de ordenao consideradouniversalmente superior a todos os outros.

    necessrio analisar o problema e, com base nascaractersticas dos dados, decidir qual mtodo melhor seaplica ele.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (11)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Conceitos Bsicos de Ordenao

    O que estudaremos?

    Neste curso estudaremos apenas algoritmos de ordenaointerna e que utilizam o princpio da comparao.

    Nesta aula:BubbleSort.

    SelectionSort.

    InsertionSort.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (12)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Contedo

    1 IntroduoConceitos Bsicos de Ordenao

    2 BubbleSort

    3 SelectionSort

    4 InsertionSort

    5 Concluso

    6 Exerccios

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (13)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Mtodo da Bolha

    Funcionamento

    Os elementos vo borbulhando a cada iterao do mtodoat a posio correta para ordenao da lista.

    Como os elementos so trocados (borbulhados)frequentemente, h um alto custo com troca de elementos.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (14)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Mtodo da Bolha

    Algoritmo

    1 void Bolha ( TItem * v, int n) {2 int i, j;3 TItem aux;4 for (i = 0; i < n -1; i++) {5 for (j = 1; j < n-i; j++) {6 if (v[j]. Chave < v[j -1]. Chave ) {7 aux = v[j];8 v[j] = v[j -1];9 v[j -1] = aux;

    10 }11 }12 }13 }

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (15)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Mtodo da Bolha

    Anlise de Complexidade

    Comparaes (C(n)):

    C(n) =n2i=0

    (n i 1) =n2i=0

    n n2i=0

    i n2i=0

    1

    = n(n 1) (0 + n 2)(n 1)2 (n 1)

    = n2 n2 = O(n

    2)

    Movimentaes (M(n)):

    M(n) = 3C(n) = O(n2)

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (16)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Mtodo da Bolha

    Caractersticas

    VantagensAlgoritmo simples.

    Algoritmo estvel.

    DesvantagensO fato de o arquivo j estar ordenado no ajuda a reduzir onmero de comparaes (o custo continua quadrtico), pormo nmero de movimentaes cai para zero.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (17)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Mtodo da Bolha

    Melhoria no Algoritmo

    Original:1 void Bolha ( TItem * v, int n) {2 int i, j;3 TItem aux;4 for (i = 0; i < n -1; i++) {5 for (j = 1; j < n-i; j++) {6 if (v[j]. Chave < v[j -1]. Chave ) {7 aux = v[j];8 v[j] = v[j -1];9 v[j -1] = aux;

    10 }11 }12 }13 }

    Melhorado:1 void Bolha ( TItem * v, int n) {2 int i, j, troca ;3 TItem aux;4 for (i = 0; i < n -1; i++) {5 troca = 0;6 for (j = 1; j < n-i; j++) {7 if (v[j]. Chave < v[j -1]. Chave ) {8 aux = v[j];9 v[j] = v[j -1];

    10 v[j -1] = aux;11 troca ++;12 }13 }14 if ( troca == 0) break ;15 }16 }

    MelhoriaInterrompe o processo quando no ocorrem mais trocas.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion Sort (18)

  • Introduo BubbleSort SelectionSort InsertionSort Concluso Exerccios

    Mtodo da Bolha

    Melhoria no Algoritmo

    Original:1 void Bolha ( TItem * v, int n) {2 int i, j;3 TItem aux;4 for (i = 0; i < n -1; i++) {5 for (j = 1; j < n-i; j++) {6 if (v[j]. Chave < v[j -1]. Chave ) {7 aux = v[j];8 v[j] = v[j -1];9 v[j -1] = aux;

    10 }11 }12 }13 }

    Melhorado:1 void Bolha ( TItem * v, int n) {2 int i, j, troca ;3 TItem aux;4 for (i = 0; i < n -1; i++) {5 troca = 0;6 for (j = 1; j < n-i; j++) {7 if (v[j]. Chave < v[j -1]. Chave ) {8 aux = v[j];9 v[j] = v[j -1];

    10 v[j -1] = aux;11 troca ++;12 }13 }14 if ( troca == 0) break ;15 }16 }

    MelhoriaInterrompe o processo quando no ocorrem mais trocas.

    BCC202 - Estrutura de Dados I Aula 12: Ordenao: Bubble, Selection e Insertion