[Música tocando] Doug LLOYD: Todo ben, entón bubble sort é un algoritmo pode usar para clasificar un conxunto de elementos. Imos dar un ollo a como funciona. Así, a idea básica por tras bubble sort é este. Nós xeralmente queren mover superior elementos valorados xeralmente cara á dereita, e diminuír elementos valorados en xeral á esquerda, como sería de esperar. Queremos que as cousas máis baixas para estar en o principio, e as cousas máis elevadas ser ao final. Como podemos facer isto? Ben no código pseudocódigo, poderiamos dicir, imos definir un contador de intercambio para un valor distinto de cero. A ver por que facemos isto nun segundo. E, despois, repetir o seguinte proceso ata que o contador de intercambio é 0, ou ata que non facemos swaps en todo. Reinicie o contador de intercambio para 0 se non é xa 0. A continuación, ollar para cada par adxacente de elementos. Se estes dous elementos son non en orde, troca-los, e engadir 1 ao contador de intercambio. Se está a pensar en que antes de vela, notar que este pode mover máis baixo elementos valiosos á esquerda e elementos para a dereita valorado superior, efectivamente facendo o que queremos facer, que é mover eses grupos de elementos en que xeito. Imos ver como este pode parecer a través da nosa gama que foi utilizado para probar estes algoritmos. Temos unha matriz unsorted aquí de novo, indicado por todos os elementos sendo a vermello. E eu que o meu contador de intercambio para un valor distinto de cero. Eu escollín arbitrariamente 1-- negativo non é 0. Queremos repetir este proceso ata que o contador de intercambio é 0. É por iso que eu definir a miña cambio contador para un valor distinto de cero, porque se non o contador de intercambio sería 0. Nós nin sequera comezar a proceso do algoritmo. Entón, de novo, os pasos é-- axustar o temporizador de intercambio a 0, a continuación, ollar para cada lado par, e no caso de que están fóra de orde, trocalos e engadir 1 para o contador de intercambio. Entón, imos comezar este proceso. Entón o primeiro que facemos é imos definir o contador de intercambio a 0, e, despois, comezar a ollar en cada par adxacente. Así que comezamos a mirar para 5 e 2. Vemos que están fóra de orde e para que trocalos. E nós engadimos 1 ao contador intercambio. Polo tanto, agora o noso contador de intercambio é un, e 2 e 5 foron trocados. Agora imos repetir o proceso de novo. Nós miramos para a próxima par adxacente, 5 e 1-- son tamén fóra de orde, así que trocalos e engadir 1 ao balcón intercambio. Entón, miramos para 5 e 3. Eles están fóra de orde, polo que trocar eles e nós engadimos 1 ao contador intercambio. Entón, miramos para 5 e 6. Eles están en orde, polo que, en realidade, non Debe cambiar calquera cousa neste momento. Entón, miramos para 6 e 4. Eles están fóra de orde, polo que trocar eles e nós engadimos 1 ao contador intercambio. Agora, teña en conta o que pasou. Nós movemos 6 todo o camiño ata o final. Entón, na selección tipo, se ten visto que o vídeo, o que fixemos foi acabamos cambiando a menores elementos en construción a matriz clasificada esencialmente da esquerda a dereita, menor ao maior. No caso de bubble sort, se estamos seguindo este algoritmo en particular, imos realmente a ser a construción de a matriz clasificada da dereita á esquerda, maior a menor. Temos efectivamente borbulhar 6, a O maior valor, todo o camiño ata o final. E así podemos agora declarar que é ordenada, e no futuro iterations-- pasando a matriz novamente-- non hai que considerar 6 anymore. Nós só temos que considerar os elementos sen clasificar cando nós estamos mirando para pares adxacentes. Entón, temos que rematar unha pasar por bubble sort. Entón agora imos voltar á cuestión, repetir ata que o contador de intercambio é 0. Ben, o contador de intercambio é 4, entón imos para continuar a repetir este proceso de novo. Estamos indo para axustar o temporizador de intercambio a 0, e ollar para cada par adxacente. Entón, imos comezar con dous e son 1-- fóra de orde, de xeito que trocalos e nós engadimos 1 ao contador intercambio. 2 e 3, están en orde. Non necesitamos facer nada. 3 e 5 están en orde. Non necesitamos facer nada alí. 5 e 4, están fóra de orde, e por iso, Debe trocalos e engadir 1 ao balcón intercambio. E agora nós movemo 5, o segundo elemento, para o fin da porción sen clasificar. Entón agora podemos chamar parte da porción clasificada. Agora está mirando para o pantalla e probablemente pode dicir, como pode I, que a matriz se clasifica no momento. Pero non podemos probalo aínda. Non temos unha garantía que está clasificado. Pero é aí onde o intercambio contador vai entrar en xogo. Entón, nós completados un pase. O contador de intercambio é de 2. Entón, nós estamos indo a repetir este proceso novo, repetir ata que o contador de intercambio é 0. Reinicie o contador de intercambio a 0. Entón, imos axustar-la. Agora mire para cada par adxacente. Isto é en orde, 1 e 2. 2 e 3 están en orde. 3 e 4 están en orde. Polo tanto, neste punto, observe nós completados mirando para cada par adxacente, pero o contador de intercambio que é 0. Se non temos que cambiar calquera elementos, a continuación, eles deben estar en orde, por virtude deste proceso. E así unha eficiencia de tipos, que os científicos da computación que amamos, agora podemos declarar toda a matriz debe son ordenados, porque non ter que cambiar todos os elementos. Iso é moi bo. Entón, cal é o peor caso escenario con bubble sort? No peor caso, a matriz é a fin completamente inversa, e por iso temos que burbulla cada dos grandes elementos todos a maneira a través da matriz. E nós tamén temos que efectivamente burbulla todos os pequenos elementos de volta en toda a extensión da matriz, tamén. Así, cada un dos elementos n debe moverse entre todos os outros elementos n. Entón ese é o peor escenario posible. No mellor dos casos escenario, con todo, este é lixeiramente diferente da selección de clasificación. A matriz é xa clasificadas cando imos. Non hai que facer calquera swaps sobre a primeira pasaxe. Por iso, pode ter que ollar polo menos elementos, non? Non temos que repetir este procesar un certo número de veces. Entón, o que significa isto? Entón, cal é o peor escenario para bubble sort, eo que é o mellor escenario para bubble sort? Vostede creo que iso? No peor dos casos ten que facer unha iteración en todos os elementos n veces n. Así, o peor caso é n ao cadrado. Se a matriz é perfectamente ordenada, porén, só Ten que mirar para cada os elementos dunha vez. E se o contador de intercambio que é 0, pode dicir que esta matriz é clasificada. E así, no mellor dos casos, é dicir realmente mellor que a selección sort-- é omega de n. Eu son Doug Lloyd. Este é CS50.