Ordenación por burbuja
Este sistema, denominado en inglés Bubblesort, es el sistema mas sencillo de entender aunque también es el algoritmo mas lento e ineficiente de todos, por lo que en muchos libros se recomienda ni siquiera enseñarlo en los cursos de programación. A pesar de esto comienzo por el que todos hemos empezado, aunque recomiendo usar Inserción como algoritmo iterativo y Quicksort como recursivo que son mucho mas eficientes.La idea del algoritmo es sencilla, se recorre la lista comparando cada elemento con el siguiente, si este es menor se intercambian ambos elementos. Este proceso se repite hasta que la lista esté ordenada, con cada pasada los elementos mayores se hunden en la lista rápidamente, moviendo hacia arriba los elementos ligeros mas lentamente, como burbujas en un líquido, de ahi su nombre. Vamos con el algoritmo en seudo-código que orden por burbuja una lista, indicando el primer y ultimo elemento de la misma que deseamos ordenar
ALGORITMO Burbuja (lista,primero,ultimo)
REPETIR
BUCLE i DESDE primero HASTA ultimo-1
SI lista(i) > lista(i+1) ENTONCES
INTERCAMBIA(i, i+1)
FIN SI
FIN BUCLE
HASTA QUE lista_ordenada
Como vemos es un bucle que se repite recorriendo la lista de elementos, intercambiándolos si es necesario, hasta que la lista esté ordenada. ¿Como sabemos cuando lo está? hay dos sistemas complementarios. El primero es darse cuenta de que cuando en una pasada no sean necesarios mas intercambios, la lista está ordenada. Se usa una variable auxiliar para ello a la que se le denomina centinela, y al algoritmo en general Burbuja con centinela.
ALGORITMO Burbuja (lista,primero,ultimo)
REPETIR
ordenada ← cierto
BUCLE i DESDE primero HASTA ultimo-1
SI lista(i) > lista(i+1) ENTONCES
INTERCAMBIA(i, i+1)
ordenada ← falso
FIN SI
FIN BUCLE
HASTA QUE ordenada
La otra forma es conocer cuantas pasadas necesitamos, lo que es también sencillo aunque en principio no lo parezca. Sabemos que en cada pasada el último elemento está siempre posicionado, por lo que debemos hacer tantas pasadas como elementos en la lista. Pero como sabmos que tras una pasada el último elemento está ordenado, también podemos reducir el recorrido en uno. Debemos repetir hasta que hayamos reducido la lista a un elemento. Como el método es complementario al anterior, usaremos ambos a la vez.
ALGORITMO Burbuja (lista,primero,ultimo)
REPETIR
ordenada ← cierto
BUCLE i DESDE primero HASTA ultimo-1
SI lista(i) > lista(i+1) ENTONCES
INTERCAMBIA(i, i+1)
ordenada ← falso
FIN SI
FIN BUCLE
ultimo ← ultimo - 1
HASTA QUE (ordenada) O BIEN (ultimo=primero)
Aun podemos añadir una optimización adicional. Cuando movemos un elemento puede que llegue a un punto en que los elementos a su derecha sean todos mayores que él, por lo que sabemos que esa parte ya está ordenada. Así por ejemplo si tenemos 30,12,10,40,50 y lanzamos el proceso, el 30 solo lo movemos 2 veces, quedando la lista como 12,10,30,40,50 y sabemos que en la siguiente pasada en lugar de reducir solo en uno podemos reducir en tres directamente. Como esto es nuevamente complementario lo usamos todo a la vez. No podemos alterar directamente el valor de la variable que marca el último directamente, ya que es la que se usa de compración en el bucle. Hay lenguajes como el C en que este cambio altera el bucle, y otros como el SuperBASIC en que no, como esto es un algoritmo genérico debemos pensar que puede ser alterado, y usaremos una variable auxiliar.
ALGORITMO Burbuja (lista,primero,ultimo)
REPETIR
ordenada ← cierto
derecha ← primero
BUCLE i DESDE primero HASTA ultimo-1
SI lista(i) > lista(i+1) ENTONCES
INTERCAMBIA(i, i+1)
ordenada ← falso
derecha ← i
FIN SI
FIN BUCLE
ultimo ← derecha
HASTA QUE (ordenada) O BIEN (ultimo=primero)
Se puede reempazar el bucle REPETIR por un FOR, lo que hace este algoritmo compatible con otras versiones de BASIC que no soportan esta sentencia, con dos variantes equivalentes:
FOR i = ultimo-1 TO primero STEP -1 FOR j = primero TO i-1
O bien
FOR i = primero+1 TO ultimo FOR j = primero TO ultimo-i
Solo resta un detalle, el algoritmo puede ordenar de menor a mayor o al contrario, solo es necesario cambiar el sentido de la comparación, para ello añadimos como parámetro el sentido en que deseamos ordenar, y cambiamos la comparación.
ALGORITMO Burbuja (lista,sentido[Ascendente|Descendente],primero,ultimo) REPETIR ordenada ← cierto derecha ← primero BUCLE i DESDE primero HASTA ultimo-1 SI (sentido = Ascendente) Y (lista(i) > lista(i+1)) O BIEN (sentido = Descendente) Y (lista(i) < lista(i+1)) ENTONCES INTERCAMBIA(i, i+1) ordenada ← falso derecha ← i FIN SI FIN BUCLE ultimo ← derecha HASTA QUE (ordenada) O BIEN (ultimo=primero)
Con esto ya podemos transcribir el algoritmo a SuperBASIC. Un tema que ocurre demasiado a los programadores es que una vez tienen su algoritmo, en lugar de transcribirlo en su lenguaje, lo escriben de nuevo, lo que es un esfuerzo inútil cuando todo ha sido estudiado de antemano. Aquí está mi transcripción del programa, en el que lo único que añado es que por temas de hacer las líneas mas cortas, como SuperBASIC no admite sentencias en varias líneas, uso una variable auxiliar para saber si tengo que intercambiar los elementos, y la asigno según desee que la lista sea ascendente o descendente, y que si no indico cual es el último elemento que deseo ordenar, lo calculo en función de los elementos del arreglo:
4000 REMark --------------------------------------------- 4010 REMark -- ALGORITMOS DE ORDENACION -- 4020 REMark -- Modulo....: Burbuja -- 4030 REMark -- Objetivo..: Ordena un arreglo por el -- 4040 REMark -- algoritmo de burbuja -- 4050 REMark -- Autor.....: javu61, 11/2016 -- 4060 REMark -- Parametros: -- 4070 REMark -- arreglo -> Arreglo a ordenar -- 4080 REMark -- sentido -> FALSO = Ascendente -- 4090 REMark -- primero -> primer elemento -- 4100 REMark -- ultimo -> ultimo elemento -- 4110 REMark -- Si ultimo=0 -> Todos -- 4120 REMark --------------------------------------------- 4130 DEFine PROCedure Burbuja (arreglo,sentido,primero,ultimo) 4140 LOCal derecha,cambiar,ordenada,repetir,i 4150 : 4160 IF ultimo=0 THEN ultimo=DIMN(arreglo) 4170 : 4180 REPeat repetir 4190 ordenada=Si 4200 derecha=primero 4210 FOR i=primero TO ultimo-1 4220 cambiar=No 4230 :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1 4240 IF sentido=Ascendente THEN 4250 IF arreglo(i) > arreglo(i+1) THEN cambiar=Si 4260 ELSE 4270 IF arreglo(i) < arreglo(i+1) THEN cambiar=Si 4280 END IF 4290 IF cambiar THEN 4300 :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3 4310 temp = arreglo(i) 4320 arreglo(i) = arreglo(i+1) 4330 arreglo(i+1) = temp 4340 : 4350 ordenada=No 4360 derecha=i 4370 END IF 4380 END FOR i 4390 ultimo=derecha 4400 IF ordenada OR (primero=ultimo) THEN EXIT repetir 4410 END REPeat repetir 4420 END DEFine
Las líneas que comienzan por :: son solo para contar comparaciones e intercambios, necesario solo para las pruebas, en el algoritmo definitivo hay que eliminar estas líneas para poder usarlo en otros programas.
No hay comentarios:
Publicar un comentario