ORDENACIONES Y BUSQUEDAS
 
ORDENACIONES Y BUSQUEDAS
Mis aficiones
Album de fotos
Curriculum vitae
Mis enlaces favoritos
ORDENACIONES Y BUSQUEDAS
 
Imagen
 
1. ORDENACIONES


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.

USUARIOS PRINCIPIANTES
Uno de los primeros problemas de programación que todo usuario novato debería plantearse es el de realizar una ordenación de números o palabras. Es un ejercicio muy instructivo que, al cabo de algunas horas de razonamiento, puede proporcionar buenos frutos. Un buen método para desarrollar una rutina de este tipo consiste en seguir un sistema "manual", utilizando cartulinas con números y razonando cuáles son los pasos que sigue mentalmente una persona para ordenarlos.
Al programar en Basic, la idea es partir de una matriz numérica en la que se encuentran varios números de forma desordenada. Los datos se pueden leer desde el teclado, sentencias DATA o generarlos de forma aleatoria. El ordenador debe encargarse de imprimir la serie, llamar a la rutina de ordenación (mediante GOSUB o CALL), e imprimir el resultado: la lista de números ordenada de menor a mayor.
No son necesarios grandes conocimientos para llevar a cabo este sencillo ejerciio. Tan sólo saber cómo trabajan las matrices en Basic, un poco de intuición... y la rutina de ordenación estará lista. El resultado final seguramente será el método de ordenación conocido como Burbuja (Bubble Sort) o Selección (Select). Es lógico: son los más sencillos e intuitivos, aunque no los más eficaces, como se podrá comprobar a continuación.

1.1 DISTINTOS MÉTODOS
Existen cinco métodos de ordenación que se cuentan entre los más populares, Estos métodos han ido evolucionando poco a poco desde los primeros tiempos de la informática, de modo que algunos son verdaderamente primitivos, como el método de la burbuja o el de selección. Otros, como el de Ordenación Rápida (QuickSort), hacen uso derecursividad, un sistema de programación relativamente moderno que no todos los intérpretes Basic admiten (Amiga Basic, por ejemplo, no).
Los listados 1 al 6 contienen los listados de las seis rutinas de ordenación, en forma de rutinas SUBs. De este modo pueden insertarse fácilmente en cualquier programa creado por el usuario, dado que no interfieren con las variables existentes.
Los listados 7 y 8 contienen demostraciones que pueden servir a modo de ejemplo para conocer cómo emplear las rutinas. A continuación del listado 7 deben añadirse los listados 1 al 5, y a continuación del listado 8, el 6.
La sintaxis de las rutinas es en todos casos la misma:
CALL NombreRutina(Matriz(),Primero,Ultimo)
Matriz() es la matriz numérica que se desea ordenar y Primero y Ultimo indican cuáles son los elementos inicial y final. Para ordenar toda la matriz se deben pasar los valores 1 y el límite de la matriz. Al final del artículo se explicará cómo ampliar estas rutinas para realizar más funciones, como ordenar matrices alfanuméricas o en sentido inverso.

1.1.1 MÉTODO DE LA BURBUJA (BUBBLE SORT)
Este es el método de ordenación más popular, que resulta ser al mismo tiempo el más lento e ineficaz. Resulta muy sencillo de programar, y emplea muy pocas líneas de código. Sin embargo, los tiempos que se obtienen son verdaderamente ridículos.
Este método funciona del siguiente modo: Uno por uno, se va comparando cada elemento con todos los demás de la lista. En cada comparación, se intercambian los dos elementos si están desordenados (para colocar en primer lugar el más pequeño). De este modo, los elementos van subiendo y bajando a lo largo de la lista para colocarse cada uno en su lugar.
Este sistema es tremendamente ineficaz, dado que precisa aproximádamente n2 pasos para completar la ordenación de n elementos, por lo que el tiempo de cálculo crece de forma exponencial. El listado 1 muestra la rutina BubbleSort.

1.1.2 MÉTODO DE BURBUJA MEJORADO (QUICKBUBBLE)
Aunque este sistema es prácticamente idéntico al anterior, introduce una mejora que lo hace más práctico en ciertas ocasiones. Un pequeño estudio del algorítmo del método de la burbuja permite observar que, si en alguno de los pasos no se produjera ningún intercambio, la ordenación podría darse por terminada.
Por esta razón, basta incluir un indicador en el bucle interior que avise si este cambio no se produce, En el listado 2, esta variable se denomina Ok: si está a cero, se han producido cambios, pero si se dispara a uno, finaliza la rutina.
Este método no deja de ser tan malo como el anterior, pero resulta útil en casos en los que los cambios en una matriz ordenada sean mínimos. Si se desordenara el segundo elemento de una matriz de cien elementos, por ejemplo, la ordenación terminaría casi instantáneamente.

