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.

3 comentarios:

Anónimo dijo...

Muchas gracias, tus apuntes de QuickSort y RadixSort me fueron de mucha utilidad ara u trabajo final.

Anónimo dijo...

gracias, realmente me ayudaron mucho estos apuntes de ordenacion.

Anónimo dijo...

ola ke ase

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar