O que é e COMO FUNCIONA o BubbleSort (passo-a-passo)

nesse vídeo eu quero te falar sobre o Bubble sorte um algoritmo clássico de ordenação um dos mais fáceis de entender pelo menos nessa categoria mas também infelizmente um dos menos eficientes é importante que você saiba Bubble sorte é tão Popular mas tão Popular que se você não conhece ou não consegue explicar como ele funciona fica difícil convencer alguém que você sabe algoritmos Mas vamos lá o que que vem a ser um algoritmo de ordenação o algoritmo de ordenação Recebe como entrada uma lista com elementos potencialmente ordenáveis a partir de um determinado critério e produz uma

lista onde esses elementos aparecem na ordem determinada por esse critério simples assim uma boa sorte participa de um conjunto especial de algoritmos nessa categoria ele tem atuação local que que significa significa que ele não produz necessariamente uma nova lista ele consegue alterar realmente a lista que ele recebe como entrada entendido muito bem agora que já sabemos o que o Bubble Swatch é é importante entender como ele funciona e para te explicar isso eu quero recorrer a um exemplo bem simples simplesinho mesmo uma lista somente com cinco posições cinco números colocados fora de ordem os valores

são 7 5 10 6 e 8 o objetivo é colocar essa lista em ordem numérica crescente e utilizar para isso O Bubble sorte para realizar essa ordenação Bom vamos lá o primeiro passo recomendado pelo algoritmo é comparar os valores na primeira e segunda posições íntice 0 e 1 valores 7 e 5 7 é maior que 5 Sim nesse caso a recomendação do babosat é fazer um Swap ou seja trocar os valores de posição colocar o valor que estava na segunda posição na primeira e o da primeira na segunda dessa forma o que antes 7 e

5 agora é 5 e 7 pronto nada agora avançamos vamos continuar na lista comparamos os elementos na segunda e terceira posições incis 1 e 2 respectivamente valores atualizados 7 e 10 7 é maior do que 10 não então deixa como está avança compara os elementos na terceira e quarta posições índice 2 e 3 valores 10 e 6 10 é maior do que 6 sim 10 é maior do que seis nesse caso suap Troca os valores de posição e pronto agora ficou 6 e 10 e avança compara Então os valores na quarta e quinta posições três

e quatro são os índices valores 10 e 8 10 é maior do que 8 sim beleza maior que 8 você já sabe Swap trocamos os valores de posição e pronto a nossa lista está ordenada não ela não tá ordenada Mas ela está mais ordenada e nós também sabemos que o valor na última posição é o maior da lista eles subiu como uma bolha olha só é daí que vem a inspiração para o nome do algoritmo outra coisa importante que eu quero que você Observe é que o que nós fizemos aqui foi um loop nós percorremos

toda a lista se a lista fosse maior nós continuaríamos fazendo essas comparações simples assim mas como você tá vendo a lista ainda não está ordenada nós precisamos fazer algo mais vamos lá esse algo a mais é Mais do Mesmo que precisamos fazer ele retornar ao início da lista e recomeçar o processo só que dessa vez ignorando o último elementalista que já está na posição certa então vamos lá não deixa como está avança 76 7 Mark 6 sim então suap pronto avança E aí temos finalmente 7 e 8 7 é maior que 8 não não é

pronto terminamos a lista o 8 agora é com certeza o segundo valor mais alto e ele já tá na posição certa na verdade se você observar a lista você vai perceber que a lista já está em ordem numérica crescente mas o Bubble sorte ainda não sabe disso por isso o ideal seria começar de novo processo lá pelo começo mas verificando dessa vez se nesse nesse loop se faz alguma modificação quando modificação nenhuma acontece é indicativo de que a lista já está na ordem correta tudo pronto pode parar Boa sorte e pronto É só isso é

assim que o sorte funciona e esse é o código dele muito muito facinho mesmo pena mais uma vez que ele não é tão eficiente Mas vamos lá o que quer dizer com isso primeiro vamos analisar o melhor caso quando o Bubble SWAT encontra uma lista que já está ordenada Ele simplesmente precisa percorrer essa lista para validar isso nesse caso ele vai precisar de n Passos onde a n corresponde ao tamanho da lista que tá sendo analisada mas no caso médio e no pior caso se sabe que o número de passos que o bobosote executa é

quadrado é n ao quadrado mais tarde eu vou te explicar como se chega nessa conclusão Tá mas por enquanto só aceita isso ele ao quadrado tá muito longe de n log de n que até hoje é o melhor resultado que se consegue atingir com algoritmos de ordenação Pronto agora você já sabe o que é o Bubble SWAT E também como ele funciona e também o quanto eficiente ele é ou pode ser no melhor caso Muito bom até a próxima