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
Al final vemos que el mejor sistema es el de
sacudida, ya que obtiene el mejor tiempo en el caso medio, no se alarga en el mejor y obtiene un buen puesto en el peor caso, aunque veremos que el método de
inserción, que es un sencillo algoritmo iterativo que requiere menos
comparaciones y movimientos de datos gana por goleada a nuestra
Burbuja, pero aun así se ve superado por el
QuickSort, basado también en
intercambios pero recursivo.
