BCC202 - Estrutura de Dados I - Aula 12: Ordenação: Bubble ... · PDF fileIntrodução BubbleSort SelectionSort InsertionSort Conclusão Exercícios BCC202-EstruturadeDadosI Aula12:

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

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

Reinaldo Fortes

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

Website: www.decom.ufop.br/reifortesEmail: [email protected]

Material elaborado com base nos slides do Prof. Túlio Toffolo (curso de 2013/01).

2013/02

http://www.decom.ufop.br/toffolo/ensino/bcc202_2013-1/aulas/


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)


Conteúdo


2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 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.




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 ;




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.




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.




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?




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.




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.

Usam menos comparações.

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




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.




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.



Conteúdo


2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 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.

Animação


http://www.sorting-algorithms.com/bubble-sort

http://www.sorting-algorithms.com/bubble-sort


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 }

Animação Vídeo


http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

http://www.youtube.com/watch?v=lyZQPjUT5B4

http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

http://www.youtube.com/watch?v=lyZQPjUT5B4


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 − n

2 = O(n2)

Movimentações (M(n)):

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



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.



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.



Método da Bolha


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.



Conteúdo


2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 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.

Animação Vídeo


http://www.sorting-algorithms.com/selection-sort

http://www.youtube.com/watch?v=Ns4TPTC8whw

http://www.sorting-algorithms.com/selection-sort

http://www.youtube.com/watch?v=Ns4TPTC8whw



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 }

Animação


http://pt.wikipedia.org/wiki/Ficheiro:Selection-Sort-Animation.gif

http://pt.wikipedia.org/wiki/Ficheiro:Selection-Sort-Animation.gif




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 − n

2 = O(n2)

Movimentações (M(n)):

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




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.





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.





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.



Conteúdo


2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 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.

Animação Vídeo


http://www.sorting-algorithms.com/insertion-sort

http://www.youtube.com/watch?v=ROalU379l3U

http://www.sorting-algorithms.com/insertion-sort

http://www.youtube.com/watch?v=ROalU379l3U



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 }

Animação


http://pt.wikipedia.org/wiki/Ficheiro:Insertion-sort-example-300px.gif

http://pt.wikipedia.org/wiki/Ficheiro:Insertion-sort-example-300px.gif




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

Melhor caso: C i (n) = 1.

Pior caso: C i (n) = i .

Caso médio: C i (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 .





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

Melhor caso: M i (n) = 0.

Pior caso: M i (n) = i .

Caso médio: M i (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 .




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.



Conteúdo


2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 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.



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.



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?



Conteúdo


2 BubbleSort

3 SelectionSort

4 InsertionSort

5 Conclusão

6 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).


Documents

BCC202 - Estrutura de Dados I - Aula 12: Ordenação: Bubble ... · PDF fileIntrodução BubbleSort SelectionSort InsertionSort Conclusão Exercícios BCC202-EstruturadeDadosI Aula12: