varios

UNIVERSIDAD CENTRAL DEL ECUADOR


Integrantes: Édison Jiménez, Manuel Arequipa

MARCO TEORICO

ORDENACIÓN POR BURBUJA

La técnica utilizada se denomina ordenación por burbuja u ordenación por hundimiento debido a que los valores más pequeños “burbujean” gradualmente (suben) hacia la cima o parte superior del array de modo similar a como suben las burbujas en el agua, mientras que losvalores mayores se hunden en la parte inferior del array. La técnica consiste en hacer varias pasadas a través del array. En cada pasada, se comparan pare- jas sucesivas de elementos. Si una pareja está en orden creciente (o los valores son idénticos), se dejan los valores como están. Si una pareja está en orden decreciente, sus valores se intercambian en el array.


10.2.1. Algoritmo de laburbuja

En el caso de un array (lista) con n elementos, la ordenación por burbuja requiere hasta n-1 pasadas. Por cada pasada se comparan elementos adyacentes y se intercambian sus valores cuando el primer elemento es mayor que el segundo elemento. Al final de cada pasada, el elemento mayor ha “burbujeado” hasta la cima de la sublista actual. Por ejemplo, después que la pasada 0 está completa, lacola de la lista A[n-1] está ordenada y el frente de la lista permanece desordenado. Las etapas del algoritmo son :

• En la pasada 0 se comparan elementos adyacentes

(A[0],A[1]),(A[1],A[2]),(A[2],A[3]),...(A[n-2],A[n-1])

Se realizan n-1 comparaciones, por cada pareja (A[i],A[i+1]) se intercambian los valores si
A[i+1] < A[i].
Al final de la pasada, el elemento mayor de la lista estásituado en A[n-1].
• En la pasada 1 se realizan las mismas comparaciones e intercambios, terminando con el elemento de
segundo mayor valor en A[n-2].
• El proceso termina con la pasada n-1, en la que el elemento más pequeño se almacena en A[0] .

El algoritmo tiene una mejora inmediata, el proceso de ordenación puede terminar en la pasada n-1, o bien antes. Si en un una pasada no se produceintercambio alguno entre elementos del array es porque ya está ordenado, entonces no es necesario mas pasadas.
El ejemplo siguiente ilustra el funcionamiento del algoritmo de la burbuja con un array de 5 elemen- tos (A = 50, 20, 40, 80, 30) donde se introduce una variable interruptor para detectar si se ha pro- ducido intercambio en la pasada.


Pasada 0

Intercambio 50 y 20




Intercambio50 y 40




50 y 80 ordenados





Intercambio 80 y 30




• Elemento mayor es 80
• Interruptor = TRUE



Pasada 1 20 y 40 ordenados




40 y 50 ordenados




Se intercambian 50 y 30




• 50 y 80 elementos mayores ordenados
• Interruptor = TRUE

En la pasada 2, sólo se hacen dos comparaciones y se produce un intercambio.


Pasada 2 20 y 40 ordenados• Se intercambian 40 y 30
• Interruptor = TRUE







En la pasada 3, se hace una única comparación de 20 y 30, y no se produce intercambio.

Pasada 3 20 y 30 ordenados




• Lista ordenada
• Interruptor = FALSE


En consecuencia, el algoritmo de ordenación de burbuja mejorado contempla dos bucles anidados : el bucle externo controla la cantidad de pasadas (al principio dela primera pasada todavía no se ha produci- do ningún intercambio por tanto la variable interruptor se pone a valor falso (0) ; el bucle interno con- trola cada pasada individualmente y cuando se produce un intercambio, cambia el valor de interruptor a verdadero (1).
El algoritmo terminará, bien cuando se finalice la última pasada (n-1) o bien cuando el valor del inte- rruptor sea falso (0), esdecir no se haya hecho ningún intercambio. La condición para realizar una nue- va pasada se define en la expresión lógica:

(pasada < n-1) && interruptor


10.2.2. Codificación del algoritmo de la burbuja

La función ordBurbuja() implementa el algoritmo de ordenación de la burbuja. Tiene dos argumentos, el array que se va a ordenar crecientemente, y el número de elementos n. En la...