|
|
Se esta página lhe ajudar, considere fazer uma doação |
A ordenação dos elementos de um vetor é um problema clássico de programação e uma das dores de cabeça dos iniciantes.
Abordaremos hoje um das formas de ordenação conhecida como ordenação por flutuação ou ordenação pelo método da bolha, "bubble sort" em inglês.
Neste método os elementos do vetor são analisados do início até o final e os pares de elementos adjacentes são comparados e ordenados, caso estejam fora de ordem. Assim, os elementos maiores vão sendo empurrados para o fim do vetor da mesma forma como as bolhas na água são empurradas para cima. Daí vem o nome de ordenação pelo método da bolha.
Para clarear este conceito vamos a um exemplo. Dado o vetor abaixo:
|
4 |
5 |
1 |
3 |
2 |
Vamos ordená-lo pelo método da bolha.
Iniciamos analisando o primeiro par de elementos adjacentes, no caso, 4 e 5.
|
4 |
5 |
1 |
3 |
2 |
Vemos que estão ordenados e nada deve ser feito.
Agora analisamos o segundo par (5 e 1).
|
4 |
5 |
1 |
3 |
2 |
Observamos que estão desordenados e executamos a troca, nosso vetor ficará assim:
|
4 |
1 |
5 |
3 |
2 |
Analisamos o terceiro par (5 e 3).
|
4 |
1 |
5 |
3 |
2 |
Estão desordenados e devem ser trocados. O vetor ficará assim:
|
4 |
1 |
3 |
5 |
2 |
Analisamos o quarto par (5 e 2).
|
4 |
1 |
3 |
5 |
2 |
Estão desordenados e devem ser trocados. O vetor ficará assim:
|
4 |
1 |
3 |
2 |
5 |
Chegando ao final da primeira passagem, verificamos se o vetor está completamente ordenado e notamos que ainda não está. Então, iniciamos a segunda passagem analisando os dois primeiros pares (4 e 1).
|
4 |
1 |
3 |
2 |
5 |
Pares desordenados. Troca e nosso vetor ficará assim:
|
1 |
4 |
3 |
2 |
5 |
Próxima análise (4 e 3).
|
1 |
4 |
3 |
2 |
5 |
Pares desordenados. Outra troca.
|
1 |
3 |
4 |
2 |
5 |
E este processo continua até que todo o vetor esteja ordenado. Isto acontecerá quando em uma passagem por todo o vetor, nenhum par adjacente precise ser trocado.
Abaixo você pode ver um algoritmo para a resolução deste problema:
INÍCIO
DECLARAÇÃO DE VARIÁVEIS
inteiro: V(n);
inteiro: i <== 1;
inteiro: parOk <== 0;
inteiro: aux <== 0;
ENTRADA DE DADOS
ler V(n);
PROCESSAMENTO
enquanto VERDADE faça
para i de 1 até n incremento 1 faça
se V(i) <= V(i + 1)
parOk <== parOk + 1;
senão
aux <== V(i + 1);
V(i + 1) <== V(i);
V(i) <== aux;
fimse;
se parOk = (n - 1)
SAIR DO LAÇO enquanto;
senão
parOK <== 0;
fimse;
fimpara;
fimenquanto;
SAÍDA DE DADOS
imprimir V(n);
FIM
Para este algoritmo eu usei a notação descrita em minha apostila sobre algoritmos que pode ser acessada em http://www.samueldiasneto.com/algo1/index.htm.
A variável parOk é usada para controlar quantos pares adjacentes estão ordenados. A quantidade de pares adjacentes do vetor é igual ao seu número de elementos menos 1. Assim, um vetor de 5 elementos tem 4 pares adjacentes, como podemos ver no exemplo explanado acima, antes do algoritmo.
O comando enquanto VERDADE faça representa um laço infinito que será abandonado quando a variável parOK for igual ao número de pares adjacentes do vetor, ou seja, quando todos os pares estiverem ordenados.
Abaixo temos a codificação deste algoritmo em Python:
#!/usr/bin/python
# -*- coding: iso-8859-1 -*-
# bubble-sort.py
# Ordenando inteiros pelo método da bolha
V = []
i = 0
parOk = 0
aux = 0
while True:
nr = input("Entre com um inteiro ou zero para encerrar):")
V.append(nr)
if nr == 0:
break
n = len(V)
while True:
for i in range(0,(n - 1)):
if V[i] <= V[i + 1]:
parOk = parOk + 1
else:
aux = V[i + 1]
V[i + 1] = V[i]
V[i] = aux
if parOk == (n -1):
break
else:
parOk = 0
print V
Por hoje é só pessoal. A codificação em C eu deixo para vocês. Bons estudos.
Samuel
|
|
Se esta página lhe ajudou, considere fazer uma doação |