Programación del Sinclair QL (VII): Algoritmos de ordenación, planteamiento para las pruebas

Índice de entradas sobre programación del Sinclair QL

---

Nota importante sobre los programas que se presenten

Incluiré el código completo del programa siempre al final de la entrada, pero a lo mejor veis que no coinciden los números de línea, e incluso que en la misma entrada los números de línea se solapan entre trozos del código.

Salvo en el módulo de carga en el resto del módulos no usan GOTO o GOSUB, aunque nunca es problema renumerarlos, ya que los números de línea solo sirven como referencia para la edición y los comentarios que haga,  incluso puede que en algunos casos veáis que se solapan dentro del mismo articulo. Al final siempre encontrareis el código completo del mismo, podéis usarlo para vuestro QL o con vuestro emulador.

La base para las pruebas de algoritmos con datos en memoria

Empezaremos con lo básico para las pruebas de los algoritmos que es disponer de una estructura común para todos, que los llame con las mismas condiciones iniciales y guarde los resultados del proceso. En el QL hay un Reloj que podemos explotar bien desde código máquina, pero desde SuperBASIC solo tenemos posibilidad de contar segundos, es un poco limitado pero creo que bastará para las pruebas.

Voy a ordenar un arreglo de números de la longitud que le indiquemos, un procedimiento o funciona acepta un arreglo como parámetro de entrada, pero yo el arreglo no se lo puedo pasar al algoritmo como parámetro pues las variables se pasan por valor y lo que se ordenaría sería el arreglo copiado y no el original, es una limitación importante de no disponer de punteros.

El proceso lo voy a dividir en ficheros separados que cargaré usando MERGE, de esta forma es mas sencillo el mantenimiento, y tiene la ventaja de que cada módulo de ordenación es un fichero independiente, por lo que se puede usar en otros programas.

Módulo de carga

 

Este es el modulo que realizará la carga del resto, de forma que no hay que hacerlo manualmente nunca. Es muy sencillo pero hay que eliminarlo si se desea ejecutar el programa para que no lo vuelva a ejecutar, acuérdate de usar DLINE TO 999 cuando termine de cargar. Cada vez que incluyo un módulo debo cambiar la línea 170, y añadir dos líneas mas tras la 290 por cada módulo:

100 REMark ----------------------------------------
110 REMark -- ALGORITMOS DE ORDENACION --
120 REMark -- Modulo: Cargador de modulos --
130 REMark -- Autor.: javu61, noviembre 2016 --
140 REMark ----------------------------------------
150 :
160 :
170 DATA "mdv1_"
180 DATA "o_base" , "Modulo base"
190 DATA "o_selector" , "Modulo Selector"
200 DATA "o_burbuja" , "Modulo Burbuja"
210 DATA "o_sacudida" , "Modulo Sacudida"
220 DATA ""
230 :
240 actual = 0 : total = 0
250 DIM p$(20,2,20)
260 :
270 RESTORE 
280 READ u$
290 REPeat leer_data
300 READ p$(total,0) : IF p$(total,0)="" THEN EXIT leer_data
310 READ p$(total,1)
320 p$(total,0)=u$ & p$(total,0)
330 total=total+1
340 END REPeat leer_data
350 :
360 MODE 4 : PAPER 0 : CLS
370 PRINT "Cargando modulos del programa"
380 :
390 PRINT " (";actual;"/";total;") ";p$(actual,1)
400 MERGE p$(actual,0)
410 actual=actual+1
420 IF p$(actual,0) <> "" THEN GO TO 390
430 :
440 :
450 PRINT "Ejecute DLINE TO 999 antes de ejecutar"
460 STOP

En la línea 420 hay un GOTO, el único que encontrarás en el programa, está ya que al ejecutar la sentencia MERGE dentro de un bucle se pierden los punteros, hay que recurrir al método tradicional para que funcione.

Módulo base

Este es el modulo que realizará las pruebas de los algoritmos. Como veréis todo lo empiezo por una cabecera general con lo que es, no es necesario pero si una practica de buen programador. Una técnica para acelerar los programas en BASIC es eliminar comentarios, ya que el programa pasa por ellos y los debe analizar, esto no es necesario en SuperBASIC pues monta una tabla de procedimientos y funciones, por lo que casi nunca pasará por los comentarios.

