MÉTODOS DE ORDENAMIENTO

Para poder ordenar una cantidad determinada de números almacenadas en un vector o matriz, existen distintos métodos (algoritmos) con distintas características y complejidad. Existe desde el método más simple, como el Bubblesort (o Método Burbuja), que son Simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo. 

Bubble Sort (Ordenamiento Burbuja)

Es el algoritmo de ordenamiento más sencillo de todos, conocido también como método del intercambio directo, el funcionamiento se basa en la revisión de cada elemento de la lista que va a ser ordenada con el elemento siguiente, intercambiando sus posiciones si están en el orden equivocado, para esto se requieren varias revisiones hasta que ya no se necesiten más intercambios, lo que indica que la lista ha sido ordenada.

El origen del nombre de este algoritmo proviene de la forma con la que suben por la lista los elementos durante los intercambios, tal y como si fueran "burbujas", el algoritmo fundamental de este método es la simple comparación de elementos siendo así el más fácil de implementar.

A continuación el algoritmo del método de ordenamiento burbuja

public class ORDENAMIENTO_BURBUJA {

    public static void main(String[] args) {
        int[] vector = {15, 8, 3, 4, 12, 1};
        int temp;

        for (int i = 0; i < vector.length; i++) {
            for (int j = i + 1; j < vector.length; j++) {
                if (vector[i] > vector[j]) {
                    temp = vector[i];
                    vector[i] = vector[j];
                    vector[j] = temp;
                }
            }
        }
        for (int k = 0; k < vector.length; k++) {
            System.out.println(vector[k]);
        }
    }
}

Quick Sort (Ordenamiento Rápido): 

Es el algoritmo de ordenamiento más eficiente de todos, se basa en la técnica de "Divide y Vencerás", que permite en promedio, ordenar n elementos en un tiempo proporcional a n*log(n). 

Algoritmo Fundamental: 

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. 
• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
•  La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. 
• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

A continuación el algoritmo del método de ordenamiento QuickSort

import java.io.IOException;
import java.io.InputStreamReader;

public class ordenamiento_quicksort {

    static BufferedReader entrada = new BufferedReader(new InputStreamReader(
            System.in));

    public static void main(String[] args) throws IOException {

        int n;
        int[] v;
        System.out.print("Ingrese el numero de elementos: ");
        n = Integer.parseInt(entrada.readLine());
        v = new int[n];
        entradaArreglo(v, n);
        System.out.println("\n\tLista original de " + n + " elementos");
        imprimirArreglo(v, n);
        ordenarecursivo(v, n);
        System.out.println("\n\tLista ordenada de " + n + " elementos");
        imprimirArreglo(v, n);

    }

    static void ordenarecursivo(int a[], int n) {
        ordenareducer(a, 0, n - 1);
    }

    static void ordenareducer(int a[], int INI, int FIN) {
        int IZQ, DER, POS, AUX;
        boolean BAND;
        IZQ = INI;
        DER = FIN;
        POS = INI;
        BAND = true;
        while (BAND) {
            BAND = false;
            while (a[POS] <= a[DER] && (POS != DER)) {
                DER = DER - 1;
            }
            if (POS != DER) {
                AUX = a[POS];
                a[POS] = a[DER];
                a[DER] = AUX;
                POS = DER;
                while (a[POS] >= a[IZQ] && (POS != IZQ)) {
                    IZQ = IZQ + 1;
                }
                if (POS != IZQ) {
                    BAND = true;
                    AUX = a[POS];
                    a[POS] = a[IZQ];
                    a[IZQ] = AUX;
                    POS = IZQ;
                }
            }

        }
        if ((POS - 1) > INI) {
            ordenareducer(a, INI, POS - 1);
        }
        if (FIN > (POS + 1)) {
            ordenareducer(a, POS + 1, FIN);
        }
    }

    static void imprimirArreglo(int a[], int n) {
        for (int i = 0; i < n; i++) {
            String c;
            c = (i % 10 == 0) ? "\n" : " ";
            System.out.print(c + a[i]);
        }
    }

    static void entradaArreglo(int a[], int n) throws IOException {
        System.out.println("\n Entrada de los elementos");
        for (int i = 0; i < n; i++) {
            System.out.print("a[" + i + "]= ");
            a[i] = Integer.parseInt(entrada.readLine());
        }
    }

}