Mejoras a la ordenación por Burbuja. Tortugas y liebres
Seguimos dando vueltas a la Burbuja, buscando optimizarla al máximo. Adelanto que es una búsqueda vana, como indican todos los autores Burbuja nunca será un método óptimo, no puede competir con la Ordenación por Inserción que es también un algoritmo sencillo, y mucho menos con el QuickSort.
Cuando lanzamos la ordenación por Burbuja los elementos mayores van rápidamente al final de la lista por lo que se les denomina liebres, mientras que los elementos mas pequeños suben poco a poco hacia su posición por lo que se les denomina tortugas. Existen una serie de variantes de la Burbuja que intentan convertir las tortugas en liebres para que se acelere el proceso. Se usan en general dos técnicas, una es cambiar la dirección del recorrido para ir subiendo y bajando por los elementos de la lista, y la otra es intercambiar elementos separados y no cercanos.
Ordenación por Sacudida, cambiando la dirección en cada pasada
La Ordenación por Sacudida, Burbuja Bidireccional o Cocktail Sort es una variante que en cada pasada cambia el sentido en que recorre la lista, de forma que cuando llega al final empieza a recorrerla de mayor a menor ubicando en ese momento el menor elemento el primero. Ahora vuelve a empezar pero recorriendo la lista del elemento 2 al penúltimo en ida y vuelta. De esta manera en cada cambio de sentido las tortugas se convierten en liebres y viceversa.
ALGORITMO Sacudida (lista,sentido[Ascendente|Descendente],primero,ultimo)
izquierda ← primero
derecha ← ultimo-1
REPETIR
// --> Burbuja hacia la derecha
ordenada ← cierto
BUCLE i DESDE izquierda HASTA derecha
SI (sentido = Ascendente) Y (lista(i) < lista(i+1)) O BIEN
(sentido = Descendente) Y (lista(i) > lista(i+1)) ENTONCES
INTERCAMBIA_ELEMENTOS(i, i+1)
ordenada ← falso
ultimo ← i
FIN SI
FIN BUCLE_PARA
izquierda ← izquierda+1
derecha ← ultimo
SI ordenada O BIEN (izquierda>derecha) ENTONCES
FIN_REPETIR
FIN SI
// <-- b="" burbuja="" cierto="" hacia="" izquierda="" la="" ordenada="">BUCLE
i DESDE derecha HASTA izquierda
cambiar ← falso
SI (sentido = Ascendente) Y (lista(i-1) < lista(i)) O BIEN
(sentido = Descendente) Y (lista(i-1) > lista(i)) ENTONCES
INTERCAMBIA_ELEMENTOS(i-1, i)
ordenada ← falso
ultimo ← i
FIN SI
FIN BUCLE_PARA
izquierda ← primero
derecha ← derecha-1
SI ordenada O BIEN (izquierda>derecha) ENTONCES
FIN_REPETIR
FIN SI
Esta versión mejora el proceso en el caso medio pero solo si hay bastantes elementos a ordenar, si son pocos elementos, si la lista está casi ordenada o está en orden inverso o casi invertido los tiempos son los mismos que para la burbuja. Veamos el código en SuperBASIC.
01 DEFine PROCedure Sacudida (arreglo,sentido,primero,ultimo) 02 LOCal izquierda,derecha,cambiar,ordenada,repetir,i 03 : 04 IF ultimo=0 THEN ultimo=DIMN(arreglo) 05 izquierda=primero 06 derecha=ultimo-1 07 : 08 REPeat repetir 09 : 10 REMark Bucle hacia la derecha 11 : 12 ordenada=Si 13 FOR i=izquierda TO derecha 14 cambiar=No 15 :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1 16 IF sentido=Ascendente THEN 17 IF arreglo(i) > arreglo(i+1) THEN cambiar=Si 18 ELSE 19 IF arreglo(i) < arreglo(i+1) THEN cambiar=Si 20 END IF 21 IF cambiar THEN 22 :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3 23 temp = arreglo(i) 24 arreglo(i) = arreglo(i+1) 25 arreglo(i+1) = temp 26 : 27 ordenada=No 28 ultimo=i 29 END IF 30 END FOR i 31 izquierda=izquierda+1 32 derecha=ultimo 33 IF ordenada OR (izquierda>derecha) THEN EXIT repetir 34 : 35 REMark Bucle hacia la izquierda 36 : 37 ordenada=Si 38 FOR i=derecha TO izquierda STEP -1 39 cambiar=No 40 :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1 41 IF sentido=Ascendente THEN 42 IF arreglo(i-1) > arreglo(i) THEN cambiar=Si 43 ELSE 44 IF arreglo(i-1) < arreglo(i) THEN cambiar=Si 45 END IF 46 IF cambiar THEN 47 :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3 48 temp = arreglo(i-1) 49 arreglo(i-1) = arreglo(i) 50 arreglo(i) = temp 51 : 52 ordenada=No 53 primero=i 54 END IF 55 END FOR i 56 izquierda=primero 57 derecha=derecha-1 58 IF ordenada OR (izquierda > derecha) THEN EXIT repetir 59 END REPeat repetir 60 END DEFine
Ordenación por Cremallera, cambiando tortugas por liebres
La Ordenación de cremallera, conocida como Gnome Sort (ordenación de los nomos) o Stupid Sort (ordenación tonta), usa también la táctica de cambiar de dirección pero lo hace continuamente intentando localizar lo mas rápido posible una tortuga, para convertirla en liebre y moverla rápido hacia su lugar. El algoritmo empieza comparando las parejas de valores, si están en orden avanza a la siguiente pareja, pero si no están en orden, se intercambian entre si, y ahora se cambia de sentido, se reduce el puntero y se compara en dirección contraria hasta que haya un intercambio o se alcance el inicio del arreglo. El proceso se detiene cuando se alcanza el final del arreglo. Así va trabajando buscando tortugas y moviendo liebres.ALGORITMO Cremallera (lista,sentido[Ascendente|Descendente],primero,ultimo)
i ← primero + 1
MIENTRAS i < ultimo
SI (sentido = Ascendente) Y (lista(i-1) <= lista(i)) O BIEN
(sentido = Descendente) Y (lista(i-1) >= lista(i)) ENTONCES
i ← i + 1
SI NO
INTERCAMBIA_ELEMENTOS(i-1, i)
SI i > primero + 1 ENTONCES
i ← i - 1
FIN SI
FIN SI
FIN MIENTRAS
Como vemos, el algoritmo tiene la ventaja de ser muy sencillo, y en un lenguaje interpretado como nuestro SuperBASIC es importante la sencillez para mejorar la velocidad, pero tampoco es un algoritmo rápido.
630 DEFine PROCedure Cremallera (arreglo,sentido,primero,ultimo) 640 LOCal cambiar,repetir,i 650 : 660 IF ultimo=0 THEN ultimo=DIMN(arreglo) 670 : 680 i=primero+1 690 REPeat repetir 700 IF i > ultimo THEN EXIT repetir 710 : 720 :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1 730 cambiar=No 740 IF sentido=Ascendente THEN 750 IF arreglo(i-1) > arreglo(i) THEN cambiar=Si 760 ELSE 770 IF arreglo(i-1) < arreglo(i) THEN cambiar=Si 780 END IF 790 IF NOT cambiar THEN 800 i=i+1 810 ELSE 820 :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3 830 temp = arreglo(i-1) 840 arreglo(i-1) = arreglo(i) 850 arreglo(i) = temp 860 : 870 IF i > primero+1 THEN i=i-1 880 END IF 900 END REPeat repetir 910 END DEFine
Ordenación por Peine, cambiando elementos separados
La ordenación por Peine o Comb Sort utiliza la técnica de comparar elementos no correlativos sino separados entre sí, de esta forma movemos grupos de elementos en la dirección adecuada, en lugar de posicionar solo un elemento en cada vez. La técnica es muy simple, se calcula un valor de distanciamiento entre elementos, inicialmente tomando la parte entera de dividir el número de elementos entre 1.3 (valor que se ha calculado experimentalmente como el mejor, aunque el valor teórico es de 1.2473). Se recorre la lista de elementos, comparando los valores separados por ese incremento en lugar de comparar los contiguos, intercambiándolos si es necesario, hasta que no se necesiten mas intercambios. Luego se vuelve a tomar como separación entre elementos la parte entera de dividir el valor anterior por 1.3, y se repite el proceso, hasta que la distancia es 1 y se convierte en una burbuja ordinaria. En cada pasada los elementos están un poco mas ordenados, y sobre todo mas cercanos a su lugar definitivo, evitando mover los elementos muchas posiciones a lo largo de la lista.
Su creador es Włodzimierz Dobosiewicz en 1980, pero en un articulo publicado originalmente en la revista BYTE en 1991 por Stephen Lacey y Richard Box, argumentan que cuando la distancia es 9 o 10 se optimiza el algoritmo cambiando el factor a 11, a esta variante la llamaron Combsort11, lo que es el trozo en color naranja del siguiente algoritmo:
ALGORITMO Peine (lista,sentido[Ascendente|Descendente],primero,ultimo)
distancia ← ultimo - primero + 1
factor ← 1.3
REPETIR
distancia ← TOMAR_PARTE_ENTERA(distancia / factor)
SI (distancia = 9) O BIEN (distancia = 10) ENTONCES
distancia ← 11
FIN SI
SI distancia < 1 ENTONCES
distancia ← 1
FIN SI
ordenado ← Cierto
derecha ← primero
BUCLE PARA i DESDE primero HASTA ultimo - distancia
SI (sentido = Ascendente) Y (lista(i) > lista(i+distancia)) O BIEN
(sentido = Descendente) Y (lista(i) < lista(i+distancia)) ENTONCES
INTERCAMBIA_ELEMENTOS(i, i+distancia)
ordenado ← Falso
derecha ← i
FIN SI
FIN BUCLE PARA
SI distancia = 1 ENTONCES
ultimo ← derecha
FIN SI
HASTA QUE (distancia = 1) Y ordenado
Estos valores de 11 en lugar de 9 o 10, igual que el de 1.3 como mejor factor, se han calculado teóricamente y comprobado experimentalmente usando listas de miles de elementos, si nuestras listas son pequeñas no se alcanzan diferencias pues el aumentar la complejidad del algoritmo reduce sus ventajas.
130 DEFine PROCedure Peine (arreglo,sentido,primero,ultimo) 140 LOCal distancia,factor,derecha,cambiar,ordenada,repetir,i 150 : 160 IF ultimo=0 THEN ultimo=DIMN(arreglo) 170 : 180 distancia=ultimo-primero+1 190 factor=1.3 200 REPeat repetir 210 distancia=INT(distancia/factor) 220 IF (distancia=9) OR (distancia=10) THEN distancia=11 230 IF distancia < 1 THEN distancia = 1 240 : 250 ordenada=Si 260 derecha=primero 270 FOR i=primero TO ultimo-distancia 280 cambiar=No 290 :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1 300 IF sentido=Ascendente THEN 310 IF arreglo(i) > arreglo(i+1) THEN cambiar=Si 320 ELSE 330 IF arreglo(i) < arreglo(i+1) THEN cambiar=Si 340 END IF 350 IF cambiar THEN 360 :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3 370 temp = arreglo(i) 380 arreglo(i) = arreglo(i+1) 390 arreglo(i+1) = temp 400 : 410 ordenada=No 420 derecha=i 430 END IF 440 END FOR i 450 IF distancia=1 THEN 460 IF ordenada THEN EXIT repetir 470 ultimo=derecha 480 END IF 490 END REPeat repetir 500 END DEFine
Pares o nones ¿jugando a ordenar?
La Ordenación Impar-Par es usada sobre todo en su variante para procesamiento paralelo, es una burbuja en la que en una primera pasada se recorren los elementos impares de la lista, y en una segunda se recorre por los elementos pares, por tanto el algoritmo es muy parecido al de la sacudida, pero sin cambiar el sentido. No aporta nada, pero si tenemos la posibilidad de usar varios procesadores es un algoritmo sencillo para repartir entre todos la carga.
ALGORITMO Impar_Par (lista,sentido[Ascendente|Descendente],primero,ultimo)
REPETIR
ordenada ← cierto
// Burbuja de impares
BUCLE i DESDE 1 HASTA ultimo-1 SUMANDO 2
SI (sentido = Ascendente) Y (lista(i) < lista(i+1)) O BIEN
(sentido = Descendente) Y (lista(i) > lista(i+1)) ENTONCES
INTERCAMBIA_ELEMENTOS(i, i+1)
ordenada ← falso
FIN SI
FIN BUCLE_PARA
// Burbuja de pares
BUCLE i DESDE 0 HASTA ultimo-1 SUMANDO 2
SI (sentido = Ascendente) Y (lista(i) < lista(i+1)) O BIEN
(sentido = Descendente) Y (lista(i) > lista(i+1)) ENTONCES
INTERCAMBIA_ELEMENTOS(i, i+1)
ordenada ← falso
FIN SI
FIN BUCLE_PARA
SI ordenada ENTONCES
FIN_REPETIR
FIN SI
Este algoritmo no aporta mucho, solo lo desarrollo por completar las variantes. En lugar de dos bucles independientes, por simplificar uso dos bucles anidados, en primero recorre solo 1 y 0 que son los inicios de los dos bucles.
130 DEFine PROCedure Impar_par (arreglo,sentido,primero,ultimo) 140 LOCal cambiar,ordenada,repetir,i,j 150 : 160 IF ultimo=0 THEN ultimo=DIMN(arreglo) 170 : 180 REPeat repetir 190 ordenada=Si 200 FOR j=1 TO 0 STEP -1 210 FOR i=j TO ultimo-1 STEP 2 220 cambiar=No 230 :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1 240 IF sentido=Ascendente THEN 250 IF arreglo(i) > arreglo(i+1) THEN cambiar=Si 260 ELSE 270 IF arreglo(i) < arreglo(i+1) THEN cambiar=Si 280 END IF 290 IF cambiar THEN 300 :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3 310 temp = arreglo(i) 320 arreglo(i) = arreglo(i+1) 330 arreglo(i+1) = temp 340 : 350 ordenada=No 360 END IF 370 END FOR i 380 END FOR j 390 IF ordenada THEN EXIT repetir 400 END REPeat repetir 410 END DEFine
Comparativa final de resultados con algoritmos de intercambio
El resultado final de la comparativa es muy poco alentador. Partiendo de la base de que todos los algoritmos acaban intercambiando el mismo número de elementos (como es lógico pues al final siempre usan el mismo sistema), el algoritmo mas rápido será el que menos comparaciones requiera, otro valor que es similar en todos los algoritmos ya que se basan en el mismo principio. Con 200 elementos y sumando los tiempos de las tres ordenaciones de la prueba, vemos este resultado:
- 29 minutos 31 segundos Burbuja
- 26 minutos 27 segundos Sacudida
- 44 minutos 40 segundos Cremallera
- 33 minutos 35 segundos Peine
- 28 minutos 55 segundos Impar-Par
No hay comentarios:
Publicar un comentario