1000 REMark ----------------------------------------
1010 REMark -- ALGORITMOS DE ORDENACION           --
1020 REMark --   Modulo: Base para las pruebas    --
1030 REMark --   Autor.: javu61, noviembre 2016   --
1040 REMark ----------------------------------------

Primero creo un manejador de errores, es una muy buena costumbre tener al menos una estándar, debe estar al principio para que el programa sepa que existe esa rutina de errores.

1060 REMark ----------------------------------------
1070 REMark -- Manejo de errores                  --
1080 REMark ----------------------------------------
1090 WHEN ERRor 
1100   PRINT "En la linea ";ERLIN;" se ha producido un error ";ERNUM;": ";
1110   REPORT #1,ERNUM
1120   STOP
1130 END WHEN 

Ahora voy lanzando procesos que hagan las cosas, contra mas modular mejor, pues es difícil seguir un programa largo y al dividirlo en partes pequeñas se simplifica su lectura, lo que para el mantenimiento es fundamental. Creo que fue Ole-Johan Dahl, uno de los creadores de la programación orientada a objetos, el que dijo que una función no debía ocupar mas de una página (supongo que de papel y no de pantalla). Empiezo borrando pantalla y pidiendo los elementos a ordenar, contra mas tenga mas tardará, y mejor resultado darán las prueba, pero el QL no es un veloz galgo, no os paséis.

1160 REMark ----------------------------------------
1170 REMark -- Pedir elementos a procesar         --
1180 REMark ----------------------------------------
1190 LET nroelem = 0    : REMark Nro elementos a ordenar
1200 :
1210 MODE 4 : PAPER 0 : CLS
1220 INPUT "Numero de elementos a ordenar: ";nroelem
1230 nroelem=nroelem - 1  : REMark Empieza en cero

A mi me gusta definir las variables siempre, ahorra errores, pero en SuperBASIC no es necesario ni posible mas que para los arreglos, pero lo simulo inicializándolas a un valor, y uso LET para distinguir que solo es la primera declaración. En SuperBASIC no existen las constates que hacen el código mas legible, las voy a simular con variables, todas son booleanas, en SuperBASIC cero equivale a falso y distinto de cero equivale a cierto.

1260 REMark ----------------------------------------
1270 REMark -- Definir Seudo-Contantes            --
1280 REMark ----------------------------------------
1290 LET No = 0          : REMark Valor para falso
1300 LET Si = 1          : REMark Valor para cierto
1310 LET Ascendente  = 0 : REMark Orden a montar
1320 LET Descendente = 1 : REMark Orden a montar
1330 :
1340 :
1350 REMark ----------------------------------------
1360 REMark -- Definir variables globales         --
1370 REMark ----------------------------------------
1380 LET m = 20         : REMark Nro maximo de ruinas a probar
1390 LET nrutina = 0    : REMark Algoritmo en prueba
1400 LET nropaso = 0    : REMark Paso en la prueba
1410 DIM nombres$(m,18) : REMark Nombres de algoritmos
1420 DIM tiempoi(m,3)   : REMark Guardar tiempos inicio
1430 DIM tiempof(m,3)   : REMark Guardar tiempos fin
1440 DIM nrocomp(m,3)   : REMark Numero de comparaciones
1450 DIM nromovi(m,3)   : REMark Numero de movimientos
1460 :
1470 DIM Abase(nroelem) : REMark Arreglo base aleatorio
1480 DIM Atemp(nroelem) : REMark Arreglo a ordenar

Solo queda ir llamando a los tres procesos que voy a utilizar, inicializar todo, llamar a la pruebas y presentar el resultado.

1510 REMark ----------------------------------------
1520 REMark -- Lanzar por procesos                --
1530 REMark ----------------------------------------
1540 Inicializar
1550 Probar
1560 INPUT "Finalizado",fin$
1570 Resultados
1580 STOP

El proceso de inicio crea un arreglo para los valores aleatorios y lo muestra en pantalla como referencia, para que veamos el origen.

