Algoritmos de ordenación en Java: Quicksort y Mergesort explicados

Algoritmos de ordenación en Java

A continuación se presentan implementaciones de los algoritmos Quicksort y Mergesort en Java, junto con la ordenación por inserción utilizada como apoyo.

Quicksort

El algoritmo Quicksort emplea la estrategia de divide y vencerás: selecciona un pivote, reorganiza los elementos y ordena recursivamente las particiones resultantes. En esta implementación, cuando el subarreglo es pequeño se utiliza la ordenación por inserción, y el pivote se elige como la mediana de tres valores.

package quicksort;

public class Quicksort {
    public static void quickSort(Comparable[] temp) {
        quickSort(temp, 0, temp.length - 1);
    }

    public static void quickSort(Comparable[] enteros, int ini, int fin) {
        if (ini + 10 > fin) {
            ordenacionPorInsercion(enteros);
        } else {
            int medio = (ini + fin) / 2;
            if (enteros[ini].compareTo(enteros[medio]) > 0) {
                intercambiar(enteros, ini, medio);
            }
            if (enteros[fin].compareTo(enteros[medio]) > 0) {
                intercambiar(enteros, fin, medio);
            }
            if (enteros[ini].compareTo(enteros[fin]) > 0) {
                intercambiar(enteros, ini, fin);
            }
            intercambiar(enteros, medio, fin - 1);
            Comparable pivote = enteros[fin - 1];
            int i, j;
            for (i = ini, j = fin - 1;;) {
                while (enteros[++i].compareTo(pivote) < 0)
                    ;
                while (pivote.compareTo(enteros[--j]) < 0)
                    ;
                if (i >= j) {
                    break;
                }
                intercambiar(enteros, i, j);
            }
            intercambiar(enteros, i, fin - 1);
            quickSort(enteros, ini, i - 1);
            quickSort(enteros, i + 1, fin);
        }
    }

    private static void intercambiar(Comparable[] a, int b, int c) {
        Comparable temp = a[b];
        a[b] = a[c];
        a[c] = temp;
    }

    public static void ordenacionPorInsercion(Comparable[] temp) {
        for (int i = 1; i < temp.length; i++) {
            Comparable entero = temp[i];
            for (int j = i; j > 0 && entero.compareTo(temp[j - 1]) < 0; j--) {
                temp[j] = temp[j - 1];
                temp[j - 1] = entero;
            }
        }
    }
}

Mergesort

El algoritmo Mergesort divide el arreglo en dos mitades, ordena cada una de forma recursiva y luego las mezcla en un arreglo auxiliar. Su complejidad temporal es O(n log n) en todos los casos.

public void mergesort(Comparable[] a) {
    Comparable[] vectorAux = new Comparable[a.length];
    mergesort(a, vectorAux, 0, a.length - 1);
}

private void mergesort(Comparable[] a, Comparable[] vectorTemp, int izq, int der) {
    if (izq < der) {
        int centro = (izq + der) / 2;
        mergesort(a, vectorTemp, izq, centro);
        mergesort(a, vectorTemp, centro + 1, der);
        mezclar(a, vectorTemp, izq, centro + 1, der);
    }
}

private void mezclar(Comparable[] a, Comparable[] vectorAux, int posIzq, int posDer, int fin) {
    int finIzq = posDer - 1;
    int posAux = posIzq;
    int numElementos = fin - posIzq + 1;

    while (posIzq <= finIzq && posDer <= fin) {
        if (a[posIzq].compareTo(a[posDer]) <= 0) {
            vectorAux[posAux++] = a[posIzq++];
        } else {
            vectorAux[posAux++] = a[posDer++];
        }
    }
    while (posIzq <= finIzq) {
        vectorAux[posAux++] = a[posIzq++];
    }
    while (posDer <= fin) {
        vectorAux[posAux++] = a[posDer++];
    }
    for (int i = 0; i < numElementos; i++, fin--) {
        a[fin] = vectorAux[fin];
    }
}