viernes, 25 de noviembre de 2016

Programación del Sinclair QL (XVI): Estructuras de Datos. Mas sobre Pilas y Colas



Hay una función que también es usada en pilas y colas que es la de consultar el elemento sin extraerlo, es decir consultar el elemento que está en la cima de la pila o consultar el elemento en la cabeza de la cola.

Para la pila hay se usa el mismo código que para el POP quitando la linea que mueve el puntero a la cima, pero cuando una función esté incluida en otra hay que reutilizar siempre el código y no duplicarlo, ya que esto además de simplificar el código evita errores, si mañana se cambia la forma de extraer el elemento de la cima, solo hay una función que modificar, por lo que además de añadir la función PILA_VER cambio también la función PILA_POP (como siempre las lineas que comienzan por :: son prescindibles, están para rellenar con ceros y que visualmente sea mas fácil localizar la cima en el arreglo):

1540 REMark --------------------------------------------------------------
1550 REMark -- v = PILA_VER -- Devuelve dato sin extraerlo              --
1560 REMark -- RETORNA: Valor de la cima de la pila                     --
1570 REMark --------------------------------------------------------------
1580 DEFine FuNction PILA_VER
1590   IF PILA_VACIA THEN 
1600     PRINT"Error: Pila vacia"
1610     STOP
1620   END IF 
1630   RETurn ArrPila(ArrPila(PILA_TOP))
1640 END DEFine 
1650 :
1660 REMark --------------------------------------------------------------
1670 REMark -- v = PILA_POP -- Saca un dato de la pila                  --
1680 REMark -- RETORNA: Valor de la cima de la pila                     --
1690 REMark --------------------------------------------------------------
1700 DEFine FuNction PILA_POP
1710   LOCal valor
1720   :
1730   valor=PILA_VER
1740   :: ArrPila(ArrPila(PILA_TOP))=0
1750   ArrPila(PILA_TOP)=ArrPila(PILA_TOP)-1
1760   RETurn valor
1770 END DEFine 

Para la cola lo mismo exactamente, se crea la nueva función COLA_VER y se modifica COLA_EXTRACT para que la use. Para la cola simple:

1710 REMark --------------------------------------------------------------
1720 REMark -- v = COLA_VER -- Muestra el dato de la cabeza de la cola  --
1730 REMark -- RETORNA: Valor de la cabeza de la cola                   --
1740 REMark --------------------------------------------------------------
1750 DEFine FuNction COLA_VER
1760   IF COLA_VACIA THEN 
1770     PRINT"Error: Cola vacia"
1780     STOP
1790   END IF 
1800   :
1810   RETurn ArrCola(ArrCola(COLA_CABEZA))
1820 END DEFine 
1830 :
1840 REMark --------------------------------------------------------------
1850 REMark -- v = COLA_EXTRACT    -- Saca un dato de la cola           --
1860 REMark -- RETORNA: Valor de la cabeza de la cola                   --
1870 REMark --------------------------------------------------------------
1880 DEFine FuNction COLA_EXTRACT
1890   LOCal valor
1900   :
1910   valor = COLA_VER
1920   :: ArrCola(ArrCola(COLA_CABEZA))=0
1930   ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1
1940   IF COLA_VACIA THEN COLA_INIT
1950   RETurn valor
1960 END DEFine 

Y para la cola circular la función COLA_VER es exactamente la misma anterior, solo cambia la función COLA_EXTRACT de la misma manera que en la anterior:

1990 REMark --------------------------------------------------------------
2000 REMark -- v = COLA_EXTRACT    -- Saca un dato de la cola           --
2010 REMark -- RETORNA: Valor de la cabeza de la cola                   --
2020 REMark --------------------------------------------------------------
2030 DEFine FuNction COLA_EXTRACT
2040   LOCal valor
2050   :
2060   valor=COLA_VER
2070   :: ArrCola(ArrCola(COLA_CABEZA))=0
2080   ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1
2090   IF ArrCola(COLA_CABEZA) > DIMN(ArrCola) THEN 
2100     ArrCola(COLA_CABEZA)=2
2110   END IF 
2120   :
2130   REMark Ver si cola vacia
2140   IF ArrCola(COLA_CABEZA) = ArrCola(COLA_COLA)+1 THEN COLA_INIT
2150   RETurn valor
2160 END DEFine 


Existen mas variantes de las colas, la cola circular une cabeza y cola de forma que se puede ir recorriendo de manera continua. Las dobles colas unen pila y cola en una misma estructura, en ellas los elementos se pueden introducir o extraer por cualquiera de los dos lados. Las colas por prioridades son una variante en que los elemento se extraen comenzando por los mas prioritarios.

En general para montar una pila se usa un espacio en memoria contiguo, similar a un arreglo, pero las colas en cambio se suelen montar usando estructuras de nodos enlazados en lugar de arreglos, ya que son mas flexibles, cuesta un poco mas de montar, pero son muy sencillas de recorrer. Esto lo haré en otra entrada de manera sencilla usando también un arreglo, lo que será la base de la siguiente estructura de datos importante, los árboles. Posteriormente quiero usar las estructuras de datos directamente en memoria, pero eso en un lenguaje que no soporta punteros ni estructuras como el BASIC o el SuperBASIC es otro cantar, hay que pasar a manejar directamente la memoria del ordenador con PEEK y POKE, desarrollar un controlador de memoria que nos controle los huecos y la ocupación, y alguna cosita mas. Es un reto muy interesante para un programador, recomiendo intentarlo por vuestra cuenta pues es muy instructivo.

Aquí todo lo desarrollado hasta el momento.

Programación del Sinclair QL (XV): Estructuras de Datos. Colas



Otra estructura de datos muy usada

Las colas son la otra estructura de datos simple mas usada. Se comporta como cualquier cola, cuando llegas te pones al final, y conforme se va procesando lo que está en la cabecera vas avanzando. Aquí la máxima es que el primero en entrar es el primero en salir.

Todos usáis una impresora en vuestro ordenador, cuando enviar cosas a imprimir se colocan en una cola de trabajos, y se van procesando de uno en uno. De esta forma podemos tener todos los trabajos de impresión que necesitemos, nuestros o de otros usuarios, y no se lía la impresora ya que los procesa por estricto orden de llegada.

Las colas son sencillas de implementar usando un arreglo y dos variables que hacen de punteros, uno a la cabeza y otro a la cola, conforme llegan los elementos se aumenta el apuntador a la cola y se ubican en el lugar que indique, cuando se desea sacar algo se usa el elemento ubicado en la posición apuntada por la cabeza y se aumenta el apuntador. La cola esta vacía cuando la cabeza supera a la cola. Para evitar que crezcan indefinidamente, cuando se saca un elemento de la cola y esta queda vacía, se reinician los punteros de cabeza y cola. Otro proceso importante es que muchas veces se introducen un conjunto de elementos a una velocidad y se retiran a otra, con lo que puede que el puntero de cola alcance el tamaño máximo disponible, pero como la cabeza ha avanzado queda espacio disponible al comienzo de la cola, por lo que para recuperar ese espacio hay que compactar la cola, desplazando todos los elementos hacia el comienzo.

Esta implementación de la cola que realizo en SuperBASIC usando un arreglo es muy sencilla, utilizo el elemento 0 del arreglo como apuntador a la cabecera, y el elemento 1 como apuntador a la cola, de esta forma mantengo toda la información de manejo en el arreglo. Dispongo de una serie de procedimientos y funciones para el manejo:
  • COLA_CREAR crea una cola con un tamaño mínimo
  • COLA_NUEVA crea una cola del tamaño que se le indique y un margen mínimo
  • COLA_VACIA retorna un booleano que indica si la cola está vacía
  • COLA_ADD añade un dato al final de la cola, si está llena intenta compactarla, si sigue llena la amplia al doble de su tamaño
  • COLA_EXTRACT retorna el dato ubicado en la cabecera de cola
  • COLA_REDUCE reduce la cola al tamaño real que ocupa mas el margen mínimo
  • COLA_CAMBIA cambia su tamaño al que se le indique, puede ser mayor o menor que el tamaño actual de la cola, pero nunca la reduce a menos del numero de elementos que contiene mas el margen mínimo
  • COLA_INIT de uso interno por los otros procesos, sirve para inicializar los punteros de la cola, no debe ser usada mas que por los otros procesos de manejo de la cola
  • COLA_COMPACTA de uso interno por los otros procesos, pasa todos los elementos ocupados por la cola al principio de la misma, dejando todo el espacio libre al final.
