ordenacionmergesort.java

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

/**
 * OrdenacionMergesort.java
 */
package soluciones.practi07;

import problemas.ProblemaOrdenacion;
import soluciones.EstrategiaSolucion;
import esquemas.EsquemaDYV;

/**
 * Clase que da soluci髇 a la ordenaci髇 con mergesort, implementando la clase
 * abstracta EsquemaDYV. El objetivo de esta clase ordenar el vector de
 * enteros.Implementa la interfaz <code>EstrategiaSolucion</code> para que las
 * soluciones puedan ser medidas; por tanto han de implementarse los m閠odos de
 * dicha interfaz, <code>procesamientoInicial()</code>,
 * <code>procesamientoFinal()</code> y <code>solucion()</code>.
 * 
 * @version 2.1, 05/11/2005
 */
public class OrdenacionMergesort extends EsquemaDYV implements
        EstrategiaSolucion {
    /*
     * Contiene los atributos privados umbral, pb, sol, numElem, datosModelo,
     * array.
     */
    private int umbral = 1;

    private Problema pb;

    private Solucion sol;

    private ProblemaOrdenacion p;

    private int[] a; // el vector a ordenar

    private int[] auxiliar;

    /**
     * El m閠odo constructor carga el problema de ordenaci髇.
     */
    public OrdenacionMergesort(ProblemaOrdenacion p) {
        this.p = p;
    }

    /**
     * Permite darle al umbral un valor distinto al valor por omisi髇 (1).
     * @param umbral El nuevo valor de umbral.
     */
    public void setUmbral(int umbral) {
        if (umbral < 1) {
            throw new IllegalArgumentException("El umbral tiene que ser > 0");
        }
        this.umbral = umbral;
    }

    /**
     * Devuelve el valor de umbral.
     * @return El umbral.
     */
    public int getUmbral() {
        return umbral;
    }

    /**
     * Llama a dYV y actualiza la solucion.
     */
    public void solucion() {
        sol = dYV(pb);
    }

    /**
     * Crea un nuevo problema para cada ejecuci髇 tomando el array del problema.
     */
    public void procesamientoInicial() {
        // copia a del problema
        a = p.getArray();
        pb = new ProblemaOrd(0, a.length - 1);
        auxiliar = new int[a.length];
    }

    /**
     * De <code>EstrategiaSolucion</code>. No hace nada.
     */
    public void procesamientoFinal() {
        // nada
    }

    /**
     * comprueba si se ha llegado al valor umbral
     */
    protected boolean esCasoBase(Problema p) {
        if (((ProblemaOrd) p).ultimo <= ((ProblemaOrd) p).primero + umbral - 1) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Obtiene la soluci髇 para el caso base
     */
    protected Solucion resuelveCasoBase(Problema p) {
        ProblemaOrd p1 = (ProblemaOrd) p;
        insercion(p1.primero, p1.ultimo);
        return new SolucionOrd(p1.primero, p1.ultimo);
    }

    /**
     * Divide el problema en dos subproblemas.
     */
    protected Problema[] divide(Problema p1) {
    	// TODO comienza relleno
    	ProblemaOrd p = (ProblemaOrd) p1;
        int inicio = p.primero;
        int fin = p.ultimo;
        int mitad = (inicio + fin) / 2;
        Problema[] pbs = new Problema[2];
        pbs[0] = new ProblemaOrd(inicio, mitad);
        pbs[1] = new ProblemaOrd(mitad + 1, fin);
        return pbs;
        // fin del relleno
    }

    /**
     * Combina las subsoluciones obtenidas al resolver cada uno de los
     * subproblemas obteniedo la soluci髇 del problema formado por esos
     * subproblemas.
     */
    protected Solucion combina(Solucion[] subsoluciones) {
        // inicio1 es el 韓dice del primero del primer subarray a mezclar
    	// TODO comienza el relleno
        int inicio1 = ((SolucionOrd) subsoluciones[0]).primero;

        // fin1 es el 韓dice del 鷏timo del primer subarray
        int fin1 = ((SolucionOrd) subsoluciones[0]).ultimo;

        // inicio2 es el 韓dice del primero del segundo subarray a mezclar
        // es siempre 1 + fin1
        int inicio2 = ((SolucionOrd) subsoluciones[1]).primero;

        // fin2 es el 韓dice del 鷏timo del segundo subarray
        int fin2 = ((SolucionOrd) subsoluciones[1]).ultimo;

        // Mezclamos ahora los dos subarrays en las posiciones correspondientes
        // del array auxiliar
        int indice1 = inicio1;
        int indice2 = inicio2;
        int indAux = inicio1;
        
        // Mientras tengamos elementos en la primera mitad Y en la segunda
        // mitad, comparamos los elementos de los dos subarrays, colocando
        // el menor de los dos subarrays en el auxiliar (el que contendr