Cómo hacer una especie de burbuja

Ordenamiento de burbuja es uno de los algoritmos de ordenación más fáciles. Se llama ordenamiento de burbuja porque los Valora la "burbuja" en la lista de la parte superior (o inferior dependiendo de la forma de pensar de la misma). Si bien es una especie fácil, no es tan eficiente como las clases más avanzadas, y debe solo ser usado para los propósitos de aprendizaje (a menos que usted sabe que su lista es casi ordenadas, en cuyo caso no es malo)

Instrucciones

1 Creo que la mejor manera de discutir la ordenación 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 darle una idea de cómo funciona. Así que, primero, la idea.

2 Ordenamiento de burbuja se utiliza para ordenar una lista de elementos en orden ascendente o descendente. Asumamos por este tipo que usted quiere poner la lista en orden ascendente (es decir, 1,2,3, etc.). El tipo trabaja pasando 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 están conmutados. Si el primer elemento es menor que o igual que el segundo, no pasa nada. Después de ver este elemento, el elemento siguiente se mira, y el proceso se repite.

3 Cuando la clase ha mirado cada elemento, un 'pase' ha completado. 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 "burbuja" al final de la lista. Por desgracia, no sabe si el resto de la lista está ordenada, por lo que tiene que tomar otro pase. Sin embargo, en este paso, puede detener uno de los elementos antes del final ya que usted sabe que el número ya está en la posición correcta.

4 Ordenamiento de burbuja (por lo general) requiere varias pasadas para completar. El mayor número de pases que se requerirá 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 través de un ejemplo para explicar mejor.

5 Vamos a utilizar la siguiente lista no clasificada:
6, 3, 1, 8, 2, 4

Nos gustaría que la lista para tener este aspecto:
1, 2, 3, 4, 6, 8

En el primer paso, vamos a comparar los números uno a la vez, y sabemos que después de una pasada deberíamos tener el mayor número hasta el final a la derecha, por lo que en este caso, que habrá 8. Para nuestro ejemplo, el signo ^ apuntará al lugar de la lista que estamos examinando.

6 6, 3, 1, 8, 2, 4

Pase 1, Etapa 1) Comparar el 6 y el 3. 6 es mayor que 3, lo que vamos a intercambiarlas.
3, ^ 6, 1, 8, 2, 4

Pase 1, Paso 2) Comparar el 6 y el 1. 6 es mayor que 1, lo que vamos a intercambiarlas.
3, 1, ^ 6, 8, 2, 4

Pase 1, Etapa 3) Compare el 6 y el 8. 6 es menor o igual a 8, por lo que no pasa nada.
3, 1, 6, 8 ^, 2, 4

Pase 1, Paso 4) Comparar el 8 y el 2. 8 es mayor que 2, por lo intercambiarlas.
3, 1, 6, 2, 8 ^, 4

Pase 1, Paso 5) Comparar el 8 y el 4. 8 es mayor que 4, por lo intercambiarlas.
3, 1, 6, 2, 4, 8

Y ya está el primer paso!

7 3, 1, 6, 2, 4, 8 no es una lista ordenada, pero se puede ver, como se había prometido, el 8 es en el extremo. Ahora voy a escribir lo que la lista se ve como después de cada pasada. Inténtelo usted mismo, y ver si el suyo partidos de minas:
Pase 2: 1, 3, 2, 4, 6, 8 (mirando mejor)
Pase 3: 1, 2, 3, 4, 6, 8 (hecho)
Pase 4: 1, 2, 3, 4, 6, 8 (umm ... no se que ya hecho?)
Pase 5: 1, 2, 3, 4, 6, 8 (todavía hecho!)

8 Como se puede ver, la lista se solucionó después de 3 pases, pero el ordenamiento de burbuja siguió su camino. ¿Porqué es eso? Pues bien, el algoritmo básico de ordenamiento de burbuja es bastante tonto. Se quiere asegurarse de que va a trabajar en el peor de los casos (que es una lista que es completamente hacia atrás como 9, 8, 7, 6, 5). Puede añadir una velocidad hasta que su ordenamiento de burbuja correr un poco más rápido. En cada pase, tener una bandera que consigue establece a true sólo si realmente cambia dos números. Antes de hacer la siguiente pasada, comprobar para ver si la bandera es verdadera o falsa. Si bien es cierto, que intercambian dos números, y hay que hacer otra pasada. Si es falsa, se ordena su lista, y usted puede hacer. En nuestro ejemplo, a pesar de que la lista se solucionó después de 3 pases, tendríamos todavía necesita para hacer un pase cuarto porque hicimos un canje en el 3er pase.

9 Ahora usted sabe cómo hacer una especie de burbuja. Dejar comentarios con cualquier pregunta que pueda tener. ¡Gracias por leer!

Consejos y advertencias

• Si usted está tratando de poner en práctica la ordenación de burbuja en un lenguaje de programación, y tiene problemas, un lápiz y papel pueden ayudarle a visualizar lo que su algoritmo está tratando de hacer
• Recuerde, la ordenación de burbuja no es una especie muy eficiente. Así que si usted necesita para ordenar una lista enorme, usted debe buscar a algunos otros métodos.