lunes, 14 de noviembre de 2016

Programación del Sinclair QL (IX): Ordenación por intercambio iterativo, variantes de la Burbuja



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.

No hay comentarios:

Publicar un comentario