NOTA: Las líneas marcadas con :: son opcionales, sirven para limpiar los elementos que se van extrayendo y que sea mas sencillo visualizar los datos de las pruebas, pero no son necesarias para el funcionamiento de las rutinas.
1000 REMark --------------------------------------------------------------
1010 REMark -- ESTRUCTURAS DE DATOS                                     --
1020 REMark --   Modulo....: Cola                                       --
1030 REMark --   Objetivo..: Cola usando un arreglo simple              --
1040 REMark --   Autor.....: javu61, 11/2016                            --
1050 REMark --   Procesos..:                                            --
1060 REMark --     COLA_CREAR      -- Crear la cola                     --
1070 REMark --     COLA_NUEVA(tam) -- Crea la cola con un tamaño        --
1080 REMark --     COLA_INIT       -- Inicializa una cola               --
1090 REMark --     b=COLA_VACIA    -- Ver si la cola esta vacia         --
1100 REMark --     COLA_ADD(dato)  -- Introduce un dato en la cola      --
1110 REMark --     v=COLA_EXTRACT  -- Saca un dato de la cola           --
1120 REMark --     COLA_REDUCE     -- Compacta y reduce su tamaño       --
1130 REMark --     COLA_CAMBIA(tam)-- Cambia el tama‰o de la cola       --
1140 REMark --     COLA_COMPACTA   -- Compacta la cola                  --
1150 REMark --   Puntero...: Se usa el elemento cero del arreglo como   --
1160 REMark --               puntero a la cabeza, y el elemento 1 como  --
1170 REMark --               puntero a la cola                          --
1180 REMark --------------------------------------------------------------
1190 :
1200 REMark --------------------------------------------------------------
1210 REMark --     COLA_CREAR      -- Crea la cola                      --
1220 REMark --------------------------------------------------------------
1230 DEFine PROCedure COLA_CREAR
1240   COLA_NUEVA 10,5 : REMark Espacio para 10 elementos, crece minimo 5
1250 END DEFine 
1260 :
1270 REMark --------------------------------------------------------------
1280 REMark --     COLA_NUEVA(tam,fac) -- Crea la cola con un tama‰o y  --
1290 REMark --                            con un factor de crecimiento  --
1300 REMark --------------------------------------------------------------
1310 DEFine PROCedure COLA_NUEVA(tam,fac)
1320   LET COLA_FACTOR = fac
1330   LET COLA_CABEZA = 0
1340   LET COLA_COLA   = 1
1350   DIM ArrCola(tam+1) : REMark Elementos 0 y 1 se usan como punteros
1360   COLA_INIT
1370 END DEFine 
1380 :
1390 REMark --------------------------------------------------------------
1400 REMark --     COLA_INIT -- Inicializa una cola                     --
1410 REMark --------------------------------------------------------------
1420 DEFine PROCedure COLA_INIT
1430   ArrCola(COLA_CABEZA) = 2 : REMark Puntero a cabeza
1440   ArrCola(COLA_COLA)   = 1 : REMark Puntero a cola
1450 END DEFine 
1460 :
1470 REMark --------------------------------------------------------------
1480 REMark -- b = COLA_VACIA      -- Ver si la cola esta vacia         --
1490 REMark -- RETORNA: Booleano (Si, No)                               --
1500 REMark --------------------------------------------------------------
1510 DEFine FuNction COLA_VACIA
1520   RETurn (ArrCola(COLA_CABEZA) > ArrCola(COLA_COLA))
1530 END DEFine 
1540 :
1550 REMark --------------------------------------------------------------
1560 REMark --     COLA_ADD(dato) -- Introduce un dato en la cola, si   --
1570 REMark --                       esta llena crece al doble          --
1580 REMark --------------------------------------------------------------
1590 DEFine PROCedure COLA_ADD(dato)
1600   IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 
1610     COLA_COMPACTA
1620   END IF 
1630   IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 
1640     COLA_CAMBIA(DIMN(ArrCola)*2)
1650   END IF 
1660   ArrCola(COLA_COLA)=ArrCola(COLA_COLA)+1
1670   ArrCola(ArrCola(COLA_COLA))=dato
1680 END DEFine 
1690 :
1700 REMark --------------------------------------------------------------
1710 REMark -- v = COLA_EXTRACT    -- Saca un dato de la cola           --
1720 REMark -- RETORNA: Valor de la cabeza de la cola                   --
1730 REMark --------------------------------------------------------------
1740 DEFine FuNction COLA_EXTRACT
1750   LOCal valor
1760   :
1770   IF COLA_VACIA THEN 
1780     PRINT"Error: Cola vacia"
1790     STOP
1800   END IF 
1810   :
1820   valor=ArrCola(ArrCola(COLA_CABEZA))
1830   :: ArrCola(ArrCola(COLA_CABEZA))=0
1840   ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1
1850   IF COLA_VACIA THEN COLA_INIT
1860   RETurn valor
1870 END DEFine 
1880 :
1890 REMark --------------------------------------------------------------
1900 REMark --     COLA_REDUCE     -- Compacta y reduce su tama‰o       --
1910 REMark --------------------------------------------------------------
1920 DEFine PROCedure COLA_REDUCE
1930   COLA_COMPACTA
1940   COLA_CAMBIA(ArrCola(COLA_CABEZA)+COLA_FACTOR)
1950 END DEFine 
1960 :
1970 REMark --------------------------------------------------------------
1980 REMark --     COLA_CAMBIA -- Cambia el tama‰o de la cola           --
1990 REMark --------------------------------------------------------------
2000 DEFine PROCedure COLA_CAMBIA(tam)
2010   LOCal b(DIMN(ArrCola)),minimo,i
2020   :
2030   COLA_COMPACTA
2040   FOR i=0 TO ArrCola(COLA_COLA)
2050     IF i > DIMN(ArrCola) THEN EXIT i
2060     b(i)=ArrCola(i)
2070   END FOR i
2080   minimo = ArrCola(COLA_COLA)-ArrCola(COLA_CABEZA)+1 + COLA_FACTOR
2090   IF tam < minimo      THEN tam = minimo
2100   IF tam < COLA_FACTOR THEN tam=tam+COLA_FACTOR
2110   COLA_NUEVA tam,COLA_FACTOR
2120   FOR i=0 TO b(COLA_COLA)
2130     ArrCola(i)=b(i)
2140   END FOR i
2150 END DEFine 
2160 :
2170 REMark --------------------------------------------------------------
2180 REMark --     COLA_COMPACTA   -- Compacta la cola                  --
2190 REMark --------------------------------------------------------------
2200 DEFine PROCedure COLA_COMPACTA(tam)
2210   LOCal i,ini,fin
2220   :
2230   IF (NOT COLA_VACIA) AND (ArrCola(COLA_CABEZA) > 2) THEN 
2240     ini=ArrCola(COLA_CABEZA)
2250     fin=ArrCola(COLA_COLA)
2260     COLA_INIT
2270     FOR i=ini TO fin
2280       COLA_ADD ArrCola(i)
2290     END FOR i
2300     :: FOR i=fin+1 TO DIMN(ArrCola) : ArrCola(i)=0
2310   END IF 
2320 END DEFine 
Además de esta implementación mas simple, existe la posibilidad de aprovechar mejor el espacio evitando ampliaciones, cuando la cola alcanza el final del espacio, mira si hay sitio libre al comienzo, lo que será habitual si se han extraído elementos, y continua la cola por allí hasta alcanzar la cabeza. Ahora hay que poner el indicador de cola vacia al sacar un elemento, no podemos fiarnos de que los punteros se crucen ya. Las funciones que se manejan externamente son iguales a las anteriores, solo cambian las funciones de uso interno. He definido los procedimientos siguientes:
  • COLA_CREAR crea una cola con un tamaño mínimo
  • COLA_NUEVA crea una cola del tamaño que se le indique y un margen mínimo
  • COLA_VACIA retorna un booleano que indica si la cola está vacía
  • COLA_ADD añade un dato al final de la cola, si está llena intenta compactarla, si sigue llena la amplia al doble de su tamaño
  • COLA_EXTRACT retorna el dato ubicado en la cabecera de cola
  • COLA_REDUCE reduce la cola al tamaño real que ocupa mas el margen mínimo
  • COLA_CAMBIA cambia su tamaño al que se le indique, puede ser mayor o menor que el tamaño actual de la cola, pero nunca la reduce a menos del numero de elementos que contiene mas el margen mínimo
  • COLA_INIT de uso interno por los otros procesos, sirve para inicializar los punteros de la cola, no debe ser usada mas que por los otros procesos de manejo de la cola
  • COLA_REORDENA de uso interno por los otros procesos, pasa todos los elementos ocupados por la cola al principio de la misma, dejando todo el espacio libre al final.  Es la única función que tiene otro nombre entre las dos versiones, ya que realmente hacen lo mismo pero de forma un poco diferente.

