- Comparadas
- Intercambiadas
- En su sitio
Ordenamiento de burbuja
El ordenamiento de burbuja recorre una lista una y otra vez, compara cada par de vecinos y los intercambia cuando el de la izquierda es mayor. Tras cada pasada, el mayor valor aún fuera de lugar ha subido hasta el final como una burbuja. Reproduce la ordenación a cualquier velocidad, o avanza de comparación en comparación, y observa los contadores de comparaciones, intercambios y pasadas. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto. Los recuadros cuentan comparaciones, intercambios y pasadas. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Elige cuántas barras hay y cómo empiezan: aleatorias, casi ordenadas, invertidas o con pocos valores distintos. O escribe tus propios números.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
- Observa cómo los recuadros cuentan comparaciones, intercambios y pasadas, y compáralos con el peor caso.
Cómo funciona el ordenamiento de burbuja
Empieza por la izquierda. Compara los dos primeros valores; si el de la izquierda es mayor, intercámbialos. Avanza un lugar a la derecha y vuelve a comparar, hasta el final de la lista. Eso es una pasada, y deja el mayor valor en el último lugar. La siguiente pasada se detiene un lugar antes. Sigue hasta que una pasada no haga intercambios, o hasta que solo quede un valor.
Contar el trabajo
Con n valores, la primera pasada hace n − 1 comparaciones, la siguiente n − 2, y así sucesivamente, así que una ordenación completa hace como máximo n(n − 1)/2 comparaciones. El número de intercambios siempre es el número de inversiones de la lista inicial: pares de valores que están en el orden equivocado. Una lista invertida tiene el máximo, n(n − 1)/2. Una lista ordenada no tiene ninguna y, con la parada anticipada, solo necesita una pasada de n − 1 comparaciones.
Preguntas frecuentes
¿Por qué se llama ordenamiento de burbuja?
Porque los valores grandes suben hacia el final de la lista como burbujas en el agua. En cada pasada, el mayor valor que aún no está en su sitio avanza paso a paso hacia la derecha hasta llegar a su lugar definitivo.
¿Cuántas comparaciones e intercambios hace el ordenamiento de burbuja?
Como máximo n(n − 1)/2 comparaciones para n valores: 45 para 10 valores, 780 para 40. Los intercambios siempre son iguales al número de inversiones de la lista inicial, desde ninguno en una lista ordenada hasta n(n − 1)/2 en una invertida.
¿Para qué sirve la parada anticipada?
Si una pasada entera no hace intercambios, todos los pares de vecinos están en orden, así que la lista está ordenada y el algoritmo puede parar. Con la parada anticipada activada, una lista ordenada necesita una sola pasada. Sin ella, el ordenamiento de burbuja siempre hace las n − 1 pasadas.
¿Se usa el ordenamiento de burbuja en la práctica?
Rara vez. Es sencillo y estable, pero de media tarda un tiempo proporcional a n². El ordenamiento por inserción hace lo mismo con menos pasos en listas pequeñas o casi ordenadas, y el ordenamiento por mezcla o el quicksort son mucho más rápidos en listas grandes.
¿Se envían mis números a algún sitio?
No. La ordenación se ejecuta en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor