Bubble Sort (pt.2)

Bom, hoje irei explicar a segunda optimização para o algoritmo de ordenação Bubble Sort.

Recomendo que leiam o primeiro post que explica o básico e a primeira optimização, clicando neste link.

Vamos rever alguns conceitos do algoritmo, para então darmos enfase à segunda optimização.

Vejamos como exemplo a seguinte cadeia de valores: (5, 3, 6, 4, 1).

Se prestarmos atenção, notaremos que existe um valor que é maior que todos os outros, o 6.

Nesta cadeia em particular ele é o maior, apenas mantenham isso em mente.

Agora façamos a primeira varredura, que trará o seguinte resultado: (3, 5, 4, 1, 6).

Notem que o maior número (o 6) foi mandado, já na primeira varredura, para a última posição, posição à qual ele realmente pertence.

Isso faz com que, na próxima varredura, possamos ignorar a verificação da última posição, visto que ela já está ocupada pelo valor correto.

Aí está a optimização.

O fato de ignorarmos o último valor, nos poupará o trabalho de verificarmos algo que já está correto.

Vale lembrar que isso vale para as seguintes varreduras também, ou seja, agora ignoramos o maior valor (6), na próxima varredura traremos o segundo maior valor (5) para a penúltima posição, e então o ignoraremos na próxima varredura, e por aí vai.

Ainda não entendeu a vantagem?

Pense numa cadeia de 100 valores, onde eu precisarei fazer a 50 varreduras, farei a verificação da posição 1 até o 100.

Agora implementamos essa optimização.

A cadeia tem 100 valores, e farei a varredura 50 vezes. Porém agora, a primeira verificação irá da posição 1 até o 100, a segunda vai da posição 1 até o 99, ... , e a quinquagésima varredura irá da posição 1 até o 50 apenas.
Pode não ser algo grandioso, mas de fato é uma economia significativa.

Bom, é isso aí, como prometido eu expliquei a segunda optimização do algoritmo Bubble Sort.

Caso surjam dúvidas, comentem.

Até a próxima.