[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