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

  • Upload
    dominh

  • View
    225

  • Download
    4

Embed Size (px)

Citation preview

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

BCC202 - Estrutura de Dados IAula 12: Ordenação: Bubble, Selection e Insertion Sort

ASN

Universidade Federal de Ouro Preto, UFOPDepartamento de Computação, DECOM

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

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conteúdo

1 IntroduçãoConceitos Básicos de Ordenação

2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 Exercícios

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (2)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conteúdo

1 IntroduçãoConceitos Básicos de Ordenação

2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 Exercícios

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (3)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

O que é um método de ordenação?

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

A ordenação visa facilitar a recuperação posterior de itens doconjunto ordenado.

Dificuldade de se utilizar um catálogo telefônico se os nomesdas pessoas não estivessem listados em ordem alfabética.

Em ciência da computação um método de ordenação colocaos elementos de uma dada sequência em uma certa ordem,ou seja, efetua sua ordenação completa ou parcial.

As ordens mais usadas são a numérica e a lexicográfica.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (4)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

Notação

Os métodos trabalham sobre os registros de um arquivo.

Cada registro possui uma chave utilizada para controlar aordenação.

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: Ordenação: Bubble, Selection e Insertion Sort (5)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

Características

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

Um método de ordenação é estável se a ordem relativa dositens com chaves iguais não se altera durante a ordenação.

Alguns dos métodos mais eficientes não são estáveis.

A estabilidade pode ser forçada quando o método énão-estável.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (6)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

Características

Os métodos de ordenação podem ser classificados como:Ordenação Interna: o arquivo a ser ordenado cabe todo namemória principal.

Qualquer registro pode ser imediatamente acessado.

Ordenação Externa: o arquivo a ser ordenado não cabe todona memória principal.

Registros são acessados seqüencialmente ou em blocos.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (7)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

Características

A maioria dos métodos de ordenação é baseada emcomparações das chaves.

Existem métodos de ordenação que utilizam o princípio dadistribuição.

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: Ordenação: Bubble, Selection e Insertion Sort (8)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

Critérios de análise

Sendo n o número registros no arquivo, as medidas decomplexidade relevantes são:

Número de comparações C(n) entre chaves.

Número de movimentações M(n) de registros do arquivo.

O uso econômico da memória disponível é um requisitoprimordial na ordenação interna.

Métodos de ordenação in situ são os preferidos.

Métodos que utilizam listas encadeadas não são muitoutilizados.

Métodos que fazem cópias dos itens a serem ordenadospossuem menor importância.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (9)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

Ordenação Interna por Comparação

Métodos simples:Adequados para pequenos arquivos.

Requerem O(n2) comparações.

Produzem programas pequenos.

Métodos eficientes:Adequados para arquivos maiores.

Requerem O(n log n) comparações.

As comparações são mais complexas nos detalhes.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (10)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

O melhor algoritmo

AtençãoNão existe um método de ordenação consideradouniversalmente superior a todos os outros.

É necessário analisar o problema e, com base nascaracterísticas dos dados, decidir qual método melhor seaplica à ele.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (11)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conceitos Básicos de Ordenação

O que estudaremos?

Neste curso estudaremos apenas algoritmos de ordenaçãointerna e que utilizam o princípio da comparação.

Nesta aula:BubbleSort.

SelectionSort.

InsertionSort.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (12)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conteúdo

1 IntroduçãoConceitos Básicos de Ordenação

2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 Exercícios

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (13)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método da Bolha

Funcionamento

Os elementos vão “borbulhando” a cada iteração do métodoaté a posição correta para ordenação da lista.

Como os elementos são trocados (borbulhados)frequentemente, há um alto custo com troca de elementos.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (14)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método 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: Ordenação: Bubble, Selection e Insertion Sort (15)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método da Bolha

Análise de Complexidade

Comparações (C(n)):

C(n) =n−2∑i=0

(n − i − 1) =n−2∑i=0

n −n−2∑i=0

i −n−2∑i=0

1

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

= n2 − n2 = O(n2)

Movimentações (M(n)):

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

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (16)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método da Bolha

Características

VantagensAlgoritmo simples.

Algoritmo estável.

DesvantagensO fato de o arquivo já estar ordenado não ajuda a reduzir onúmero de comparações (o custo continua quadrático), porémo número de movimentações cai para zero.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (17)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método 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 não ocorrem mais trocas.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (18)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método 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 não ocorrem mais trocas.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (18)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conteúdo

1 IntroduçãoConceitos Básicos de Ordenação

2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 Exercícios

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (19)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Seleção

Funcionamento

Seleciona do n-ésimo menor (ou maior) elemento da lista.

Troca do n-ésimo menor (ou maior) elemento com a n-ésimaposição da lista.

É realizada apenas uma única troca a cada iteração.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (20)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Seleção

Algoritmo

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

10 v[Min] = v[i];11 v[i] = aux;12 }13 }

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (21)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Seleção

Análise de Complexidade

Comparações (C(n)):

C(n) =n−2∑i=0

(n − i − 1) =n−2∑i=0

n −n−2∑i=0

i −n−2∑i=0

1

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

= n2 − n2 = O(n2)

Movimentações (M(n)):

M(n) = 3(n − 1) = O(n)

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (22)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Seleção

Características

VantagensCusto linear no tamanho da entrada para o número demovimentos de registros.

É o algoritmo a ser utilizado para arquivos com registrosmuito grandes (alto custo de movimentação).

É muito interessante para arquivos pequenos.

DesvantagensO fato de o arquivo já estar ordenado não ajuda em nada,pois o custo continua quadrático.

O algoritmo não é estável.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (23)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Seleção