1000 REMark --------------------------------------------------------------
1010 REMark -- ESTRUCTURAS DE DATOS                                     --
1020 REMark --   Modulo....: Cola                                       --
1030 REMark --   Objetivo..: Cola usando un arreglo, cola circular      --
1040 REMark --   Autor.....: javu61, 11/2016                            --
1050 REMark --   Procesos..:                                            --
1060 REMark --     COLA_CREAR      -- Crear la cola                     --
1070 REMark --     COLA_NUEVA(tam) -- Crea la cola con un tamaño        --
1080 REMark --     COLA_INIT       -- Inicializa una cola               --
1090 REMark --     b=COLA_VACIA    -- Ver si la cola esta vacia         --
1100 REMark --     COLA_ADD(dato)  -- Introduce un dato en la cola      --
1110 REMark --     v=COLA_EXTRACT  -- Saca un dato de la cola           --
1120 REMark --     COLA_REDUCE     -- Reordena y reduce su tamaño       --
1130 REMark --     COLA_CAMBIA(tam)-- Cambia el tama‰o de la cola       --
1140 REMark --     COLA_REORDENA   -- Reordena la cola                  --
1150 REMark --   Puntero...: Se usa el elemento cero del arreglo como   --
1160 REMark --               puntero a la cabeza, y el elemento 1 como  --
1170 REMark --               puntero a la cola                          --
1180 REMark --------------------------------------------------------------
1190 :
1200 REMark --------------------------------------------------------------
1210 REMark --     COLA_CREAR      -- Crea la cola                      --
1220 REMark --------------------------------------------------------------
1230 DEFine PROCedure COLA_CREAR
1240   COLA_NUEVA 10,5 : REMark Espacio minimo 10 elementos
1250 END DEFine 
1260 :
1270 REMark --------------------------------------------------------------
1280 REMark --     COLA_NUEVA(tam,fac) -- Crea la cola con un tama‰o y  --
1290 REMark --                            con un factor de crecimiento  --
1300 REMark --------------------------------------------------------------
1310 DEFine PROCedure COLA_NUEVA(tam,factor)
1320   LET COLA_FACTOR = factor
1330   LET COLA_CABEZA = 0
1340   LET COLA_COLA   = 1
1350   DIM ArrCola(tam+1) : REMark Elementos 0 y 1 se usan como punteros
1360   COLA_INIT
1370 END DEFine 
1380 :
1390 REMark --------------------------------------------------------------
1400 REMark --     COLA_INIT -- Inicializa una cola                     --
1410 REMark --------------------------------------------------------------
1420 DEFine PROCedure COLA_INIT
1430   ArrCola(COLA_CABEZA) = 0 : REMark Puntero a cabeza
1440   ArrCola(COLA_COLA)   = 0 : REMark Puntero a cola
1450 END DEFine 
1460 :
1470 REMark --------------------------------------------------------------
1480 REMark -- b = COLA_VACIA      -- Ver si la cola esta vacia         --
1490 REMark -- RETORNA: Booleano (Si, No)                               --
1500 REMark --------------------------------------------------------------
1510 DEFine FuNction COLA_VACIA
1520   RETurn (ArrCola(COLA_CABEZA) = 0)
1530 END DEFine 
1540 :
1550 REMark --------------------------------------------------------------
1560 REMark --     COLA_ADD(dato) -- Introduce un dato en la cola, si   --
1570 REMark --                       esta llena crece al doble          --
1580 REMark --------------------------------------------------------------
1590 DEFine PROCedure COLA_ADD(dato)
1600   REMark Si la cola estΠvacia, posiciono al comienzo
1610   IF ArrCola(COLA_COLA)=0 THEN 
1620     ArrCola(COLA_CABEZA)=2
1630     ArrCola(COLA_COLA)  =1
1640   ELSE 
1650     :
1660     REMark Si la cola alcanza la cabeza, estΠlleno
1670     IF ArrCola(COLA_COLA)+1 = ArrCola(COLA_CABEZA) THEN 
1680       COLA_CAMBIA(DIMN(ArrCola)*2)
1690     END IF 
1700     :
1710     REMark Si la cola alcanza el final del arreglo
1720     IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 
1730       IF ArrCola(COLA_CABEZA) >2 THEN 
1740         ArrCola(COLA_COLA)=1
1750       ELSE 
1760         COLA_CAMBIA(DIMN(ArrCola)*2)
1770       END IF 
1780     END IF 
1790   END IF 
1800   :
1810   ArrCola(COLA_COLA)=ArrCola(COLA_COLA)+1
1820   ArrCola(ArrCola(COLA_COLA))=dato
1830 END DEFine 
1840 :
1850 REMark --------------------------------------------------------------
1860 REMark -- v = COLA_EXTRACT    -- Saca un dato de la cola           --
1870 REMark -- RETORNA: Valor de la cabeza de la cola                   --
1880 REMark --------------------------------------------------------------
1890 DEFine FuNction COLA_EXTRACT
1900   LOCal valor
1910   :
1920   IF COLA_VACIA THEN 
1930     PRINT"Error: Cola vacia"
1940     STOP
1950   END IF 
1960   :
1970   valor=ArrCola(ArrCola(COLA_CABEZA))
1980   :: ArrCola(ArrCola(COLA_CABEZA))=0
1990   ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1
2000   IF ArrCola(COLA_CABEZA) > DIMN(ArrCola) THEN 
2010     ArrCola(COLA_CABEZA)=2
2020   END IF 
2030   :
2040   REMark Ver si cola vacia
2050   IF ArrCola(COLA_CABEZA) = ArrCola(COLA_COLA)+1 THEN COLA_INIT
2060   RETurn valor
2070 END DEFine 
2080 :
2090 REMark --------------------------------------------------------------
2100 REMark --     COLA_REDUCE     -- Reordena y reduce su tama‰o       --
2110 REMark --------------------------------------------------------------
2120 DEFine PROCedure COLA_REDUCE
2130   COLA_REORDENA
2140   COLA_CAMBIA(0)
2150 END DEFine 
2160 :
2170 REMark --------------------------------------------------------------
2180 REMark --     COLA_CAMBIAR -- Cambia el tama‰o de la cola          --
2190 REMark --------------------------------------------------------------
2200 DEFine PROCedure COLA_CAMBIA(tam)
2210   LOCal b(DIMN(ArrCola)),mintam,i
2220   :
2230   COLA_REORDENA
2240   FOR i=0 TO ArrCola(COLA_COLA) : b(i)=ArrCola(i)
2250   :
2260   mintam = ArrCola(COLA_COLA)-ArrCola(COLA_CABEZA)+1 + COLA_FACTOR
2270   IF tam < mintam      THEN tam=mintam
2280   IF tam < COLA_FACTOR THEN tam=tam+COLA_FACTOR
2290   COLA_NUEVA tam, COLA_FACTOR
2300   :
2310   FOR i=0 TO b(COLA_COLA)
2320     ArrCola(i)=b(i)
2330   END FOR i
2340 END DEFine 
2350 :
2360 REMark --------------------------------------------------------------
2370 REMark --     COLA_REORDENA   -- Reordena la cola                  --
2380 REMark --------------------------------------------------------------
2390 DEFine PROCedure COLA_REORDENA
2400   LOCal b(DIMN(ArrCola)),i,j,ini,fin
2410   :
2420   ini=ArrCola(COLA_CABEZA)
2430   fin=ArrCola(COLA_COLA)
2440   j=1
2450   :
2460   REMark Copio de la cabeza al final o a la cola
2470   FOR i=ini TO DIMN(ArrCola)
2480     IF (fin > ini) AND (i > fin) THEN EXIT i
2490     j=j+1: : b(j)=ArrCola(i)
2500   END FOR i
2510   :
2520   REMark Copio del inicio a la cola
2530   IF (fin < ini) THEN 
2540     FOR i=2 TO fin
2550       j=j+1: : b(j)=ArrCola(i)
2560     END FOR i
2570   END IF 
2580   :
2590   ArrCola(COLA_CABEZA) = 2
2600   ArrCola(COLA_COLA)   = j
2610   FOR i= 2 TO j : ArrCola(i)=b(i)
2620   :: FOR i=j+1 TO DIMN(ArrCola) : ArrCola(i)=0
2630 END DEFine 


Para realizar las pruebas de las colas he creado un pequeño programita que me las automatiza, siempre hay que definir una serie de pruebas de funcionamiento diversas y pensadas para probar los puntos vulnerables de las rutinas, y luego pasarlas para las dos rutinas, lo que al usar las funciones con el mismo nombre me aseguro de funciona y ambas pasan las mismas pruebas.

