1. Búsqueda en vectores.

Una operación muy frecuente es la búsqueda de un componente de un vector, que tenga un valor determinado. La forma en que se especifique esta búsqueda dependerá de que los componentes del vector, estén ordenados o no lo estén.

Si el vector no está ordenado, la forma más simple de realizar la búsqueda, consistirá en ir inspeccionando uno a uno los componentes del vector, hasta dar con aquel componente cuyo valor sea el pedido, comenzando por el primero.

Vamos a implementar la búsqueda lineal de un vector.

• Abrimos Gambas.
• Hacemos clic en la opción Nuevo proyecto.
• Marcamos la opción Aplicación de consola y hacemos clic en el botón Siguiente.

• Seleccionamos el directorio donde se guardarán todos los ficheros necesarios para el proyecto. El sitio ideal sería dentro de nuestra carpeta Documentos. Creamos un directorio llamado BASIC y dentro de él otro directorio llamado 4AVANZADO en el que se creará un directorio para cada uno de los proyectos que vamos a hacer. Así crearemos el directorio 4AVANZADO y tendremos Documentos/BASIC/4AVANZADO. Tras esto hacemos clic en el botón Siguiente.

• Le damos el nombre "07VectoresAvanzados" y el título "Proyecto aplicaciones avanzadas con vectores ". Después hacemos clic en OK.
• En última instancia, se muestra la pantalla que confirma la creación del proyecto. Una vez confirmados estos datos, ya no podremos efectuar cambios en nuestro proyecto, como es el nombre, directorio, etc. Hacemos clic en el botón OK.

Vamos a crear un nuevo módulo para nuestro programa.

• Hacemos clic con el botón derecho del ratón sobre el árbol de carpetas. Aparecerá un menú contextual. Elegimos la opción Nuevo→Módulo.
• Surgirá una ventana en la que escribimos el nombre del Módulo: “BusquedaLineal”. Pulsamos el botón OK.
• Hacemos clic con el botón derecho del ratón sobre el nuevo módulo y marcamos la opción Clase de inicio.
• Escribimos el siguiente código:

• Ejecutamos el programa. Comprobamos que funciona correctamente:

• Guarda los cambios. Vas a seguir trabajando en el proyecto y sólo al final tendrás que subirlo a la plataforma (de todas maneras, si no te ha dado tiempo a acabar la práctica completa, puedes subirla y después recuperarla otro día, en ese caso tendrías que subir toda la carpeta del proyecto comprimida)

2. Ordenación de vectores.

Generalmente se considera ordenar como el proceso de reorganizar un conjunto dado de objetos, en una secuencia especificada.

Ordenar un vector es, por tanto, la operación de situar sus componentes en un orden secuencial de acuerdo con un criterio determinado.

Existen multitud de técnicas de ordenación de vectores, si bien la eficacia de un método u otro dependerá de los recursos de memoria que necesite y del coste temporal de ordenar los elementos.

2.1. Ordenación por inserción directa