Melhoria no Algoritmo

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

10 v[Min] = v[i];11 v[i] = aux;12 }13 }

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

10 aux = v[Min ];11 v[Min] = v[i];12 v[i] = aux;13 }14 }15 }

MelhoriaRealiza troca apenas quando é realmente necessário.

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

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Seleção

Melhoria no Algoritmo

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

10 v[Min] = v[i];11 v[i] = aux;12 }13 }

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

10 aux = v[Min ];11 v[Min] = v[i];12 v[i] = aux;13 }14 }15 }

MelhoriaRealiza troca apenas quando é realmente necessário.

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

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conteúdo

1 IntroduçãoConceitos Básicos de Ordenação

2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 Exercícios

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (25)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Inserção

Funcionamento

Algoritmo utilizado pelo jogador de cartas:As cartas são ordenadas da esquerda para direita uma por uma.

O jogador escolhe a segunda carta e verifica se ela deve ficarantes ou na posição que está.

Depois a terceira carta é classificada, deslocando-a até suaposição correta.

O procedimento é repetido até ordenar todas as cartas.

Alto custo em remover uma carta de uma posição e colocá-laem outra quando a representação é feita por arrays.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (26)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Inserção

Algoritmo

SEM Sentinela:1 void Insercao ( TItem * v, int n) {2 int i,j;3 TItem aux;4 for (i = 1; i < n; i++) {5 aux = v[i];6 j = i - 1;7 while (j >= 0 && aux. Chave < v[j].

Chave ) {8 v[j + 1] = v[j];9 j--;

10 }11 v[j + 1] = aux;12 }13 }

COM Sentinela:1 void Insercao ( TItem * v, int n) {2 int i,j;3 for (i = n -2; i >= 0; i--) {4 v[n] = v[i];5 j = i + 1;6 while (v[n]. Chave > v[j]. Chave ) {7 v[j - 1] = v[j];8 j++;9 }

10 v[j - 1] = v[n]11 }12 }

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (27)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Inserção

Análise de Complexidade

Comparações (C(n)):No laço mais interno, na i -ésima iteração:

Melhor caso: Ci (n) = 1.

Pior caso: Ci (n) = i .

Caso médio: Ci (n) = 1i ∗ (1 + 2 + ... + i) = i+1

2 .

Assumindo que todas as permutações de n são igualmenteprováveis no caso médio, temos:

Melhor caso: C(n) = (1 + 1 + ... + 1) = n − 1.

Pior caso: C(n) = (1 + 2 + ... + (n − 1)) = n22 − n

2 .

Caso médio: C(n) = (1/2) ∗ (2 + ... + n) = n24 + n

4 − 12 .

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (28)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Inserção

Análise de Complexidade

Movimentações (M(n)):No laço mais interno, na i -ésima iteração:

Melhor caso: Mi (n) = 0.

Pior caso: Mi (n) = i .

Caso médio: Mi (n) = 1i ∗ (0 + 1 + 2 + ... + i − 1) = i−1

2 .

Assumindo que todas as permutações de n são igualmenteprováveis no caso médio, temos:

Melhor caso: M(n) = (2 + 2 + ... + 2) = 2n − 2.

Pior caso: M(n) = ((2+ 1) + ... + (2+ n − 1)) = n2+3n−42 .

Caso médio: M(n) = (1/2) ∗ (2 + 3 + ... + n) = n2+n−22 .

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (29)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Método de Inserção

Características

O número mínimo de comparações e movimentos ocorrequando os itens estão originalmente em ordem.

O número máximo ocorre quando os itens estão originalmentena ordem reversa.

É o método a ser utilizado quando o arquivo está “quase”ordenado.

É um bom método quando se deseja adicionar uns poucositens a um arquivo ordenado, pois o custo é linear.

O algoritmo de ordenação por inserção é estável.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (30)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conteúdo

1 IntroduçãoConceitos Básicos de Ordenação

2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 Exercícios

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (31)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conclusão

Conclusão

Nesta aula tivemos o primeiro contato com algoritmos deordenação.

Foram vistos os algoritmos BubbleSort, SelectionSort eInsertionSort.

Cada algoritmo possui suas características particularidades:Não existe um método de ordenação consideradouniversalmente superior a todos os outros.

É necessário analisar o problema e, com base nas característicasdos dados, decidir qual método melhor se aplica à ele.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (32)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conclusão

Conclusão

Quadro comparativo dos métodos de ordenação:

AlgoritmoComparações Movimentações

Espaço Estável In situMelhor Médio Pior Melhor Médio Pior

Bubble O(n2) O(n2) O(1) Sim Sim

Selection O(n2) O(n) O(1) Não∗ Sim

Insertion O(n) O(n2) O(n) O(n2) O(1) Sim Sim

∗ Existem versões estáveis.

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (33)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conclusão

Conclusão

A tarefa de ordenação é muito importante, ela é umanecessidade básica para a solução de muitos problemas.

Próxima aula: MergeSort.

Dúvidas?

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (34)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Conteúdo

1 IntroduçãoConceitos Básicos de Ordenação

2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 Exercícios

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (35)

Introdução BubbleSort SelectionSort InsertionSort Conclusão Exercícios

Exercícios propostos

Exercício 01

Dada a sequência de números: 3 4 9 2 5 1 8.

Ordene em ordem crescente utilizando os três algoritmosaprendidos em sala (BubbleSort, SelectionSort eInsertionSort), apresentando a sequência dos números a cadapasso (Teste de Mesa).

BCC202 - Estrutura de Dados I Aula 12: Ordenação: Bubble, Selection e Insertion Sort (36)