1610 REMark ----------------------------------------
1620 REMark -- Inicializar                        --
1630 REMark ----------------------------------------
1640 DEFine PROCedure Inicializar
1650   Montar_arreglo Abase
1660   PRINT "----- Elementos a ordenar"
1670   Presentar_arreglo Abase
1680 END DEFine 

Paso al proceso que lanza las pruebas. En lenguajes que soporten punteros como el C o los orientados a objeto se puede crear un arreglo con los enlaces a las rutinas que definamos, no en SuperBASIC, por lo que empezamos un bucle indefinido, guiado por la variable nrutina en la que llevamos un contador de rutinas a probar, según el número seleccionamos el nombre del algoritmo o salimos del bucle. Luego hacemos tres pasadas por un bucle, la primera ordena el arreglo base aleatorio, la segunda con el mejor caso que es con el arreglo ya ordenado, y la tercera con el peor caso lo que invierte el arreglo completamente.

1710 REMark ----------------------------------------
1720 REMark -- Proceso de pruebas                 --
1730 REMark ----------------------------------------
1740 DEFine PROCedure Probar
1750   REPeat prueba_rutina
1760     Seleccion No
1770     IF nombres$(nrutina)="" THEN EXIT prueba_rutina
1780     PRINT "** Probando rutina ";nrutina;" ";nombres$(nrutina)
1790     :
1800     Copiar_arreglo Abase,Atemp
1810     FOR nropaso=0 TO 2
1820       IF nropaso <> 2 THEN 
1830         orden = Ascendente
1840       ELSE 
1850         orden = Descendente
1860       END IF 
1870       tiempoi(nrutina,nropaso)=DATE
1880       Seleccion Si,Atemp,orden
1890       tiempof(nrutina,nropaso)=DATE
1900       :
1910       Verifica_arreglo Atemp, orden
1920       :
1930       PRINT "-- ";nombres$(nrutina);
1940       SELect ON nropaso
1950         ON nropaso=0 : PRINT !" Aleatorio";
1960         ON nropaso=1 : PRINT !" Ordenado ";
1970         ON nropaso=2 : PRINT !" Inverso  ";
1980       END SELect 
1990       REMark PRINT !" (";DATE$;") "
2000       t=tiempof(nrutina,nropaso)-tiempoi(nrutina,nropaso)
2010       PRINT !"T: ";t;" seg";
2020       PRINT !"C: ";nrocomp(nrutina,nropaso);
2030       PRINT !"I: ";nromovi(nrutina,nropaso);
2040       PRINT
2050     END FOR nropaso
2060     :
2070     nrutina=nrutina+1
2080     IF nrutina &amp;gt; m THEN EXIT prueba_rutina
2090     :
2100   END REPeat prueba_rutina
2110 END DEFine 

Terminamos este grupo con la parte que presenta los resultados en la pantalla para poder compararlos todos entre sí. Para evitar líneas largas uso variables auxiliares con lo que mostrar.

2140 REMark ----------------------------------------
2150 REMark -- Presentar los resultados           --
2160 REMark ----------------------------------------
2170 DEFine PROCedure Resultados
2180   LOCal e1$,g1$,g2$
2190   :
2200   e1$=FILL$(" ",25)
2210   g1$=FILL$("-",24)
2220   g2$=FILL$("-",15)
2230   :
2240   CLS
2250   PRINT e1$;"+";g2$;"+";g2$;"+";g2$;"+"
2260   PRINT "       Con "; : Pnumero nroelem+1,3: PRINT " elementos";
2270   PRINT " |  Caso medio   |  Caso mejor   |   Caso peor   |"
2280   PRINT "+";g1$;"+";g2$;"+";g2$;"+";g2$;"+"
2290   FOR i=0 TO DIMN(nombres$)
2300     IF nombres$(i)="" THEN EXIT i
2310     t0=tiempof(i,0)-tiempoi(i,0)
2320     t1=tiempof(i,1)-tiempoi(i,1)
2330     t2=tiempof(i,2)-tiempoi(i,2)
2340     PRINT "| "; : Pnumero i,2
2350     PRINT " "; : PRINT nombres$(i);
2360     lon = 19-LEN(nombres$(i))
2370     IF lon > 0 THEN PRINT FILL$(" ",lon);
2380     PRINT " | "; : Pnumero t0,3
2390     PRINT " "; : Pnumero nrocomp(i,0),4
2400     PRINT " "; : Pnumero nromovi(i,0),4
2410     PRINT " | "; : Pnumero t1,3
2420     PRINT " "; : Pnumero nrocomp(i,1),4
2430     PRINT " "; : Pnumero nromovi(i,1),4
2440     PRINT " | "; : Pnumero t2,3
2450     PRINT " "; : Pnumero nrocomp(i,2),4
2460     PRINT " "; : Pnumero nromovi(i,2),4
2470     PRINT " |"
2480   END FOR i
2490   PRINT "+";g1$;"+";g2$;"+";g2$;"+";g2$;"+"
2500 END DEFine 

 
Luego tenemos rutinas auxiliares, la primera rellena un arreglo de un tamaño dado con valores aleatorios entre 10 y 99, de esta forma con un PRINT salen en columnas homogéneas.

