/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package ejercicioordenacion;

/**
 *
 * @author mariano
 */
public class EjercicioOrdenacion {

    static int[] arrayAuxiliar;
    
    public static void quicksort(int array[]) {
        quicksortAux(0, array.length - 1, array);
    }

    private static void quicksortAux(int izquierda, int derecha, int array[]) {
        int i = izquierda;
        int j = derecha;
        int intermedio = array[(izquierda + derecha) / 2];

        do {
            while (array[i] < intermedio) {
                i++;
            }

            while (intermedio < array[j]) {//Si el inermedio es el menor del
                //array, entonces se sale del bucle cuando pase por el propio
                //inermedio
                j--;
            }

            if (i <= j) {
                int aux = array[i];
                array[i] = array[j];
                array[j] = aux;
                i++;
                j--;
            }
        } while (i <= j);
        if (izquierda < j) {
            quicksortAux(izquierda, j, array);
        }
        if (i < derecha) {
            quicksortAux(i, derecha, array);
        }
    }

    public static void mergesort(int array[]) {
        arrayAuxiliar = new int[array.length];
        mergesortAux(array, 0, array.length - 1, arrayAuxiliar);
    }

    private static void mergesortAux(int array[], int indiceInicio,
            int indiceFin, int[] arrayAuxiliar) {
        int longitud = indiceFin - indiceInicio;
        if (longitud > 0) {
            int indiceMedio = (indiceInicio + indiceFin) / 2;
            System.out.println("----------------------------------");
            System.out.println("Índices parte 1: " + indiceInicio
                    + " " + indiceMedio + "\n"
                    + "Índices parte 2: " + (indiceMedio + 1)
                    + " " + indiceFin);
            mergesortAux(array, indiceInicio, indiceMedio, arrayAuxiliar);
            mergesortAux(array, indiceMedio + 1, indiceFin, arrayAuxiliar);
            mezclar(array, indiceInicio, indiceFin);
        }
    }

    // Adaptado de http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html#mergesort_quicksort
    private static void mezclar(int[] array, int indiceInicio, int indiceFin) {
        // Copy both parts into the helper array
        System.arraycopy(array, indiceInicio, arrayAuxiliar, indiceInicio, indiceFin - indiceInicio + 1);

        int indiceMedio = (indiceInicio + indiceFin) / 2;

        int i = indiceInicio;
        int j = indiceMedio + 1;
        int k = indiceInicio;
        
        // Copy the smallest values from either the left or the right side back
        // to the original array
        while (i <= indiceMedio && j <= indiceFin) {
            if (arrayAuxiliar[i] <= arrayAuxiliar[j]) {
                array[k] = arrayAuxiliar[i];
                i++;
            } else {
                array[k] = arrayAuxiliar[j];
                j++;
            }
            k++;
        }
        
        // Copy the rest of the left side of the array into the target array
        while (i <= indiceMedio) {
            array[k] = arrayAuxiliar[i];
            k++;
            i++;
        }

    }
    
    public static void ordenarPorSeleccionDirecta(int array[]) {
        for (int i = 0; i < array.length; i++) {
            intercambiarConMinimoDesdeIndice(array, i);
        }

    }

    //Ejemplos de ejecución de este método:
    //EJEMPLO 1. Si se aplica a [3, 4, 5, 8, 1, 3, 1] a partir del índice 0, se 
    // obtiene [1, 4, 5, 8, 3, 3, 1]. Como se puede observar, el elemento del
    // lugar 0 (el 3) se ha intercambiado por la primera ocurrencia del 1 
    // (que es el elemento con valor mínimo en el array).
    //EJEMPLO 2. Si se aplica a [1, 1, 5, 8, 3, 3, 4] a partir del índice 2, se 
    // obtiene [1, 1, 3, 8, 5, 3, 4]. Como se puede observar, el elemento del 
    // lugar 2 (el 5) se ha intercambiado por la primera ocurrencia del 3
    // (que es el elemento con valor mínimo a partir del lugar 2).
    private static void intercambiarConMinimoDesdeIndice(int[] array,
            int indice) {
        //Se inicializan los valores de mínimo y de índiceDelMínimo. Ésta
        //última variable se utiliza para saber dónde está el valor mínimo
        //dentro del array.
        int minimo = array[indice];
        int indiceDelMinimo = indice;

        //Se recorre el array buscando el mínimo
        for (int i = indice; i < array.length; i++) {
            //Si el elemento por el que vamos es menor que mínimo actual, 
            //entonces dicho elemento pasa a ser el mínimo, y su índice el
            //índiceDelMínimo.
            if (minimo > array[i]) {
                minimo = array[i];
                indiceDelMinimo = i;
            }
        }

        //Se realiza el intercambio.
        int aux = array[indiceDelMinimo];
        array[indiceDelMinimo] = array[indice];
        array[indice] = aux;
    }

    public static void escribirArray(int[] array) {
        System.out.print("{");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.print("}");
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int[] array = {8, 3, 5, 9, 1};

        //ordenarPorSeleccionDirecta(array);
        mergesort(array);
        //quicksort(array);

        escribirArray(array);
    }

}