Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [BUBBLE SORT]
[JACKSON Steinkamp HARVARD UNIVERSITY]
[ESTO ES CS50. CS50TV]
Ordenar burbuja es un ejemplo de un algoritmo de clasificación -
es decir, un procedimiento para la clasificación de un conjunto de elementos en
ascendente o descendente.
Por ejemplo, si desea ordenar una matriz que consiste en los números
[3, 5, 2, 9], una implementación correcta de Bubble Sort devolvería el
matriz ordenada [2, 3, 5, 9], en orden ascendente.
Ahora, voy a explicar en pseudocódigo cómo funciona el algoritmo.
>> Digamos que estamos ordenar una lista de 5 números enteros - 3, 2, 9, 6 y 5.
El algoritmo se observa, en los dos primeros elementos, 3 y 2,
y comprobar si están fuera de orden uno respecto al otro.
Ellos son - 3 es mayor que 2.
Para estar en orden ascendente, que debe ser al revés.
Así que intercambiarlas.
Ahora la lista es la siguiente: [2, 3, 9, 6, 5].
>> A continuación, nos fijamos en los elementos segundo y tercero, 3 y 9.
Están en el orden correcto con relación a otra.
Esto es, 3 es menor que 9 por lo que el algoritmo no intercambiarlos.
A continuación, vemos a las 9 y 6. Están fuera de orden.
>> Por lo tanto, tenemos que cambiar porque 9 es mayor que 6.
Por último, nos fijamos en los últimos dos números enteros, 9 y 5.
Están fuera de servicio, por lo que debe ser cambiado.
Después de la primera pasada completa a través de la lista,
se ve así: [2, 3, 6, 5, 9].
No está mal. Es casi ordenados.
Pero tenemos que repasar la lista de nuevo para conseguir totalmente ordenados.
Dos es menor que 3, por lo que no intercambiarlas.
>> Tres es inferior a 6, por lo que no intercambiarlas.
Seis es mayor que 5. Nos cambiado.
Seis es menor que 9. No intercambiar.
Después de la segunda pasada a través, que se ve así: [2, 3, 5, 6, 9]. Perfecto.
Ahora, vamos a escribir en pseudocódigo.
Básicamente, para cada elemento de la lista, tenemos que mirarlo
y el elemento directamente a su derecha.
Si están fuera de orden con relación a otra - es decir, si el elemento de la izquierda
es mayor que el de la derecha - que deben intercambiar los dos elementos.
>> Hacemos esto para cada elemento de la lista, y hemos hecho un paso adelante.
Ahora sólo tenemos que ver los tiempos de paso a través suficientes para garantizar la lista
está completamente, correctamente ordenados.
Pero ¿cuántas veces tenemos que pasar por la lista para
garantizar que hemos terminado?
Pues bien, el peor escenario es que si tenemos una lista completamente al revés.
Luego se toma una serie de pasar-throughs igual al número
elementos de n-1.
Si esto no tiene sentido intuitivamente, pensar en un caso simple - la lista [2, 1].
>> Esto va a tomar un paso a través de ordenar correctamente.
[3, 2, 1] - El peor caso es que con 3 elementos ordenados hacia atrás,
que va a tomar 2 iteraciones para ordenar.
Después de una iteración, es [2, 1, 3].
Los rendimientos segundos la matriz ordenada [1, 2, 3].
Así que ya sabes que nunca tenga que ir a través de la matriz, en general,
más de n-1 veces, donde n es el número de elementos en la matriz.
Se llama Bubble Sort porque los elementos más grandes tienden a "burbuja-up '
a la derecha con bastante rapidez.
De hecho, este algoritmo tiene un comportamiento muy interesante.
>> Después de m iteraciones a través de toda la matriz,
el de la derecha m elementos están garantizados
para ser ordenados en su lugar correcto.
Si quieres ver esto por ti mismo,
podemos probarlo en una lista completamente al revés [9, 6, 5, 3, 2].
Después de una pasada a través de toda la lista,
[Sonido de la escritura]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
el elemento más a la derecha 9 está en su lugar apropiado.
Después de la segunda transferencia, el 6 tendrá 'burbujea hacia arriba "a la
lugar más a la derecha segundo.
Los dos elementos de la derecha - 6 y 9 - estarán en sus lugares correctos
después de los dos primeros pases-through.
>> Así que, ¿cómo podemos usar esto para optimizar el algoritmo?
Bueno, después de una iteración a través de la matriz
que en realidad no necesita comprobar el elemento más a la derecha
porque sabemos que está ordenada.
Después de dos iteraciones, sabemos a ciencia cierta el de la derecha dos elementos están en su lugar.
Así que, en general, después de k iteraciones a través de toda la gama,
la comprobación de los elementos k últimos es redundante, ya que sabemos
que están en el lugar correcto ya.
>> Así que si estás ordenar un arreglo de n elementos,
en la primera iteración - usted tiene que clasificar todos los elementos - la primera n-0.
En la segunda iteración, usted tiene que mirar todos los elementos excepto el último -
la primera n-1.
Otra optimización podría ser la de comprobar si la lista ya está ordenada
después de cada iteración.
Si ya está clasificado, no es necesario realizar más iteraciones cualquier
a través de la lista.
¿Cómo podemos hacer esto?
Bueno, si no hacemos ningún swaps en un paso a través de la lista,
está claro que la lista se ordenan ya porque no cambiar nada.
Así que definitivamente no tiene que ordenar de nuevo.
>> Tal vez usted podría inicializar una variable de indicador llamado "Sin ordenar 'a
false y cambiarlo a true si usted tiene que cambiar algún elemento de
una iteración a través de la matriz.
O igualmente, hacer un contador para contar el número de intercambios que haya realizado
en cualquier iteración dada.
Al final de una iteración, si no cambiar cualquiera de los elementos,
Conoce la lista ya está ordenada y ya está.
Bubble Sort, al igual que otros algoritmos de ordenación, puede ser
ajustado para trabajar por todos los elementos que tienen un método de ordenación.
>> Es decir, dados dos elementos que tienen una manera de decir si la primera
es mayor que, igual a, o menor que el segundo.
Por ejemplo, puede ordenar las letras del alfabeto diciendo
que a Ordenar burbuja es de ninguna manera un algoritmo de clasificación muy eficiente o rápida.
Su peor tiempo de ejecución es de Big O ² n
porque hay que hacer n iteraciones a través de una lista
la comprobación de todos los elementos del n cada transferencia, nxn = n ².
Esto significa que el tiempo de ejecución como el número de elementos que estés clasificación aumenta,
el tiempo de ejecución aumenta cuadráticamente.
>> Pero si la eficiencia no es una preocupación importante de su programa
o si sólo ordenar un pequeño número de elementos,
usted puede ser que encuentre Bubble Sort útil porque
que es uno de los más sencillos algoritmos de ordenación de entender
y para codificar.
También es una gran manera de conseguir experiencia en la traducción de una parte teórica
algoritmo en código de funcionamiento real.
Bueno, eso es Bubble Sort para usted. Gracias por su atención.
CS50.TV