Em alguns posts que virão, veremos alguns algoritmos de ordenação.
Um algoritmo de ordenação recebe como entrada um vetor com elementos em uma ordem qualquer (por ex. [4, 9, 6, 1, 3, 5]) e retorna o vetor com seus elementos seguindo uma certa ordem (crescente, por ex., como em [1, 3, 4, 5, 6, 9] - ordenação do vetor do exemplo anterior).
Um dos algoritmos de ordenação mais simples é o Bubble Sort, mais conhecida como "Algoritmo da Bolha" (em português). A ideia é ir comparando elementos dois a dois e trocá-los de ordem, dependendo de como se deseja ordenar o vetor. Após isso ser feito n vezes, o vetor final estará ordenado.
Ex:
- para cada elemento à direita do maior, vamos invertendo suas posições para que assim o maior chegue ao final
5 6 9 3 7 4 2
5 6 9 3 7 4 2
5 6 9 3 7 4 2
5 6 3 9 7 4 2
5 6 3 7 9 4 2
5 6 3 7 4 9 2
5 6 3 7 4 2 9
- no próximo passo, deixamos de verificar a parte já ordenada (em azul), pegamos apenas o subvetor restante e repetimos o processo
5 6 3 7 4 2 9
5 6 3 7 4 2 9
5 3 6 7 4 2 9
5 3 6 7 4 2 9
5 3 6 4 7 2 9
5 3 6 4 2 7 9
- continuamos até que todos sejam verificados
5 3 6 4 2 7 9
3 5 6 4 2 7 9
3 5 6 4 2 7 9
3 5 4 6 2 7 9
3 5 4 2 6 7 9
(é como se cada elemento maior encontrado fosse uma bolha que fosse flutuando até chegar ao topo)
3 5 4 2 6 7 9
3 5 4 2 6 7 9
3 4 5 2 6 7 9
3 4 2 5 6 7 9
3 4 2 5 6 7 9
3 4 2 5 6 7 9
3 2 4 5 6 7 9
* Observe que só precisamos executar o processo n-1 vezes, pois quando o penúltimo maior elemento foi colocado na posição correta, o vetor restante desordenado só contém 1 elemento, que é menor do que todos à sua direita. Portanto, o vetor final estará completamente ordenado.
3 2 4 5 6 7 9
2 3 4 5 6 7 9
Veja abaixo alguns videos que mostram a execução do algoritmo.
Quer ler mais sobre o BubbleSort? Clique aqui. Na wikipedia você vai encontrar várias implementações desse algoritmo. Em posts futuros, falaremos sobre complexidade. Mas já adiantando, o BubbleSort é O(n²). Você saberia explicar por quê?
=)
Até a próxima!
