[Powered by Google Translate] [Espécie de bolha] [JACKSON Steinkamp Universidade de Harvard] [Esta é CS50. CS50TV] Ordenar bolha é um exemplo de um algoritmo de ordenação - isto é, um processo para a classificação de um conjunto de elementos em ordem crescente ou decrescente. Por exemplo, se você quiser classificar um array contendo os números [3, 5, 2, 9], uma implementação correta de Bubble Sort voltaria a array ordenado [2, 3, 5, 9], em ordem crescente. Agora, eu vou explicar em pseudocódigo como o algoritmo funciona. Vamos dizer que estamos ordenar uma lista de 5 números inteiros - 3, 2, 9, 6 e 5. O algoritmo começa por olhar para os dois primeiros elementos, 3 e 2, e verificar se eles estão fora de ordem em relação ao outro. Eles são - 3 é maior do que 2. Para estar em ordem ascendente, que deve ser o contrário. Então, nós trocá-los. Agora, a lista fica assim: [2, 3, 9, 6, 5]. Em seguida, olhamos para os segundo e terceiro elementos, 3 e 9. Eles estão na ordem correta em relação ao outro. Isto é, 3 é inferior a 9 de modo que o algoritmo não trocá-las. Em seguida, olhamos para 9 e 6. Eles estão fora de ordem. Então, precisamos trocá-los, porque 9 é maior que 6. Por fim, olhar para os últimos dois números inteiros, 9 e 5. Eles estão fora de ordem, então eles devem ser trocados. Após a primeira passagem completa através da lista, parece que esta: [2, 3, 6, 5, 9]. Não é mau. É quase classificados. Mas precisamos percorrer a lista novamente para obtê-lo completamente classificados. Dois é menor que 3, de modo que não trocá-los. Três é menor que 6, de modo que não trocá-los. Seis é maior do que 5. Trocamos. Seis é menor que 9. Nós não trocar. Após a segunda passagem, parece que este: [2, 3, 5, 6, 9]. Perfeito. Agora, vamos escrever em pseudocódigo. Basicamente, para cada elemento da lista, temos de olhar para ele eo elemento diretamente à sua direita. Se eles estão fora de ordem em relação ao outro - isto é, se o elemento do lado esquerdo é maior que o da direita - devemos trocar os dois elementos. Fazemos isso para cada elemento da lista, e nós fizemos uma passagem. Agora só temos de fazer as vezes de passagem através suficientes para assegurar a lista é totalmente, devidamente classificados. Mas quantas vezes temos que passar a lista para garantir que estamos a fazer? Bem, o pior cenário é se temos uma lista completamente para trás. Em seguida, ele recebe um número de repasses igual ao número de elementos n-1. Se isso não faz sentido intuitivamente, pense em um caso simples - a lista [2, 1]. Isso vai levar uma passagem para classificar corretamente. [3, 2, 1] - O pior caso é que, com 3 elementos ordenados para trás, que vai levar 2 iterações para classificar. Depois de uma iteração, é [2, 1, 3]. Os rendimentos segundo a matriz classificada [1, 2, 3]. Então você sabe que nunca tem que ir através da matriz, em geral, mais do que n-1 vezes, onde n é o número de elementos na matriz. É chamado Bubble Sort porque as maiores elementos tendem a "bolha-up ' para a direita muito rapidamente. De fato, este algoritmo tem um comportamento muito interessante. Depois de iterações m através de toda a matriz, os elementos mais à direita m são garantidos para ser classificado em seu lugar correto. Se você quer ver isso por si mesmo, podemos experimentá-lo em uma lista completamente para trás [9, 6, 5, 3, 2]. Depois de uma passagem pela lista inteira, [Som da escrita] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] o elemento mais à direita 9 está em seu devido lugar. Após a segunda passagem, a 6 terá 'borbulhou-se' para o lugar mais à direita segundo. Os dois elementos à direita - 6 e 9 - estarão em seus lugares corretos após os dois primeiros repasses. Então, como podemos usar isso para otimizar o algoritmo? Assim, após uma iteração através da matriz nós realmente não precisa verificar o elemento mais à direita porque sabemos que está classificado. Depois de duas iterações, sabemos com certeza que os dois elementos mais à direita estão no lugar. Portanto, em geral, após k iterações através de todo o conjunto, verificando os elementos últimas k é redundante uma vez que sabemos eles estão no local correto já. Então, se você está classificando um array de n elementos, na primeira iteração - você tem de resolver todos os elementos - o primeiro n-0. Na segunda iteração, você tem que olhar para todos os elementos, mas a última - o primeiro n-1. Outra otimização pode ser o de verificar se a lista já está classificado após cada iteração. Se já classificados, não precisamos fazer mais alguma iterações através da lista. Como podemos fazer isso? Bem, se não fazemos qualquer troca em uma passagem da lista, é claro que a lista já estava classificado porque não trocar nada. Então, nós definitivamente não tem a sorte de novo. Talvez você possa inicializar uma variável bandeira chamada "não classificados" para false e alterá-lo para verdadeiro se você tem que trocar todos os elementos sobre uma iteração através da matriz. Ou do mesmo modo, fazer um contador para contar quantos swaps você faz em qualquer dada iteração. No fim de cada iteração, se não trocar qualquer um dos elementos, você sabe que a lista já está classificado e está feito. Ordenar bolha, como algoritmos de ordenação outros, pode ser tweaked para trabalhar para todos os elementos que têm um método de ordenação. Isto é, dados dois elementos que você tem uma maneira de dizer se o primeiro é maior do que, igual a ou menor do que o segundo. Por exemplo, você pode classificar as letras do alfabeto, dizendo que a