El ordenamiento de elementos es uno de los problemas clásicos de la computación. En esta entrada se presentará un algoritmo clave y sencillo, aunque no eficiente, para el ordenamiento de elementos: el ordenamiento por burbuja.
Considere la siguiente secuencia de elementos:
Considere la siguiente secuencia de elementos:
15, -4, 0, -9, 7, 10
Con toda seguridad, si consigue una hoja de papel y un lápiz, incluso quizá mentalmente, podrá ordenarlos ascendentemente obteniendo como resultado:
-9, -4, 0, 7, 10, 15
Ahora bien, ¿cuál fue el procedimiento que siguió para ordenarlos?, ¿lo podría especificar y detallar para convertirlo en un algoritmo?
No hay una única forma de ordenar una secuencia de elementos, aunque quizá la más común sea la búsqueda del elemento menor de la lista, colocarlo es su lugar, y buscar el siguiente elemento menor de la lista, colocarlo en su lugar, y continuar así sucesivamente hasta terminar con toda la secuencia de elementos a ordenar.
El algoritmo de la burbuja se basa en ir comparando elementos contigüos, es decir, tomar el elemento i-ésimo y compararlo con el elemento i-ésimo + 1, si ese par de elementos no está ordenado, entonces se intercambian, si lo están, se dejan tal y como se encontraron.
Para la secuencia anterior, el algoritmo de la burbuja generaría los siguientes intercambios para el primer recorrido:
No hay una única forma de ordenar una secuencia de elementos, aunque quizá la más común sea la búsqueda del elemento menor de la lista, colocarlo es su lugar, y buscar el siguiente elemento menor de la lista, colocarlo en su lugar, y continuar así sucesivamente hasta terminar con toda la secuencia de elementos a ordenar.
El algoritmo de la burbuja se basa en ir comparando elementos contigüos, es decir, tomar el elemento i-ésimo y compararlo con el elemento i-ésimo + 1, si ese par de elementos no está ordenado, entonces se intercambian, si lo están, se dejan tal y como se encontraron.
Para la secuencia anterior, el algoritmo de la burbuja generaría los siguientes intercambios para el primer recorrido:
15, -4, 0, -9, 7, 10
-4, 15, 0, -9, 7, 10
-4, 0, 15, -9, 7, 10
-4, 0, -9, 15, 7, 10
-4, 0, -9, 7, 15, 10
-4, 0, -9, 7, 10, 15
Observe que aunque los elementos aún no están ordenados todavía, el mayor de ellos (15) fue intercambiándose y ascendiendo a su posición final; de hecho ésta es la razón por la cual el algoritmo recibe el nombre de burbuja, en analogía al efecto ascendente de las burbujas de aire en el agua.
La secuencia anterior de intercambios, constituye de hecho el primer recorrido para la lista de elementos, y en principio, se necesitan n - 1 recorridos para una lista de n elementos y n - 1 comparaciones dentro de cada recorrido para saber si realiza o no el intercambio.
Siguiendo la idea planteada hasta ahora termine de hacer los recorridos restantes, es decir: los cuatro recorridos que faltan con sus cinco iteraciones de comparación en cada uno.
El Ejemplo 6.4 muestra un archivo de biblioteca personalizada (.h) que contiene dos versiones para el ordenamiento por burbuja. La versión que nos compete por el momento es la función definida en las líneas 23-34, la cual implementa la versión tradicional del ordenamiento por burbuja, también conocido como burbuja clásico o ingenuo.
La estructura de repetición for de la línea 26 controla el número de veces que se recorre el arreglo, que como ya se mencionó es de n - 1 veces, donde n es el número de elementos a ordenar. Ahora bien, para una n muy grande se tiene:
La secuencia anterior de intercambios, constituye de hecho el primer recorrido para la lista de elementos, y en principio, se necesitan n - 1 recorridos para una lista de n elementos y n - 1 comparaciones dentro de cada recorrido para saber si realiza o no el intercambio.
Siguiendo la idea planteada hasta ahora termine de hacer los recorridos restantes, es decir: los cuatro recorridos que faltan con sus cinco iteraciones de comparación en cada uno.
El Ejemplo 6.4 muestra un archivo de biblioteca personalizada (.h) que contiene dos versiones para el ordenamiento por burbuja. La versión que nos compete por el momento es la función definida en las líneas 23-34, la cual implementa la versión tradicional del ordenamiento por burbuja, también conocido como burbuja clásico o ingenuo.
La estructura de repetición for de la línea 26 controla el número de veces que se recorre el arreglo, que como ya se mencionó es de n - 1 veces, donde n es el número de elementos a ordenar. Ahora bien, para una n muy grande se tiene:
Por lo que se puede decir que un arreglo de n elementos se recorre n veces.
Por otro lado, el ciclo for de la línea 27 realiza en general n - 1 iteraciones para comparar parejas de números candidatas a intercambio para los n elementos del arreglo, pero por la misma razón que antes establecida por el límite, es posible decir que se repite n veces. Esto quiere decir que por cada recorrido se realizan n comparaciones.
En base a lo anterior, el ordenamiento por burbuja tiene el siguiente comportamiento general:
Por otro lado, el ciclo for de la línea 27 realiza en general n - 1 iteraciones para comparar parejas de números candidatas a intercambio para los n elementos del arreglo, pero por la misma razón que antes establecida por el límite, es posible decir que se repite n veces. Esto quiere decir que por cada recorrido se realizan n comparaciones.
En base a lo anterior, el ordenamiento por burbuja tiene el siguiente comportamiento general:
donde n es el número de elementos a ordenar.
La notación de la expresión anterior se lee como ''o grande de n cuadrada", y su explicación queda fuera de los alcances de este blog; por ahora, basta con saber que el ordenamiento por burbuja tiene un comportamiento cuadrático.
La notación de la expresión anterior se lee como ''o grande de n cuadrada", y su explicación queda fuera de los alcances de este blog; por ahora, basta con saber que el ordenamiento por burbuja tiene un comportamiento cuadrático.
Burbuja mejorado.
Si terminó de realizar las iteraciones propuestas en párrafos anteriores para ordenar la secuencia de números que se presentó, probablemente se haya dado cuenta de que la secuencia está ordenada después de la primera iteración de comparación del tercer recorrido.
Se deriva entonces una pregunta más que pertitente: ¿Tiene sentido realizar los recorridos e iteraciones de comparación restantes? Con toda seguridad su respuesta será negativa.
El ordenamiento por burbuja clásico no hace ningún tipo de verificación en éste sentido, por lo que realizaría siempre todos los recorridos e iteraciones de comparación basándose única y exclusivamente en el número de elementos a ordenar aún cuando los datos estuvieran ordenados desde el principio, de ahí que al ordenamiento por burbuja clásico también se le denomine ingenuo.
Para subsanar esta deficiencia, se pueden hacer esencialmente dos cosas basadas en las siguientes consideraciones:
Las banderas más comunes son las banderas binarias o booleanas, las cuales toman únicamente dos valores: 1 (verdadero) o 0 (falso).
El lenguaje de programación C no tiene tipos de datos booleanos, por lo que tienen que ser simulados o implementados con variables de tipo entero. Cuando a una bandera booleana se le asigna verdadero, se dice que se enciende la bandera, y cuando se le asigna falso, se dice que se apaga la bandera en analogía a un interruptor (switch) de encendido/apagado.
Se deriva entonces una pregunta más que pertitente: ¿Tiene sentido realizar los recorridos e iteraciones de comparación restantes? Con toda seguridad su respuesta será negativa.
El ordenamiento por burbuja clásico no hace ningún tipo de verificación en éste sentido, por lo que realizaría siempre todos los recorridos e iteraciones de comparación basándose única y exclusivamente en el número de elementos a ordenar aún cuando los datos estuvieran ordenados desde el principio, de ahí que al ordenamiento por burbuja clásico también se le denomine ingenuo.
Para subsanar esta deficiencia, se pueden hacer esencialmente dos cosas basadas en las siguientes consideraciones:
- Después de cada recorrido, el elemento mayor de serie de elementos se encontrará ya en su posición final; en el segundo recorrido el segundo elemento mayor y así sucesivamente, ¿tiene sentido seguir comparando estos elementos que sabemos ya ordenados? La respuesta es no, por lo que si después de cada recorrido reducimos también el número de iteraciones de comparación, se mejorará la eficiencia. Ésta es precisamente la mejora que se implementa en el ciclo for de la línea 13 del Ejemplo 6.4, en donde la expresión condicional se ha modificado para que dependa también del número de veces que se ha realizado el recorrido.
- Ahora bien, si la serie de elementos se encuentra ya ordenada en alguna parte del proceso de ordenamiento antes de las n x n iteraciones, tampoco tendría sentido continuar. Para dicho caso se ha utilizado una bandera (línea 9), la cual asumirá que después de cada recorrido la serie de elementos estará probablemente ordenada, por lo que la bandera se apaga (línea 12) para que la expresión condicional del ciclo for de la línea 11 sea falsa y los recorridos sobre la serie de elementos terminen; sin embargo, si la expresión condicional del if de la línea 14 se cumple para al menos una de las iteraciones de comparación, entonces la serie de elementos no está ordenada todavía y se enciende nuevamente la bandera (línea 18) para procesar al menos un nuevo recorrido.
Las banderas más comunes son las banderas binarias o booleanas, las cuales toman únicamente dos valores: 1 (verdadero) o 0 (falso).
El lenguaje de programación C no tiene tipos de datos booleanos, por lo que tienen que ser simulados o implementados con variables de tipo entero. Cuando a una bandera booleana se le asigna verdadero, se dice que se enciende la bandera, y cuando se le asigna falso, se dice que se apaga la bandera en analogía a un interruptor (switch) de encendido/apagado.
No hay comentarios.:
No se permiten comentarios nuevos.