Começaremos neste artigo uma série que apresentará quatro dos mais conhecidos algoritmos de ordenação (bubblesort, insertsort, mergesort e quicksort), explicando como cada um funciona e dando exemplos de implementações em Python.
Os dois primeiros algoritmos que apresentaremos são talvez os que as pessoas normalmente consideram mais óbvios de se pensar para a ordenação: o bubblesort e o insertsort. Neste primeiro artigo, introduziremos o bubble sort.
O bubblesort
Pense no seguinte vetor de números: [4,5,2,1,3,7,5].
A primeira idéia de algumas pessoas que nunca pensaram antes no problema da ordenação é a de percorrer cada posição desse vetor, verificando se cada número é realmente maior que seu anterior e, caso não for, inverter as posições de um com a de outro.
Se fizermos isso uma vez, teremos: [4,2,1,3,5,5,7].
Realmente o vetor está "menos desordenado" agora, mas ele ainda não está completamente ordenado. A solução é ir repetindo esse procedimento até que ele esteja completamente ordenado. Saberemos que ele está completamente ordenado quando não precisarmos realizar mais nenhuma troca durante esse procedimento.
Repetindo o procedimento, temos:
[2,1,3,4,5,5,7]
[1,2,3,4,5,5,7]
Agora o vetor está ordenado. Podemos verificar isso repetindo o procedimento e percebendo que nenhuma troca mais será realizada. O máximo de vezes que o procedimento terá que ser repetido para um vetor ser ordenado é equivalente ao número n de elementos do vetor. Isso ocorrerá caso o maior elemento esteja na primeira posição, exigindo que n trocas sejam feitas para ele chegar ao final do vetor.
Como o pior que pode acontecer é o procedimento ser repetido n vezes, e como o procedimento realiza no máximo n trocas (uma para cada posição do vetor), o maior número de trocas que podem precisar ser realizadas para ordenar um vetor por esse método é de n² trocas.
Como uma troca de valor entre duas posições demora mais ou menos sempre o mesmo tempo para ser realizada, dizemos que a complexidade desse algoritmo é O(n²).
Um exemplo de implementação desse algoritmo em Python é apresentado a seguir:
def bsort(a):
sorted = False
while not sorted:
sorted = True
for i in range(1, len(a)):
if a[i-1] > a[i]:
sorted = False
t = a[i-1]
a[i-1] = a[i]
a[i] = t
a = [4,5,2,1,3,7,5]
print repr(a)
bsort(a)
print repr(a)
$ python bsort.py
[4, 5, 2, 1, 3, 7, 5]
[1, 2, 3, 4, 5, 5, 7]
Não perca amanhã o próximo artigo da série sobre o insertsort!
