El_algoritmo_de_la_burbuja_.docx

EL ALGORITMO DE LA BURBUJA Uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada (patrón de arreglo). El objetivo de este proceso generalmente es facilitar la búsqueda de uno o más elementos pertenecientes a un conjunto. Como ejemplos de conjunto de datos ordenados tenemos:  

Meses del año (ordenados de 1 al 12). Listado de estudiantes (ordenados alfabéticamente).

La ordenación, tanto numérica como alfanumérica, sigue las mismas reglas que empleamos nosotros en la vida normal. Esto es, un dato numérico es mayor que otro cuando su valor es más grande, y una cadena de caracteres es mayor que otra cuando esta después por orden alfabético.

El algoritmo de ordenación por el método de la burbuja, también conocido como intercambio directo, es uno de los más simples que se conocen. Se basa en una serie de intercambios entre elementos adyacentes. Esos intercambios dan la impresíón de que cada elemento va ascendiendo a través del array acercándose cada vez más a su posición final, recordando a cómo ascienden las burbujas de gas en un líquido.

¡ ejemplo . Suponer que queremos ordenar estos valores con el algoritmo de la burbuja: 45, 52, 21, 37, 49, así pues, n=5 1ª pasada: comparamos cada uno de los cuatro primeros (n-1) con los que le siguen. Si un elemento no está en orden con respecto al siguiente, los intercambiamos de sitio y seguimos. El elemento de mayor valor (52) irá "ascendiendo" hasta la última posición. 45, 52, 21, 37, 49 → Comparar 45 y 52. (1º y 2º) Están en orden. Seguimos. 45, 52, 21, 37, 49 → Comparar 52 y 21. (2º y 3º) No están en orden. Intercambio. 45, 21, 52, 37, 49 → seguimos 45, 21, 52, 37, 49 → Comparar 52 y 37 (3º y 4º). No están en orden. Intercambio. 45, 21, 37, 52, 49 → seguimos 45, 21, 37, 52, 49 → Comparar 52 y 49. (4º y 5º). No están en orden. Intercambio. 45, 21, 37, 49, 52 → Ya hemos terminado esta pasada. 45, 21, 37, 49, 52 → El 5º elemento ya está en su sitio.

2ª pasada: comparamos cada uno de los tres primeros (n-2) con los que le siguen. No llegamos a hacer comparaciones que involucren al 5º elemento, porque la primera pasada hizo que el mayor de todos los elementos ocupara la última posición, con lo cual, sabemos que ese ya está en su sitio. Trabajaremos sólo con los cuatro que quedan. 45, 21, 37, 49, 52 → Comparar 1º y 2º. No están en orden. Intercambio. 21, 45, 37, 49, 52 → seguimos 21, 45, 37, 49, 52 → Comparar 2º y 3º. No están en orden. Intercambio. 21, 37, 45, 49, 52 → seguimos 21, 37, 45, 49, 52 → Comparar 3º y 4º. Están en orden. Pasada terminada. 21, 37, 45, 49, 52 → El 4º elemento ya está en su sitio. 3ª pasada: Comparamos cada uno de los dos primeros (n-3) con los siguientes. 21, 37, 45, 49, 52 → 1º y 2º. Están en orden. Seguimos. 21, 37, 45, 49, 52 → 2º y 3º. Están en orden. Pasada terminada. 21, 37, 45, 49, 52 → Ya tenemos tres en orden.

4ª y última pasada: Comparamos el primero con el segundo. 21, 37, 45, 49, 52 → 1º y 2º están en orden. Pasada terminada. 21, 37, 45, 49, 52 → Ya tenemos los cuatro últimos en orden. 21, 37, 45, 49, 52 → Así pues, el primero también lo está. Expresado en pseudocódigo, podría ser algo como esto: Pseudocódigo algoritmo burbuja( A : array de n elementos indizados de 1 a n) para i desde 1 hasta n-1 hacer: //las n-1 pasadas para j desde 1 hasta n-i hacer: //el recorrido si A[j] > A[j+1] entonces //Si no están en orden intercambiar A[j] y A[j+1] //Se intercambian fin para fin para fin algoritmo

Por supuesto, es necesario adaptarlo a las necesidades concretas. Por ejemplo, en C/C++/C#/Java, etc... los índices de los arrays empiezan en 0 y terminan en n-1. El array a ordenar no tiene por qué ser de enteros, puede ser de cualquier cosa ordenable, pero entonces, análogamente, la operación de comparación (">") debe ser sustituida por la operación que compare nuestros elementos por el criterio que nosotros queramos. #include #define SIZE 7

void main(void) { int vector[SIZE]; int j, i, temp; printf("Introduce los %d valores para ordenar:\n", SIZE); for(i=0; i<SIZE; i++) { printf("%d: ", i+1); scanf("%d", &vector[i]); printf("\n"); } /* se aplica el algoritmo de la burbuja */ for(i=0; i<(SIZE-1); i++) { for (j=i+1; j<SIZE; j++) { if(vector[j]
}