miércoles, 7 de diciembre de 2016

Programación del Sinclair QL (XVIII): Ordenación por inserción usando una lista enlazada



Como ya tenemos las rutinas de manejo de las listas enlazadas con sus elementos ordenados, la voy a usar como algoritmo de ordenación general, simplemente tomo los algoritmos de lista enlazada y los simplifico al máximo, creo la lista con tamaño exacto para los elementos a ordenar, la relleno, y luego la recorro modificando el arreglo original, y al final resultando un algoritmo muy sencillo, aunque para ordenar una lista necesita otras dos adicionales, por lo que gasta bastante más memoria.

ALGORITMO Insercion_lista (arreglo, primero, ultimo)
 
  raiz ← null  
  tamaño ← ultimo - primero + 1
  CREAR_ARREGLO Datos(tamaño)
  CREAR_ARREGLO Enlaces(tamaño)

  BUCLE i DESDE primero HASTA ultimo
    LISTA_ORDENADA_INSERTAR(arreglo(i), Datos, Enlaces, raiz)
  FIN BUCLE
    
  pos ← raiz
  BUCLE i DESDE primero HASTA ultimo
    arreglo(nro) ← Datos(pos)
    pos ← Enlaces(pos)
  FIN BUCLE

ALGORITMO LISTA_ORDENADA_INSERTAR (valor, ListaDatos, ListaNodos, NodoRaiz)
 
   // Busco un nodo libre
   nro ← BUSCAR_ELEMENTO_LIBRE
   SI nro = NULL ENTONCES
      ERROR No hay espacio libre
      SALIR DEL ALGORITMO
   FIN SI

   // Ubico el elemento
   ListaDatos(nro) = Valor

   // Si es el primer nodo lo ubico en la raiz
   SI (NodoRaiz ES NULO) ENTONCES 
     ListaNodos(nro) ← NULL
     NodoRaiz ← nro
   FIN SI
 
   // Si no es el primero buscamos su posición
   SI (NodoRaiz NOES NULO) ENTONCES  
     pos ← NodoRaiz  // Nodo por el que vamos
     ant ← NULL      // Nodo anterior al que vamos
     REPETIR
       encontrado ← Falso 
       
       // Si he encontrado un elemento mayor o igual, debo ubicarlo antes
       SI (ListaDatos(pos) ≥ Valor) ENTONCES 
         // Si es el primer elemento, hay que ubicarlo en la raiz
         SI (ant ES NULO) ENTONCES 
           ListaNodos(nro) ← NodoRaiz
           NodoRaiz        ← nro
           encontrado      ← Cierto 
         FIN SI
  
         // Si no es el primer elemento, hay que ubicarlo tras el anterior
         SI (ant NOES NULO) ENTONCES 
           ListaNodos(nro) ← ListaNodos(ant)
           ListaNodos(ant) ← nro
           encontrado      ← Cierto 
         FIN SI
       FIN SI
       
       // Si se ha llegado al final se pone el último
       SI (ListaNodos(pos) ES NULO) ENTONCES 
         ListaNodos(pos) ← nro
         ListaNodos(nro) ← NULL
         encontrado      ← Cierto
      END IF 
      
      //No encontrado seguimos iterando
      SI (NO encontrado) ENTONCES 
        ant ← pos
        pos ← ListaNodos(pos)
      FIN SI
     HASTA QUE (encontrado)
   FIN SI 


Aquí el programa completo en SuperBASIC correspondiente, son las rutinas desarrolladas en el manejo de listas pero simplificadas al máximo dejando solo lo necesario. Para gastar un poco menos de memoria y optimizar algo las velocidades (aunque en SuperBASIC la velocidad no se nota por su forma de trabajar), habría que hacer que la lista de punteros sea de enteros en lugar de reales. De momento no lo voy a hacer así.

