>> [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.