100 MODE 4: PAPER 0 : CLS
110 INPUT "Cual prefiere (1)=Simple (2)=Circular",t$
120 IF t$<>"1" AND t$<>"2" THEN GO TO 110
130 n$="mdv1_ed_cola_arreglo" & t$
140 PRINT "Cargando ";n$
150 MERGE n$
160 :
170 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1
180 t1=DATE
190 :
200 COLA_CREAR
210 :
220 PRINT "PRUEBA 1: Introduce 3 elementos y los extrae"
230 FOR i=1 TO 3   : mete(i)
240 FOR i=1 TO 3   : saca(i)
250 PRINT
260 :
270 PRINT "PRUEBA 2: Introduce 9, extrae 5, introduce 3, extrae 9"
280 FOR i=1 TO 9   : mete(i)
290 FOR i=1 TO 5   : saca(i)
300 FOR i=10 TO 13 : mete(i)
310 FOR i=6 TO 13  : saca(i)
320 PRINT
330 :
340 PRINT "PRUEBA 3: Inroduce 9, Extrae 2, introduce 10 y reduce"
350 FOR i=1 TO 9   : mete(i)
360 FOR i=1 TO 2   : saca(i)
370 FOR i=10 TO 19 : mete(i)
380 PRINT "CM "; : COLA_REDUCE : ver
390 PRINT
400 :
410 PRINT "PRUEBA 4: Extrae elementos hasta error por vacia"
420 FOR i=3 TO 19  : saca(i)
430 t2=DATE
440 PRINT "Tard֠";t2-t1;" segundos"
450 saca(0)
460 STOP
470 :
480 DEFine PROCedure mete(a)
490   PRINT "EN ";a;" - ";
500   COLA_ADD(a)
510   ver
520 END DEFine 
530 :
540 DEFine PROCedure saca(a)
550   PRINT "SA ";
560   s=COLA_EXTRACT
570   IF a<>s THEN PRINT "ERROR" : STOP
580   PRINT s;" - "; : ver
590 END DEFine 
600 :
610 DEFine PROCedure ver
620   LOCal xx
630   :
640   IF COLA_VACIA THEN 
650     PRINT "v ";
660   ELSE 
670     PRINT "  ";
680   END IF 
690   PRINT ArrCola(0);!ArrCola(1);": ";
700   FOR xx=2 TO DIMN(ArrCola) : PRINT !ArrCola(xx);
710   PRINT
720 END DEFine 

En ambos casos ha tardado 24 segundos en ejecutarse, ya que la diferencia es mínima entre ambas, con mas datos seguro que la primera es mas rápida que la segunda si no hay aumentos de tamaño por ser mas simple, pero la segunda ganará cuando tenga muchos movimientos de entrada y salida continua, por no necesitar reordenar ni ampliar la cola.

Todo lo que he desarrollado hasta ahora de algoritmos de ordenación y de estructuras de datos está aquí para que lo podáis descargar.

miércoles, 23 de noviembre de 2016

Programación del Sinclair QL (XIV): Estructuras de Datos. Pilas. QuickSort no recursivo



La estructura de datos fundamental

Mezclaré un poco los temas de algoritmos y de estructuras de datos, ya que son los dos aspectos fundamentales de la programación. Comenzamos por la mas usada en todos los ordenadores, las pilas son la base de los lenguajes, tanto nuestro querido Basic como de los modernos lenguajes orientados a objeto, todos usan las pilas para guardar datos de manera temporal.

Imaginemos una pila de platos. Cuando queremos poner un plato lo debemos ubicar siempre encima, y si deseamos sacar un plato siempre lo debemos retirar de la cima. De esta forma podemos ir poniendo y sacando platos de la pila, hasta que la pila se quede vacía, o hasta que ocupe todo el espacio y no pueda creer mas. El primer plato que pongamos en la pila no lo podemos sacar hasta que no hayamos retirado todos los que estén encima, por lo que se dice que el primero en entrar será el último en salir.

En Basic clásico, cuando se encuentra un GOSUB se introduce en la pila la dirección desde la que se ha llamado, y cuando encuentra el RETURN la saca de la pila y salta a la línea siguiente. De esta forma si encuentra varios GOSUB seguidos, introduce las direcciones en la pila, y luego siempre sabe a donde regresar con los RETURN conforme los encuentra. En los lenguajes modernos se usan mucho las pilas para pasar los parámetros de las funciones en las llamadas.

Hay una forma sencilla de crear una pila usando un arreglo y una variable que haga de puntero a la cima. Se inicia el puntero a cero, cuando se añade un elemento se incrementa el puntero y se añade en la posición del arreglo a la que apunta, si se solicita un elemento se leer de la posición apuntada y luego se resta uno. Si el apuntador es cero la pila está vacía. Esta técnica solo requiere saber de antemano el tamaño máximo de la pila, lo que no siempre es posible, pero funciona en cualquier versión del BASIC. En SuperBASIC es sencillo, al existir el elemento cero del arreglo lo usaré para guardar el puntero a la cima. Creo varias funciones para su manejo, una que inicia la pila con un tamaño por defecto, otra que la crea con un tamaño inicial, uno que nos indica si la pila está vacía, la que introduce un valor (en inglés PUSH) y hace crecer el tamaño de la pila si es necesario, la que lee un valor (en inglés POP), una para compactar la pila y reducir su tamaño al mínimo, y una ultima para cambiar el tamaño de la pila, tanto hacia arriba como hacia abajo.

6150 REMark --------------------------------------------------------------
6160 REMark --     PILA_CREAR      -> Crea la pila                      --
6170 REMark --------------------------------------------------------------
6180 DEFine PROCedure PILA_CREAR
6190   REMark Espacio minimo en la pila
6200   LET PILA_FACTOR = 10
6210   DIM ArrPila(PILA_FACTOR)
6220 END DEFine 
6230 :
6240 REMark --------------------------------------------------------------
6250 REMark --     PILA_NUEVA(tam) -> Crea la pila con un tama‰o        --
6260 REMark --------------------------------------------------------------
6270 DEFine PROCedure PILA_NUEVA(tam)
6280   LET PILA_FACTOR = tam
6290   DIM ArrPila(tam)
6300 END DEFine 
6310 :
6320 REMark --------------------------------------------------------------
6330 REMark -- b = PILA_VACIA      -> Ver si la pila esta vacia         --
6340 REMark -- RETORNA: Booleano (Si, No)                               --
6350 REMark --------------------------------------------------------------
6360 DEFine FuNction PILA_VACIA
6370   RETurn NOT ArrPila(0)
6380 END DEFine 
6390 :
6400 REMark --------------------------------------------------------------
6410 REMark --     PILA_PUSH(dato) -> Introduce un dato en la pila, si  --
6420 REMark --                        esta llena crece al doble         --
6430 REMark --------------------------------------------------------------
6440 DEFine PROCedure PILA_PUSH(dato)
6450   IF ArrPila(0) = DIMN(ArrPila) THEN 
6460     PILA_CAMBIA(ArrPila(0)*2)
6470   END IF 
6480   ArrPila(0)=ArrPila(0)+1
6490   ArrPila(ArrPila(0))=dato
6500 END DEFine 
6510 :
6520 REMark --------------------------------------------------------------
6530 REMark -- v = PILA_POP        -> Saca un dato de la pila           --
6540 REMark -- RETORNA: Valor de la cima de la pila                     --
6550 REMark --------------------------------------------------------------
6560 DEFine FuNction PILA_POP
6570   IF PILA_VACIA THEN 
6580     PRINT"Error: Pila vacia"
6590     STOP
6600   END IF 
6610   ArrPila(0)=ArrPila(0)-1
6620   RETurn ArrPila(ArrPila(0)+1)
6630 END DEFine 
6640 :
6650 REMark --------------------------------------------------------------
6660 REMark --     PILA_COMPACTA   -> Compacta la pila                  --
6670 REMark --------------------------------------------------------------
6680 DEFine PROCedure PILA_COMPACTA
6690   PILA_CAMBIA(ArrPila(0)+PILA_FACTOR)
6700 END DEFine 
6710 :
6720 REMark --------------------------------------------------------------
6730 REMark --     PILA_CAMBIAR -> Cambia el tamaño de la pila          --
6740 REMark --------------------------------------------------------------
6750 DEFine PROCedure PILA_CAMBIA(tam)
6760   LOCal b(tam),i
6770   :
6780   FOR i=0 TO tam
6790     IF i > DIMN(ArrPila) THEN EXIT i
6800     b(i)=ArrPila(i)
6810   END FOR i
6820   IF tam < ArrPila(0)  THEN tam=ArrPila(0)+PILA_FACTOR
6830   IF tam < PILA_FACTOR THEN tam=tam+PILA_FACTOR
6840   DIM ArrPila(tam)
6850   FOR i=0 TO tam : ArrPila(i)=b(i)
6860 END DEFine 


