[Powered by Google Translate] [Sorte de burbulla]
[Jackson Steinkamp Universidade de Harvard]
[Esta é CS50. CS50TV]
Ordenar burbulla é un exemplo dun algoritmo de ordenación -
é dicir, un proceso para a clasificación dun conxunto de elementos
orde crecente ou decrecente.
Por exemplo, se quere clasificar un array que contén os números
[3, 5, 2, 9], unha implementación correcta de Bubble Sort volvería
array ordenado [2, 3, 5, 9], en orde crecente.
Agora, eu vou explicar en pseudocódigo como o algoritmo funciona.
>> Imos dicir que estamos ordenar unha lista de 5 números enteiros - 3, 2, 9, 6 e 5.
O algoritmo comeza por mirar para os dous primeiros elementos, 3 e 2,
e comprobar que eles están fóra de orde en relación ao outro.
Son - 3 é maior que 2.
Para estar en orde ascendente, que debe ser o contrario.
Entón, nós troca-los.
Agora, a lista fica así: [2, 3, 9, 6, 5].
>> A continuación, miramos para os segundo e terceiro elementos, 3 e 9.
Eles están na orde correcta en relación ao outro.
É dicir, 3 é inferior a 9 de modo que o algoritmo non troca-las.
A continuación, miramos para 9 e 6. Eles están fóra de orde.
>> Entón, necesitamos trocalos, porque 9 é maior que 6.
Por fin, ollar para os últimos dous números enteiros, 9 e 5.
Eles están fóra de orde, entón eles deben ser trocados.
Tras a primeira pasaxe completa a través da lista,
parece que esta: [2, 3, 6, 5, 9].
Non é malo. É case clasificados.
Pero necesitamos percorrer a lista de novo para obtelo completamente clasificados.
Dous é menor que 3, de xeito que non troca-los.
>> Tres é menor que 6, de modo que non troca-los.
Seis é maior que 5. Trocamos.
Seis é menor que 9. Non cambiar.
Tras a segunda pasaxe, parece que este: [2, 3, 5, 6, 9]. Perfecto.
Agora, imos escribir en pseudocódigo.
Basicamente, para cada elemento da lista, temos que mirar para el
eo elemento directamente á súa dereita.
Se eles están fóra de orde en relación ao outro - é dicir, o elemento do lado esquerdo
é maior que o da dereita - debemos cambiar os dous elementos.
>> Facemos isto para cada elemento da lista, e nós fixemos unha pasaxe.
Agora só temos que facer as veces de paso a través suficientes para asegurar a lista
é totalmente, debidamente clasificados.
Pero cantas veces temos que pasar a lista para
garantir que estamos a facer?
Ben, o peor escenario é se temos unha lista completamente para atrás.
A continuación, el recibe un número de repasses igual ao número
de elementos n-1.
Se iso non ten sentido intuitivamente, pense en un caso sinxelo - unha lista [2, 1].
>> Isto vai levar un paso para clasificar correctamente.
[3, 2, 1] - O peor caso é que, con 3 elementos ordenados cara atrás,
que vai levar 2 iterações para clasificar.
Despois dunha iteração, é [2, 1, 3].
Os ingresos segundo a matriz clasificada [1, 2, 3].
Entón vostede sabe que non ten que ir a través da matriz, en xeral,
máis que n-1 veces, onde n é o número de elementos na matriz.
É chamado Bubble Sort porque as maiores elementos tenden a "burbulla-up '
a dereita moi rapidamente.
De feito, este algoritmo ten un comportamento moi interesante.
>> Despois de iterações m través de toda a matriz,
os elementos máis á dereita m son garantir
para ser clasificado no seu lugar correcto.
Se queres ver iso por si mesmo,
podemos probalo nunha lista completamente para atrás [9, 6, 5, 3, 2].
Despois dunha pasaxe pola lista enteira,
[Son da escritura]
[6, 9, 5, 3, 2] [6, 5, 9, 3, 2] [6, 5, 3, 9, 2] [6, 5, 3, 2, 9]
o elemento máis á dereita 9 está no seu debido lugar.
Tras a segunda pasaxe, a 6 terá 'abrollou a' para o
lugar máis á dereita segundo.
Os dous elementos á dereita - 6 e 9 - estarán nos seus lugares correctos
tras os dous primeiros repasses.
>> Entón, como podemos usar isto para optimizar o algoritmo?
Así, tras unha iteração través da matriz
nós realmente non precisa comprobar o elemento máis á dereita
porque sabemos que está clasificado.
Despois de dúas iterações, sabemos con certeza que os dous elementos máis á dereita están no lugar.
Polo tanto, en xeral, tras k iterações a través de todo o conxunto,
comprobando os elementos últimas k é redundante xa que sabemos
eles están no lugar correcto xa.
>> Entón, se está clasificando un array de n elementos,
na primeira iteração - ten que resolver todos os elementos - o primeiro n-0.
Na segunda iteração, ten que mirar para todos os elementos, pero a última -
o primeiro n-1.
Outra optimización pode ser o de comprobar a lista xa está clasificado
despois de cada iteração.
Se xa clasificados, non precisamos facer algunha iterações
a través da lista.
Como podemos facer iso?
Ben, se non facemos calquera cambio nunha pasaxe da lista,
está claro que a lista xa estaba clasificado porque non cambiar nada.
Entón, nós definitivamente non ten a sorte de novo.
>> Talvez podes iniciar unha variable bandeira chamada "non clasificados" para
false e cambia-lo para certo se ten que cambiar todos os elementos sobre
unha iteração través da matriz.
Ou mesmo, facer un contador para contar cantos swaps fai
en calquera dada iteração.
Ao final de cada iteração, se non cambiar calquera dos elementos,
vostede sabe que a lista xa está clasificado e está feito.
Ordenar burbulla, como algoritmos de ordenación outros, pode ser
tweaked para traballar a todos os elementos que teñen un método de ordenación.
>> É dicir, dados dous elementos que ten unha forma de dicir o primeiro
é maior que, igual a ou menor que o segundo.
Por exemplo, pode clasificar as letras do alfabeto, dicindo
que a <b, b <c, etc
Ou pode clasificar días da semana onde o domingo e menos de luns
que é inferior a terceira.
>> Ordenar burbulla é de ningunha maneira un algoritmo de ordenación moi eficiente ou rápido.
Seu tempo de execución do peor caso é Big O de n ²
porque ten que facer n iterações través dunha lista
verificación de todos os n elementos cada paso, nxn = n ².
Este tempo de execución significa que, como o número de elementos que está clasificando aumenta,
o tempo de execución aumenta de forma cuadrática.
>> Pero se a eficiencia non é unha gran preocupación do seu programa
ou se está só a clasificación de un pequeno número de elementos,
podes atopar Bubble Sort útil porque
é un dos máis simple algoritmos de ordenación de entender
e codificar.
É tamén unha boa forma de comezar a experiencia coa tradución dun teórico
algoritmo de código de funcionamento real.
Ben, iso é unha especie de burbulla para ti. Grazas por asistir.
CS50.TV