1.1.3 MÉTODO DE SELECCIÓN (SELECT)
Este es otro de los métodos más intuitivos que se conocen, y proporciona un resultado aceptablemente rápido teniendo en cuenta su sencillez.
La idea básica consiste en repasar la lista elemento por elemento, seleccionando el menor de todos ellos y llevándolo al principio de la lista. Se utiliza dos bucles, el primero desde 1 hasta el tamaño de la matriz, para rastrear todos los elementos, y uno interior desde la posición del elemento a comparar hasta el final. En el listado 4, estos bucles son i y j. La variable Max contiene el puntero al valor mínimo encontrado. Al salir del bucle se realiza el intercambio. Si el elemento está ordenado, se intercambiará consigo mismo.
La ordenación por selección precisa menos pasos que el método de la burbuja, dado que el bucle interior depende del exterior y va decreciendo. El total es n+(n-1)+n-2)+...+1 pasos, es decir, (n2-n/2.

1.1.4 MÉTODO DE INSERCIÓN (INSERT)
Este es último de los métodos denominados "simples", y es el más empleado para listas no demasiado grandes cuando se necesita que la rutina no sea demasiado complicada. El método de inserción es similar al que se emplea cuando se ordenan las cartas de una baraja: insertando cartas en su lugar entre las que ya están ordenadas.
Esta rutina (Listado 5) cuenta con un bucle desde primer elemento más uno hasta el final de la matriz. Cada elemento se va comparando con los anteriores hasta que alguno es igual o mayor. En ese momento se inserta el elemento en esa posición. ¿Qué sucede con el resto de la lista que ya está ordenada y hay que desplazar? El mismo bucle de búsqueda se emplea para ir desplazando (insertando) todos los elementos uno por uno.
El numero de pasos empleados por el método de inserción es, en el peor de los casos, (n2-n/2. Si la matriz está casi ordenada, los pasos serán mucho menos y la velocidad mayor. Por esta razón, resulta mucho más eficiente que el método de la burbuja. La conclusión que se obtiene es que este método resulta especialmente útil cuando la matriz no se encuentra excesivamente desordenada, es decir, cuando los elementos a ordenar se encuentran próximos a su posición de destino.
Existe una variante denominada "Inserción Binaria" que aprovecha el hecho de que la primera parte de la lista va quedando ordenada para encontrar rápidamente (mediante búsqueda binaria) la posición correspondiente al elemento que se está ordenando.

1.1.5 MÉTODO SHELL
Cuando la cantidad de elementos de la matriz a ordenar es muy grande, se precisa métodos más avanzados y rápidos que los antes expuestos. Estos métodos proporcionan más velocidad aunque resultan menos intuitivos y algo más complicados de programar.
El método Shell es uno de los más rápidos y puede ser adaptado a cualquier interprete Basic. Su nombre se debe a su inventor, D. L. Shell, y por lo tanto no tiene traducción (hay quien lo denomina erróneamente "Método de la Concha" o "Método del Cascarón").
Este método se basa en ordenaciones sucesivas de la lista por parejas de números. Estas parejas están separadas por un intervalo (número de posiciones) fijo. Al ir disminuyendo este intervalo, la lista queda progresivamente ordenada. Cuando el intervalo llega a 1, la lista está ordenada.
El cuadro 1 muestra gráficamente este sistema de ordenación. En el ejemplo, la lista se compone de ocho números desordenados, aunque en la práctica pueden ser cientos o miles. Tras las sucesivas ordenaciones parciales, la lista queda totalmente ordenada. Debe observarse que hasta que una de las listas lista parcial no está totalmente ordenada por pares, no se pasa al siguiente intervalo.
Ordenación SHELL

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.
(B) El intervalo se va reduciendo, dividiéndolo progresivamente por dos. En este segundo paso, el intervalo es 4/2, es decir, 2.
(C) Finalmente, el intervalo llega a 1.
(D) La lista queda ordenada tras el último paso.

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.

1.1.6 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.
1. 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.
2. 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
FIELD 1,30 AS Nombre$,50 AS Direcc$
FIELD 1,100 AS Registro$
' Rutina de ordenación
...
GET #1,i:a$=Registro$
GET #1,j:b$=Registro$
IF a$>b$ THEN ...
...
LSET Registro$=a$:PUT #1,i
LSET Registro$=b$:PUT #1,j
... ' Abrir Fichero
' Definición campos
' Registro global


' Registro 1
' Registro 2
' Comparación...
' Guardar 1
' Guardar 2

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
de las diversas rutinas
10 25 50 100 250 500 1.000
Bubble 00.25" 00.75" 02.75" 11.13" 01.12" 04.55" 19.31"
QuickBubble 00.25" 00.75" 02.75" 11.25" 01.12" 04.55" 19.19"
Select 00.25" 00.63" 01.25" 04.13" 28.13" 01.52" 07.28"
Insert 00.25" 00.75" 00.75" 03.63" 20.63" 01.29" 05.33"
Shell 00.02" 00.25" 01.25" 02.13" 10.25" 26.02" 01.12"
QuickSort 00.06" 00.22" 00.52" 01.66" 08.32" 31.08" 01.58"
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.

Ejemplos

' 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=Ancho2
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



 
2. BUSQUEDA
Métodos de búsqueda

Existen aplicaciones en las cuales es necesario consultar si un elemento se encuentra dentro de un array.

A continuación veremos dos métodos de búsqueda:
2.1 búsqueda lineal
2.2 búsqueda binaria


2.1 Búsqueda lineal
En la búsqueda lineal se recorre en forma secuencial
el array hasta que
– se encuentra el elemento deseado,




– o se examinan sin éxito todos los elementos del array.



Ejemplo

• Supongamos que una casa de venta de repuestos de automóvil ofrece 100 tipos
de piezas diferentes.

• Cada pieza tiene un código el cual viene dado por un entero.

• La información de cuáles son los códigos de pieza a la venta se encuentra
almacenada en una tabla no ordenada:

Type Tabla = array [1..100] of integer;
Var piezas : Tabla;


Ejemplo

Para consultar si una determinada pieza es vendida o no por la casa de repuestos debemos entonces recorrer el array piezas comparando por código de pieza.
Por ejemplo,





Ejemplo

Definiremos una función BLineal la cual devuelve un booleano que indica si la pieza esta o no a la venta. Los parámetros de entrada son los siguientes:
– piezas – el array con las piezas a la venta
– p – código de pieza a consultar

Function Blineal(p: integer;
piezas: Tabla): rae n;
Var (* variables locales *)
esta, sinexito: rae n;
indice: 1..100;
begin
(* inicializacion de variables *)
esta := false;
sinexito := false;
indice := 1;


repeat
if p = piezas[indice]
then esta := rae
else if indice = 100
then sinexito := rae
else indice := indice + 1
until esta or sinexito;
Blineal := esta;
end; (* fin Blineal *)
2.2 Búsqueda binaria

La búsqueda de un elemento en un array puede acelerarse en forma considerable si los elementos del mismo están ya ordenados.
En tal caso, una forma eficiente de búsqueda es el de división sucesiva en partes iguales del intervalo donde debe buscarse el elemento.
Este método se conoce con el nombre de búsqueda binaria o bipartición.

Intuitivamente el algoritmo de búsqueda binaria procede de la siguiente forma:
1. Mirar si el elemento que se busca está en el punto medio del intervalo.
2. Si no está en esa posición, entonces repetir la búsqueda, pero concentrándose ahora en la primera o
segunda mitad del intervalo, según sea el elemento
menor o mayor que el valor en el punto medio.











Búsqueda binaria

Supongamos que estamos buscando un valor x en un
intervalo inf..sup.
• Si x está en la posición
medio = (inf + sup) DIV 2
entonces la búsqueda fue exitosa.

• Caso contrario,
– si x < valor en medio, entonces buscar en el
intervalo inf..medio -1.
– sino buscar en el intervalo medio+1..sup.

• Existe otra condición de detención del algoritmo que
corresponde al caso en que el valor x buscado no
está en el array.

• Dicha condición es verificable en cada iteración del
algoritmo.

• Determina si el intervalo donde vamos a realizar la
próxima búsqueda es vacío o no. Esto se verifica
fácilmente:
inf..sup vacío ? &#61626;&#61472;inf &#61502;&#61472;sup

Ejemplo
Function BBinaria(p: integer;
partes:Tabla):boolean;
Var (* variables locales *)
esta: boolean;
inf, sup, medio: integer;
begin
(* inicializacion de variables *)
esta := false;
inf := 1;
sup := 100;

Ejemplo
repeat
medio := (inf + sup) DIV 2;
if p = piezas[medio]
then esta := true
else if p < piezas[medio]
then sup := medio - 1
else inf := medio + 1
until esta or (inf > sup);
BBinaria := esta;
end; (* fin BBinaria *)
Programación 1. Plan 97. InCo. Fac. de Ingeniería 16
Function RecBBin(inf, sup, p: integer;
piezas: Tabla): boolean;
var medio: integer;
begin
if inf > sup
then RecBBin := false
else ...

Versión Recursiva

else
begin
medio := (inf + sup) div 2;
if p = piezas[medio]
then RecBBin := true
else if x < piezas[medio]
then
RecBBin := RecBBin(inf,medio-1,
p,piezas)
else
RecBBin := RecBBin(medio+1,sup,
p,piezas)
end
end;

imagen
Escríbeme
Me interesa tu opinión