O programa a seguir, em Python, implementa o algoritmo do mé...

A bolha verifica se cada elemento da posição i é maior que o próximo (i+1). Se for maior, trocam de lugar, se não, não trocam. O "i" será o 1º número, depois o 2º, depois o 3º... no exemplo abaixo, primeiro o i = 4 (1º número), e por isso trocarão de lugar. Ato contínuo, o i = 4 novamente, porque 4 trocou de lugar com 3 e agora é o 2º número. E assim sucessivamente.

[4, 3, 1, 9, 8, 7, 2, 5] - 4 é maior que 3, sim. Troca de lugar → [3, 4, 1, 9, 8, 7, 2, 5] 
[3, 4, 1, 9, 8, 7, 2, 5] - 4 é maior que 1, sim. Troca de lugar → [3, 1, 4, 9, 8, 7, 2, 5]
[3, 1, 4, 9, 8, 7, 2, 5] - 4 é maior que 9, não. Não troca → [3, 1, 4, 9, 8, 7, 2, 5]
[3, 1, 4, 9, 8, 7, 2, 5] - 9 é maior que 8, sim. Troca de Lugar → [3, 1, 4, 8, 9, 7, 2, 5]
[3, 1, 4, 8, 9, 7, 2, 5] - 9 é maior que 7, sim. Troca de Lugar → [3, 1, 4, 8, 7, 9, 2, 5]
[3, 1, 4, 8, 7, 9, 2, 5] - 9 é maior que 2, sim. Troca de Lugar → [3, 1, 4, 8, 7, 2, 9, 5]
[3, 1, 4, 8, 7, 2, 9, 5] - 9 é maior que 5, sim. Troca de Lugar → [3, 1, 4, 8, 7, 2, 5, 9]

Linha 1: [3, 1, 4, 8, 7, 2, 5, 9]

E assim segue o raciocínio, basta ir comparando "i" com o próximo número e trocando de lugar se o número seguinte for menor:

Linha 2: [1, 3, 4, 7, 2, 5, 8, 9]
Linha 3: [1, 3, 4, 2, 5, 7, 8, 9]
Linha 4: [1, 3, 2, 4, 5, 7, 8, 9]

A bolha (bubble sort) é o algoritmo mais simples, mas o menos eficiente, pois pode ser ineficiente para listas muito grandes.

Flávio Diniz, por que a primeira linha do teu esquema é o último resultado da alternância dos números dados inicialmente na questão?

Vejamos:

def bolha(lista):

#a lista contém [ 4, 3, 1, 9, 8, 7, 2, 5] , 8 itens

  for passo in range(len(lista)-1,0,-1):

# dado o 'len(lista)-1,0,-1' aqui, 'passo' recebe valores do 7 ao 0 (8-1);

    for i in range(passo):

# 'i' recebe os valores em 'passo', que são (7,6,5,4,3,2,1,0)

      if lista[i]>lista[i+1]:

# compara valores da lista conforme o valor corrente de 'i'. por exemplo:

# lista[6] >lista[7] = 2>5? se a resposta for 'sim', executa a próxima linha

        lista[i],lista[i+1]=lista[i+1],lista[i]

# isso aqui acaba mudando os valores de um pelo outro, criando ordem crescente

  print(lista)

Rodei o código e deu:

def bolha(lista):
    for passo in range(len(lista)-1,0,-1):
        for i in range(passo):
            if lista[i]>lista[i+1]:
                lista[i],lista[i+1] = lista[i+1],lista[i]
        print(lista)

[3, 1, 4, 8, 7, 2, 5, 9]
[1, 3, 4, 7, 2, 5, 8, 9]
[1, 3, 4, 2, 5, 7, 8, 9]
[1, 3, 2, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]

def bolha(lista):    
___for passo in range(len(lista)-1,0,-1):        
______for i in range(passo):
_________print(i)           
_________print(lista[i], lista[i+1])      
_________if lista[i]>lista[i+1]:                
____________lista[i], lista[i+1] = lista[i+1], lista[i]        
______print(lista) bolha([ 4, 3, 1, 9, 8, 7, 2, 5])

0             valor de ' i '
4 3          valor da lista[i] lista[i+1]
1             valor de ' i '
4 1          valor da lista[i] lista[i+1]
2             valor de ' i '
4 9          valor da lista[i] lista[i+1]
3             valor de ' i '
9 8          valor da lista[i] lista[i+1]
4             valor de ' i '
9 7          valor da lista[i] lista[i+1]
5             valor de ' i '
9 2          valor da lista[i] lista[i+1]
6             valor de ' i '
9 5          valor da lista[i] lista[i+1]
[3, 1, 4, 8, 7, 2, 5, 9]            1º L
0             valor de ' i '
3 1          valor da lista[i] lista[i+1]
1             valor de ' i '
3 4          valor da lista[i] lista[i+1]
2             valor de ' i '
4 8          valor da lista[i] lista[i+1]
3             valor de ' i '
8 7          valor da lista[i] lista[i+1]
4             valor de ' i '
8 2          valor da lista[i] lista[i+1]
5             valor de ' i '
8 5          valor da lista[i] lista[i+1]
[1, 3, 4, 7, 2, 5, 8, 9]            2º L
0             valor de ' i '
1 3          valor da lista[i] lista[i+1]
1             valor de ' i '
3 4          valor da lista[i] lista[i+1]
2             valor de ' i '
4 7          valor da lista[i] lista[i+1]
3             valor de ' i '
7 2          valor da lista[i] lista[i+1]
4             valor de ' i '
7 5          valor da lista[i] lista[i+1]
[1, 3, 4, 2, 5, 7, 8, 9]            3º L
0             valor de ' i '
1 3          valor da lista[i] lista[i+1]
1             valor de ' i '
3 4          valor da lista[i] lista[i+1]
2             valor de ' i '
4 2          valor da lista[i] lista[i+1]
3             valor de ' i '
4 5          valor da lista[i] lista[i+1]
[1, 3, 2, 4, 5, 7, 8, 9]            4º L
0
1 3
1
3 2
2
3 4
[1, 2, 3, 4, 5, 7, 8, 9]
0
1 2        
1            
2 3       
[1, 2, 3, 4, 5, 7, 8, 9]
0
1 2
[1, 2, 3, 4, 5, 7, 8, 9]

Então, coloquei os comandos abaixo, para descobrir qual o valor de ' i ' que o programa estava executando:
_________print(i)           
_________print(lista[i], lista[i+1])

Sabendo que, os valores possíves de ' i ' são os regados pelo range abaixo
range(len(lista)-1,0,-1)
range(8-1,0,-1)
range(7,0,-1)
[7,6,5,4,3,2,1]

Porém, observa-se que o programa está para usando ' i ' os valores [0,1,2,3,4,5,6] ao invés dos gerados pelo range(len(lista)-1,0,-1)

Alguém poderia me explicar, o que não não consegui entender ?

Obrigado.