practi05.java

Java examples for dinamic programming, divide and conquer, greedy algorithms and backtracking.

/*
 * Practi05.java
 */

package practicas;

import problemas.ProblemaOrdenacion;
import soluciones.practi05.OrdenacionGenerica;
import soluciones.practi05.OrdenacionHeapsort;
import soluciones.practi05.OrdenacionInsercion;
import soluciones.practi05.OrdenacionIntercambio;
import soluciones.practi05.OrdenacionMergesort;
import soluciones.practi05.OrdenacionQuicksort;
import soluciones.practi05.OrdenacionSeleccion;
import temporizadores.FuncionTiempo;
import temporizadores.Temporizador;

/**
 * Contiene el programa principal que lanza la ejecuci髇 de diversos algoritmos
 * de ordenaci髇, cronometrando su tiempo de ejecuci髇, y encontrando la funci髇
 * que da el tiempo en funci髇 del tama駉 del problema
 * 
 * @version 2.0, 26/10/2005
 */
public class Practi05 {
	private static int tipoOrdenacion;

	private static int numeroProblemas;

	private static int baseNumElem;

	private static boolean directo;

	private static int numPruebas;

	/**
	 * Lanza la ejecuci髇 del problema planteado en la pr醕tica
	 */
	public static void main(String[] args) {
		long inicio = System.currentTimeMillis();
		
//		 tipoOrdenacion = ProblemaOrdenacion.DESORDENADO;
//		 numeroProblemas = 20;
//		 directo = true;
//		 baseNumElem = 100;
//		 numPruebas = 5;

		tipoOrdenacion = ProblemaOrdenacion.DESORDENADO;
		numeroProblemas = 40;
		directo = false;
		baseNumElem = 2000;
		numPruebas = 5;

		int numeroParametros; // para los directos 3, para los otros 4
		int tipoEcuacion; // para los directos N2, para los otros NLOGN
		/*
		 * factorAumentoProblema es por lo que hay que multiplicar baseNumElem
		 * para obtener los distintos n鷐eros de elementos a ordenar
		 */
		int[] factorAumentoProblema;

		Temporizador t = new Temporizador(numPruebas);
		ProblemaOrdenacion p;
		OrdenacionGenerica ord;

		if (directo) {
			// TODO inicializar numeroParametros, tipoEcuacion y
            // factorAumentoProblema para los directos
			numeroParametros = 3;
			tipoEcuacion = FuncionTiempo.N2;
			factorAumentoProblema = new int[3];
			factorAumentoProblema[0] = 1;
			factorAumentoProblema[1] = 3;
			factorAumentoProblema[2] = 10;
		} else {
			// TODO inicializar numeroParametros, tipoEcuacion y
            // factorAumentoProblema para los directos
			numeroParametros = 4;
			tipoEcuacion = FuncionTiempo.NLOGN;
			factorAumentoProblema = new int[4];
			factorAumentoProblema[0] = 1;
			factorAumentoProblema[1] = 2;
			factorAumentoProblema[2] = 5;
			factorAumentoProblema[3] = 10;
		}

        // TODO crear un array numeroElementosProblema de numeroParametros
        // elementos en el que almacenar los n鷐eros de elementos a ordenar
		int[] numeroElementosProblema = new int[numeroParametros];

        // TODO Crear tres arrays en los que almacenar los tiempos medios de
        // ejecuci髇 de las tres t閏nicas
		double[] tiempoMedio1 = new double[numeroParametros];
		double[] tiempoMedio2 = new double[numeroParametros];
		double[] tiempoMedio3 = new double[numeroParametros];

		for (int i = 0; i < numeroParametros; i++) {
            
			// TODO calcular numElem
			int numElem = baseNumElem * factorAumentoProblema[i];

            // TODO inicializar contadores de tiempos de ejecuci髇 para las tres
            // t閏nicas
			long tiempo1 = 0;
			long tiempo2 = 0;
			long tiempo3 = 0;

            // TODO Crear numeroProblemas problemas, y por cada uno de ellos,
            // crear una soluci髇 de cada tipo, dependiendo del valor de
            // directo, cronometrarla y acumular sus tiempos m韓imos de
            // ejecuci髇
			for (int j = 0; j < numeroProblemas; j++) {
				p = new ProblemaOrdenacion(numElem, tipoOrdenacion);
				if (directo) {
					ord = new OrdenacionIntercambio(p);
					t.cronometra(ord);
					tiempo1 += t.getTiempoMinimo();
					ord = new OrdenacionSeleccion(p);
					t.cronometra(ord);
					tiempo2 += t.getTiempoMinimo();
					ord = new OrdenacionInsercion(p);
					t.cronometra(ord);
					tiempo3 += t.getTiempoMinimo();
				} else {
					ord = new OrdenacionMergesort(p);
					t.cronometra(ord);
					tiempo1 += t.getTiempoMinimo();
					ord = new OrdenacionHeapsort(p);
					t.cronometra(ord);
					tiempo2 += t.getTiempoMinimo();
					ord = new OrdenacionQuicksort(p);
					t.cronometra(ord);
					tiempo3 += t.getTiempoMinimo();
				}
			}

            // TODO guardar el valor de numElem en numeroElementosProblema y de
            // los tiempos promedios de ejecuci髇 en los tres arrays de tiempos,
            // que llamaremos tiempoMedio1, tiempoMedio2 y tiempoMedio3
			numeroElementosProblema[i] = numElem;
			tiempoMedio1[i] = tiempo1 / numeroProblemas;
			numeroElementosProblema[i] = numElem;
			tiempoMedio2[i] = tiempo2 / numeroProblemas;
			numeroElementosProblema[i] = numElem;
			tiempoMedio3[i] = tiempo3 / numeroProblemas;
		}
		// Salida:
		System.out.println("Tipo de ordenaciones: "
				+ (directo ? "directas" : "r醦idas"));
		System.out.print("Ordenaci髇 del array: ");
		switch (tipoOrdenacion) {
		case ProblemaOrdenacion.ASCENDENTE:
			System.out.println("ascendente");
			break;
		case ProblemaOrdenacion.DESCENDENTE:
			System.out.println("descendente");
			break;
		case ProblemaOrdenacion.DESORDENADO:
			System.out.println("desordenado");
			break;
		default:
			break;
		}
		System.out.println("baseNumElem: " + baseNumElem);
		System.out.println("N鷐ero de problemas: " + numeroProblemas);
		System.out.println("numPruebas en Temporizador: " + numPruebas);
		if (directo) {
			System.out.println("Ordenaci髇 por intercambio:");
			FuncionTiempo.calculaEImprime(tipoEcuacion,
					numeroElementosProblema, tiempoMedio1);
			System.out.println("Ordenaci髇 por selecci髇:");
			FuncionTiempo.calculaEImprime(tipoEcuacion,
					numeroElementosProblema, tiempoMedio2);
			System.out.println("Ordenaci髇 por inserci髇:");
			FuncionTiempo.calculaEImprime(tipoEcuacion,
					numeroElementosProblema, tiempoMedio3);
		} else {
			System.out.println("Ordenaci髇 por Mergesort:");
			FuncionTiempo.calculaEImprime(tipoEcuacion,
					numeroElementosProblema, tiempoMedio1);
			System.out.println("Ordenaci髇 por Heapsort:");
			FuncionTiempo.calculaEImprime(tipoEcuacion,
					numeroElementosProblema, tiempoMedio2);
			System.out.println("Ordenaci髇 por Quicksort:");
			FuncionTiempo.calculaEImprime(tipoEcuacion,
					numeroElementosProblema, tiempoMedio3);
		}
		System.out.println("Tiempo total empleado en la prueba: "
				+ (System.currentTimeMillis() - inicio) + " ms");
	}
}