[MÚSICA] Vamos agora então, estudar pouco diferente algoritmo de ordenação, chamado algoritmo da bolha, ou BubbleSort, inglês. Qual que é a ideia do BubbleSort? Pensa na lista que você quer ordenar como se fosse tubo de ensaio vertical, assim, onde você tem os elementos dentro desse tubo de ensaio de forma que os elementos mais leves sobem à superfície, como se fossem uma bolha, e os mais pesados vão afundando. Então, a gente vai percorrer verticalmente assim o vetor várias vezes, e a cada passo, o mais pesado se deposita lá no fundo e os mais leves vão subindo. Então, esse algoritmo, ele percorre a lista múltiplas vezes, e a cada passagem ele compara todos os elementos adjacentes. Ele vai comparando dois a dois os elementos adjacentes e se eles estiverem na ordem certa, ou seja, o menor pra cima e o mais pesado, maior, para baixo, ele deixa, não faz nada, vai para o próximo parzinho. Se esse parzinho dos dois estão na ordem errada, ou seja, o mais leve embaixo, o mais pesado cima, ele troca de ordem esses dois. Então, ele vai subindo assim trocando de ordem. Daí, a cada passagem, que a gente vê que o elemento mais pesado se deposita no fundo do tubo de ensaio, e se o vetor tem N posições, a gente vai fazer N passagens dessa, e a cada passagem o mais pesado vai para o fundo e então depois das N passagens o vetor inteiro está ordenado. Então, vamos ver como que funciona esse algoritmo. A gente tem aqui. Eu vou continuar trabalhando nessa classe ordenador que a gente estava antes e agora eu vou definir o algoritmo aqui da bolha. Ou se você preferir, pode chamar de BubbleSort, ele vai receber como parâmetro ali também uma lista e eu também vou querer que essa variável fim só pra ficar mais claro, como sendo o comprimento da lista. Daí, o que nós podemos fazer. Primeiro eu vou fazer esse for, que vai usar índice I e eu quero que esse primeiro for, eu vou começar lá no fim do vetor, na posição fim -1, que é a última posição ali do vetor. Eu quero que ele vá até a posição 0 e o passo é de -1 -1. Então, esse aqui vai ser o meu for. Então, eu começo lá no fim, vou indo pro começo e de -1 -1, e a cada uma dessas passagens eu vou descobrir quem é o mais pesado e vou jogar lá pra baixo na minha lista. O mais pesado seria qual é o maior número e vou jogar lá pra baixo na lista. Então, agora, cada uma dessas passadas eu vou ter que percorrer todo o vetor, fazendo aquela troca dos elementos adjacentes que estão fora de ordem. Então, como que eu faço isso? Vou fazer for j in range e daí, o range que vou querer, vou querer desde a posição zero até a posição I -1. Então, eu vou fazer isso aqui for j in range I. E daí, eu vou comparar os dois elementos adjacentes aí, desse for. Então, como que eu faço isso? Se a lista, o elemento que tá na posição j da lista é maior do que o elemento que está na posição j +1, isso significa que está na ordem errada. Porque eu quero que os elementos maiores, se é ordem crescente, esteja mais pro final da lista. Se o j é maior do que o que tá no j +1, quer dizer que eles estão na ordem inversa. Então, eu preciso trocar os dois de ordem, e daí o jeito de fazer isso Python, tem aquele jeito simples Python pra trocar. Lista de j, lista de j +1 recebe o oposto, recebe lista de j +1 vírgula lista de j. Então, isso aqui vai trocar de lugar os elementos que estão na posição lista de j e lista de j +1. E por incrível que pareça, terminou, é só isso o algoritmo do BubbleSort. Para vocês entenderem bem como funciona, eu gostaria que vocês rastreassem casa isso aqui. Pegassem exemplo e rastreasse. Pensando rapidamente, vamos só de brincadeira aqui rastrear exemplo aqui. Por exemplo, vamos supor que eu tenho esse vetor aqui, 5-1-7-3-2. Então, eu quero ordenar de forma que o 5 é a primeira posição do vetor, e o 2 é a última posição do vetor. Então, eu começo aqui do final, vendo dois a dois. Então, primeiro eu vou comparar aqui. A gente vai percorrer na primeira interação o vetor inteiro. E daí, tem aquele segundo for, lembra? Segundo for era for j in range (i). Então, ele vai de zero até a última posição do vetor, comparando dois a dois. Então primeiro posição zero é essa daqui do topo. Ele vai comparar o cinco com o. Cinco com está na ordem certa? Ou seja, o menor vem antes? Não, está na ordem errada. Então o que ele vai fazer? Ele vai trocar de lugar aqui, vai colocar e cinco aqui. E agora vai comparar o cinco com o sete. Cinco com sete está na ordem certa? Sim, está na ordem certa porque sete é maior que cinco. Então, não faz nada vem pro próximo. O sete fica aqui. Sete com três está na ordem certa? Sete com três não, porque o três é menor. Então, troca de lugar. O três vem pra cá, e o sete pra cá. Sete com dois está na ordem certa? Não também. Então, o dois vem pra cá e o sete está aqui. Então, assim terminou a primeira interação daquele for mais externo. E a gente viu que o mais pesado já tá aqui na última posição, e agora a gente executa de novo, lá do começo, mas agora indo só até aqui o dois. Não precisa mais mexer com o sete. Então, pronto. Com cinco, tá na ordem certa? Sim. Então não mexe nada. Cinco com três, tá na ordem certa? Não. Então troca. Aqui vem o três, aqui vem o cinco. Cinco com dois tá na ordem certa? Não. Troca, dois cinco. E agora pronto, terminou. E o sete não mexe mais. Então, note que agora o cinco e o sete já estão ordenados. Então começa de novo lá de cima. Com três tá na ordem certa? Sim. Então não troca. Três com dois, tá na ordem certa? Não. Então troca. Dois vem pra cá e o três vem pra cá. E pronto terminou, o cinco e o sete já estão ordenados. Então, nesse ponto o três, o cinco e o sete já tão ordenados, só falta ver o com dois. Com dois tá na ordem certa? Sim, então não troca nada. E o resto também não troca nada. Terminou, nosso vetor está ordenado. Então, assim que funciona o BubbleSort. Vamos compilar aqui, executar uma vez pra ver se tá certo nosso BubbleSort. Olha, eu cometi erro de sintaxe. O que foi que eu cometi? Eu esqueci dos dois pontos, realmente, é preciso esses dois pontos aqui. Agora, a compilação, vamos ver, agora deu certo. Então, eu vou usar a mesma lista que eu tinha usado no exemplo anterior. Eu vou criar aqui ordenador Tinha usado esse exemplo na seleção direta. Vamos agora executar com a bolha. Pronto. Vamos ver a lista, se ela ficou ordenada. Ficou ordenada, tá bom. Então pelo menos para esse caso, o BubbleSort está funcionando. Vamos na próxima aula testar uns casos maiores, fazer uns testes mais interessantes. Particular, eu tô interessado saber qual o algor
