evp 7

                         ordenamiento por borbuja

El ordenamiento por borbuja es bastante sencillo, consiste en evaluar pares de elementos contiguos del arreglo y si el primero es mayor que el siguiente los intercambia (los más chicos quedan abajo). Todo ésto sucede dentro de dos ciclos for que recorren el arreglo. El ciclo más interno realiza las comparaciones, y se asegura ya en la primera pasada completa que el elemento ás grande del arreglo suba a la posición más alta (ésto más adelante nos permitirá desarrollar un algorítmo mejorado del método burbuja)

                 Vamos a ver un ejemplo. 

 Esta es nuestra lista:

4 - 3 - 5 - 2 - 1

Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos:

3 - 4 - 5 - 2 - 1

Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos:

3 - 4 - 2 - 5 - 1

Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente:

3 - 4 - 2 - 1 - 5

Repitiendo este proceso vamos obteniendo los siguientes resultados:

3 - 2 - 1 - 4 - 5

2 - 1 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5 

Éste es el análisis para la versión no optimizada del algoritmo:

• Estabilidad: Este algoritmo nunca intercambia registros con clave iguales. Por lo tanto es estable.
• Requirimiento de memoria: Este algoritmo sólo requiere de una variable adicional para realizar los intercambios.
• Tiempo de ejecucion: El ciclo interno se ejecuta n veces para una lista de n elementos. El ciclo externo también se ejecuta n veces. Es decir, la complejidad es n * n = O(n²). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue siendo O(n²).

Ventajas:

• Fácil implementación.
• No requiere memoria adicional.

Desventajas:

• Muy lento.
• Realiza numerosas comparaciones.
• Realiza numerosos intercambios. 

Ejemplos de aplicaion :

 #include <iostream>
 using namespace::std;

 enum { Tamano = 10};
 // Cambiar la variable Tamano para ordenar una
 // cantidad diferente de datos
 

 /*Prototipo de funcion Imprime */
 void Imprime( int A[]);

 /*prototipo de funcion Recibe */
 void Recibe ( int B[]);

 /*Prototipo de funcion Burbuja */
 void Burbuja( int C[]);
 

 int main()

 {           // Abre main

 int Arreglo[Tamano] = {0, 0};
 // El Arreglo se ha inicializado a 0
 
 cout <<"\nEste programa recibe una serie de %d numeros enteros" << Tamano;
 cout <<" y los ordena por medio del algoritmo de ordenacion burbuja. "<< endl; 

 /*Se llena el arreglo mediante un llamado a la funcion Recibe*/
 Recibe(Arreglo);

 /*Se imprime el arreglo con las entradas en el orden original */
 cout <<"\nEsta es el orden en que se introdujeron los elementos: " <<endl;
 Imprime(Arreglo);

 /*Se ordena el arreglo mediante una llamada a la funcion Burbuja*/
 Burbuja(Arreglo);

 /*Se imprime el arreglo ordenado */
 cout <<"\nEste es el orden despues de el ordenamiento burbuja. " <<endl;
 Imprime(Arreglo);

 return 0;
 }           // Cierra main


 //////////////////////////////////////////////////
 //FUNCION IMPRIME 
 /////////////////////////////////////////////////
 
 void Imprime( int A[] )
 {     // Abre la funcion Imprime
 
 for ( int j = 0; j < Tamano; j++ )
 {      // Abre for
 cout << "\t" << A[j]; 

 if ( 0 == j + 1 % 10)
 cout <<endl <<endl;

 }      // Cierra for

 cout <<endl <<endl;
 }     // Cierra la funcion Imprime

 ////////////////////////////////////////////////////////////////////////////
 //FUNCION RECIBE
 //////////////////////////////////////////////////////////////////////////
 

 void Recibe( int B[] )
 {         // Abre funcion Recibe
 
 for ( int i = 0; i < Tamano; i++ )
 {      // Abre for
 cout << "\nIntroduzca el elemento " << i + 1 << " del arreglo: " << endl;
 cin >> B[i];
 }
 }         // Cierra funcion Recibe



 ///////////////////////////////////////////////
 //FUNCION BURBUJA
 /////////////////////////////////////////////////
 

  void Burbuja( int C[])
 {                 // Abre funcion Burbuja

 int temporal;

 for ( int m = 0; m < Tamano - 1; m++ )
 for ( int n = 0; n <= Tamano - 1; n++ )
 {    // Abre for
     
 if ( C[n] > C[n + 1] )
 {    // Abre if
 temporal = C[n]; 
 C[n] = C[n + 1];
 C[n + 1] = temporal;

 }    // Cierra if 
 }         //Cierra for
 }                 // Cierra funcion Burbuja