20000 REMark ---------------------------------------------
20010 REMark -- ALGORITMOS DE ORDENACION                --
20020 REMark --   Modulo....: Insercion con lista       --
20030 REMark --   Objetivo..: Ordena un arreglo usando  --
20040 REMark --               enlazada                  --
20050 REMark --   Autor.....: javu61, 12/2016           --
20060 REMark --   Parametros:                           --
20070 REMark --     arreglo -- Arreglo a ordenar        --
20080 REMark --     sentido -- FALSO = Ascendente       --
20090 REMark --     primero -- primer elemento          --
20100 REMark --     ultimo  -- ultimo elemento          --
20110 REMark --                Si ultimo=0 -- Todos     --
20120 REMark ---------------------------------------------
20130 DEFine PROCedure Insercion_Lista (arreglo,sentido,primero,ultimo)
20140   LOCal pos,nro
20150   :
20160   IF ultimo = 0 THEN ultimo=DIMN(arreglo)
20170   :
20180   REMark Crear los elementos de la lista
20190   LET L_NULO   = -1        : REMark Puntero nulo
20200   LET L_RAIZ   = L_NULO    : REMark Puntero al nodo raiz
20210   DIM ArrPuntero(ultimo-primero) : REMark Puntero siguiente elemento
20220   DIM ArrLista(ultimo-primero)   : REMark Elementos de la lista
20230   :
20240   REMark Rellenar la lista
20250   FOR pos = primero TO ultimo : LISTA_ADD pos,arreglo(pos),sentido
20260   :
20270   REMark A partir de la lista montar el arreglo ordenado
20290   FOR nro=primero TO ultimo
20300     MUEVE ArrLista(L_RAIZ), arreglo(nro)
20310     L_RAIZ= ArrPuntero(L_RAIZ)
20320   END FOR nro
20330 END DEFine 
20340 :
20350 REMark -------------------------------------------------------------
20360 REMark -- LISTA_ADD(dato) -- Introduce un dato en la lista        --
20370 REMark -------------------------------------------------------------
20380 DEFine PROCedure LISTA_ADD(nro,dato,sentido)
20390   LOCal repetir,pos,ant
20400   :
20410   REMark Ubico el elemento
20420   ArrLista(nro) = dato
20430   :
20440   REMark Si es el primer nodo, lo ubico en la raiz
20450   IF L_RAIZ = L_NULO THEN 
20460     ArrPuntero(nro) = L_NULO
20470     L_RAIZ = nro
20480   ELSE 
20490     REMark Si no es el primero, buscamos su posición recorriendo
20500     pos = L_RAIZ
20510     ant = L_NULO
20520     REPeat repetir
20530       REMark Si he econtrado su posición
20540       IF COMPARA(ArrLista(pos), dato, sentido) >= 0 THEN 
20550         REMark Segun sea ahora el primer elemento o no
20560         IF ant = L_NULO THEN 
20570           ArrPuntero(nro) = L_RAIZ
20580           L_RAIZ = nro
20590         ELSE 
20600           ArrPuntero(nro) = ArrPuntero(ant)
20610           ArrPuntero(ant) = nro
20620         END IF 
20630         EXIT repetir
20640       END IF 
20650       REMark Si he llegado al final, lo añado como utimo elemento
20660       IF ArrPuntero(pos)=L_NULO THEN 
20670         ArrPuntero(pos) = nro
20680         ArrPuntero(nro) = L_NULO
20690         EXIT repetir
20700       END IF 
20710       ant = pos
20720       pos = ArrPuntero(pos)
20730     END REPeat repetir
20740   END IF 
20750 END DEFine 
20760 :
20770 :


Las pruebas de las rutinas de ordenación por inserción desarrolladas hasta el momento dan el siguiente resultado con 50 elementos, vemos que Shell es el mas rápido en el caso medio y es bastante bueno para listas ordenadas o en orden inverso, además no requiere mucha memoria. La inserción pura y la inserción con lista enlazada tardan mas o menos lo mismo en el caso medio, ya que son muy similares en cuanto a la cantidad de elementos a recorrer para insertar uno en su lugar, pero por su forma de trabajar la inserción pura es la mas rápida para listas ordenadas mientras la de lista enlazada es la peor, y para listas en orden inverso se cambian las tornas.



