Entender el algoritmo de ordenación de burbujas es vital para quienes trabajan en programación informática o están interesados en aprender sobre él. La ordenación por burbujas es un algoritmo de ordenación simple que puede servir como una buena introducción a algoritmos de ordenación más complicados como la ordenación rápida, la ordenación por cubos y la ordenación por fusión.
En este artículo, definimos la ordenación por burbujas, discutimos por qué puedes necesitar usarla, damos instrucciones paso a paso sobre cómo hacer la ordenación por burbujas y cubrimos algunas preguntas frecuentes.
Habilidades del programador informático: Definición y ejemplos
¿Qué es la clasificación de burbujas?
Una lista se ordena utilizando el algoritmo de ordenación de burbujas, comparando los elementos adyacentes e intercambiándolos si están en el orden incorrecto. El algoritmo sigue haciendo pasadas por la lista hasta que todos los elementos están en el orden deseado.
El algoritmo de ordenación por burbujas es un tipo de ordenación por comparación y debe su nombre a la forma en que los elementos más grandes del conjunto «burbujean» hacia la parte superior del conjunto de datos. Sin embargo, como la ordenación por burbujas es un proceso simple, puede no ser eficiente para ordenar grandes conjuntos de datos.
Relacionado: Las 45 mejores preguntas de la entrevista sobre programación (con ejemplos de respuestas)
¿Por qué puede necesitar la clasificación por burbujas?
La ordenación de burbujas es un algoritmo sencillo que se utiliza a menudo en entornos educativos para introducir el concepto de un algoritmo de ordenación a los estudiantes de informática. Otros usos de la ordenación por burbujas incluyen la ordenación de pequeños conjuntos de datos, la ordenación de conjuntos de datos que ya están casi correctamente ordenados o la confirmación de que los elementos de un conjunto de datos existente ya aparecen en el orden correcto. En comparación con otros algoritmos de ordenación, la ordenación por burbujas puede ser más rápida a la hora de reconocer si el orden de una lista ya es correcto.
Por ejemplo, una pequeña empresa puede utilizar la ordenación por burbujas para ordenar una lista de empleados según el tiempo que llevan trabajando en la empresa. La ordenación por burbujas puede ser un medio práctico de ordenación en este escenario porque el conjunto de datos es probablemente pequeño y puede no necesitar muchas pasadas por la lista para poner los datos en el orden correcto.
Otro ejemplo puede ser un programa de campamentos de verano que quiera ordenar a los campistas por edad. Si el programa utiliza una base de datos que divide a los campistas por grupos de edad, la ordenación por burbujas puede ser un algoritmo útil para organizar a los campistas por edad dentro de su grupo.
Relacionado: Las 8 mejores carreras de informática
Cómo hacer la clasificación por burbujas
A continuación se desglosa paso a paso cómo funciona la clasificación por burbujas:
1. Empezar con una lista sin clasificar
La clasificación por burbujas comienza con un conjunto desordenado de elementos. Por ejemplo, imagine que está escribiendo un código para una aplicación y necesita ordenar el siguiente conjunto de datos en orden ascendente: 4, 3, 1, 2, 5. Como se trata de un pequeño conjunto de datos que ya está ordenado en su mayor parte, puedes decidir utilizar la ordenación por burbujas porque es un código sencillo de implementar. Después de incorporar el código, el algoritmo de ordenación por burbujas pone los números en orden comparando dos elementos a la vez.
2. Comparar los dos primeros elementos
El algoritmo comienza comparando los dos primeros elementos del conjunto. Si el primer elemento del conjunto es mayor que el segundo, los intercambia. Por ejemplo, el primer número del conjunto de datos anterior es el cuatro, que es mayor que el segundo elemento del conjunto de datos, el tres. El algoritmo intercambia estos números y el nuevo conjunto de datos se convierte en 3, 4, 1, 2, 5.
3. Evaluar el segundo y tercer elemento
A continuación, el algoritmo compara el segundo elemento de la lista con el tercero. Si el segundo elemento de la lista es mayor que el tercero, el algoritmo intercambia los números. Siguiendo con el conjunto de datos de muestra, el segundo elemento del conjunto es el número cuatro, que es mayor que el tercer elemento del conjunto, el número uno. El algoritmo intercambia estos números y el nuevo conjunto de datos pasa a ser 3, 1, 4, 2, 5.
4. Continúa con el tercer y cuarto elemento
El algoritmo continúa el patrón. A continuación, compara el tercer elemento del conjunto de datos con el cuarto elemento del conjunto de datos. En el conjunto de datos de la muestra, el tercer número es el cuatro y el cuarto es el dos. Como el cuatro es mayor que el dos, el algoritmo vuelve a intercambiar los números. Ahora, el conjunto de datos debería ser 3, 1, 2, 4, 5.
5. Completar la primera pasada y evaluar la lista
Ahora, el algoritmo compara el cuarto elemento del conjunto de datos con el quinto elemento del conjunto. En la lista de muestra, el cuarto elemento es el número cuatro y el quinto es el número cinco. Como el número cinco es mayor que el número cuatro, el algoritmo no intercambia los elementos. El conjunto sigue siendo 3, 1, 2, 4, 5, y el algoritmo completa su primera pasada. Sin embargo, como la lista sigue desordenada, el algoritmo debe completar más pases. El código indica automáticamente al algoritmo que continúe con el patrón hasta ordenar todo el conjunto.
6. Continúe haciendo pases hasta que esté completamente clasificado
El algoritmo comienza su segunda pasada. Sigue el mismo patrón de los pasos 1 a 5, comparando dos elementos del conjunto a la vez e intercambiando elementos según sea necesario. El algoritmo realiza tantas pasadas como sea necesario para colocar todos los elementos del conjunto en el orden correcto. Una vez que reconoce que el orden es correcto, se detiene sin necesidad de más datos. Como el algoritmo se detiene una vez que ha ordenado la lista, es fácil saber cuándo está completa. Cuando el algoritmo se detiene, el conjunto está listo para ser utilizado.
Relacionado: Cómo preparar una entrevista de codificación en 10 pasos
Preguntas frecuentes sobre la clasificación de burbujas
Estas son algunas de las preguntas más frecuentes sobre la clasificación de las burbujas:
¿Cuál es la mejor complejidad temporal del caso para la selección de burbujas?
Para una lista ya ordenada, la complejidad de la ordenación por burbujas es O(n ). En el mejor de los casos, la complejidad temporal es O(n ) porque tiene que recorrer cada elemento del conjunto de datos antes de confirmar que todos los elementos aparecen en el orden correcto.
¿Es la clasificación de burbujas un algoritmo estable?
La ordenación de burbujas es un algoritmo estable. Para que un algoritmo sea estable, dos objetos con claves iguales aparecen en la salida ordenada en el mismo orden en que aparecen en el conjunto de datos de entrada sin ordenar.
¿Es lenta la clasificación de las burbujas?
La clasificación por burbujas es lo suficientemente lenta como para que su uso sea poco práctico en la mayoría de las aplicaciones reales. Aunque tiene una función eficaz en el mejor de los casos, es más lento que otros algoritmos de ordenación. Por ejemplo, es dos veces más lento que la ordenación por selección y cuatro veces más lento que la ordenación por inserción. La ordenación por selección y la ordenación por inserción son comparables a la ordenación por burbujas, ya que son algoritmos de ordenación simples. Sin embargo, utilizan procesos ligeramente diferentes que pueden darles distintas ventajas para diferentes tareas de ordenación.
2. ¿Cuáles son las ventajas de la concordancia de burbuja?
La mayor ventaja que tiene la ordenación por burbujas sobre otros algoritmos de ordenación es su capacidad para detectar si una lista está ordenada de forma eficiente. En comparación con otros algoritmos de ordenación, la ordenación por burbujas puede ser más rápida a la hora de describir cuándo se ha completado la ordenación de un conjunto de datos. Además, debido a su simplicidad, la ordenación por burbujas es fácil de implementar y sólo se necesitan unas pocas líneas de código para añadirlas a su programa.
¿Es la concordancia de burbujas un algoritmo en funcionamiento?
La ordenación de burbujas es un algoritmo in situ. Un algoritmo in-place no necesita un espacio extra y produce una salida utilizando la misma memoria que contiene los datos manipulando la entrada en un solo lugar.