Home UC3M
Home IT
Home / Docencia / I. Telecomunicación / Programación de sistemas/ Práctica 8
anteriorsiguiente

Práctica 8. Búsqueda y Ordenación

Fecha: 30 de mayo de 2006
Conceptos: Algoritmos de Búsqueda y Ordenación, Complejidad
Profesores: Jose Jesus García Rueda, Raquel Crespo García, José María Rubio Manso Daniel Díaz Sánchez

 INTRODUCCIÓN

En esta práctica, vamos a codificar y visualizar algunos algoritmos clásicos de búsqueda y ordenación. También se analizará la complejidad de los mismos.

 EJERCICIO 1
ALGORITMOS DE BÚSQUEDA

 

En este ejercicio vamos a codificar y, de paso, darnos cuenta de la complejidad de los dos algoritmos de búsqueda vistos en clase. Por cierto, ¿cuál de los dos sería más complejo? Veamos.

Para ello, vamos a diseñar una clase abstracta llamada Search (cuyo código puede descargarse aquí Search.java), que dejará indefinido el método de búsqueda (search) para que sea implementado por cada una de las clases correspondientes a los algoritmos vistos en clase. Ambas búsquedas tendrán un main (que será dado) por el cual, tratarán de encontrar una palabra de entre varias (elementos) que se pasarán por la entrada estándar (System.in). Aunque los string de entrada se den en orden aleatorio el constructor de Search las ordenará alfabéticamente. Por lo que, la búsqueda (search) se realizará siempre sobre un array de Strings ordenados alfabéticamente.

Apartado 1. Búsqueda Lineal

La búsqueda lineal consiste en recorrer los elementos de búsqueda de principio hasta el final hasta encontrar la palabra a buscar.

Se pide: Codificar el método search que realiza la búsqueda lineal. Se puede descargar un esqueleto de esta clase aquí LinealSearch.java.

Apartado 2. Búsqueda Binaria

La búsqueda binaria consiste en emplear "divide y vencerás" para, dividiendo el problema por la mitad, dirigirse a la izquierda o derecha dependiendo de la comparación de la palabra a encontrar con el elemento del medio, y así sucesivamente, hasta encontrar la palabra a buscar. Tened en cuenta que la implementación más sencilla del algoritmo supone invocar recursivamente al método buscar (search).

Se pide: Codificar el método search que realiza la búsqeda binaria. Se puede descargar un esqueleto de esta clase aquí BinarySearch.java.

Ayuda:

public void int compareTo(String a)
  • Dados dos String:
    • String cadena1
    • String cadena2
  • El método compareTo funciona de la siguiente forma:
    cadena1.compareTo(cadena2)
    • devuelve un número negativo si cadena1 < cadena2
    • devuelve un número positivo si cadena1 > cadena2
    • devuelve 0 si cadena1 = cadena2
 EJERCICIO 2
ALGORITMOS DE ORDENACIÓN

 

En este ejercicio, codificaremos el algoritmo de ordenación por inserción y analizaremos otros algoritmos (ya codificados) en los cuales analizaremos su complejidad.

Apartado 1. Ordenación por inserción

El método de ordenación por inserción consiste en ir insertando los elementos que vayamos leyendo en la posición precisa de nuestro array de elementos. Para ello necesitaremos un doble bucle que se recorre en todas sus posiciones (de ahí que sea un algoritmo de orden O(n2)) Vamos a codificarlo en una clase cuyo main se proporciona. El siguiente enlace posee varios algoritmos animados: visualicemos previamente el algoritmo InsertionSort y después abordemos la práctica.

Se pide: Codificar el método InsertionSort (el constructor) que internamente ordena la matriz de enteros que se pasa en el main. Un esqueleto de la clase InsertionSort puede descargarse aquí InsertionSort.java.

 

Apartado 2. Probar todos los algoritmos de ordenación y búsqueda

Este ejercicio es muy sencillo, sólo te llevará unos cuantos minutos crear una clase y un método main para probar los distintos algoritmos vistos hasta ahora. El método main lo puedes reaprovechar en todas las clases sin más que cambiar la línea donde se hace la llamada al método de ordenación. Como es de suponer, no se provee el código correspondiente al algoritmo del apartado anterior.
  • Crea un fichero por cada uno de los siguientes algoritmos de los algoritmos de ordenación: PruebaInsertionSort.java, PruebaSelectionSort.java, PruebaShellSort.java, PruebaMergeSort.java, PruebaQuickSort.java, PruebaBubleSort.java
  • Añade a cada fichero:
    • La declaración de la clase
    • Un método main
      • Que coja los parámetros de la línea de comandos y los almacene en un arrayEntrada
      • Que llame al método de ordenación
      • Que imprima el arrayEntrada (después de llamar al método de ordenación)
    • El código fuente de los métodos de ordenación están alistados en la siguiente tabla:

     

    Método Complejidad
    BubleSort
    O(n2)
    O(n2)
    O(n2)
    O(n7/6)
    MergeSort
    O(n log2 n)
    QuickSort
    O(n log2 n)
Compila el resultado y pruébalo con distintas entradas para ver que funciona correctamente.
Los 6 primeros algoritmos se pueden ver animados en el siguiente enlace. Pínchalo y entiende los algoritmos.

Apartado 3. Comparación de Strings en lugar de enteros

Modifica el apartado anterior para que trabaje con arrays de String en lugar de hacerlo con array de ints

NOTA Recuerda que no puedes comparar dos String con los operadores relacionales "<" ">" y "=" Debes utilizar en su lugar el método de la clase String

 SOLUCIONES
 
Última actualización:

Localización | Personal | Docencia | Investigación | Novedades | Intranet
inicio | mapa del web | contacta