Qual o princípio de ordenação do Bubble Sort?
Soluções para a tarefa
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, e a cada passagem fazer flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
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).