2530 REMark ----------------------------------------
2540 REMark -- Rellena un arreglo con numeros     --
2550 REMark -- aleatorios de dos cifras           --
2560 REMark ----------------------------------------
2570 DEFine PROCedure Montar_arreglo(arreglo)
2580   LOCal i
2590   :
2600   FOR i=0 TO DIMN(arreglo)
2610     arreglo(i)=RND(10 TO 99)
2620   END FOR i
2630 END DEFine 

La segunda copia un arreglo sobre otro, es muy sencilla.

2660 REMark ----------------------------------------
2670 REMark -- Copiar un arreglo sobre otro       --
2680 REMark ----------------------------------------
2690 DEFine PROCedure Copiar_arreglo(origen,destino)
2700   LOCal i
2710   :
2720   IF DIMN(destino) < DIMN(origen) THEN 
2730     PRINT "ERROR copiando arreglo: Destino menor que origen"
2740     STOP
2750   END IF 
2760   :
2770   FOR i=0 TO DIMN(origen)
2780     destino(i)=origen(i)
2790   END FOR i
2800 END DEFine 

Luego otra para presentar por pantalla un arreglo, como todos los valores son de 2 cifras, mas el espacio intermedio, caben 25 valores por línea en modo 4.

2830 REMark ----------------------------------------
2840 REMark -- Presenta en pantalla un arreglo    --
2850 REMark ----------------------------------------
2860 DEFine PROCedure Presentar_arreglo(arreglo)
2870   LOCal i
2880   :
2890   FOR i=0 TO DIMN(arreglo)
2900     PRINT !arreglo(i);
2910   END FOR i
2920   PRINT
2930 END DEFine 

Para poder asegurarme de que las rutinas funciona bien, este proceso verifica que están bien ordenados los elementos del arreglo según el orden indicado.

2960 REMark ----------------------------------------
2970 REMark -- Ver si el arreglo esta ordenado    --
2980 REMark ----------------------------------------
2990 DEFine PROCedure Verifica_arreglo(arreglo, orden)
3000   LOCal i,hayerror
3010   :
3020   hayerror = No
3030   FOR i=0 TO DIMN(arreglo) - 1
3040     IF orden = Ascendente THEN 
3050       IF arreglo(i) > arreglo(i+1) THEN hayerror=Si
3060     ELSE 
3070       IF arreglo(i) < arreglo(i+1) THEN hayerror=Si
3080     END IF 
3090     IF hayerror THEN 
3100       PRINT "ERROR: Mal en orden";
3110       SELect ON orden
3120         = Ascendente  : PRINT !"ascendente";
3130         = Descendente : PRINT !"descendente";
3140       END SELect 
3150       PRINT !"Posicion ";i;"(";arreglo(i);")";
3160       PRINT !"Posicion ";i+1;"(";arreglo(i+1);")"
3170       Presentar_arreglo arreglo
3180       STOP
3190     END IF 
3200   END FOR i
3210 END DEFine   

Esta toma un número cualquiera y lo presenta relleno a ceros por la izquierda si es de menos de tres dígitos. Es sencillo ampliarla para que acepte como parámetro la longitud a rellenar.

