| N°
7- Febrero 1990 |
|
ORDENACION EN BASIC |
|
Por Alvaro Ibáñez
Prácticamente cualquier aplicación, desde una simple agenda hasta una base de datos, necesita realizar algún tipo de ordenación con variables numéricas o alfanuméricas. Cuando llega la hora de programar una aplicación en la que se emplee una rutina de ordenación (Sort, en inglés), es necesario disponer del sistema más rápido posible, dado que la velocidad del programa suele ser un factor clave. Por esta razón, este artículo presentará algunos de los sistemas más conocidos, indicando sus características, forma de funcionamiento y verdadera utilidad. Se ha elegido el Basic por ser el lenguaje más popular y estar a disposición de todos los usuarios de Amiga. Cualquiera que tenga conocimientos de C o Ensamblador puede convertir fácilmente las rutinas aquí presentadas, sobre todo porque se encuentran comentadas y explicadas en detalle.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
El método Shell ordena la lista realizando comparaciones entre elementos separados por un intervalo fijo, que va disminuyendo progresivamente. (A) Se comienza
con un intervalo igual a la mitad del número de elementos, en
este caso 4. Las parejas se ordenan independientemente. |
 |
Ordenación
SHELL En el programa (Listado 3), la variable Ancho es la que controla el intervalo. La variable Flag permite comprobar que la lista está correctamente ordenada por pares antes de pasar al siguiente intervalo.
El método SHELL es sumamente eficaz, y necesita aproximadamente n1.2 pasos para ordenar la lista. Por esta razón, es mucho más recomendable para matrices con muchos elementos que los métodos anteriores.
Método QuickSort
El último de los métodos se denomina QuickSort (Ordenación Rápida) y fue creado por C. R. Hoare. Se trata del método más rápido de todos, y muchos (yo entre ellos) lo consideran el más elegante. Aunque existen distintas variaciones, la base del método es la recursividad. Se dice que el programa o rutina es recursivo cuando se "llama" a sí mismo. En este caso, QuickSort divide la lista de elementos en listas más pequeñas y se llama a sí mismo para ordenarlas, una y otra vez, recursivamente.
El intérprete Basic del Amiga es tan lamentable y malo que, entre sus muchos defectos se encuentra el de no permitir recursividad. El gracioso mensaje "Esa rutina ya se está utilizando" te dirige al manual, donde se especifica claramente que "La recursividad no está permitida". (Esto le hace a uno plantearse por qué de entre todo el software existente, el peor tiene que ser el que te regalan con la máquina).
De modo que esta rutina, tal y como está diseñada, no puede utilizarse en Amiga Basic. Por esta razón, se ha desarrollado bajo True BASIC, otro de los intérpretes Basic para el Amiga, que sí permite recursividad, aunque también tiene algunas incomodidades.
QuickSort parte de la lista desordenada y elige un elemento que se denomina "Pivote". Este punto puede ser el punto central o un punto aleatorio de la lista (este método se conoce genéricamente como "Montecarlo" en términos informáticos, y suele proporcionar mejores resultados). A continuación, agrupa en uno de los lados todos los elementos menores que el pivote, y a otro lado los mayores. El resultado son dos sublistas, que se ordenan llamando de forma recursiva a la rutina QuickSort.
El cuadro 2 muestra gráficamente y de forma práctica una ordenación mediante QuickSort.
Ordenación QUICKSORT |
|
| El
método QuickSort ordena una lista de elementos seleccionando un
punto al azar, agrupando los elementos menores y mayores a ambos
lados del pivote y realizando una llamada recursiva para ordenar
los dos grupos. (A) Se elige al azar un elemento pivote (en este ejemplo, el número 2). Este valor, que será el utilizado para las comparaciones, se intercambia con el último elemento de la lista. Más adelante se colocará en el lugar que corresponda. (B) Dos punteros (I y J, representados por una flecha negra o otra blanca en el gráfico) recorren la lista de izquierda a derecha y de derecha a izquierda. El primero se detendrá cuando el elemento al que apunta sea mayor que el pivote, y el segundo cuando sea menor que el pivote. En este caso, al llegar 8 y 1. (C) Los dos elementos se intercambian. (D) La búsqueda con los punteros I y J se repite, hasta que J sea menor que I. (E) Terminado el agrupamiento, se intercambia el pivote (2) por el valor de I. De este modo el pivote queda en su lugar. (F) El resultado son dos sub-listas, de 1 a J y de I al último elemento. La primera es globalmente "menor" que la segunda. Ambas listas se ordenan respectivamente mediante llamadas recursivas a QuickSort. Cuando las listas tienen uno o dos elementos, QuickSort finaliza. |
QuickSort es el método más rápido de todos los conocidos, y algunas de sus variantes se utilizan "de fabrica" en muchos compiladores de C, en forma de función (qSort, generalmente) de forma que el usuario no necesita mo desarrollar esta rutina.
En el listado pueden apreciarse perfectamente todos los pasos que realiza QuickSort para ordenar la matriz. Se ha empleado una rutina adicional, llamada Swap que equivale a la función SWAP de Amiga Basic (no incluida en True BASIC) y que sirve para intercambiar dos variables. La variable Randy es la que selecciona el pivote de forma aleatoria. Partition es el valor del pivote. Si se desea utilizar siempre el punto central en vez de un punto aleatorio, basta con cambiar la línea esta:
LET randy=INT((high-low+1)/2)
La parte final de la rutina realiza la llamada recursiva a QuickSort. ¿Por qué hay cuatro llamadas en vez de dos? La razón es importante: Las llamadas recursivas emplean bastante memoria del stack (pila) del intérprete o compilador. Muchas llamadas recursivas pueden producir un error "Out of Memory". Si se llama primero a QuickSort para que ordene la parte más pequeña, esta lista se liberará antes, ahorrando un poco de memoria. Esta operación puede ser crítica en algunas coasiones. Si la rutina pudiera adaptarse a Amiga Basic, habría que ampliar la memoria para STACK, mediante una instrucción como CLEAR ,,4096, aunque esto depende del número de elementos que se tengaprevisto ordenar. (No es éste el caso de True BASIC, donde no parecen importar las necesidades de STACK, al menos hasta 2.500 elementos).
La rutina QuickSort puede ordenar de forma casi instantánea hasta 100 elementos. Los tiempos de la tabla del cuadro 3 para la rutina QuickSort son significativos pero no pueden compararse con los de las demás rutinas, al estar compiladas bajo distintos sistemas.
Otras variantes
Cualquier usuario puede emplear estas rutinas en sus propios programas. Después de encontrar la que mejor se ajuste a sus necesidades, podrá crear sus propias variantes: rutinas que ordenen de mayor a menor (ordenación inversa), que traten matrices alfanuméricas, o de varias dimensiones.
En ocasiones, para ordenar de forma inversa una matriz no es necesario cambiar los "Menor que" por "Mayor que" y viceversa. Utilizando un pequeño truco de lógica booleana se puede adaptar cualquiera de estas rutinas. Al principio se deben inicializar las siguientes varibles:
False = 0
True = NOT False
HaciaArriba =
En la variable HaciaArriba se puede colocar el valor True (verdadero, -1) si se desea ordenación ascendente, o False (falso, 0) para ordenación descendente. En la rutina, se deben sustituir las expresiones como:
IF n(j) > n(i) THEN ...
por
IF (n(j) > n(i))= HaciaArriba THEN ...
El resultado de la expresion (n(j) > n(i)) es siempre 0 ó -1 (verdadero o falso). Al comparar este valor con HaciaArriba (que también es verdadero o false), se obtienen el resultado deseado de forma automática.
La mayoría de las rutinas necesitan un solo cambio de este tipo, aunque en QuickSort, por ejemplo, serían necesarios varios cambios.
Para la ordenación de matrices alfanuméricas sólo hay que sustituir todas las apariciones de n() por n$(). Como es bien sabido, el Basic entiende que una cadena es "mayor" que otra teniendo en cuenta el orden alfabético de los caracteres que la componen.
Ordenación de ficheros en disco
Un paso más allá en las posibilidades de los sistemas de ordenación de estas rutinas lleva a la ordenación automática de ficheros, tanto secuenciales (por líneas) como directos (por registros). ¿Qué sería necesario? Pueden darse dos casos.
- Si las líneas o registros pueden introducirse en una matriz, la solución está clara: Sólo es necesaria una rutina que transfiera los datos del fichero a la memoria, para después llamar a la rutina de ordenación y finalmente volver a transferir los datos de la memoria al fichero.
- Si el volumen de datos es demasiado grande para la memoria disponible, hay que realizar la operación directamente sobre el disco. Antes de cada comparación deben leerse del fichero los dos registros a comparar, y grabarlos después de los intercambios. Este sistema sólo es válido para los ficheros aleatorios y sorprendentemente rápido y efectivo si se emplea disco duro.
En el caso de los ficheros aleatorios, un pequeño truco permite acelerar la velocidad de acceso, de programación y de manejo de variable: definir un campo (FIELD) con el contenido de todo registro (Amiga Basic permite definir distintas variables para un mismo registro). Ejemplo:
|
OPEN "Fichero" AS 1 LEN=80 ' Rutina de ordenación |
' Abrir Fichero
' Guardar 1
|
En el intercambio de variables, deben cambiarse a$ y b$ si es necesario. Lo mejor es utiizar variables auxiliares (a$, b$) porque las variables de FIELD no pueden asisgnarse directamente.
Un truco más (a veces la programación en Basic permite más trucos que la chistera de un mago) consiste en definir un campo falso inicial, de forma que se pueda ordenar el fichero por el resto de los campos, creándose así una especie de índice. Para ello bastaría añadir las siguientes líneas al principio del programa:
| Longitud=80 Saltar=30 ... |
'
Longitud Fichero ' Bytes a ignorar |
| Field 1,Saltar AS Nulo$,Longitud-Saltar AS Indice$ | |
Al realizar el GET del fichero, se debe asignar Registro$ del mismo modo que antes, pero también se deben asignar otras dos variables, por ejemplo i1$=Indice$ e i2$=Indice$. La comparación se realiza entonces con la variable Indice$ en vez de a$ y b$, y finalmente se graba Registro$, del mismo modo que antes. Hay que tener cuidado para no perder ningún dato en el intercambio de variables.
 |
