Ordenaciones

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.


Ordenación por Selección - SelectSort

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.


Ordenación por Inserción

El algoritmo de ordenación por inserción toma cada elemento a partir del segundo y recorre el vector en sentido inverso ubicando el elemento en su posición correcta haciendo los intercambios necesarios. Cuando termina de ubicar un elemento en su posición correcta, continúa con el siguiente elemento hasta hacer este proceso con todos los elementos del arreglo.

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

// Algoritmo de ordenacion por insercion
    public static void ordenacionInsercion(int[] v) {
        final int N = v.length;
        for(int i=1; i<N; i++) {
            int j=i;
            while(j>0 && v[j]<v[j-1] ){
                int tmp = v[j];
                v[j]    = v[j-1];
                v[j-1]  = tmp;
                j--;
            }
        }
    }

La complejidad del algoritmo es cuadrática, puesto que cada para insertar el elemento en su posición correcta se deben recorrer los elementos anteriores a él. Sin embargo, este algoritmo presenta un mejor desempeño que otros algoritmos de complejidad cuadrática pues no es necesario recorrer para cada elemento la totalidad de los elementos anteriores, sino solamente hasta la posición correcta para un elemento en particular. 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.


Ordenación por Burbuja - BubbleSort

El algoritmo de ordenación por el método de la burbuja, o Bubble Sort recorre todo el arreglo comparando cada uno de los elementos con el elemento siguiente e intercambiándolos de ser necesario. Al finalizar este proceso, el elemento mayor queda ubicado en la última posición de arreglo, mientras que todos los elementos menores han "ascendido" una posición. El proceso se continúa repitiendo nuevamente desde la posición inicial del arreglo hasta que cada elemento "caiga" a su posición correcta.

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

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

La complejidad del algoritmo es cuadrática, puesto que cada para lograr llevar un elemento a la última posición del arreglo se deben recorrer todos los elementos del mismo, y este proceso se repite para todos los demás elementos. 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.


Ordenación Shaker

El algoritmo de ordenación por el método Shaker, también conocido como "Cocktail" o "Sacudida" es una mejora del método de la burbuja en la cual el proceso se realiza tanto desde la primera posición a la última del arreglo como en sentido inverso, evitando así que los elementos más pequeños tarden un mayor tiempo en "ascender" a las posiciones superiores.

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

// Algoritmo de ordenacion Shaker Sort
    public static void ordenacionShaker(int[] v) {
        final int N = v.length;
        int limInferior = 0;
        int limSuperior = N-1;
        while(limInferior <= limSuperior) {
            for(int j=limInferior; j<limSuperior; j++) {
                if(v[j]>v[j+1]) {
                    int tmp = v[j];
                    v[j]    = v[j+1];
                    v[j+1]  = tmp;
                }
            }
            limSuperior--;
            for(int j=limSuperior;j>limInferior; j--) {
                if(v[j]<v[j-1]) {
                    int tmp = v[j];
                    v[j]    = v[j-1];
                    v[j-1]  = tmp;
                }
            }
            limInferior++;
        }
    }
La complejidad del algoritmo es cuadrática, puesto que si bien mejora un poco el rendimiento del método de la burbuja, no cambia el hecho de recorrer el arreglo una vez por cada cada elemento que se quiere dejar en su posición correcta. 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.


Ordenación Shell

El algoritmo de ordenación Shell Sort se base en el algoritmo de ordenación por inserción, el cuál tiene un muy buen desempeño si el vector está relativamente ordenado.  Entonces, teniendo esto como premisa, el Shell Sort, ordena por inserción subconjuntos del vector que están separados entre sí por distancias relativamente mayores (empezando con distancias iguales a la mitad del tamaño del vector), la cuales se van reduciendo rápidamente.

El siguiente código escrito en el lenguaje JAVA recibe como parámetro el conjunto de elementos representado en un arreglo de números enteros y define inicialmente el incremento como la mitad del tamaño del vector, entonces se ordenan por inserción los elementos de las posiciones v[0] y v[n/2], luego los de las posiciones v[1] y v[n/2] +1, y así sucesivamente.  Cuando termina este proceso, se divide por dos el tamaño del incremento y se repite el proceso hasta que el incremento sea igual a 1, en cuyo caso su comportamiento sería exactamente el del algoritmo de ordenación por inserción.

