Bubble sort é um dos mais fáceis de algoritmos de classificação. Ele é chamado bubble sort , porque os valores ele vai "bolha" na sua lista para o superior (ou inferior , dependendo de como você pensa sobre isso ) . Embora seja um tipo fácil, ele não é tão eficiente como os tipos mais avançados, e só deve realmente ser utilizado para fins de aprendizagem (a menos que você sabe que sua lista é quase classificado , caso em que não é ruim ) Coisas que você precisa
Um computador que pode compilar alguma linguagem de programação ou
Lápis e papel para passar pelo exemplo
Mostrar Mais instruções
1

acho que a melhor maneira de discutir bubble sort é um exemplo . Eu vou dar uma visão geral do algoritmo, e depois vamos trabalhar com um exemplo passo-a- passo para se ter uma idéia de como ele funciona . Então, primeiro, a idéia.
2

Bubble sort é usado para classificar uma lista de itens em ordem crescente ou decrescente . Vamos supor que para este tipo que você deseja colocar a lista em ordem crescente (ou seja, 1,2,3 , etc.) O tipo trabalha passando por cima de cada elemento em sua lista e compará-lo para o próximo elemento da lista. Se o primeiro elemento é maior do que o segundo elemento , os dois são comutadas . Se o primeiro elemento é inferior ou igual à segunda , nada acontece . Depois de olhar para esse elemento , o próximo elemento é olhado , eo processo se repete .
3

Quando o tipo olhou para cada elemento , um 'pass' foi concluída. Depois de uma passagem, você tem certeza de que um número tem de estar na posição correta. Em nossa ordem crescente, o maior valor será "bolha" para o fim da lista. Infelizmente, você não sabe se o resto da lista é ordenada , por isso você tem que tomar outra passagem. No entanto, nesta passagem, você pode parar de um elemento antes do final , pois você sabe que o número já está na posição correta.
4

Bubble sort (geralmente) requer vários passes para completar . A maioria passa exigirá é igual ao número de elementos na lista menos 1 . Então se você tem 10 elementos em sua lista , pode demorar nove passes para completar o tipo . Vamos passar por um exemplo para melhor explicar
5

Vamos usar a seguinte lista não ordenada : . 6, 3, 1, 8, 2, 4

Gostaríamos que a lista para parecido com este: 1, 2 , 3, 4 , 6, 8

na primeira passagem , vamos comparar os números um de cada vez, e nós sabemos que após uma passagem que devemos ter o maior número todo o caminho para a direita, portanto, neste caso , que será de 8 . Para o nosso exemplo , o sinal ^ irá apontar para o local na lista que estamos actualmente a analisar .
6

6 , 3, 1, 8 , 2, 4

Passe 1 , Passo 1 ) Comparar a 6 e o 3 . 6 é maior que 3 , então vamos trocar them.3 , ^ 6 , 1, 8 , 2, 4

Passe 1 , Passo 2) Compare o 6 eo 1. 6 é maior que 1, então vamos trocar them.3 , 1, ^ 6, 8 , 2, 4

Passe 1 , Passo 3) Compare o 6 eo 8. 6 é menor do que ou igual a 8 , de modo que nada happens.3 , 1 , 6 , ^ 8 , 2 , 4

Passa 1 , Passo 4 ) Comparar a 8 e o 2 . 8 é maior do que 2 , de modo them.3 permuta , 1 , 6 , 2 , ^ 8 , 4

Passa 1 , Passo 5 ) Comparar a 8 e a 4 . 8 é maior do que 4, então them.3 swap, 1 , 6, 2 , 4, 8

E está feito o primeiro passo !
7

3, 1, 6, 2, 4, 8 não é uma lista ordenada , mas você pode ver , como prometido, o 8 é no final. Eu agora vou escrever o que a lista parece que após cada passagem. Tente você mesmo , e veja se o seu combina meu: Passe 2: 1, 3, 2, 4, 6, 8 (olhando melhor) Passe 3: 1, 2 , 3, 4 , 6, 8 ( feito) Passe 4: 1 , 2, 3 , 4, 6 , 8 ( ? umm ... não foram já feito) Passe 5 : 1, 2 , 3, 4 , 6, 8 ( ! ainda feito)
8

Como você pode ver , a lista foi ordenada depois de três passes , mas o bubble sort continuei. Por que isso? Bem, o algoritmo básico tipo bolha é muito burro . Ele quer ter certeza de que ele vai trabalhar no pior caso (que é uma lista que é completamente para trás como 9, 8, 7, 6, 5). Você pode adicionar uma velocidade de até fazer o seu bubble sort correr um pouco mais rápido. Em cada passagem, ter uma bandeira que será definido como verdadeiro somente se você realmente mudar dois números. Antes de fazer a próxima passagem , verifique se o sinalizador é verdadeiro ou falso . Se é verdade , você trocou dois números , e você tem que fazer uma outra passagem . Se for falsa , a sua lista é ordenada , e você pode ser feito. No nosso exemplo, mesmo que a lista foi ordenada após 3 passes , nós ainda precisamos fazer uma quarta passagem porque fizemos uma troca na 3 ª passagem.
9

Agora você sabe como fazer um bubble sort . Deixe comentários com qualquer dúvida que possa ter. Obrigado por ler !