Ordenación Clásica

El algoritmo de ordenación clásica es el primer algoritmo de ordenación que se enseña, normalmente dentro de un curso básico de algoritmos o de programación. Consiste básicamente en tomar el primer elemento del arreglo e irlo comparando con los demás y, en caso de encontrar un elemento menor que él, intercambiarlo inmediatamente. Una vez terminado de recorrer el vector, se tiene en la primera posición al menor elemento de todos. El proceso se repite ahora con el segundo elemento del arreglo y así para todos los elementos.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritmo de ordenacion tradicional.
    public static void ordenacionTradicional(int[] v) {
        final int N = v.length;
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                if(v[i]>v[j]) {
                    int tmp = v[i];
                    v[i] = v[j];
                    v[j] = tmp;
                }
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada uno de los n elementos del arreglo se compara con los i-1 elementos posteriores a él. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.