Em diversas aplicações, tanto cientificas como comerciais, vamos encontrar problemas de ordenação, como por exemplo, ordenar números em ordem crescente ou decrescente, nomes em ordem alfabética, etc. Para ordenar os elementos de uma maneira eficaz é necessário o uso de um algoritmo de ordenação. Existem diversos algoritmos de ordenação, o conhecimento deles e suas aplicações é algo muito importante para um programador; conhecendo esses algoritmos, o programador poderá escolher o melhor de acordo com a necessidade, melhorando o desempenho da aplicação.
Para entendermos os algoritmos de ordenação mais complexos, devemos entender primeiro os mais simples.
Este artigo tem como objetivo demonstrar um dos algoritmos mais simples, o Bubble Sort. Uma forma de trabalhar com o algoritmo Bubble Sorte é comparando os elementos adjacentes (dois a dois), por exemplo: compara-se a primeira posição do vetor com a segunda, na segunda iteração (repetição), compara-se a segunda posição do vetor com a terceira, e assim sucessivamente. De acordo com o algoritmo, podemos ordenar o vetor de forma crescente ou decrescente.
O algoritmo Bubble Sort percorre todo o vetor diversas vezes, por isso, não é recomendado o uso dele para aplicações que requerem velocidade ou trabalhem com uma grande quantidade de dados. Como exemplo, vamos ordenar um vetor em ordem crescente composto pelos elementos {8, 9, 3, 5, 1}.
O algoritmo inicia comparando a primeira posição do vetor, que tem o elemento 8, com a segunda posição do vetor que tem o elemento 9.
Como o elemento 8 é menor que o elemento 9, não há troca de posição. {8, 9, 3, 5, 1}
Na próxima iteração, compara-se a segunda posição do vetor, que tem o elemento 9, comparando-o com a terceira posição do vetor, que tem o elemento 3. {8, 9, 3, 5, 1}
Como elemento 9 é maior que o elemento 3 é feito a troca de posição e reordena-se o vetor.
Compara-se com a terceira posição do vetor, que agora tem o elemento 9, com a quarta posição do vetor que tem o elemento 5. {8, 3, 9, 5, 1}
Como o elemento 9 é maior que o elemento 5, é feito a troca de posição e reordena-se o vetor.
Compara-se a quarta posição do vetor, que tem o elemento 9, com a quinta posição do vetor, que tem o elemento 1. {8, 3, 5, 9, 1}
Como elemento 9 é maior que o elemento 1 é feito a troca de posição.
Reordenando o vetor: {8, 3, 5, 1, 9}
Dessa forma é feita a primeira iteração por completo. Com podemos verificar, o elemento com maior valor (9) foi ficou na última posição do vetor, esse processo vai se repetir até que o vetor esteja ordenado. Na próxima iteração, o segundo maior valor será ordenado para penúltima posição do vetor. Essa ordenação lembra como as bolhas num tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo, Bubble Sort (literalmente "flutuação por Bolha"). Na próxima iteração, todo esse processo vai se repetir, vejamos:
{8, 3, 5, 1, 9}: 8 > 3 = Sim, realizar troca. Reordenando o vetor:
{3, 8, 5, 1, 9}: 8 > 5 = Sim, realizar troca. Reordenando o vetor:
{3, 5, 8, 1, 9}: 8 > 1 = Sim, realiza troca. Reordenando o vetor:
{3, 5, 1, 8, 9}: 8 > 9 = Não, vetor permanece como está.
Com isso é feito uma segunda iteração por completo. Novamente o processo vai se repetir.
{3, 5, 1, 8, 9}: 3 > 5 = Não, vetor permanece como está.
{3, 5, 1, 8, 9}: 5 > 1 = Sim, realiza troca. Reordenando o vetor:
{3, 1, 5, 8, 9}: 5 >8 = Não, vetor permanece como está.
{3, 1, 5, 8, 9}: 8 > 9 = Não, vetor permanece como está.
Terceira iteração realizada por completo. O processo se repete novamente:
{3, 1, 5, 8, 9}: 3 > 1 = Sim, realiza troca. Reordenando o vetor:
{1, 3, 5, 8, 9}: 3 > 5 = Não, vetor permanece como está.
{1, 3, 5, 8, 9}: 5 > 8 = Não, vetor permanece como está.
{1, 3, 5, 8, 9}: 8 > 9 = Não, vetor permanece como está.
Terminada a quarta iteração, o vetor está ordenado em ordem crescente. Podemos observar que o vetor tem cinco posições e foram feitas quatro iterações, por quê?
Como vimos, a comparação é sempre da seguinte forma: V[posição] > v[posição +1].
Ex: Posição zero com posição um, ou seja, v[0] > v[1].
Desta forma, se o laço for até a última posição do vetor, ele irá comparar com um valor que não existe, e conseqüentemente irá retornar mensagem de erro.
Por isso só repetimos o laço por 4 vezes, a última repetição fica da seguinte forma: v[4] > v[5] (Comparando todos os elementos do vetor).
Existem outras formas de implementar o algoritmo Bubble Sort, porém, entendendo este código, você poderá implementar de outras forma para treinar.
Abaixo segue o código do Bubble Sort implementado em Java, este código segue o exemplo demonstrado acima. Existem outras formas de fazer o Bubble Sort, mas a idéia desse artigo é demonstrar o funcionamento do algoritmo passo a passo, por isso o algoritmo segue o exemplo simulado acima.
Listagem 1: Código do algoritmo Buble Sort em Java
public static void main(String args[]){
int[] vet = {8, 9, 3, 5, 1};
int aux = 0;
int i = 0;
System.out.println("Vetor desordenado: ");
for(i = 0; i<5; i++){
System.out.println(" "+vet[i]);
}
System.out.println(" ");
for(i = 0; i<5; i++){
for(int j = 0; j<4; j++){
if(vet[j] > vet[j + 1]){
aux = vet[j];
vet[j] = vet[j+1];
vet[j+1] = aux;
}
}
}
System.out.println("Vetor organizado:");
for(i = 0; i<5; i++){
System.out.println(" "+vet[i]);
}
}
Assim finalizamos este artigo. Até a próxima.