La línea 6460 es la que permite hacer crecer la pila si se llena. Hay varias técnica posibles para fijar el tamaño en que se aumentar la pila automáticamente:
  • La mas sencilla es usar in incremento fijo, de forma que cada vez que se llene se aumente su tamaño en ese valor. Funciona si la pila crece pocas veces y en poca cantidad cada vez. Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño + Cantidad. Si elegimos 10 aumenta en forma de 10, 20, 30, 40, 50, 60, 70...
  • Una muy usada es incrementar en un porcentaje del tamaño, de esta forma conforme mas crece el tamaño se va adaptando.  Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño + (Anterior_Tamaño * Porcentaje / 100), si elegimos porcentaje del 50% el crecimiento es 10, 15, 23, 35, 53, 80, 120,...
  • El crecimiento exponencial es sencillo y efectivo, igual que el porcentual intenta crecer mas cuanto mas grande sea el tamaño inicial, se basa en multiplicar el tamaño por un factor, de forma que aumenta mas rápido que usando el porcentual, aunque hay que usarlo con cuidado ya que el tamaño crece muy rápido, pero es bueno si hay pocas ampliaciones. Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño * Factor. En mi rutina uso el factor 2 que es bueno para crecer en un factor 10, 20, 40, 80, 160, 320, 640...
La rutina PILA_CAMBIA es la que permite cambiar el tamaño del arreglo. Como SuperBASIC no permite ampliar el arreglo de manera estándar, es necesario crear un arreglo temporal, copiar la pila en el, cambiar el tamaño de la pila, y volver a copiar el temporal a la pila. Esto cuesta un tiempo, por eso hay que buscar un tamaño de incremento adecuado.

Veamos un uso práctico de la pila, escribiré el algoritmo QuickSort para que en lugar de ser recursivo use la pila para ir guardando inicio y fin de las sublistas, y así cambio el proceso por uno iterativo.

ALGORITMO QuickSort_Pila (arreglo, primero, ultimo)
 
  Pila.Push(primero, ultimo)      
  REPETIR
 
    Pila.Pop(primero, ultimo)   
    REPETIR
      izquierda ← primero
      derecha ← ultimo
      pivote ← ENTERO((primero + ultimo)/2))    
    
      REPETIR
        MIENTRAS arreglo(izquierda) < arreglo(pivote) 
          izquierda ← izquierda + 1
        FIN_MIENTRAS
        MIENTRAS arreglo(derecha) > arreglo(pivote) do 
         derecha ← derecha - 1
        FIN_MIENTRAS
        SI izquierda <= derecha ENTONCES
          SI izquierda <> derecha ENTONCES
            INTERCAMBIA_ELEMENTOS(izquierda, derecha)
          FIN_SI       
          izquierda ← izquierda + 1
          derecha ← derecha - 1
        FIN_SI
      HASTA_QUE izquierda >= derecha
      
      SI derecha - primero > ultimo - izquierda ENTONCES 
        SI primero < derecha ENTONCES
          Pila.Push(primero, derecha)
        FIN_SI
        primero ← izquierda
      SI NO
        SI izquierda < ultimo ENTONCES 
          Pila.Push(izquierda, ultimo)
        FIN_SI
        ultimo ← derecha
      FIN_SI
    HASTA_QUE primero >= ultimo
  HASTA_QUE Pila.Vacia 


Esto se traduce muy sencillo a superBASIC, solo hay que tomar nuestra rutina QuickSort y añadirle primero la creación de la pila, introducimos en ella como inicio comienzo y fin, cambiamos la llamada recursiva por introducir inicio y fin de la sublista en la pila, y seguir iterando hasta que la pila quede vacía.

100 DEFine PROCedure Rapida_Pila (arreglo,sentido,primero,ultimo)
110   IF ultimo=0 THEN ultimo=DIMN(arreglo)
120   QsortP arreglo, sentido, primero, ultimo
130 END DEFine 
140 :
150 DEFine PROCedure QsortP (arreglo,sentido,primero,ultimo)
160   LOCal rep_pila,pivote,izquierda,derecha,r1,r2,r3
170   :
180   PILA_CREAR
190   PILA_PUSH primero : PILA_PUSH ultimo
200   REPeat rep_pila
210     :
220     REMark Sacamos en orden inverso al introducido
230     ultimo = PILA_POP : primero = PILA_POP
240     :
250     IF (primero+1 = ultimo) THEN 
260       IF COMPARA(arreglo(primero),arreglo(ultimo),sentido) = 1 THEN 
270         SWAP arreglo(primero),arreglo(ultimo)
280       END IF 
290     ELSE 
300       izquierda = primero
310       derecha = ultimo
320       pivote = INT((primero + ultimo) / 2)
330       :
340       REPeat r1
350         IF (izquierda > pivote) OR (derecha < pivote) THEN EXIT r1
360         REPeat r2
370           IF (izquierda > pivote) THEN EXIT r2
380           IF COMPARA(arreglo(izquierda),arreglo(pivote),sentido)<>-1
390             EXIT r2
400           END IF 
410           izquierda = izquierda + 1
420         END REPeat r2
430         REPeat r3
440           IF (derecha < pivote) THEN EXIT r3
450           IF COMPARA(arreglo(derecha),arreglo(pivote),sentido)<>1
460             EXIT r3
470           END IF 
480           derecha = derecha - 1
490         END REPeat r3
500         SWAP arreglo(izquierda), arreglo(derecha)
510         izquierda = izquierda + 1
520         derecha = derecha - 1
530         IF (izquierda - 1) = pivote THEN 
540           derecha = derecha + 1
550           pivote = derecha
560         ELSE IF (derecha + 1) = pivote THEN 
570           izquierda = izquierda - 1
580           pivote = izquierda
590         END IF 
600       END REPeat r1
610       IF (primero < pivote-1) THEN 
620          PILA_PUSH primero : PILA_PUSH pivote-1
630       END IF 
640       IF (ultimo > pivote+1) THEN 
650         PILA_PUSH pivote+1 : PILA_PUSH ultimo
660       END IF 
670     END IF 
680     IF PILA_VACIA THEN EXIT rep_pila
690   END REPeat rep_pila
700 END DEFine 

martes, 22 de noviembre de 2016

Programación del Sinclair QL (XIII): Ordenación por inserción, el mejor iterativo



Ordenar como un humano

Los algoritmos de inserción ordenan como lo hacemos nosotros. Supongamos que tenemos una serie de papeles con un número cada uno ya ordenados, si los tenemos en la mano para insertar uno buscamos su lugar y lo ponemos sin mas. Si en lugar de uno sobre otros los tenemos dispuestos de forma consecutiva en una mesa, buscamos su lugar, desplazamos todos los elementos mayores para dejarle hueco, y lo ubicamos.

Esto es lo que hace nuestro algoritmo, para un elemento dado, se lo guarda en un temporal, recorre la lista en sentido inverso desde el anterior a su posición hacia el comienzo, si el valor es mayor lo mueve una posición a la derecha y repite el proceso hasta que el elemento sea menor o igual, en ese momento deja de mover y posiciona el elemento en el temporal en su lugar correcto.

ALGORITMO Insercion (arreglo,sentido,primero,ultimo)
  
  BUCLE pivote DESDE primero+1 HASTA ultimo
    temp ← arreglo(pivote)
    pos ← pivote
    REPETIR
      SI (pos-1 < primero) O BIEN (COMPARA(temp,arreglo(pos-1),sentido) = 1) ENTONCES
        SALIR_DE_REPETIR
      FIN SI

      arreglo(pos) ← arreglo(pos-1)
      pos ← pos-1
    FIN REPETIR
    arreglo(pos) ← temp
  FIN BUCLE


Empleo un procedimiento para mover un valor sobre otro, esto me permite diseñar un algoritmo que funciona con cualquier tipo de elementos, no solo un arreglo de enteros, y que este me cuente los movimientos necesarios, igualando la velocidad de las llamadas con el resto de algoritmos. El resultado es el siguiente:

01 DEFine PROCedure Insercion (arreglo,sentido,primero,ultimo)
02   LOCal repetir,pivote,pos,temp
03   :
04   IF ultimo = 0 THEN ultimo=DIMN(arreglo)
05   :
06   FOR pivote = 1 TO ultimo
07     temp = arreglo(pivote)
08     pos = pivote
09     REPeat repetir
10       IF pos-1 < primero THEN EXIT repetir
11       IF COMPARA(temp,arreglo(pos-1),sentido) = 1 THEN 
12         EXIT repetir
13       END IF 
14       :
15       MUEVE arreglo(pos-1),arreglo(pos)
16       pos=pos-1
17     END REPeat repetir
18     MUEVE temp,arreglo(pos)
19   END FOR pivote
20 END DEFine 