// Algoritmo de ordenacion ShellSort
    public static void ordenacionShell(int[] v) {
        final int N = v.length;
        int incremento = N;
        do {
            incremento=incremento/2;
            for(int k=0; k<incremento;k++) {
                for(int i=incremento+k; i<N; i+=incremento) {
                    int j=i;
                    while(j-incremento>=0 && v[j]<v[j-incremento] ){
                        int tmp = v[j];
                        v[j]    = v[j-incremento];
                        v[j-incremento]  = tmp;
                        j-=incremento;
                    }
                }
            }
        } while(incremento > 1);
    }

En cuanto a la complejidad del algoritmo, ésta tiende a ser O(n log n), teniendo en cuenta que este método se basa en la ordenación por inserción la cual tiende a ser O(n) en el mejor de los casos (es decir, cuando el vector está casi ordenado), y que el proceso de ordenación por inserción se repite tantas veces como tarde la variable incremento en llegar al valor de 1, que es aproximadamente el logaritmo en base 2 del tamaño del vector.




Ordenación por Combinación

El algoritmo de ordenación por combinación o Merge Sort, basado en la técnica Divide y Vencerás, ordena recursivamente un conjunto de elementos dividiéndolo en dos, ordenando cada una de estas partes en forma independiente y combinando los dos resultados.

Este código en el lenguaje de programación JAVA 1.6 recibe como entrada un arreglo de números enteros denominado v, lo parte utilizando el método copyOfRange de la clase java.util.Arrays, se llama recursivamente con cada una de las dos partes como argumento y, una vez terminada la ordenación de dichas partes, invoca al proceso de combinación de las dos respuestas implementado en el método combinar, el cual recibe como entrada el arreglo original y las dos mitades del mismo previamente ordenadas que serán combinadas en el arreglo original.

// Algoritmo de ordenacion por combinacion: Merge Sort
    public static void ordenacionCombinacion(int[] v) {
        final int N = v.length;
        if(N<=1) return;
        int mitad=N/2;
        int[] izq = Arrays.copyOfRange(v, 0, mitad);
        int[] der = Arrays.copyOfRange(v, mitad, N);
        ordenacionCombinacion(izq);
        ordenacionCombinacion(der);
        combinar(v, izq, der);
    }

    public static void combinar(int[] resp, int[] izq, int[] der) {
        int i = 0;
        int j = 0;
        for(int k=0; k<resp.length;k  ) {
            if(i>=izq.length) { resp[k]=der[j++]; continue; }
            if(j>=der.length) { resp[k]=izq[i++]; continue; }
            resp[k]=(izq[i]<der[j])?izq[i]:der[j];
        }
    }

Este algoritmo tiene complejidad O(n log n), que se obtiene resolviendo la ecuación de recurrencias T(n) = k n + 2 T(n/2).  La solución a la misma se puede comprobar gracias a la tecnologías del sitio WolframAlpha


Ordenación Rápida

El algoritmo de ordenación rápida, o QuickSort, se implementa a través de un procedimiento recursivo que implementa tres pasos:

  1. Selecciona un elemento de referencia o pivote, con base en el cual se reorganizará el arreglo a ordenar
  2. Reorganiza el arreglo de tal manera que a la izquierda del pivote se sitúen todos los elementos menores a él y a la derecha los mayores.
  3. Se invoca recursivamente el método de ordenación tanto para el subconjunto de elementos de la izquierda como para el de la derecha.

En la siguiente implementación en JAVA, el proceso de ordenación está implementado en el método quickSort, mientras que el método ordenacionRapida sirve para presentar al usuario final un mismo estilo de invocación del algoritmo.

// Ordenacion rapida: Quick Sort
    public static void ordenacionRapida(int[] v) {
        final int N = v.length;
        quickSort(v,0,N-1);
    }

    public static void quickSort(int[] v, int inicio, int fin) {
        if(inicio>=fin) return ;
        int pivote = v[inicio];
        int izq    = inicio+1;
        int der    = fin;
        while(izq<=der) {
            while(izq<=fin   && v[izq]< pivote) izq++;
            while(der>inicio && v[der]>=pivote) der--;
            if(izq<der) {
                int tmp = v[izq];
                v[izq]  = v[der];
                v[der]  = tmp;
            }
        }
        if(der>inicio) {
            int tmp  = v[inicio];
            v[inicio]= v[der];
            v[der]   = tmp;
        }
        quickSort(v,inicio, der-1);
        quickSort(v, der+1, fin);
    }

