domingo, octubre 03, 2010

Ordenación por Burbuja - Bubble Sort

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.

4 comentarios:

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...