Este algoritmo consigue dos mejoras importantes sobre la burbuja, la primera es que mover un elemento requiere un solo paso en lugar de los tres que requiere un intercambio, por lo que el número de movimientos de elementos se reduce, por otro usa el sistema de dividir la lista en sublistas y posicionar los elementos en su lugar, esto es similar a lo que hace el Quicksort, aunque la rutina de intercambio mueve muchas veces los mismos valores mientras que Quicksort minimiza los movimientos. Como este algoritmo es muy muy sencillo, requiere solo una posición auxiliar para guardar un dato, y es bastante mas eficiente que la burbuja, por lo que es el preferido cuando no existe la posibilidad de usar la recursión. También se usa mucho combinado con Quicksort cuando las sublistas tienen ya pocos elementos, momento en que deja de ser eficiente, depende mucho de la máquina, podemos hablar de unos 100 en máquinas rápidas, y como mínimo entre 10 y 20 elementos en máquinas mas lentas.

La variante del señor Shell

He visto mencionar el nombre de este algoritmo queriendo traducir el nombre de su creador, Donald Shell, lo que no es correcto (sería Ordenación de concha o de caparazón). Esta variante es similar a la ordenación por Peine, en lugar de mover elementos separados por una posición lo hace entre elementos separados varias posiciones, pero con la gran ventaja de que va creando sublistas de forma similar a las de Quicksort ya que todos los elementos de la sublista serán mayores que los ubicados a su izquierda y menores que los de su derecha. Reducimos el tamaño de las sublistas en cada paso, hasta que se convierta en 1 y pasa a ser un algoritmo por inserción normal. Como siempre elegir el tamaño de cada sublista es importante para la eficiencia del algoritmo:
  • La propuesta original de Shell es usar f(n+1)=ENTERO(n/2), para una lista de 100 elementos sería 50,25,12,6,3,1 sencillo y directo. Lo mas usado realmente es f(n+1)=ENTERO(n/2.2), con esta pequeña diferencia se ahorran particiones sin mermar la eficiencia, o lo que es lo mismo se emplea f(n+1)=ENTERO(n*5/11) cuando el lenguaje trata mal con decimales
  • La propuesta de Hibbard es de usar f(n)=2n − 1, resultando f(1)=1,f(2)=3,f(3)= 7,f(4)=15,f(5)=31,f(6)=63,f(7)=127. Para una lista de 100 elementos sería calcular la secuencia hasta que sea mayor de 100 e ir usando los elementos, lo que resultaría 63,31,15,7,3,1
  • La propuesta de Sedgewick es la que mejor resultado obtiene pero no es de cálculo muy directo, hay que usar el resultado de ir alternando los valores producidos por dos funciones:
    • f(n) = 9(4n) − 9(2n) + 1          ⇨ f(0)=1,f(1)=19,f(2)=109,f(3)=505,...
    • g(n) = (2n+2) * (2n+2-3) + 1   ⇨ g(0)=5,g(1)=41,g(2)=209,g(3)=929,...
    • La secuencia completa sería 1,5,19,41,109,209,505,929... y para 100 elementos usar 41,19,5,1
El algoritmo general es el siguiente:

ALGORITMO Shell (arreglo,sentido,primero,ultimo)
 
  inc ← ultimo - primero
  REPETIR
    inc ← INT(inc/2.2)
    SI inc <= 2 ENTONCES
      inc=1
    FIN_SI
    
    BUCLE pivote DESDE inc HASTA ultimo
      temp ← arreglo(pivote)
      pos ← pivote
      REPETIR
        SI (pos-inc < primero) O BIEN (COMPARA(temp,arreglo(pos-inc),sentido) = 1) ENTONCES
          SALIR_DE_REPETIR
        FIN SI

        arreglo(pos) ← arreglo(pos-inc)
        pos ← pos-inc
      FIN REPETIR
      arreglo(pos) ← temp
    FIN BUCLE
  HASTA QUE inc=1


Y en nuestro SuperBASIC lo traduzco así, solo se añade un bucle externo al algoritmo básico de inserción.

01 DEFine PROCedure Shell (arreglo,sentido,primero,ultimo)
02   LOCal bucle1,repetir,inc,pivote,pos,temp
03   :
04   IF ultimo = 0 THEN ultimo=DIMN(arreglo)
05   :
06   inc = ultimo - primero
07   REPeat bucle1
08     inc=INT(inc/2.2)
09     IF inc <= 2 THEN inc=1
10     :
11     FOR pivote = inc TO ultimo
12       temp = arreglo(pivote)
13       pos = pivote
14       REPeat repetir
15         IF pos-inc < primero THEN EXIT repetir
16         IF COMPARA(temp,arreglo(pos-inc),sentido) = 1 THEN 
17           EXIT repetir
18         END IF 
19         :
20         MUEVE arreglo(pos-inc),arreglo(pos)
21         pos=pos-inc
22       END REPeat repetir
23       MUEVE temp,arreglo(pos)
24     END FOR pivote
25    IF inc = 1 THEN EXIT bucle1
26   END REPeat bucle1
27 END DEFine 

lunes, 21 de noviembre de 2016

Programación del Sinclair QL (XII): Ordenación por intercambio recursivo, Quicksort de tres vias



Ordenar listas con elementos repetidos

Quicksort produce dos sublistas con los valores menores y mayores al pivote elegido, pero si la lista tiene elementos repetidos, podemos usar una variante del algoritmo denominada de 3 vías, que genera 3 sublistas:

  • Sublista izquierda: elementos menores al pivote
  • Sublista central: elementos iguales al pivote (de al menos hay un elemento)
  • Sublista derecha: elementos mayores al pivote
Como la sublista central está ordenada y correctamente ubicada ya no entra en el juego, y se llama a la rutina de forma recursiva con las sublistas izquierda y derecha. Esta técnica no ralentiza la rutina apenas, por lo que es posible usarla aunque no tenga elementos repetidos. También da origen a una variante en la que se usan dos pivotes para generar tres sublistas, pero no la presentaré pues no aporta demasiado.

ALGORITMO Qsort3 (arreglo, primero, ultimo)

    SI (ultimo &lt;= primero) ENTONCES
      RETurn
    FIN SI 
    
    izquierda ← primero
    derecha ← ultimo
    pivote ← primero
    pos ← primero+1

    MIENTRAS (pos &lt;= derecha) 
      cmp ← COMPARA_ELEMENTOS(pos, pivote)
      SI cmp = -1 ENTONCES
          SWAP arreglo(izquierda),arreglo(pos)
          izquierda←izquierda+1
          pivote←pivote+1
          pos←pos+1
      SI cmp =  0 ENTONCES
          pos←pos+1
      SI cmp = +1 ENTONCES
          INTERCAMBIA_ELEMENTOS(pos, derecha)
          derecha←derecha-1
      FIN SI 
    FIN MIENTRAS

    Qsort3 arreglo, primero, izquierda-1
    Qsort3 arreglo, derecha+1, ultimo

Esto lo convierto a superBASIC con esta rutina con dos mejoras, para optimizar si la lista es de dos elementos los comparo e intercambio directamente si es necesario, así acelero un poco el algoritmo, y solo hago llamadas recursivas si hay elementos en las sublistas, para ahorrar llamadas no necesarias. La segunda optimización es que en lugar de usar el primer elemento como pivote, uso el central y lo pongo como primero antes de empezar, así en caso de listas casi ordenadas o en orden inverso funciona mejor el algoritmo.

17140 DEFine PROCedure Rapida_3vias (arreglo,sentido,primero,ultimo)
17150   IF ultimo=0 THEN ultimo=DIMN(arreglo)
17160   Qsort3 arreglo, sentido, primero, ultimo
17170 END DEFine 
17180 :
17190 :
17200 DEFine PROCedure Qsort3(arreglo, sentido, primero, ultimo)
17210   LOCal izquierda,derecha,pivote,pos,repetir,cmp
17220   :
17230   IF (primero+1 = ultimo) THEN 
17240     IF COMPARA(arreglo(primero),arreglo(ultimo),sentido) &gt; 0 THEN 
17250       SWAP arreglo(primero),arreglo(ultimo)
17260     END IF 
17270   ELSE 
17280     izquierda = primero
17290     derecha = ultimo
17300     pivote = INT((primero+ultimo)/2)
17310     SWAP arreglo(primero),arreglo(pivote)
17320     pivote = primero
17330     pos = primero+1
17340     :
17350     REPeat repetir
17360       IF (pos &gt; derecha) THEN EXIT repetir
17370       cmp = COMPARA(arreglo(pos),arreglo(pivote),sentido)
17380       SELect ON cmp
17390         =-1
17400           SWAP arreglo(izquierda),arreglo(pos)
17410           izquierda=izquierda+1
17420           pivote=pivote+1
17430           pos=pos+1
17440         = 0
17450           pos=pos+1
17460         =+1
17470           SWAP arreglo(derecha),arreglo(pos)
17480           derecha=derecha-1
17490       END SELect 
17500     END REPeat repetir
17510     :
17520     REMark Sublista 1: arreglo[primero..izquierda-1]
17530     REMark Sublista 2: arreglo[izquierda..derecha] = pivote
17540     REMark Sublista 3: arreglo[derecha+1..ultimo]
17550     IF primero &lt; izquierda-1 THEN 
17560       Qsort3 arreglo, sentido, primero, izquierda-1
17570     END IF 
17580     IF ultimo &gt; derecha+1 THEN 
17590       Qsort3 arreglo, sentido, derecha+1, ultimo
17600     END IF 
17610   END IF 
17620 END DEFine