He dividido los programas en dos grupos, aquí todo lo desarrollado sobre estructuras de datos y sus pruebas hasta el momento, y aquí todo lo desarrollado sobre ordenación hasta el momento.

lunes, 5 de diciembre de 2016

Programación del Sinclair QL (XVII): Estructuras de Datos. Listas enlazadas



Las listas enlazadas son las estructuras mas útiles, ya que sirven para casi todo. La estructura en sencilla, un registro se divide en dos partes, una con los datos que se necesitan guardar, y otro con un enlace al siguiente registro de datos. De esta manera no es necesario que los registros estén en posiciones consecutivas.

No voy a explicar mucho mas de las listas, hay suficiente información en la Web sobre ellas, presento un pequeño esquema de lo que es una lista enlazada, y las operaciones básicas de inserción de elementos en ellas:


Las listas pueden estar ordenadas por el criterio que se desee, en este caso yo voy a usar el mantener la lista en orden creciente de sus datos, así me sirve como rutina de ordenación, pero esto no es imprescindible y se pueden usar listas ordenadas con el criterio que se desee, por ejemplo para construir una cola se emplea una lista en la que se introducen elementos por el principio de la misma y se extraen por el final (o al contrario)

Para hacerlo sencillo en nuestro SuperBASIC usaré en esta ocasión arreglos para implementar nuestra lista, ya mas adelante hablaremos del manejo de la memoria. Voy a usar dos arreglos para almacenar los datos, en uno me guardo los datos del registro (en este caso será una lista de números, pero puede ser cambiado de manera sencilla a una lista de cadenas por ejemplo), y otro arreglo numérico con los enlaces, que inicio con un valor que indica que el nodo está vacío, así es muy sencillo encontrar elementos libres conforme crece el tamaño de la lista y se han ido añadiendo y retirando elementos. Esta técnica no es la mas eficiente, pero si sencilla. Además, hay unas variables auxiliares para guardar la cabecera entre otras cosas.

