Método Burbuja

Este método consiste permite ordenar de menor a mayor (o de menor a mayor) una serie de números cualquiera.

El método va comparando pares de números.

Ejemplo:

arreglo original	7	5	3	25	acción
paso 1	5	7	3	25	compara el 7 con 5 y los intercambia
	5	3	7	25	compara el 7 con 3 y los intercambia
	5	3	7	25	compara el 7 con 25 y no los intercambia
paso 2	3	5	7	25	compara el 3 con 5 y los intercambia
	3	5	7	25	compara el 5 con 7 y no los intercambia
	3	5	7	25	compara el 7 con 25 y no los intercambia
paso 3	3	5	7	25	compara el 3 con 5 y no los intercambia
	3	5	7	25	compara el 5 con 7 y no los intercambia
	3	5	7	25	compara el 7 con 25 y no los intercambia

Pseudocódigo del método burbuja

1.- inicio
2.- reservar espacio en la memoria
3.- Leer secuencia
4.- para (i=1,...,N-1) hacer
5.-	para (j=1,...,N-1) hacer
6.-		comparar X[i] con X[i+1] y ordenar
7.-	fin para
8.- fin para
9.- imprimir secuencia de números ordenados
10.- fin

2º refinamiento

1.- inicio
2.- reservar espacio en la memoria
3.- Leer secuencia
4.- para (i=1,...,N-1) hacer
5.-	para (j=1,...,N-1) hacer
6.-		si X[i] > X[i+1] entonces
7.-			permutar X[i] con X[i+1]
8.-		fin si
9.-	fin para
10.- fin para
11.- imprimir secuencia de números ordenados
12.- fin

3^er refinamiento

1.- inicio
2.- reservar espacio en la memoria
3.- Leer secuencia
4.- para (i=1,...,N-1) hacer
5.-	para (j=1,...,N-1) hacer
6.-		si X[i] > X[i+1] entonces
7.-			AUX=X[i];
8.-			X[i]=X[i+1];
9.-			X[i+1]=AUX;
10.-		fin si
11.-	fin para
12.- fin para
13.- imprimir secuencia de números ordenados
14.- fin

El método burbuja es simple de implementar, pero es muy lento, por lo cual es sólo adecuado para pequeños conjuntos de números.

Nº de operaciones menor o igual a (N-1)(N-1)(1+3)
(el 3 es por las 3 asignaciones para permutar)
O sea Nº de operaciones menor o igual a 4(N-1)²

Por ejemplo, para ordenar 10 números:

Nº de operaciones menor igual que 4 x 9² = 324

Si poseemos un PC que trabaje a 400MHz,

==> 1 operación = 1/(4 x 10⁸) segundos

Por lo tanto, para ejcutar las 324 operaciones necesitamos:

324/(4 x 10⁸) segundos = 8.1 x 10^-7 segundos

Otro ejemplo, para ordenar 1000 números:

Nº de operaciones menor igual que 4 x 999² = 3992004

Si utilizamos el mismo PC:

3992004/(4 x 10⁸) segundos = 9.98 x 10^-3 segundos

Supongamos que queremos ordenar los RUTs de los aproximadamente 18 millones e chilenos

Nº de operaciones menor igual que 4 x (18 x 10⁶)² = 1.296 x 10¹⁵

Si utilizamos el mismo PC:

(1.296 x 10¹⁵)/(4 x 10⁸) segundos = 3240000 segundos

((3240000/60)/60)/24 = 37.5 días

Ejemplo Código Método Burbuja burbuja1.zip

Home



© 2000 Made in Bufoland