En todas las pruebas que he efectuado el resultado final es que el mejor en tiempos siempre es el algoritmo mas sencillo, que es el segundo de los tres presentados, y usar el elemento central es ligeramente mejor que usar un elemento aleatorio como pivote. Si la lista tiene muchos repetidos, la variante de 3 vías es mejor que las otras, pero si no hay demasiada repetición al ser mas complejo tarda siempre un poco mas. En el caso mejor, el algoritmo con pivote variable genera muchas sublistas de dos elementos, pero al introducir el que esos dos elementos se comparen directamente se acelera el proceso y no se produce ningún intercambio, pero sigue siendo un algoritmo malo en caso de lista casi ordenada o en orden inverso.



He vuelto a modificar la rutina de comparación, ahora paso al enfoque clásico en que se comparan dos valores y se retorna 0 si son iguales, 1 si el primero es mayor y -1 si es menor. Mantengo el uso del parámetro del sentido para mantener al máximo los algoritmos originales, aunque ya no hace falta con este nuevo enfoque, lo cambiaré en breve:

3560 DEFine FuNction COMPARA(a,b,sentido)
3570   :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+3
3580   IF sentido=0 THEN 
3590     IF a &lt; b THEN RETurn -1
3600     IF a = b THEN RETurn  0
3610     IF a &gt; b THEN RETurn +1
3620   ELSE 
3630     IF a &gt; b THEN RETurn -1
3640     IF a = b THEN RETurn  0
3650     IF a &lt; b THEN RETurn +1
3660   END IF 
3670 END DEFine


Y aquí os dejo los ficheros modificados, como siempre solo hay que cargar y ejecutar om_carga para que monte todo el sistema y lance los algoritmos.

jueves, 17 de noviembre de 2016

Programación del Sinclair QL (XI): Ordenación por intercambio recursivo, mas sobre el Quicksort



Mas consideraciones sobre el Pivote

La elección de un mal pivote es lo que mas ralentiza el algoritmo, en la anterior entrada usé un algoritmo que busca un pivote según recorre los elementos, lo que funciona bien cuando la lista es aleatoria, pero mal cuando esta casi ordenada pues tiende a hacer muchas listas de un solo elemento, lo que al final hace que el algoritmo sea muy ineficiente.

Otra cosa que dije es que el mejor pivote es el valor medio de la lista, lo que es cierto solo si los elementos están distribuidos en la lista de forma regular, si por ejemplo nos encontramos con esta lista [10,3,15,300,9] el valor medio es 67'4, usándolo como pivote obtenemos [10,3,15,9] [300] lo que produce sublistas de un elemento, que es malo para el algoritmo.

Veamos un enfoque mixto, usaremos como Pivote el elemento central de la lista inicialmente, pero conforme avancemos lo podemos ir variando si encontramos uno mas adecuado. Podemos cambiar el uso del central por uno aleatorio sin problemas.

ALGORITMO PROCedure Qsort (arreglo,sentido,primero,ultimo)
     izquierda ← primero
     derecha ← ultimo
     pivote ← INT((primero + ultimo) / 2) 

     MIENTRAS (izquierda <= pivote) Y (derecha >= pivote)
       MIENTRAS (izquierda <= pivote) Y (arreglo(izquierda) < arreglo(pivote))
         izquierda ← izquierda + 1
       FIN MIENTRAS
       MIENTRAS (derecha >= pivote) Y (arreglo(derecha) > arreglo(pivote))
         derecha ← derecha - 1
       FIN MIENTRAS
       
       INTERCAMBIA_ELEMENTOS(izquierda, derecha)
       
       izquierda ← izquierda + 1
       derecha ← derecha - 1
       SI (izquierda - 1) = pivote ENTONCES 
         derecha ← derecha + 1
         pivote ← derecha
       SI NO
         SI (derecha + 1) = pivote ENTONCES
           izquierda ← izquierda - 1
           pivote ← izquierda
         FIN SI
       FIN SI 
     FIN MIENTRAS
     
     SI (primero < pivote-1) ENTONCES 
       QsortM arreglo,sentido,primero ,pivote-1,aleatorio
     FIN SI 
     SI (ultimo > pivote+1) ENTONCES 
       QsortM arreglo,sentido,pivote+1,ultimo  ,aleatorio
     FIN SI 

Como vemos el algoritmo es casi el mismo, cambia el que estemos usando desde el principio el valor del pivote para la división de las sublistas, en lugar de buscar el punto de cruce para elegir uno, y luego ya lo usaremos o cambiaremos segun lo que nos vamos encontrando. En la implementación uso una pequeña mejora, si la sublista tiene dos elementos, directamente los compare y busco su orden en lugar de meterme en el algoritmo de nuevo.

15140 DEFine PROCedure Rapida_Medio (arreglo,sentido,primero,ultimo,aleatorio)
15150   IF ultimo=0 THEN ultimo=DIMN(arreglo)
15160   QsortM arreglo, sentido, primero, ultimo,aleatorio
15170 END DEFine 
15180 :
15190 :
15200 DEFine PROCedure QsortM (arreglo,sentido,primero,ultimo,aleatorio)
15210   LOCal pivote,izquierda,derecha
15220   :
15230   IF (primero+1 = ultimo) THEN 
15240     IF compara(arreglo(primero),arreglo(ultimo),sentido,No) THEN 
15250       SWAP arreglo(primero),arreglo(ultimo)
15260     END IF 
15270   ELSE 
15280     izquierda = primero
15290     derecha = ultimo
15291     if aleatorio then
15292       pivote = rnd(primero,ultimo)
15293     else
15300       pivote = INT((primero + ultimo) / 2)
15301     end if
15310     :
15320     REPeat r1
15330       IF (izquierda > pivote) OR (derecha < pivote) THEN EXIT r1
15340       REPeat r2
15350         IF (izquierda > pivote) THEN EXIT r2
15360         IF compara(arreglo(izquierda),arreglo(pivote),sentido,Si)
15370           EXIT r2
15380         END IF 
15390         izquierda = izquierda + 1
15400       END REPeat r2
15410       REPeat r3
15420         IF (derecha < pivote) THEN EXIT r3
15430         IF compara(arreglo(derecha),arreglo(pivote),NOT sentido,Si)
15440           EXIT r3
15450         END IF 
15460         derecha = derecha - 1
15470       END REPeat r3
15480       SWAP arreglo(izquierda), arreglo(derecha)
15490       izquierda = izquierda + 1
15500       derecha = derecha - 1
15510       IF (izquierda - 1) = pivote THEN 
15520         derecha = derecha + 1
15530         pivote = derecha
15540       ELSE IF (derecha + 1) = pivote THEN 
15550         izquierda = izquierda - 1
15560         pivote = izquierda
15570       END IF 
15580     END REPeat r1
15590     IF (primero < pivote-1) THEN 
15600       QsortM arreglo,sentido,primero ,pivote-1,aleatorio
15610     END IF 
15620     IF (ultimo > pivote+1) THEN 
15630       QsortM arreglo,sentido,pivote+1,ultimo  ,aleatorio
15640     END IF 
15650   END IF 
15660 END DEFine 

Se usa una función para comparar y otra para intercambiar valores, he modificado los algoritmos para las todos las usen, así simplifico su código y hago que la comparación es posible entre todos al usar la misma llamada siempre, ver el código de las funciones de intercambio iterativas que adjunto al final.

3371 Remar ----------------------------------------
3372 Remar -- Intercambia dos valores            --
3373 Remar ----------------------------------------
3380 DEFine PROCedure SWAP (a,b)
3390   :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
3400   t=a
3410   a=b
3420   b=t
3430 END DEFine 
3440 :
3450 :
3460 Remar ----------------------------------------
3470 Remar -- FUNCION que compara dos números    --
3480 Remar --   a,b     -> Numeros a comparar    --
3490 Remar --   sentido -> 0=Ascendente          --
3500 Remar --   igual   -> Si es por igual o no  --
3510 Remar ----------------------------------------
3520 DEFine FuNction compara(a,b,sentido,igual)
3530   :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
3540   IF igual THEN 
3550     IF sentido=Ascendente THEN 
3560       IF a >= b THEN RETurn Si
3570     ELSE 
3580       IF a <= b THEN RETurn Si
3590     END IF 
3600   ELSE 
3610     IF sentido=Ascendente THEN 
3620       IF a > b THEN RETurn Si
3630     ELSE 
3640       IF a < b THEN RETurn Si
3650     END IF 
3660   END IF 
3670   :
3680   RETurn No
3690 END DEFine 


