21
Estrutura de Dados (DPADF 0056) Aula 15 Bubble Sort Universidade Federal de Santa Maria Colégio Agrícola de Frederico Westphalen Curso Superior de Tecnologia em Sistemas para Internet Prof. Bruno B. Boniati www.cafw.ufsm.br/~bruno

Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Embed Size (px)

Citation preview

Page 1: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Estrutura de Dados (DPADF 0056)Aula 15 – Bubble Sort

Universidade Federal de Santa Maria

Colégio Agrícola de Frederico Westphalen

Curso Superior de Tecnologia em Sistemas para Internet

Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno

Page 2: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Ordenação por Seleção e Troca

http://www.sorting-algorithms.com

Page 3: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Bubble Sort

• Método de ordenação por troca ou flutuação;

• Um dos algoritmos mais simples;

• Consiste em percorrer uma lista diversas vezes

“empurrando” os elementos maiores para o final

do vetor.

• Seu funcionamento lembra a forma como as

bolhas de ar procuram a saída em um fluído;

Page 4: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Bubble Sort

• Algoritmo:

▫ Percorra o vetor inteiro comparando elementos

vizinhos (dois a dois);

▫ Troque as posições dos elementos se eles

estiverem fora de ordem;

▫ Repita os dois primeiros passos até o ordenação

estar completa.

• Implementação:

▫ Laços de repetição aninhados.

Page 5: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Bubble Sort (simulação)

Dados

originais

Iteração

Iteração

Page 6: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Bubble Sort (simulação)

Iteração

Iteração

Iteração

Page 7: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Bubble Sort (simulação)

Iteração

Iteração

Iteração

Neste caso não há troca

Neste caso não há troca

Page 8: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Bubble Sort (simulação)

Iteração

10ª

Iteração

11ª

Iteração

Neste caso não há troca

Não há troca nessa iteração e nem na próxima.

Page 9: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Algoritmo – Bubble Sort

void bubbleSort(int* vet, int tam) {

int i;

int trocou;

do {

tam--;

trocou = 0;

for(i = 0; i < tam; i++)

if(vet[i] > vet[i + 1]) {

troca(&vet[i],&vet[i+1]);

trocou = 1;

}

} while(trocou);

}

Page 10: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Exercícios para fixação

Page 11: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Bubble Sort para ordenar uma LDE

• Implemente uma subrotina para ordenar uma

lista duplamente encadeada utilizando a técnica

Bubble Sort.

1017

6

40

2

ɸ

ɸ

Page 12: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Estrutura de Dados (DPADF 0056)Aula 16 – Shell Sort

Universidade Federal de Santa Maria

Colégio Agrícola de Frederico Westphalen

Curso Superior de Tecnologia em Sistemas para Internet

Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno

Page 13: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Ordenação por Inserção através de

Incrementos

http://www.sorting-algorithms.com

Page 14: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Shell Sort• Resultado de trabalho publicado pelo matemático

Donald Shell em 1959.

• Ordenação por inserção através de incrementos;

• Consiste em passar várias vezes pela lista dividindo-a

em grupos. Nos grupos menores é aplicado outro

método de ordenação (geralmente insertion sort).

• É o algoritmo mais eficiente entre os de baixa

complexidade de implementação;

Page 15: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Shell Sort

• Algoritmo:▫ Inicialmente a seqüência original é dividida em grupos;

Isso pode ser feito dividindo-se o tamanho da sequência

ao meio. O resultado dessa divisão é guardado em uma

variável (h, que representa a quantidade de saltos

necessários para formar um grupo);

▫ Em seguida são aplicadas ordenações (com qualquer

outro algoritmo) nos sub-grupos (que são formados

saltando-se de “h em h elementos”);

▫ O valor de h vai sendo novamente dividido até que os

“saltos” sejam de elemento em elemento;

Page 16: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Shell Sort (simulação)

Dados originais

(5 elementos)

1ª rodada

(elementos

de 2 em 2)

Cálculo do número de saltos (valor inteiro)

h = tam ÷ 2 h = 2

Grupo 1

Grupo 2

Page 17: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Shell Sort (simulação)

Ordenação

do Grupo 1

1ª Iteração

Ordenação

do grupo 1

concluída

2ª Iteração

Page 18: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Shell Sort (simulação)

Ordenação

do Grupo 2

1ª Iteração

Observe que a

ordenação da

sequencia

resultante é mínima

neste caso não há troca

Novo cálculo do número de saltos (valor inteiro)

h = h ÷ 2 h = 1

Page 19: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Algoritmo – Shell Sort

void shellSort(int* vet, int tam) {

int h = tam / 2;

int chave, j, i;

while (h > 0) {

for (i = h; i < tam; i++) {

chave = vet[i];

j = i;

while (j >= h && vet[j - h] > chave) {

vet[j] = vet[j - h];

j = j - h;

}

vet[j] = chave;

}

h = h / 2;

}

}

Page 20: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Exercícios para fixação

Page 21: Estrutura de Dados (DPADF 0056) - cafw.ufsm.br · PDF fileBubble Sort •Método de ordenação por troca ou flutuação; •Um dos algoritmos mais simples; •Consiste em percorrer

Variações do Shell Sort

• A definição do Shell Sort deixa em aberto a

escolha do algoritmo utilizado para ordenar os

subgrupos (apenas sugere-se a utilização de

Insertion Sort)

▫ Experimente adaptar o algoritmo de ordenação Shell

Sort, utilizando um algoritmo alternativo ao Insertion

Sort para ordenar os subgrupos.