Este algoritmo tiene complejidad O(n log n), que se obtiene resolviendo la ecuación de recurrencias T(n) = k n + 2 T(n/2).  La solución a esta ecuación se puede comprobar utilizando la tecnología del motor de cálculo WolframAlpha 


Ordenación por Montículos

El algoritmo de ordenación por montículos o Heap Sort recorre el conjunto de elementos desde la posición de la mitad hasta la primera organizando el montículo correspondiente a dicho elemento.  Una vez terminado este proceso, se inicia el proceso de ordenación intercambiando el primer elemento por el último del arreglo y reorganizando el montículo a partir de la primera posición.

// Ordenacion por monticulos - HeapSort
    public static void ordenacionMonticulos(int[] v) {
        final int N = v.length;
        for(int nodo = N/2; nodo>=0; nodo--) hacerMonticulo(v, nodo, N-1);
        for(int nodo = N-1; nodo>=0; nodo--) {
            int tmp = v[0];
            v[0]    = v[nodo];
            v[nodo] = tmp;
            hacerMonticulo(v, 0, nodo-1);
        }
    }

    public static void hacerMonticulo(int[] v, int nodo, int fin) {
        int izq = 2*nodo+1;
        int der = izq+1;
        int may;
        if(izq>fin) return;
        if(der>fin) may=izq;
        else may= v[izq]>v[der]?izq:der;
        if(v[nodo] < v[may]) {
            int tmp = v[nodo];
            v[nodo] = v[may];
            v[may]  = tmp;
            hacerMonticulo(v, may, fin);
        }
    }

La complejidad del algoritmo de ordenación por montículos es O(n log n) teniendo en cuenta que el proceso de organizar el montículo en el peor caso solamente tiene que hacer intercambios sobre una sola línea de elementos desde la raíz del ábol hasta alguna de las hojas para un máximo de log n intercambios.


Ordenación por Residuos - Radix Sort

El método de ordenación por residuos, o RadixSort, utiliza una aproximación diferente a la de comparar los elementos del arreglo entre sí. En vez de esto, este algoritmo recorre el arreglo trasladando cada elemento a una cola determinada por el residuo, o dígito menos significativo del número. Cuando todos los elementos han sido trasladados a las colas, se recorren todas las colas en orden trasladando ahora los elementos al vector. El proceso se repite ahora para los demás dígitos de los elementos del vector.

Si bien se habla de dígitos (unidades, decenas, centenas, etc), para un computador es más eficiente hacer las operaciones a nivel de bit, con desplazamientos, que las operaciones de división y residuo. Por tal motivo, la implementación que se presenta a continuación utiliza corrimientos de 4 bits, que se pueden representar como dígitos hexadecimales.


public static void ordenacionResiduos(int[] v) {
        int max    = 1;     // cantidad de repeticiones
        int nbytes = 4;     // numero de bytes a desplazar
        int nColas = (int) Math.pow(2,nbytes) ;
        // Creación e inicialización del arreglo de colas
        Queue<Integer>[] cola = new LinkedList[nColas];
        for(int i=0; i<nColas; i++) cola[i]=new LinkedList<Integer>();

        int     div     = 0;        // posición a comparar
        for(int i=0; i<max; i++) {
            // parte 1: recorrer el vector  para guardar cada elemento
            // en la cola correspondiente
            for(int numero: v) {
                // buscar el mayor número del vector
                if(i==0) if(numero>max) max=numero;
                // calcular en qué cola debe ir cada número
                int numCola = (numero>>div) & 0xf;
                cola[numCola].add(numero);
            }
            div = div+nbytes;

            // parte 2: recorrer las colas en orden para poner cada
            // elemento en el vector;
            int j=0;
            for(Queue<Integer> c: cola) {
                while(!c.isEmpty()) v[j++]=c.remove();
            }
            // la primera vez se actualiza el número de veces que se
            // debe ejecutar el proceso
            if(i==0) { max = (int) (Math.log(max)/Math.log(nColas)) + 1; }
        }
    }


La complejidad de este algoritmo es lineal, O(NxM), donde N es el número de elementos del arreglo y M es el número de dígitos del mayor elemento del vector.

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...