1000 REMark --------------------------------------------------------------
1010 REMark -- ESTRUCTURAS DE DATOS                                     --
1020 REMark --   Modulo....: Lista encadenada ordenada                  --
1030 REMark --   Objetivo..: Lista encadenada usando un arreglo de dos  --
1040 REMark --               dimensiones: 0 elementos, 1 punteros       --
1050 REMark --   Autor.....: javu61, 11/2016                            --
1060 REMark --   Procesos..:                                            --
1070 REMark --     LISTA_CREAR      -- Crear la lista                   --
1080 REMark --     LISTA_NUEVA(tam) -- Crea la lista con un tama‰o      --
1090 REMark --     b=LISTA_LEN      -- Nro de elementos de la lista     --
1100 REMark --     LISTA_ADD(dato)  -- Introduce un dato en la lista    --
1110 REMark --     LISTA_DELETE(n)  -- Borra el elemento n de la lista  --
1120 REMark --     v=LISTA_VER(n)   -- Muestra elemento n de la lista   --
1130 REMark --     b=LISTA_BUSCAR(n)-- Busca un elemento en la lista    --
1140 REMark --     LISTA_CAMBIA(tam)-- Cambia el tama‰o de la lista     --
1150 REMark --   Procesos de uso interno:                               --
1160 REMark --     LISTA_INIT       -- Inicializa una lista             --
1170 REMark --     b=LISTA_EL_LIBRE -- Retorna elemento libre           --
1180 REMark --   Elementos.: Se usan los siguientes elementos globales  --
1190 REMark --     L_FACTOR        -- Factor de crecimiento             --
1200 REMark --     ArrLista(tam)   -- Elementos de la lista             --
1210 REMark --     ArrPuntero(tam) -- Puntero al siguiente elemento     --
1220 REMark --     L_NULO          -- Puntero nulo                      --
1230 REMark --     L_VACIO         -- Puntero vacio                     --
1240 REMark --     L_RAIZ          -- Puntero al nodo raiz              --
1250 REMark --     L_NRO           -- Nro de elementos de la lista      --
1260 REMark --------------------------------------------------------------
1270 :
1280 :
1290 REMark --------------------------------------------------------------
1300 REMark -- LISTA_CREAR -- Crea la lista                             --
1310 REMark --------------------------------------------------------------
1320 DEFine PROCedure LISTA_CREAR
1330   LISTA_NUEVA 9,5 : REMark Espacio para 10 elementos, crece minimo 5
1340 END DEFine 
1350 :
1360 REMark --------------------------------------------------------------
1370 REMark -- LISTA_NUEVA(tam,fac) -- Crea la lista con un tama‰o y un --
1380 REMark --                         factor de crecimiento            --
1390 REMark --------------------------------------------------------------
1400 DEFine PROCedure LISTA_NUEVA(tam,fac)
1410   LET L_FACTOR = fac  : REMark Factor de crecimiento
1420   DIM ArrLista(tam)   : REMark Elementos de la lista
1430   DIM ArrPuntero(tam) : REMark Puntero al siguiente elemento
1440   LISTA_INIT
1450 END DEFine 
1460 :
1470 REMark --------------------------------------------------------------
1480 REMark -- LISTA_INIT -- Inicializa una lista                       --
1490 REMark --------------------------------------------------------------
1500 DEFine PROCedure LISTA_INIT
1510   LOCal i
1520   :
1530   LET L_NULO  = -1     : REMark Puntero nulo
1540   LET L_VACIO = -2     : REMark Puntero vacio
1550   L_RAIZ      = L_NULO : REMark Puntero al nodo raiz
1560   L_NRO       = 0      : REMark Nro de elementos de la lista
1570   :
1580   REMark Inicializa lista de elementos libres
1590   FOR i=0 TO DIMN(ArrPuntero)
1600     ArrPuntero(i) = L_VACIO : REMark elemento vacio
1610   END FOR i
1620 END DEFine 
1630 :
1640 REMark --------------------------------------------------------------
1650 REMark -- b = LISTA_LEN -- Retorna el nro de elementos de la lista --
1660 REMark -- RETORNA: 0 si vacia, >0 = nro de elementos               --
1670 REMark --------------------------------------------------------------
1680 DEFine FuNction LISTA_LEN
1690   RETurn L_NRO
1700 END DEFine 
1710 :
1720 REMark --------------------------------------------------------------
1730 REMark -- b = LISTA_EL_LIBRE -- Retorna elemento libre de la lista --
1740 REMark -- RETORNA:  <0 no hay libres, >=0 nro del elemento         --
1750 REMark --------------------------------------------------------------
1760 DEFine FuNction LISTA_EL_LIBRE
1770   LOCal i
1780   :
1790   FOR i=0 TO DIMN(ArrPuntero)
1800     IF ArrPuntero(i) = L_VACIO THEN RETurn i
1810   END FOR i
1820   RETurn L_NULO
1830 END DEFine 
1840 :
1850 REMark --------------------------------------------------------------
1860 REMark -- b = LISTA_BUSCAR(valor) -- Busca un elemento en la lista --
1870 REMark -- RETORNA:  nro del elemento o NULO si no encontrado       --
1880 REMark --------------------------------------------------------------
1890 DEFine FuNction LISTA_BUSCAR(valor)
1900   LOCal nro,repetir
1910   :
1920   nro = L_NULO
1930   IF L_NRO THEN 
1940     nro = L_RAIZ
1950     REPeat repetir
1960       IF ArrLista(nro) = valor    THEN EXIT repetir
1970       IF ArrLista(nro) > valor    THEN nro = L_NULO : EXIT repetir
1980       IF ArrPuntero(nro) = L_NULO THEN nro = L_NULO : EXIT repetir
1990       nro = ArrPuntero(nro)
2000     END REPeat repetir
2010   END IF 
2020   RETurn nro
2030 END DEFine 
2040 :
2050 :
2060 REMark --------------------------------------------------------------
2070 REMark -- LISTA_ADD(dato) -- Introduce un dato en la lista, si     --
2080 REMark --                    esta llena crece al doble             --
2090 REMark --------------------------------------------------------------
2100 DEFine PROCedure LISTA_ADD(dato)
2110   LOCal repetir,nro,pos,ant
2120   :
2130   REMark Busco nodo libre, crece si hace falta y ubico el elemento
2140   REPeat repetir
2150     nro = LISTA_EL_LIBRE
2160     IF nro <> L_NULO THEN EXIT repetir
2170     LISTA_CAMBIA(DIMN(ArrLista)*2)
2180   END REPeat repetir
2190   ArrLista(nro) = dato
2200   :
2210   REMark Si es el primer nodo, lo ubico en la raiz
2220   IF L_RAIZ = L_NULO THEN 
2230     ArrPuntero(nro) = L_NULO
2240     L_RAIZ = nro
2250   ELSE 
2260     REMark Si no es el primero, buscamos su posici–n recorriendo
2270     pos = L_RAIZ
2280     ant = L_NULO
2290     REPeat repetir
2300       REMark Si he econtrado su posici–n
2310       IF (ArrLista(pos) >= dato) THEN 
2320         REMark Seg™n sea ahora el primer elemento o no
2330         IF ant = L_NULO THEN 
2340           ArrPuntero(nro) = L_RAIZ
2350           L_RAIZ = nro
2360         ELSE 
2370           ArrPuntero(nro) = ArrPuntero(ant)
2380           ArrPuntero(ant) = nro
2390         END IF 
2400         EXIT repetir
2410       END IF 
2420       REMark Si he llegado al final, lo a‰ado como utimo elemento
2430       IF ArrPuntero(pos)=L_NULO THEN 
2440         ArrPuntero(pos) = nro
2450         ArrPuntero(nro) = L_NULO
2460         EXIT repetir
2470       END IF 
2480       ant = pos
2490       pos = ArrPuntero(pos)
2500     END REPeat repetir
2510   END IF 
2520   REMark Sumo un elemento a la lista
2530   L_NRO = L_NRO + 1
2540   :
2550 END DEFine 
2560 :
2570 REMark --------------------------------------------------------------
2580 REMark -- v = LISTA_VER(n) -- Muestra el elemento n de la lista    --
2590 REMark -- RETORNA: Valor del elemento                              --
2600 REMark --------------------------------------------------------------
2610 DEFine FuNction LISTA_VER(nro)
2620   LOCal pos,i
2630   :
2640   IF LISTA_LEN = 0 THEN 
2650     PRINT"Error: Lista vacia"
2660     STOP
2670   END IF 
2680   :
2690   pos = L_RAIZ
2700   FOR i=0 TO nro-1
2710     IF ArrPuntero(pos)=L_NULO THEN 
2720       PRINT "ERROR: No hay tantos elementos"
2730       STOP
2740     END IF 
2750     pos = ArrPuntero(pos)
2760   END FOR i
2770   RETurn ArrLista(pos)
2780 END DEFine 
2790 :
2800 REMark --------------------------------------------------------------
2810 REMark -- LISTA_DELETE(n)  -- Borra el elemento n de la lista      --
2820 REMark --------------------------------------------------------------
2830 DEFine PROCedure LISTA_DELETE(n)
2840   LOCal pos,i
2850   :
2860   IF n < 0 THEN 
2870     PRINT "ERROR: Intenta eliminar elementos negativos"
2880     STOP
2890   END IF 
2900   :
2910   pos = L_RAIZ
2920   ant = L_NULO
2930   FOR i=0 TO n-1
2940     IF ArrPuntero(pos)=L_NULO THEN 
2950       PRINT "ERROR: Intenta eliminar elementos que no existen"
2960       STOP
2970     END IF 
2980     ant = pos
2990     pos = ArrPuntero(pos)
3000   END FOR i
3010   :
3020   IF ant = L_NULO THEN 
3030     L_RAIZ = ArrPuntero(pos)
3040   ELSE 
3050     ArrPuntero(ant)=ArrPuntero(pos)
3060   END IF 
3070   ArrPuntero(pos) = L_VACIO
3080   :: ArrLista(pos)   = 0
3090   :
3100   REMark reducir elementos de la lista
3110   L_NRO = L_NRO - 1
3120 END DEFine 
3130 :
3140 REMark --------------------------------------------------------------
3150 REMark -- LISTA_CAMBIA -- Cambia el tama‰o de la lista             --
3160 REMark --------------------------------------------------------------
3170 DEFine PROCedure LISTA_CAMBIA(tam)
3180   LOCal b(DIMN(ArrLista)),minimo,i,elementos
3190   :
3200   REMark Guardo la lista en el auxiliar de forma compacta
3210   elementos = L_NRO
3220   FOR i=0 TO elementos-1
3230     b(i)=LISTA_VER(i)
3240   END FOR i
3250   :
3260   REMark calculo tama‰os m“nimos
3270   minimo = L_NRO + L_FACTOR
3280   IF tam < minimo   THEN tam = minimo
3290   IF tam < L_FACTOR THEN tam = tam + L_FACTOR
3300   :
3310   REMark Creo la nueva lista y la relleno
3320   LISTA_NUEVA tam,L_FACTOR
3330   :
3340   IF elementos <> 0 THEN 
3350     L_RAIZ = 0
3360     L_NRO  = elementos
3370     FOR i=0 TO elementos-1
3380       ArrLista(i)=b(i)
3390       IF i <> 0 THEN ArrPuntero(i-1) = i
3400       ArrPuntero(i) = L_NULO
3410     END FOR i
3420   END IF 
3430 END DEFine 


