Algoritmo de Ordenación por Intercambio Directo (Burbuja)

Este método también se conoce como método de la burbuja. Tiene dos versiones basadas en la misma idea: recorrer sucesivamente el vector comparando los elementos consecutivos e intercambiándolos cuando estén descolocados. En una de las versiones el vector se recorre de izquierda a derecha, desplazando los valores mayores hacia su derecha, y en la otra se recorre de derecha a izquierda, desplazando los valores menores hacia su izquierda, ambos para la clasificación en orden ascendente.
Cada pasada sobre el vector lleva un nuevo elemento a su posición definitiva, y en orden, en el extremo de la zona de comparación considerada (extremo derecho en el caso de recorrido de izquierda a derecha y en el extremo izquierdo en el caso de recorrido de derecha a izquierda), por lo que en la siguiente pasada se excluye de las comparaciones.
El algoritmo consiste en aplicar los siguientes pasos, considerando inicialmente todas las posiciones del vector:

1. Se comparan los valores de las posiciones contiguas, intercambiándolos si están mal colocados.
2. Una vez realizadas todas las posibles comparaciones, se descarta la posición del extremo izquierdo (si se realiza un recorrido de derecha a izquierda) o del extremo derecho (si se realiza un recorrido de izquierda a derecha) del intervalo de posiciones consideradas en la iteración actual, repitiéndose el proceso hasta completar un total de N-1 iteraciones.

Podemos mejorar el método, deteniendo la ordenación, si se detecta que en una pasada no se ha producido ningún intercambio, lo que significa que los datos ya están ordenados. Es necesario realizar una pasada completa sin intercambios antes de poder forzar el fin del algoritmo. Con esta mejora el número de iteraciones del algoritmo estará condicionado por el grado de desorden inicial de los datos. (Ver algoritmo de Ordenación por intercambio directo con test)
PSEUDOCÓDIGO

Ordenación por intercambio directo (izquierda-derecha)

    MÓDULO ordenacion_intercambio_directo_izq_der

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe N entera
       VARIABLES
           I, J enteras
           AUX de tipo T
    INICIO
           Para J desde 1 hasta N-1
               Para I desde 1 hasta N-J
                    Si ( V(I) > V(I+1) ) entonces
                        AUX <- V(I)
                        V(I) <- V(I+1)
                        V(I+1) <- AUX
                    fin-si
               fin-para
           fin-para
    FIN

Ordenación por intercambio directo (derecha-izquierda)

    MÓDULO ordenacion_intercambio_directo_der_izq

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe N entera
       VARIABLES
           I, J enteras
           AUX de tipo T
    INICIO
           Para J desde 1 hasta N-1
               Para I desde N hasta J+1 con incremento -1
                    Si ( V(I-1) > V(I) ) entonces
                       AUX <- V(I-1)
                       V(I-1) <- V(I)
                       V(I) <- AUX
                    fin-si
               fin-para
           fin-para
    FIN

Ordenación por intercambio directo con test

    MÓDULO ordenacion_intercambio_directo_test

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe N entera
       VARIABLES
           I, J enteras
           SEGUIR lógica
           AUX de tipo T
    INICIO
           J <- 1
           SEGUIR <- VERDADERO
           Mientras ( (SEGUIR = VERDADERO)   y   (J < N) ) hacer
               SEGUIR <- FALSO
               Para I desde 1 hasta N-J
                   Si ( V(I) > V(I+1) ) entonces
                       AUX <- V(I)
                       V(I) <- V(I+1)
                       V(I+1) <- AUX
                       SEGUIR <- VERDADERO
                   fin-si
               fin-para
               J <- J+1
           fin-mientras
    FIN

CÓDIGO C

/*Ordena un vector (de menor a mayor) por el método de la burbuja (izquierda-derecha)*/
burbuja(int *v, int n)
{
int i, j, aux;

	for(j=0;j<(n-1);j++)
	{

		for(i=0;i<n-(j+1);i++)
		{
			if(v[i]>v[i+1])
			{
			aux=v[i];
			v[i]=v[i+1];
			v[i+1]=aux;
			}
		}	
	}
}

---

Volver al índice

Volver a Búsqueda y Ordenación Interna