Bubble Sort

Prévia do material em texto

Prof. Aleffer Rocha
O algoritmo de ordenação mais conhecido dentre os
programadores. Este algoritmo consiste em percorrer o arquivo
sequencialmente várias vezes.
A cada vez que o vetor é percorrido, compara-se cada elemento
com o seu sucessor (𝑣[𝑖] com 𝑣[𝑖 + 1]) e troca os dois elementos
caso não estejam na ordem correta.
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
34 13 51 0 78 14
Primeira iteração
v[0] > v[1]
2 3 4 5v[6] = 
34 13 51 0 78 14
Primeira iteração
v[0] > v[1]
2 3 4 5v[6] = 
51 0 78 14
Primeira iteração
13 34
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 51 0 78 14
Primeira iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 51 0 78 14
Primeira iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 51 0 78 14
Primeira iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 51 0 78 14
Primeira iteração
v[2] > v[3]
10 4 5v[6] = 
13 34 51 0 78 14
Primeira iteração
v[2] > v[3]
10 4 5v[6] = 
13 34 78 14
Primeira iteração
510
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 78 14
Primeira iteração
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 78 14
Primeira iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 78 14
Primeira iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 78 14
Primeira iteração
v[4] > v[5]
1 20 3v[6] = 
13 34 510 78 14
Primeira iteração
v[4] > v[5]
1 20 3v[6] = 
13 34 510
Primeira iteração
14 78
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Primeira iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[1] > v[2]
0 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[1] > v[2]
0 3 4 5v[6] = 
13 51 14 78
Segunda iteração
340
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[3] > v[4]
1 20 5v[6] = 
13 34 510 14 78
Segunda iteração
v[3] > v[4]
1 20 5v[6] = 
13 340 78
Segunda iteração
5114
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Segunda iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[0] > v[1]
2 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[0] > v[1]
2 3 4 5v[6] = 
34 5114 78
Terceira iteração
130
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[2] > v[3]
10 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[2] > v[3]
10 4 5v[6] = 
13 510 78
Terceira iteração
3414
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Terceira iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quarta iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[0] > v[1]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[1] > v[2]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[2] > v[3]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[3] > v[4]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[4] > v[5]
1 20 3 4 5v[6] = 
13 34 510 14 78
Quinta iteração
v[4] > v[5]
Resumo de iterações
1 20 3 4 5v[6] = 
34 13 51 0 78 14
1 20 3 4 5v[6] = 
1 20 3 4 5v[6] = 
1 20 3 4 5v[6] = 
1 20 3 4 5v[6] = 
1 20 3 4 5v[6] = 
3413 510 7814
3413 510 7814
3413 510 7814
3413 510 7814
Vetor
inicial
i = 0
i = 1
i = 2
i = 3
i = 43413 510 7814
Início BubbleSort(v[], ini, fim)
Para i = ini até fim faça
Para j = 0 até fim faça
Se v[j] > v[j+1] então
troque v[j] com v[j+1];
Fim Se
Fim Para
Fim Para
Fim BubbleSort
Qual a ordem de grandeza no pior caso do algoritmo Bubble Sort?
𝑂(𝑛2) onde 𝑛 é a quantidade de elementos no vetor.
• TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, 
Moshe J. Estrutura de Dados usando C. Pearson Makron 
Books, 2004.
	ESTRUTURA DE DADOS 1 BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	BUBBLE SORT
	MATERIAL UTILIZADO