Para poder verificar que esta lista enlazada funciona uso un pequeño programa de pruebas, en el se ve siempre la lista y sus enlaces, los punteros nulos, los elementos libres, etc. Tras cada prueba se presentan los elementos que componen la lista, en la que se debe verificar que todos están ordenados.

100 REMark ----------------------------------------
110 REMark -- Manejo de errores                  --
120 REMark ----------------------------------------
130 WHEN ERRor 
140   PRINT "Se ha producido un error ";ERNUM;' en la linea ';ERLIN;" "
150   REPORT #1,ERNUM
160   STOP
170 END WHEN 
180 :
190 MODE 4: PAPER 0 : CLS
200 n$="mdv1_ed_lista_arreglo"
210 PRINT "Cargando ";n$
220 MERGE n$
230 :
240 REMark ----------------------------------------
250 REMark -- Rutinas de pruebas                 --
260 REMark ----------------------------------------
270 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1
280 p2$=""
290 t1=DATE
300 :
310 PRINT "Creacion de la lista"
320 LISTA_CREAR : ver : PRINT
330 :
340 PRINT "PRUEBA 1: Introduce elementos en orden, inversos y aleatorios"
350 LISTA_CREAR : FOR i=1 TO 3 : mete(i)
360 verlista
370 LISTA_CREAR : FOR i=3 TO 1 STEP -1 : mete(i)
380 verlista
390 LISTA_CREAR : FOR i=1 TO 5 : mete(RND(1 TO 9))
400 verlista
410 :
420 PRINT "PRUEBA 2: Introduce 9, elimina 5, introduce 3, elimina 4"
430 LISTA_CREAR
440 FOR i=1 TO 9   : mete(i)
450 FOR i=1 TO 5   : borra(0)
460 FOR i=10 TO 12 : mete(i)
470 FOR i=1 TO 3   : borra(i)
480 verlista
490 :
500 PRINT "PRUEBA 3: Introduce 9, Extrae 2, introduce 10 y reduce"
510 LISTA_CREAR
520 FOR i=1 TO 9   : mete(i)
530 FOR i=1 TO 2   : borra(i)
540 FOR i=10 TO 19 : mete(i)
550 verlista
560 PRINT "CM "; : LISTA_CAMBIA 0 : ver
570 verlista
580 :
590 PRINT "PRUEBA 4: Buscar algunos elementos"
600 FOR i= 0 TO 3 STEP 3 : PRINT "BUSCO ";i;" = ";LISTA_BUSCAR(i)
610 PRINT
620 :
630 PRINT "PRUEBA 5: Extrae elementos hasta error por vacia"
640 FOR i=1 TO 17  : borra(0)
650 t2=DATE
660 PRINT "Tard– ";t2-t1;" segundos"
670 borra(0)
680 STOP
690 :
700 DEFine PROCedure mete(a)
710   PRINT "EN ";a;":"; : LISTA_ADD(a) : ver
720 END DEFine 
730 :
740 DEFine PROCedure borra(a)
750   PRINT "BO ";LISTA_VER(a);":"; : LISTA_DELETE(a) : ver
760 END DEFine 
770 :
780 DEFine PROCedure verlista
790   p2$=""
800   FOR xx=0 TO LISTA_LEN-1 :  p2$ = p2$ & LISTA_VER(xx) & ","
810   PRINT "LISTA: ";p2$ : PRINT
820 END DEFine 
830 :
840 DEFine PROCedure ver
850   LOCal xx
860   :
870   IF LISTA_LEN = 0 THEN PRINT "v"; : ELSE PRINT "_";
880   IF L_RAIZ=L_NULO THEN PRINT "*"; : ELSE PRINT L_RAIZ;":";
890   FOR xx=0 TO DIMN(ArrLista)
900     PRINT !"(";xx;")";ArrLista(xx);
910     IF ArrPuntero(xx)=-1 THEN PRINT "*";
920     IF ArrPuntero(xx)=-2 THEN PRINT "v";
930     IF ArrPuntero(xx)>0  THEN PRINT ArrPuntero(xx);
940   END FOR xx
950   PRINT
960 END DEFine 

