>> [REPRODUCCIÓN DE MÚSICA]
DOUG LLOYD: Muy bien, así ordenamiento de burbuja es un algoritmo
se puede utilizar para ordenar un conjunto de elementos.
Echemos un vistazo a cómo funciona.
>> Así que la idea básica detrás ordenamiento de burbuja es esto.
Generalmente Queremos avanzar más alta elementos valorados generalmente a la derecha,
y bajar elementos valorados generalmente a la izquierda, como era de esperar.
Queremos que las cosas inferiores a estar en el principio, y las cosas más elevadas
a estar en el extremo.
>> Cómo hacemos esto?
Bueno en el código de pseudocódigo, podríamos decir, vamos a
fijar un contador de canje a un valor distinto de cero.
Ya veremos qué hacemos eso en un segundo.
Y luego repetimos el siguiente proceso hasta que el contador de intercambio es 0,
o hasta que no hacemos canjes en absoluto.
>> Restablecer el contador de intercambio de 0 si no lo es ya 0.
Luego, busquen en cada par adyacente de elementos.
Si esos dos elementos son no en orden, ellos intercambiar,
y añade 1 al contador de intercambio.
Si usted está pensando en esto antes de visualizarlo,
observe que este se moverá más baja elementos valiosos a la izquierda
y más alto elementos a la derecha valorada, haciendo con eficacia lo que queremos hacer,
que es mover esos grupos de elementos en esa forma.
Vamos a visualizar cómo este podría parecer utilizando nuestra gama
que utilizamos para probar estos algoritmos.
Tenemos una gran variedad clasificar aquí de nuevo, indicado por todos los elementos
estando en rojo.
Y volví mi contador de intercambio a un valor distinto de cero.
Yo elegí arbitrariamente negativo 1-- no es 0.
Queremos repetir este proceso hasta que el contador de intercambio es de 0.
Por eso me puse mi permuta contador a algún valor distinto de cero,
porque de lo contrario la contador de intercambio sería 0.
Ni siquiera podríamos comenzar el proceso del algoritmo.
Así que de nuevo, los pasos son-- restablecer el contador de intercambio
a 0, a continuación, busque en cada lado par, y si están fuera de servicio,
intercambiarlos, y añadir 1 al mostrador de intercambio.
Así que vamos a comenzar este proceso.
Así que lo primero que hacemos es nos pusimos en el mostrador de intercambio a 0,
y luego empezar a buscar en cada par adyacente.
>> Así que primero empezar a buscar a las 5 y 2.
Vemos que están fuera de Orden y así que los swap.
Y añadimos 1 al contador de intercambio.
Así que ahora nuestro contador de intercambio es 1, y 2 y 5 han sido conmutada.
Ahora repetimos el proceso de nuevo.
>> Nos fijamos en el siguiente par adyacente, 5 y 1-- están también fuera de orden,
así que los swap y añadimos 1 al contador de intercambio.
Entonces nos fijamos en 5 y 3.
Ellos están fuera de servicio, por lo que intercambian ellos y añadimos 1 al contador de intercambio.
Entonces nos fijamos en 5 y 6.
Están en orden, así que en realidad no necesitará cambiar nada esta vez.
Entonces nos fijamos en 6 y 4.
Son también fuera de servicio, así que intercambian ellos y añadimos 1 al contador de intercambio.
>> Ahora note lo que ha pasado.
Hemos pasado 6 de todo el camino hasta el final.
Así que en la selección de especie, si tienes visto ese video, lo que hicimos fue
Terminamos cambiando la los elementos más pequeños de la construcción
la matriz ordenada esencialmente de izquierda a derecha, de menor a mayor.
En el caso de ordenamiento de burbuja, si somos siguiendo este algoritmo en particular,
estamos en realidad va a ser la construcción la matriz ordenada de derecha
a izquierda, de mayor a menor.
Hemos burbujeó eficazmente 6, la valor más grande, todo el camino hasta el final.
>> Y así podemos ahora declarar que eso se solucionó,
y en el futuro iterations-- pasando por la matriz nuevo--
no tenemos que considerar 6 más.
Sólo tenemos que considerar los elementos sin clasificar
cuando estamos viendo pares adyacentes.
Así que hemos terminado un solo pasar a través de ordenamiento de burbuja.
Así que ahora volvemos a la pregunta, repetir hasta que el contador de intercambio es 0.
Bueno el contador de intercambio es 4, por lo que vamos
seguir repitiendo este proceso de nuevo.
>> Vamos a cero el contador de intercambio a 0, y buscar en cada par adyacente.
Así que empezamos con 2 y 1-- son fuera de servicio, por lo que los intercambiamos
y sumamos 1 al contador de intercambio.
2 y 3, están en orden.
No necesitamos hacer nada.
3 y 5 son en orden.
No necesitamos hacer nada allí.
>> 5 y 4, están fuera de orden, por lo que
necesario para intercambiarlas y añadir 1 al contador de intercambio.
Y ahora nos hemos movido 5, el siguiente elemento más grande,
hasta el final de la porción sin clasificar.
Así que ahora podemos llamar a eso parte de la porción ordenados.
>> Ahora usted está buscando en el pantalla y probablemente puede decir,
al igual que yo, que la matriz se clasifica en este momento.
Pero no podemos probar que todavía.
No tenemos una garantía que está ordenada.
Pero aquí es donde el canje contador que va a entrar en juego.
>> Así que hemos completado un pase.
El contador de intercambio es de 2.
Así que vamos a repetir este proceso de nuevo,
repetir hasta que el contador de intercambio es 0.
Restablecer el contador de intercambio a 0.
Así que vamos a restablecerla.
>> Ahora mira a cada par adyacente.
Ese es el fin, 1 y 2.
2 y 3 son en orden.
3 y 4 son en orden.
Así que en este punto, notamos que hemos completado buscando en cada par adyacente,
pero el contador de intercambio sigue siendo 0.
>> Si nosotros no tenemos que cambiar cualquier elemento, entonces
debe estar en orden, por virtud de este proceso.
Y así una eficiencia de clases, que los científicos de la computación nos encanta,
está ahora podemos Declaramos toda la matriz debe
ser resuelto, porque no hicimos tener que cambiar ningún elemento.
Eso es bastante agradable.
>> ¿Cuál es el peor de los casos escenario con la burbuja del tipo?
En el peor de los casos la matriz es con el fin completamente inversa,
y así tenemos que la burbuja de cada de los grandes elementos de todo
el camino a través de la matriz.
Y efectivamente tenemos también burbuja de todos los pequeños elementos de regreso
todo el camino a través de la matriz, también.
Así cada uno de los n elementos tiene que mover a través de todos los otros elementos n.
Así que ese es el peor de los casos.
En el mejor de los casos escenario sin embargo, esto es
ligeramente diferente de ordenación por selección.
La matriz es ya ordenados cuando vamos en.
Nosotros no tenemos que hacer ninguna swaps en la primera pasada.
Así que puede ser que tengamos que mirar por lo menos elementos, ¿verdad?
No tenemos que repetir este procesar un número de veces.
>> ¿Entonces que significa eso?
¿Cuál es el peor de los casos de ordenamiento de burbuja, y lo que es
el mejor de los casos para la ordenación de burbuja?
¿Sabía usted adivina esto?
En el peor de los casos usted tiene que repetir a través de todos los n elementos n veces.
Así que el peor de los casos es N al cuadrado.
>> Si la matriz es perfectamente ordenada, sin embargo, sólo se
hay que mirar en cada de los elementos de una vez.
Y si el contador de intercambio sigue siendo 0, se puede decir que esta serie está ordenada.
Y así, en el mejor de los casos, se trata de en realidad mejor que la selección
sort-- es el omega de n.
>> Soy Doug Lloyd.
Esto es CS50.