Bubble sort

El algoritmo de ordenación (en inglés sort) de “la burbuja” es uno de los primeros procedimientos que uno aprende sobre cómo llevar a cabo la ordenación de datos en un computador. El nombre de este algoritmo deriva de la analogía física sobre la propagación del orden de los datos, a manera de una burbuja que poco a poco va subiendo hasta la superficie de un líquido (o de un medio en el que pueda haber burbujas y éstas desplazarse en éste desde un estado de alta energía a uno de equilibrio, por aquellos puristas que puedan leer esta entrada y de inmediato piensen en decir que burbujas no sólo pueden presentarse en un medio líquido; así que, considerando todas las posibles combinaciones de estados de la materia y densidades de los materiales, es que me adelanto). El algoritmo, por ser el más simple, viene siendo la respuesta más natural que cualquier persona daría ante un problema de ordenamiento, considerando una resolución metódica y razonada al respecto.

En fin, el procedimiento del “sort de la burbuja” (Bubble sort) es bastante simple: comparar valores de datos adyacentes (en la lista, arreglo o cualquiera que fuere la estructura de datos que contenga los elementos a ordenar) y proceder con su intercambio si éstos se encuentran fuera de orden. En el caso de números, por su valor cardinal y la relación “mayor” o “menor” que por dicho valor se establece entre ellos (y si se preguntan el porqué de esta relación debemos meternos a la teoría de los números, tema que debe ser desarrollado en otro post). Este proceso de intercambio se inicia con el primero y segundo valor, se continúa con el segundo y tercero, luego tercero y cuarto, y así hasta llegar a comparar el penúltimo y último elementos; y se repite hasta llegar siempre a una comparación menos que el ciclo previo, ya que el último valor alcanzado en éste debe estar ya en orden. La siguiente animación ilustra la idea.

Bubble sort example

Transformar dicha idea en código es algo directo:

void BubbleSort(Vector a, int n)
{
    for(int j=n-1; j > 0; j--)
        for(int k=0; k < j; k++)
            if (a[k+1] < a[k])
                Swap(a,k,k+1);
}

En mi caso, el Bubble sort fue también el algoritmo con el que me inicié en el tema de la complejidad computacional, tema que es a la computación lo que la teoría de los números es a las matemáticas, uno de esos esquemas de razonamiento más puros que pueden tenerse, para muchos obscuros y que rayan en lo “esotérico”– en términos científicos, of course. Un tema que siempre ha sido de mi interés1 como de muchas otras personas2-4.

Bubble concept animationCiertamente, el “sort de la burbuja” es el más fácil de implementar (es el “más bobo”, como muchos diríamos), a tal grado que puede hacerse en forma igualmente simple en otros paradigmas de programación5, como es el de “hoja de cálculo” (form-based paradigm, de acuerdo a la clasificación de Ambler et al5),  tal facilidad trae un costo asociado: es el más lento, siendo de complejidad O(n2).

Sobre esto último, hay algunos puntos interesantes. El primero es que, si bien la medida señalada en el párrafo previo es para el tiempo, lo es también en el espacio requerido en la implementa´ción en una hoja de cálculo6. El segundo es que, si se cuenta con una cantidad de procesadores equivalente a la mitad de elementos a ordenar (en la ilustración inferior considere cada “caja” como un procesador), paradójicamente, el algoritmo puede transformarse en uno O(n)7.

Consider every box as a processing element

Referencias

  1. Eduardo René Rodríguez Ávila, “El Correcto y Completo Desarrollo de un Algoritmo“, Researchgate, web. Uploaded: 2015-10-08, retrieved: 2016.09.14. DOI: 10.13140/RG.2.1.4759.1128. URL: https://www.researchgate.net/publication/282660374_El_Correcto_y_Completo_Desarrollo_de_un_Algoritmo.
  2. Tim Slavin, “Bubble sorts“, Kids, Code and Computer Science, November 2013. URL: https://www.kidscodecs.com/bubble-sorts/.
  3. Owen Astrachan, “Bubble Sort: An Archaeological Algorithmic Analysis“, Duke University, Computer Science Department, web. URL: https://users.cs.duke.edu/~ola/bubble/bubble.html.
  4. O. J. Reeves, “Sorting Algorithms: The Bubble Sort“, OJ’s Perspective, blog. Published: 2008.08.14, retrieved: 2016.09.14. URL: http://buffered.io/posts/sorting-algorithms-the-bubble-sort/.
  5. Ambler, A. L., Burnett, M. M., & Zimmerman, B. A., “Operational Versus Definitional: A Perspective on Programming Paradigms“. Computer, Vol. 25, 28–43, September 1992. DOI:10.1109/2.156380. URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=156380.
  6. Eduardo René Rodríguez Ávila,”Bubble sort algorithm implementation for a form-based programming paradigm“, MS Excel spreadsheet. URL: https://eravila.files.wordpress.com/2016/09/sorting-v1-00.xlsx.
  7. Goodman, S. E. & Hedetniemi, S. T., “Introduction to the Design and Analysis of Algorithms“; 5th Ed., McGraw-Hill International Editions; Singapore, 1988. ISBN 0-07-Y66300-9

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s