[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 <b, b <c, etc
Ou você pode classificar dias da semana onde o Domingo é menos de segunda-feira
que é inferior a terça.
>> Ordenar bolha é de nenhuma maneira um algoritmo de ordenação muito eficiente ou rápido.
Seu tempo de execução do pior caso é Big O de n ²
porque você tem que fazer n iterações através de uma lista
verificação de todos os n elementos cada passagem, nxn = n ².
Este tempo de execução significa que, como o número de elementos que você está classificando aumenta,
o tempo de execução aumenta de forma quadrática.
>> Mas se a eficiência não é uma grande preocupação de seu programa
ou se você está apenas a classificação de um pequeno número de elementos,
você pode encontrar Bubble Sort útil porque
é um dos mais simples algoritmos de ordenação de entender
e codificar.
É também uma ótima maneira de começar a experiência com a tradução de um teórico
algoritmo em código de funcionamento real.
Bem, isso é uma espécie de bolha para você. Obrigado por assistir.
CS50.TV