Como siempre aquí todo lo desarrollado hasta el momento.

viernes, 2 de diciembre de 2016

Mis contribuciones en la Wikipedia

El otro día buscando información sobre lenguajes de programación vi que no había entrada en castellano en la Wikipedia sobre PL/M, el lenguaje desarrollado por Gary Kildall en Intel, que luego utilizó para desarrollar su CP/M. Al lanzar la traducción de la página ahora sale un magnífico asistente que te ayuda mucho en la traducción, y esto me ha echo recopilar aquí las entradas sobre computación que he traducido o ampliado en la Wikipedia, recordando un poco la falta de ayudas de hace unos años y lo cómodo que hoy día para traducciones y mejoras:

  • Tras hacerme con una en 2011, creé la entrada sobre la C64 Direct-to-TV a partir de la traducción manual de la entrada en inglés.
  • En 2012 amplié la entrada sobre la Z1 a partir de información en ingles de varias fuentes, ampliando los apartados de historia y diseño, añadiendo el resto de apartados, ampliando enlaces y referencias. Todo lo hice manualmente.
  • En junio de este año 2016 creé la página sobre los Intellec usando el asistente de traducción, que ayudaba pero no era todavía comparable al actual.
  • Ahora acabo de traducir la entrada sobre PL/M, usando el nuevo asistente de traducción, que es muy bueno, a poco que puedas entender el idioma de origen es muy cómodo y rápido, ya que te pone los dos textos uno junto al otro, te propone la traducción automática, y solo tienes que ir revisando y ajustando. Además, la entrada en Francés me permitió añadir alguna referencia, y la entrada en Polaco es muy buena por lo que añadí algunas cosas y enlaces de esa página, a pesar de no entender el idioma, si comprendía lo que querían decir.
  • Luego traduje una entrada muy relacionada con la anterior sobre el S.O. ISIS de Intel con el asistente, nuevamente la entrada en Polaco es muy buena por lo que añadí algunas cosas y enlaces de esa página.

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. 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