Un equipo que puede compilar algún lenguaje de programación o
lápiz y papel para ir a través del ejemplo
Mostrar más instrucciones
1
Creo que la mejor manera de discutir especie de burbuja es con un ejemplo . Voy a dar una visión general del algoritmo, y luego vamos a trabajar a través de un ejemplo paso a paso para que te hagas una idea de cómo funciona. Así que en primer lugar, la idea.
2
ordenamiento de burbuja se utiliza para clasificar una lista de elementos en orden ascendente o descendente . Asumamos para este tipo que se quiere poner la lista en orden (es decir, 1,2,3 , etc ) ascendente. El tipo funciona haciendo pasar sobre cada elemento de la lista y comparándolo con el siguiente elemento de la lista. Si el primer elemento es mayor que el segundo elemento , los dos se conmutan . Si el primer elemento es menor que o igual que el segundo , no pasa nada . Después de ver este elemento , el siguiente elemento se miró , y el proceso se repite.
3
Cuando el tipo se ha mirado cada elemento , una ' pass' ha terminado . Después de una pasada, que sepa con certeza que un número tiene que estar en la posición correcta. En nuestro orden ascendente, el mayor valor será "burbuja" al final de la lista . Por desgracia , no sé si el resto de la lista está ordenada , así que tienes que tomar otro paso. Sin embargo , en este paso , puede dejar un elemento antes del final ya que se sabe que el número ya está en la posición correcta.
4
ordenamiento de burbuja ( por lo general) requiere varios pasos para completar. El mayor número de pases que se necesita es igual al número de elementos en la lista menos 1. Así que si usted tiene 10 elementos en la lista, puede ser que tome 9 pases para completar el estilo. Vamos a ir a través de un ejemplo para explicar mejor
5
Usemos la siguiente lista no clasificada: . 6 , 3 , 1 , 8 , 2 , 4
Nos gustaría que la lista de Esperamos de esta manera: 1 , 2 , 3 , 4 , 6 , 8
en el primer paso , vamos a comparar los números de uno a la vez , y sabemos que después de un pase debemos tener el mayor número de todo el camino a la derecha, por lo que en este caso , que será de 8 . Para nuestro ejemplo , el signo ^ señalará el lugar en la lista que estamos examinando.
6
6 , 3 , 1 , 8 , 2 , 4
Pass 1 , Paso 1 ) Comparar el 6 y el 3. 6 es mayor que 3 , por lo que vamos a intercambiar ellos.3 , ^ 6 , 1 , 8 , 2 , 4
Paso 1 , Paso 2 ) Comparar el 6 y el 1 . 6 es mayor que 1 , por lo que vamos a intercambiar ellos.3 , 1 , ^ 6 , 8 , 2 , 4
Paso 1 , Paso 3 ) Compare la 6 y la 8 . 6 es menor o igual a 8, por lo que nada happens.3 , 1 , 6 , 8 ^ , 2 , 4
Paso 1 , Paso 4 ) Comparar el 8 y el 2 . 8 es mayor que 2 , por lo que cambiar ellos.3 , 1 , 6 , 2 , ^ 8 , 4
Paso 1 , Paso 5 ) Comparar el 8 y el 4 . 8 es mayor que 4 , por lo que intercambiar ellos.3 , 1 , 6 , 2 , 4 , 8
y ya está el primer paso !
7
3 , 1 , 6 , 2 , 4 , 8 es apenas una lista ordenada , pero se puede ver , como había prometido, el 8 es el final . Ahora voy a escribir lo que la lista parece después de cada pasada. Inténtelo usted mismo y ver si coincide con la tuya mía : Pase 2 : 1 , 3 , 2 , 4 , 6 , 8 (mirando mejor) Paso 3 : 1 , 2 , 3 , 4 , 6 , 8 (hecho ) Pass 4 : 1 , 2 , 3 , 4 , 6 , 8 ( umm ... no nos hemos hecho ya ? ) paso 5 : (¡ todavía se hace ) 1 , 2 , 3 , 4 , 6 , 8
8 < p> Como puede ver , la lista se solucionó después de 3 pases, pero la burbuja especie siguió su camino. ¿Por qué es eso? Bueno, el algoritmo básico tipo burbuja es bastante tonto . Quiere asegurarse de que va a trabajar en el peor de los casos (que es una lista que es totalmente al revés como 9 , 8 , 7 , 6 , 5 ) . Usted puede agregar una velocidad hasta que su especie de burbuja ejecutar un poco más rápido . En cada paso, tener una bandera que obtiene el valor true sólo si realmente cambia dos números. Antes de hacer el siguiente paso , compruebe si el indicador es verdadero o falso . Si bien es cierto , que intercambian dos números , y usted tiene que hacer otra pasada . Si es falso, la lista está ordenada , y usted puede hacer. En nuestro ejemplo, a pesar de que la lista se solucionó después de 3 pasos, nos quedaría por hacer un cuarto pase porque hemos hecho un intercambio en el tercero pase .
9
Ahora ya sabes cómo hacer un especie de burbuja . Dejar comentarios con cualquier pregunta que pueda tener. Gracias por leer!