3240 REMark ----------------------------------------
3250 REMark -- Presenta en pantalla un numero     --
3260 REMark ----------------------------------------
3270 DEFine PROCedure Pnumero(valor$,long)
3280   LOCal lon,aux$
3290   aux$=valor$
3300   IF aux$="" THEN aux$="0"
3310   lon = long - LEN(valor$)
3320   IF lon > 0 THEN aux$=FILL$(" ",lon) & aux$
3330   PRINT aux$;
3340 END DEFine 

Aquí terminan las rutinas de módulo base.

Módulo Selector

Este módulo contiene el procedimiento que llama al algoritmo en función del número, si no procesa monta la tabla de nombres de algoritmos, seguido por la línea que llama al algoritmo real. Hay que ir ampliandolo con los algoritmos que se desarrollen:

3500 REMark ----------------------------------------
3510 REMark -- ALGORITMOS DE ORDENACION           --
3520 REMark --   Modulo: Selector de algoritmos   --
3530 REMark --   Autor.: javu61, noviembre 2016   --
3540 REMark ----------------------------------------
3550 :
3560 :
3570 REMark ----------------------------------------
3580 REMark -- SELECCION DEL ALGORITMO            --
3590 REMark ----------------------------------------
3600 DEFine PROCedure Seleccion(procesar,arreglo,ordenacion)
3610   SELect ON nrutina
3620     ON nrutina=0
3630       nombres$(nrutina)="Burbuja"
3640       IF procesar THEN Burbuja arreglo,ordenacion,0,0
3650     ON nrutina=1
3660       nombres$(nrutina)="Burbuja Bidireccional"
3670       IF procesar THEN Sacudida arreglo,ordenacion,0,0
3680     :
3690     : REMark Aqui el resto de rutinas
3700     :
3710   END SELect 
3720 END DEFine 

Módulos de ordenación

Y por fin tenemos los métodos de ordenación, pongo la base de los dos primeros, la ordenación por burbuja y la ordenación por sacudida, solo para que el programa pueda ejecutarse y podemos ver cosas en pantalla. 

Modulo burbuja

4000 REMark ---------------------------------------------
4010 REMark -- ALGORITMOS DE ORDENACION                --
4020 REMark --   Modulo....: Burbuja                   --
4030 REMark --   Objetivo..: Ordena un arreglo por el  --
4040 REMark --               algoritmo de burbuja      --
4050 REMark --   Autor.....: javu61, 11/2016           --
4060 REMark --   Parametros:                           --
4070 REMark --     arreglo -> Arreglo a ordenar        --
4080 REMark --     sentido -> FALSO = Ascendente       --
4090 REMark --     primero -> primer elemento          --
4100 REMark --     ultimo  -> ultimo elemento          --
4110 REMark --                Si ultimo=0 -> Todos     --
4120 REMark ---------------------------------------------
4130 DEFine PROCedure Burbuja (arreglo,sentido,primero,ultimo)
4140   REMark Aqui va el codigo
4150 END DEFine 

Modulo sacudida

4500 REMark ---------------------------------------------
4510 REMark -- ALGORITMOS DE ORDENACION                --
4520 REMark --   Modulo....: Sacudida                  --
4530 REMark --   Objetivo..: Ordena un arreglo por el  --
4540 REMark --               algoritmo de burbuja      --
4550 REMark --               doble o sacudida          --
4560 REMark --   Autor.....: javu61, 11/2016           --
4570 REMark --   Parametros:                           --
4580 REMark --     arreglo -> Arreglo a ordenar        --
4590 REMark --     sentido -> FALSO = Ascendente       --
4600 REMark --     primero -> primer elemento          --
4610 REMark --     ultimo  -> ultimo elemento          --
4620 REMark --                Si ultimo=0 -> Todos     --
4630 REMark ---------------------------------------------
4640 DEFine PROCedure Sacudida (arreglo,sentido,primero,ultimo)
4650   REMark Aqui va el codigo
4660 END DEFine 

A partir de ahora solo presentaré los algoritmos que desarrolle en el QL, se añaden al final de todo, junto a código para manejarlos en el procedimiento anterior.

Podéis descargar el programa completo desde aquí, abrir los programas con un editor de textos (no el notepad que solo soporta textos con CR+LF) o cargarlo en un QL real o emulado.