Resultados comparativos
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
El cuadro muestra los tiempos empleados por las diferentes rutinas para ordenar matrices numéricas de tamaño variable, entre 10 y 1000 elementos. Las pruebas se realizaron compilando el programa SortDemo (Listado 7) con AC/Basic y QuickSortDemo (Listado 8) con True Basic. Los tiempos correspondientes a la rutina QuickSort no deben compararse directamente con los demás, dado que esa rutina está escrita y compilada con True BASIC, y la velocidad básica de ejecución es diferente. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Conclusiones
El cuadro 3 muestra unas pruebas de velocidad realizadas con las tres rutinas. Los tiempos están expresados en segundos. Como se puede observar, los tiempos para los primeros métodos crecen de forma exponencial abrumadora. Los métodos de selección e inserción pueden ser válidos hasta 100 elementos (siempre en versiones compiladas), y podrían resultar prácticos si no se desea demasiada complicación a la hora de programar, por ejemplo si se está adaptando alguno de estos métodos a código máquina. El método Shell es el indiscutible líder para ordenaciones no-recursivas (como las que se pueden obtener con Amiga Basic) y QuickSort para las aplicaciones más profesionales.
' BubbleSort 1.0
SUB BubbleSort (n(),low,high) STATIC
FOR i=low TO high-1
FOR j=low TO high-1
IF n(j)>n(j+1) THEN SWAP n(j),n(j+1)
NEXT
NEXT
END SUB
Numero de lineas: 8
|
' Ordenación por BURBUJA ' Para cada elemento... ' Comprobar todos los demás ' Intercambiar |
.265 . 86 .258 .601 .672 . 6 .959 .214 |
| LISTADO 1 | ||
' QuickBubble 1.0
SUB QuickBubbleSort (n(),low,high) STATIC
i=1:Ok=0
WHILE Ok=0 AND i<=high-1
Ok=1
FOR j=low TO high-1
IF n(j)>n(j+1) THEN
SWAP n(j),n(j+1)
Ok=0
END IF
NEXT
i=i+1
WEND
END SUB
Numero de lineas: 14
|
' Ordenación BURBUJA-rápida ' "Ok" es el indicador ' Si está a cero, fin ' (Igual que BubbleSort) ' Desactivar indicador |
. 77 .111 .270 .363 .886 .996 .922 .811 . 19 .513 . 6 .227 .987 .214 |
| LISTADO 2 | ||
' Shell 1.0
SUB ShellSort(n(),low,high) STATIC
Ancho=high-low+1
WHILE Ancho>1
Ancho=Ancho\2
Flag=0
WHILE Flag=0
Flag=1
FOR j=low TO high-Ancho
i=j+Ancho
IF n(j)>n(i) THEN
SWAP n(i),n(j):Flag=0
END IF
NEXT
WEND
WEND
END SUB
Numero de lineas: 17
|
' Ordenación SHELL ' Ancho inicial = todo ' Hasta el Ancho=1... ' Ancho = mitad de Ancho ' Indicador ' Bucle ' Activar indicador ' Calcular pareja ' ... desordenados? ' Intercambiar por pares |
.873 .154 .504 . 92 .437 .241 .751 .450 .806 .782 .401 .309 .422 . 38 . 34 .987 .214 |
| LISTADO 3 | ||
' Select 1.0
SUB SelectSort(n(),low,high) STATIC
FOR i=low TO high-1
Max=i
FOR j=i+1 TO high
IF n(j)<n(Max) THEN Max=j
NEXT
SWAP n(i),n(Max)
NEXT
END SUB
Numero lineas: 10
|
' Ordenación por SELECCION ' Comprobar todos ' Maximo = actual ' Todos los demas... ' Si es mayor, marcar ' Intercambiar |
.275 .913 .425 .703 .334 .962 . 6 .672 .959 .214 |
| LISTADO 4 | ||
' Insert 1.0
SUB InsertSort(n(),low,high) STATIC
FOR i=low+1 TO high
Aux=n(i)
j=i+1
WHILE Aux<n(j) AND j>=low
n(j+1)=n(j)
j=j-1
WEND
n(j+1)=Aux
NEXT
END SUB
Numero de lineas: 12
|
' Ordenación por INSERCION ' Para cada elemento ' Valor auxiliar=actual ' Insertar=anterior ' si hay que insertar... ' Copiar anterior ' Siguiente inserción ' Intercambiar |
.716 .607 .220 .586 .136 .779 .755 . 32 . 34 .390 .959 .214 |
| LISTADO 5 | ||
! QuickSort 1.0 para True BASIC
! (C)1990 By Alvaro Ibáñez
SUB QuickSort(n(),low,high)
IF low<high THEN
IF high-low=1 THEN
IF n(low)>n(high) THEN
CALL Swap(n(low),n(high))
END IF
ELSE
LET randy=INT(RND*(high-low+1))+low
CALL Swap(n(high),n(randy))
LET partition=n(high)
DO
LET i=low
LET j=high
DO WHILE i<j AND n(i)>=partition
LET i=i+1
LOOP
DO WHILE j>i AND n(j)>=partition
LET j=j-1
LOOP
IF i<j THEN
CALL Swap(n(i),+n(j))
END IF
LOOP WHILE i<j
CALL Swap(n(i),n(high))
IF (i-low) < (high-i) THEN
CALL QuickSort (n,low,i-1)
CALL QuickSort (n,i+1,high)
ELSE
CALL QuickSort (n,i+1,high)
CALL QuickSort (n,low,i-1)
END IF
END IF
END IF
END SUB
SUB Swap(a,b)
LET t=a
LET a=b
LET b=t
END SUB
Numero de lineas: 41
|
! ... Fin de ordenacion? ! ... Solo dos elementos? ! Solo dos, y cambiados... ! ... ordenarlos ! Obtener punto "pivote" ! Llevarlo hasta el final ! Partición = mayor ! Mover indicador ! en ambas direcciones ! hacia el pivote central ! En el centro, intercambiar? ! Si ! Mover pivote a posicion ! Llamadas recursivas... ! Ordenar parte mas pequeña ! Ordenar parte mas grande ! Ordenar parte mas pequeña ! Ordenar parte mas grande ! SWAP: Intercambiar A y B ! T es una variable temporal |
.152 .881 .561 .995 .236 . 20 .532 .513 .428 .539 . 47 . 20 .683 .966 .285 .108 .275 .419 .112 .422 .419 .873 .802 .513 .188 .424 .686 .457 .214 .428 .732 . 32 .956 .700 .654 .214 .171 .181 .242 .711 .214 |
| LISTADO 6 | ||
' Demostración rutinas de ordenación - Amiga Basic
' (c)1990 by Alvaro Ibáñez
CLS
RANDOMIZE TIMER
WINDOW 1,"DEMO",(50,20)-(550,180)
WIDTH 60
' Función ZFill
' Rellena números con ceros a la izquierda
DEF FN ZFill$(num,dig)=RIGHT$(STRING$(dig,48)+MID$(STR$(num),2),dig)
PRINT "Demostración rutinas de ordenación"
PRINT "(C)1989 by Alvaro Ibáñez"
PRINT
' Introducción de datos
INPUT "Número de elementos [10] ";n
IF n=0 THEN n=10
INPUT "Visualizar resultados para comprobación [n] ";v$
IF n=0 THEN v$="n"
PRINT
DIM n(n),Master(n) ' Dimensionar matriz
a=1:b=n ' Elementos inicial,final
FOR i=a TO b ' Generar matriz maestra
Master(i)=INT(RND(1)*(b-a)+1) ' de forma aleatoria
NEXT
FOR type=1 TO 5 ' Para los cinco tipos...
PRINT "Método";type", ordenando... ";
FOR i=a TO b ' Preparar la matriz n()
n(i)=Master(i)
NEXT
t=TIMER
ON type GOSUB Bubble,QuickBubble,Shell,Slect,Insert
t=TIMER-t
IF UCASE$(v$)<>"N" THEN ' Imprimir resultado
PRINT
FOR i=a TO b
PRINT USING "### ";n(i);
NEXT
PRINT
END IF
PRINT "Tiempo empleado: "; ' Imprimir tiempo
Min=INT(t/60)
Sec=INT(t-Min*60)
Cen=t-INT(t-Min*60)
PRINT FN ZFill$(Min,2);":";
PRINT FN ZFill$(Sec,2);":";
PRINT FN ZFill$(Cen,2)
PRINT
BEEP
NEXT
PRINT
PRINT "Pulsa RETURN"
WHILE INKEY$<>CHR$(13)
WEND
' Llamadas a las Subrutinas
Bubble:
CALL BubbleSort(n(),a,b):RETURN
QuickBubble:
CALL QuickBubblSort(n(),a,b:RETURN
Shell:
CALL ShellSort(n(),a,b):RETURN
Slect:
CALL SelectSort(n(),a,b):RETURN
Insert:
CALL InsertSort(n(),a,b):RETURN
' *** Insertar aquí las rutinas de ordenación ***
Numero de lineas: 65
|
.589 .429 .313 . 96 .723 .902 .196 . 5 .840 .951 .321 .463 .973 .650 .564 .340 .342 .463 .336 .811 .446 .811 . 61 .487 .901 .804 .987 .959 .755 . 56 . 52 .141 . 78 .508 .801 . 6 . 78 .700 .158 .725 .973 .723 .170 .305 .140 .755 .159 . 61 .463 .233 .369 . 89 .121 .667 .532 .210 .363 .847 .257 .445 . 30 .882 .502 .659 |
|
| LISTADO 7 | ||
! Demo QUICKSORT 1.0 ! (c)1990 by Alvaro Ibáñez ! Adaptado a True Basic/Amiga partiendo de las versiones ! originales de Turbo Basic / QuickBasic 4 ! ! Utilización: CALL QuickSort (Matriz(),Primero,Ultimo) ! Resultado : La parte indicada de Matriz() queda ordenada ! *** Advertencia!!! *** ! Este programa solo funciona correctamente bajo True BASIC CLEAR DIM a(5000) ! Dimensionar matriz PRINT "Demostracion rutina QuickSort" PRINT "(C)1990 by Alvaro Ibáñez" PRINT INPUT PROMPT "Numero de elementos (1-5000)? ": Num PRINT PRINT "Generando Matriz..." FOR i=1 TO num ! Generar matriz de numeros LET a(i)=INT(RND*num+1) ! Generar numero al azar PRINT a(i); ! Imprimirlo NEXT i PRINT LET t=TIME CALL QuickSort(a,1,num) ! Llamada a QuickSort LET t=TIME-t PRINT "Tiempo empleado: "; ! Imprimir tiempo LET Min=INT(t/60) LET Sec=INT(t-Min*60) LET Cen=t-INT(t) PRINT Min;":"; PRINT Sec; PRINT Cen PRINT PRINT PRINT "Matriz ordenada!" FOR i=1 TO num ! Imprimir matriz ordenada PRINT a(i); NEXT i PRINT LINE INPUT PROMPT "Pulsa RETURN": a$ END ! *** Insertar aqui la rutina QuickSort *** Numero de lineas: 42 |
. 5 .364 .987 .782 .231 .126 .199 .649 .487 .308 . 98 .760 .857 .463 .174 .463 .965 .168 .678 .310 .297 .463 .777 .855 .131 .951 .385 .816 .389 .740 .222 .413 .463 .463 .733 .928 .967 .297 .463 .986 .992 .698 |
|
| LISTADO 8 | ||
| Volver menú revistas | Volver página anterior |