La comparación entre los tres algoritmos nos da cifras muy buenas para el caso medio, como vemos casi iguales en todos, pero el buscar el puntero de forma dinámica desde el principio ralentiza el algoritmo en los casos mejor y peor, ya que tiende a producir muchas sublistas de 1 solo elemento.



Aquí tenéis los nuevos módulos, he cambiado un poco algunas cosas, por ejemplo en el proceso base he incluido la línea 1 GOTO 1000 que consigue que haciendo un RUN todo funcione sin necesidad de borrar las líneas del proceso de carga. Para que funcione cargar y ejecutar el fichero om_carga.

martes, 15 de noviembre de 2016

Programación del Sinclair QL (X): Ordenación por intercambio recursivo, Quicksort



El mejor es hijo del peor

El mejor algoritmo de ordenación es una variante de la Burbuja, solo que intenta mover los elementos lo mas cerca posible de su ubicación definitiva en lugar de moverlos una posición a la vez, por lo que reduce los intercambios al mínimo.

El algoritmo lo que hace es tomar un elemento de la lista como un pivote. Luego mueve todos los elementos de forma que los de su izquierda sean todos menores que el pivote, y los de su derecha sean todos mayores que el pivote, creando dos sublistas que se pueden ordenar independientemente.

Una vez elegido el pivote se usan dos índices, uno recorre la lista desde su inicio hacia el final buscando un elemento que sea mayor que el pivote, luego se recorre con otro puntero desde el último hacia el inicio buscando uno que sea menor que el pivote, una vez localizados los intercambia. Se siguen buscando elementos de la misma manera hasta que se crucen los punteros. De esta forma se reduce al máximo los intercambios que son una parte muy pesada del algoritmo.

El resultado es que tenemos una sublista izquierda de elementos menores que el pivote, el pivote colocado en su lugar definitivo, y otra sublista derecha de elementos mayores que el pivote. Como ambas sublistas son independientes podemos llamar de manera recursiva al algoritmo con cada una de ellas para que las ordene a su vez. El pivote no tiene porque estar incluido en la lista, ya que lo que pretendemos es obtener dos sublistas.

La elección del pivote es importante para intentar optimizar al máximo el algoritmo, si se eligen mal el algoritmo se ralentiza mucho por lo que el objetivo es que las dos sublistas sean del mismo tamaño, contra mas equilibrado esté mejor eficiencia tendrá el algoritmo. Supongamos que tenemos esta lista [2,5,1,9,7] y vamos a buscar un pivote:

  • El optimo sería el 5 que resultaría en dos pasos [2,1] [5] [9,7] ⇨ [1] [2] [5] [7] [9], pero sin analizar los datos no podemos conocer que ese es el mejor elemento.
  • Primer elemento, 2 en el ejemplo: [1] [2] [5,9,7] ⇨ [1] [2] [5] [9,7] ⇨ [1] [2] [5] [7] [9]
  • Ultimo elemento, 7 en el ejemplo: [2,5,1] [7] [9] ⇨ [1] [2,5] [7] [9] ⇨ [1] [2] [5] [7] [9]
  • Elemento central, 1 en el ejemplo: [-] [1] [2,5,9,7] ⇨ [1] [2] [5] [9,7] ⇨ [1] [2] [5] [7] [9]


Como vemos aunque el ejemplo es muy sencillo solo eligiendo un buen elemento como pivote se optimizan los pasos. Se han buscado varios sistemas para localizar los pivotes, todos pensando que tras los primeros pasos del algoritmo las listas están ya bastante ordenadas:

  • El sistema mas sencillo es usar el elemento central de la lista, en el ejemplo sería usar como pivote el [1] que hemos visto está lejos de la mejor opción, pero tras varias pasadas se aproximaría bastante. También podemos elegir un elemento al azar, esta técnica es sencilla de usar y elegir un elemento cualquiera aunque no lo parezca da buenos resultados en general, el azar tiende a compensar las cosas.
  • Lo mejor sería usar el valor medio que es 4'8, y en nuestro ejemplo queda [2,1] [5,9,7] ⇨ [1] [2] [5] [7] [9], pero su cálculo con muchos elementos ralentiza el algoritmo. Una variante es pensar que la lista esta bastante ordenada, lo que hemos visto que es cierto tras los primeros pasos del algoritmo, y tomar tres elementos de la lista calculando su media. Los elementos serían primero, central y ultimo. En nuestro ejemplo sería (2+1+7)/3 = 3'33 que también es buen valor.
  • El medio mas usado es un pivote variable, se comparan los elementos a izquierda y derecha hasta que haya que intercambiarlos, cambiando el pivote en ese momento, y se sigue comparando y cambiando el pivote, hasta que se crucen los índices, momento en que el elemento que marcan será el pivote.


ALGORITMO Qsort (lista,sentido[Ascendente|Descendente],primero,ultimo)

  izquierda ← primero
  derecha ← ultimo
  pivote ← izquierda

  REPETIR
    SI ((sentido = Ascendente) Y (lista(izquierda) > lista(derecha))) O BIEN
       ((sentido = Descendente) Y (lista(izquierda) < lista(derecha))) ENTONCES

      INTERCAMBIA_ELEMENTOS(izquierda,derecha)
      SI pivote = izquierda ENTONCES
        izquierda ← izquierda+1
        pivote ← derecha
      SI NO
        derecha ← derecha-1
        pivote ← izquierda
      FIN SI
    SI NO
      SI pivote = izquierda ENTONCES
        derecha ← derecha-1
      SI NO
        izquierda ← izquierda+1
      FIN SI
    FIN SI
  HASTA QUE izquierda >= derecha

  SI primero <> pivote ENTONCES
    qsort arreglo, primero, pivote-1
  FIN SI
  SI ultimo <> pivote ENTONCES
    qsort arreglo, pivote+1, ultimo
  FIN SI


Para mejorar la velocidad del algoritmo hay que reducir las llamadas recursivas, para lo que se suele emplear un enfoque mixto, en lugar de iterar hasta el final hacerlo hasta que las sublistas sean de pocos elementos, pueden ser entre 5 y 10 en máquinas lentas, o llegar al centenar en rápidas, y luego aplicar otro sistema de ordenación a los resultados que ya están casi ordenados, usualmente se usa la inserción. Pero voy con la rutina de Qsort hasta el final, para que sea comparable:

14130 DEFine PROCedure Rapida (arreglo,sentido,primero,ultimo)
14140   IF ultimo=0 THEN ultimo=DIMN(arreglo)
14150   Qsort arreglo, sentido, primero, ultimo
14160 END DEFine
14170 :
14180 :
14190 DEFine PROCedure Qsort (arreglo,sentido,primero,ultimo)
14200   LOCal repetir, izquierda, derecha, pivote
14210   :
14220   izquierda = primero
14230   derecha = ultimo
14240   pivote = primero
14250   :
14260   REPeat repetir
14270     IF izquierda >= derecha : EXIT repetir
14280     :
14290     :: nrocomp(nrutina,nropaso)=nrocomp(nrutina,nropaso)+1
14300     cambiar=No
14310     IF sentido=Ascendente THEN
14320       IF arreglo(izquierda) > arreglo(derecha) THEN cambiar=Si
14330     ELSE
14340       IF arreglo(izquierda) < arreglo(derecha) THEN cambiar=Si
14350     END IF
14360     IF cambiar THEN
14370       :: nromovi(nrutina,nropaso)=nromovi(nrutina,nropaso)+3
14380       temp = arreglo(izquierda)
14390       arreglo(izquierda) = arreglo(derecha)
14400       arreglo(derecha) = temp
14410       :
14420       IF pivote = izquierda
14430         izquierda = izquierda+1
14440         pivote = derecha
14450       ELSE
14460         derecha = derecha-1
14470         pivote = izquierda
14480       END IF
14490     ELSE
14500       IF pivote =izquierda
14510         derecha = derecha -1
14520       ELSE
14530         izquierda = izquierda+1
14540       END IF
14550     END IF
14560   END REPeat repetir
14570   :
14580   IF primero <> pivote THEN
14590     Qsort arreglo, sentido, primero, pivote-1
14600   END IF
14610   IF ultimo <> pivote THEN
14620     Qsort arreglo, sentido, pivote+1, ultimo
14630   END IF
14640 END DEFine Qsort


Resultado del QuickSort

En el caso medio el resultado es espectacular en comparación con la burbuja y sus variantes para 200 elementos, ya que en comparación con los 9 minutos y 48 segundos de la variante mas rápida que es la sacudida, con 13227 comparaciones y 28956 intercambios, pasamos a 1minuto y 39 segundos, con 2046 comparaciones y 1362 intercambios. Cuando la lista está ordenada o en orden inverso el resultado ya no es tan bueno, aunque sigue siendo mejor que la burbuja.

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.