Ordenación por Selección

El algoritmo de ordenación por selección recorre todo el arreglo desde la primera posición buscando el menor elemento de todos. Cuando termina, lo reemplazar por el elemento de la primera posición y repite todo el proceso con el segundo elemento y así sucesivamente.

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

// Algoritm de ordenacion por seleccion.
    public static void ordenacionSeleccion(int[] v) {
        final int N = v.length;
        for(int i=0; i<N; i++) {
            int posMenor = i;
            for(int j=i+1; j<N; j++) {
                if(v[j]<v[posMenor]) posMenor=j;
            }
            if(posMenor!=i) {
                int tmp     = v[i];
                v[i]        = v[posMenor];
                v[posMenor] = tmp;
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada para identificar cuál elemento va en cada posición se debe comparar 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.