Laboratorio 4: Algoritmos de Búsqueda y complejidad

publicado a la‎(s)‎ 22 may 2012, 12:33 por Hernan Nina Hanco   [ actualizado el 19 may 2014, 8:34 ]
I) OBJETIVOS
  • Implementar algoritmos de búsqueda y analizar su complejidad
II) MARCO CONCEPTUAL
Revisar los temas de Algoritmos de Búsqueda:
  • Búsqueda Secuencial
  • Búsqueda Indexada
    • Indice Binario
    • Arboles B
  • Dispersión
    • Dispersión Cerrada
    • Dispersión Abierta

III) PRÁCTICAS DE LABORATORIO

1) Implementar un algoritmo de Búsqueda Secuencial con cálculo de tiempo de ejecución en nanosegundos.

namespace BusquedaSecuencial
{
   class Program
   {
       static void Main(string[] args)
       {
           // Crear un cronometro
           NanoTemporizador reloj = new NanoTemporizador();
           // crear un arreglo de enteros
           int[] arreglo = {2,4,1,6,3,5,7,10,14,9};
           // buscar el elemento 7
           reloj.Start();
           int idx = busquedaSecuencial(23,arreglo);
           reloj.Stop();
           Console.WriteLine(
             "El elemento 7 esta en la posición: {0}",idx);
           Console.WriteLine(
               "Tiempo en nanosegundos: {0}", reloj.ElapsedNanoseconds);
           Console.ReadKey();
       }
       /*
        * Método para búsqueda secuencial
        * @parameter elemento: es el elemento a búscar
        * @parameter arreglo: es el arreglo que almacena numeros enteros
        * @return: un entero que indique la ubicación del elemento
        */

       static int busquedaSecuencial(int elemento, int[] arreglo)
       {
           int idx = -1; // indica la posición del elemento en el arreglo
           // Recorrido por el arreglo
           for (int i = 0; i <= arreglo.Length - 1; i++)
           {
               // verificar si el i-ésimo elemento es el que búscamos
               if (arreglo[i] == elemento) // Elemento encontrado
               {
                   idx = i;
                   break;
               }
           }
           return idx;
       }
   }
}

2) Implementar un algoritmo en Búsqueda Binaria con análisis del tiempo de ejecución en nanosegundos.

namespace BusquedaBinaria
{
    class Program
    {     
        static void Main(string[] args)
        {
            // Crear un cronometro
            NanoTemporizador reloj = new NanoTemporizador();
            // crear un arreglo de enteros ordenado
            int[] arreglo = { 1,2,3,6,8,9,12,14,16,45,90};
            // buscar el elemento 9
            reloj.Start();
            int idx = busquedaBinaria(9,arreglo,0,arreglo.Length);
            reloj.Stop();
            Console.WriteLine("El elemento 9 esta en la posición: {0}", idx);
            Console.WriteLine(
                "Tiempo en nanosegundos: {0}", reloj.ElapsedNanoseconds);
            Console.ReadKey();
        }

        /*
         * Método para búsqueda binaria 
         * @parameter elemento: es el elemento a búscar
         * @parameter arreglo: es el arreglo que almacena numeros enteros
         * @parameter l: Límite inferior
         * @parameter u: Límite superior
         * @return: un entero que indique la ubicación del elemento
         */
            
        static int busquedaBinaria(int elemento, int[] arreglo, int l, int u)
        {
            int medio;
            if (l > u)
                return -1;
            medio = (l + u) / 2;

            if (arreglo[medio] < elemento)
                return busquedaBinaria(elemento, arreglo, medio + 1, u);
            else
                if (arreglo[medio] > elemento)
                    return busquedaBinaria(elemento, arreglo, l, medio - 1);
                else
                    return medio;        
                }

    }
}



IV) TAREA:

1) Modificar el programa de la práctica para obtener datos desde un archivo de datos en modo texto, para luego realizar una búsqueda secuencial.
2) Modificar el programa de la práctica para obtener datos desde un archivo de datos en modo texto, para luego realizar una búsqueda binaria.
3) Mostrar la complejidad de algoritmos en su forma gráfica para búsqueda secuencial y binaria. realice una comparación de gráficos. Considere los tiempos en el mejor, medio y peor caso para cada algoritmo.

V) REFERENCIAS BIBLIOGRAFICAS

Comments