El ordenamiento por inserción directa (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

En la animación puedes ver el funcionamiento de este tipo de ordenación.

Vamos a implementar el método de ordenación por inserción directa.

• Hacemos clic con el botón derecho del ratón sobre el árbol de carpetas. Aparecerá un menú contextual. Elegimos la opción Nuevo→Módulo.
• Surgirá una ventana en la que escribimos el nombre del Módulo: “OrdenInsercion”. Pulsamos el botón OK.
• Hacemos clic con el botón derecho del ratón sobre el nuevo módulo y marcamos la opción Clase de inicio.
• Escribimos el siguiente código:

• Ejecutamos el programa. Comprobamos que funciona correctamente:

Pero en un método de ordenadción no sólo se pide que lo haga correctamente, eso es de esperar, sino que se quiere que lo haga rápidamente.  

En Gambas se puede controlar el tiempo que se tarda en ejecutar una parte del código que hemos implementado. Como los ordenadores son muy rápidos tendremos que aumentar el tamaño del vector a ordenar para ver resultados interesantes, por lo que cambiaremos su tamaño hasta 10000 valores.

Modificaremos el código como sigue:

• Cambiamos a 10000 el número de elementos del vector.

• En el programa principal añadimos dos nuevas variables y tomamos el inicio del tiempo justo antes de empezar la ordenación.

.

• También en el programa principal, justo al acabar el bucle de ordenación tomamos de nuevo el tiempo. Y al finalizar el programa mostramos la diferencia del tiempo final menos el inicial y la pasamos a milisegundos.

• Ejecutamos el programa. Comprobamos que sigue funcionando correctamente y que al final muestra el tiempo empleado en la ordenación, en este caso 28487,095... milisegundos. Esto dependerá de la potencia del ordenador, de la carga en el momento del cálculo, etc.

• Sube a la plataforma el fichero llamado OrdenInsercion.module que podrás encontrar dentro de la carpeta del proyecto 07VectoresAvanzados.

• Volvemos al módulo de BusquedaLineal.
• Hacemos clic con el botón derecho del ratón sobre el nuevo módulo y marcamos la opción Clase de inicio.

Antes de subirlo deberás hacer unos cambios:

• Cambia el tamaño del vector hasta los 10000 elementos, igual que hemos hecho en el caso del ejercicio anterior.
• Inserta el código necesario para averiguar cuánto tiempo se tarda en encontrar el número que elijamos.
• Muestra en pantalla el tiempo empleado.

• Ejecuta el programa y comprueba que todo funciona correctamente.
• Sube a la plataforma el fichero llamado BusquedaLineal.module que podrás encontrar dentro de la carpeta del proyecto 07VectoresAvanzados.

Ahora te toca que investigues un poco por Internet. Hay muchos algoritmos de búsqueda, algunos necesitan que el vector esté ordenado para que su funcionamiento sea óptimo.

Aprovechando que ya tienes implementado un método de ordenación, implementa el algoritmo de búsqueda dicotómica o binaria sobre un vector de 10000 elementos aleatorios que ordenes previamente.

• Seguimos con el mismo proyecto.
• Hacemos clic con el botón derecho del ratón sobre el árbol de carpetas. Aparecerá un menú contextual. Elegimos la opción Nuevo→Módulo.
• Surgirá una ventana en la que escribimos el nombre del Módulo: “BusquedaBinaria”. Pulsamos el botón OK.
• Hacemos clic con el botón derecho del ratón sobre el nuevo módulo y marcamos la opción Clase de inicio.

Requisitos del programa:

• Generará aleatoriamente un vector de 10000 elementos.
• Ordenará el vector con el sistema que ya hemos implementado.
• Una vez ordenador se solicitará el número a buscar.
• Cuando empiece el algoritmo de búsqueda se tomará el tiempo de inicio.
• Al finalizar la búsqueda se tomará el tiempo empleado.
• Se mostrará por pantalla el tiempo empleado y la posición que ocupa el elemento buscado, si existe.

Sugerencias:

• Aprovecha al máximo el código que tienes ya creado.
• En Wikipedia tienes implementado el algoritmo de búsqueda binaria en otros lenguajes, pero es muy fácil convertirlo a Gambas. Puedes mirar aquí
• Hay muchos sitios en los que el algoritmo está explicado.

• Ejecuta el programa con los cambios solicitados y comprueba que funciona correctamente. Compara el tiempo empleado en la búsqueda ahora con el tiempo del primer algoritmo de búsqueda que habíamos realizado.

• Sube a la plataforma el fichero llamado BusquedaBinaria.module que podrás encontrar dentro de la carpeta del proyecto 07VectoresAvanzados.

Ahora vas a hacer lo mismo pero con un algoritmo de ordenación. Hemos implementado el de inserción directa, pero hay muchos otros. Deberás implementar el algoritmo de ordenación de burbuja, es muy fácil encontrar información de él por Internet e incluso programas hechos en otros lenguajes para que conviertas.

Seguimos con el mismo proyecto.

• Hacemos clic con el botón derecho del ratón sobre el árbol de carpetas. Aparecerá un menú contextual. Elegimos la opción Nuevo→Módulo.
• Surgirá una ventana en la que escribimos el nombre del Módulo: “OrdenBurbuja”. Pulsamos el botón OK.
• Hacemos clic con el botón derecho del ratón sobre el nuevo módulo y marcamos la opción Clase de inicio.

Requisitos del programa:

• Generará aleatoriamente un vector de 10000 elementos.
• Cuando empiece el algoritmo de ordenación se tomará el tiempo de inicio.
• Al finalizar la ordenación se tomará el tiempo empleado.
• Se mostrará por pantalla el tiempo empleado y el vector ordenador.

Sugerencias:

• Aprovecha al máximo el código que tienes ya creado.
• Hay muchos sitios en los que el algoritmo está explicado.
• Prueba muy bien el código antes de presentarlo.

• Ejecuta el programa con los cambios solicitados y comprueba que funciona correctamente. Compara el tiempo empleado en la ordenación ahora con el tiempo del primer algoritmo de ordenación que habíamos realizado.

• Sube a la plataforma el fichero llamado OrdenBurbuja.module que podrás encontrar dentro de la carpeta del proyecto 07VectoresAvanzados.