Bolha
Ordenação
●
Procedimento de estabelecer uma ordem
em uma sequência.
1
2
3
4
5
6
101
77
42
35
12
5
1
2
3
4
5
6
5
12
35
42
77
101
"Descendo" o Menor
Elemento
●
Caminha na sequência de elementos
–
–
Move do fim para inicio
“desce” o menor valor para o inicio
usando comparações par-a-par e
trocando
1
2
3
4
5
6
101
77
42
35
12
5
O Algoritmo da “Descida”
i = n
ordenados = 1
enquanto(i > ordenados)
se(A[i] < A[i-1]) entao
Troca(A[i], A[i - 1])
fim se
i = i - 1
fimenquanto
O que precisa ser
notado
Somente o menor valor é ordenado
• Todos os outros valores podem continuar
fora da ordem
●
Assim é preciso repetir o processo
●
1
2
3
4
5
6
5
101
77
42
35
12
O menor valor está ordenado
Repetir a “Descida”
Quantas Vezes?
●
●
●
●
Se tivermos N elementos…
E se a cada passada descemos um
elemento, e colocamos ele no posição
correta...
Então nós repetimos o processo de
“descida” N – 1 vezes.
Isso garante que iremos posicionar todos
os N elementos corretamente.
Juntando as peças
Bolha(vetor A[], tamanho N )
se(A[ind] < A[ind - 1]) entao
Troca(A[ind], A[ind - 1])
fim se
ind = ind - 1
fim enquanto
ordenados = ordenados + 1
fim enquanto
Loop externo
Enquanto (ordenados < N-1)
ind = N
Enquanto (ind > ordenados)
Loop interno
ordenados = 0
Em cenário de Ordenação
parcial?
●
●
●
E se a sequência estiver ordenada?
E se somente alguns elementos
estiverem fora de ordem e após
algumas “descidas” a sequência for
ordenada?
A idéia é detectar isso e “parar
logo”!
1
2
3
4
5
6
101
77
42
35
12
5
Usando um “Status”
●
Podemos usar uma variável para determinar
se ocorreu alguma troca durante o
processo de “descida”
• Se Não ocorreu trocas, então a sequência
está ordenada!
●
Esse “status” precisa se inicializado após
cada “descida”.
teve_troca = verdade
enquanto((ordenados < N) E (teve_troca))
ind = N
teve_troca = falso
enquanto(ind > ordenados)
se(A[ind] < A[ind - 1]) então
Troca(A[ind], A[ind - 1])
teve_troca = verdade
fimse
ind = ind - 1
fim enquanto
ordenados = ordenados + 1
fim enquanto
Resumo
●
●
●
Algoritmo “Descida” move o menor valor para a
localização correta (direita)
Repete “Descida” até que todos os elementos
estejam corretamente posicionados:
– Máximo de N-1 vezes
– Pode finalizar antes se não houver troca
O número de elementos é reduzido toda vez que
um elemento é posicionado corretamente
Quanto custa O
Bubble Sort?
Seleção
Seleção
●
Procedimento de estabelecer uma ordem em
uma sequência escolhedo o menor elemento no
conjunto de elementos não-ordenados e
colocando-o na posição correta.
1
2
3
4
5
6
101
77
42
35
12
5
1
2
3
4
5
6
5
12
35
42
77
101
}
Loop externo
k = 1
enquanto( k < N ) faça {
idc_menor = k
i=k+1
enquanto( i<=N ) faça {
se vetor[idc_menor] > vetor[i]
idc_menor = i
i = i + 1
Fim enquanto
troca(vetor[k], vetor[idc_menor])
k = k + 1;
Fim enquanto
Loop interno
selecao(vetor, N){
Quanto Custa o Algoritmo?
Inserção
●
Procedimento de estabelecer uma ordem
em uma sequência posicionando o
primeiro do conjunto Não-ordenado no
conjunto de elementos ordenados.
1
2
3
4
5
6
101
77
42
35
12
5
1
2
3
4
5
6
5
12
35
42
77
101
k = 2
enquanto ( k <= N ) faça
elem = vetor[k]
i = k - 1
enquanto ( (i > 0) E (vetor[i] > elem) ) faça
vetor[i+1] = vetor[i]
i = i - 1
fim enquanto
vetor[i+1] = elem
K = k + 1;
fim enquanto
Loop externo
Loop interno
inserção(vetor, N){
Quanto custa o algoritmo?