ORDENAMIENTO POR EL MÉTODO DE BURBUJA

El Ordenamiento de Burbuja también es conocido como ordenamiento por intercambio directo y es uno de los algoritmos de ordenamiento más sencillos que existen, además de uno de los más simples de implementar.

¿Sabes por qué recibe este nombre?

El algoritmo consiste en revisar cada elemento de un arreglo o lista con el siguiente, intercambiándolos si el segundo es menor que el primero. Es necesario que esta revisión se realice varias veces hasta que se encuentren todos en el orden correcto. A estas alturas, ya debes haber escuchado al menos una vez sobre este algoritmo y conocer la forma detallada en que opera, por eso, en esta ocasión la forma en que vamos a trabajar con él, es algo distinta.

¿De qué orden es este algoritmo?

Ejercicio:

Proporcione los números de intercambios necesarios para los casos mejor, peor y promedio en el ordenamiento por burbuja, cuya definición puede encontrarse en casi todos los libros de texto sobre algoritmos. Los análisis de los casos mejor y peor son triviales. El análisis para el caso promedio puede realizarse mediante el siguiente proceso:

1.- Defina la inversa de una permutación. Sea a1,a2,..., an una permutación del conjunto (1, 2,..., n). Si i < j y aj < a¡, entonces (ai, aj) se denomina inversión de esta permutación. Por ejemplo, (3,2), (3,1), (2,1), (4,1) son, todas, inversiones de la permutación (3, 2,4,1).

2.- Encuentre la relación entre la probabilidad de que una permutación dada tenga exactamente k inversiones y la probabilidad de que el número de permutaciones de n elementos tenga exactamente k inversiones.

3.- Aplique inducción para demostrar que el número medio de intercambios necesarios para el ordenamiento por burbuja es n(n — 1)/4.

Con el siguiente programa, verificamos los tiempos antes y después de utilizar el algoritmo de ordenamiento para acomodar los elementos de un arreglo y obtenemos el total. Este experimento lo podemos hacer con diferentes tamaños de entrada y probarlo en máquinas con procesadores diferentes ó con sistemas operativos distintos, para así verificar su eficiencia para condiciones de hardware y software distintas.

using System;
using System.Threading;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class EficienciaBurbuja
{
static void Main(string[] args)
{

//Declaración de variables
long Ttotal, Tinicio, Tfinal;
Console.WriteLine("Escribe el tamaño del arreglo:");
String ab = Console.ReadLine();
int tam = int.Parse(ab);
int[] a = new int[tam];
EficienciaBurbuja burb = new EficienciaBurbuja();

//Construcción del arreglo aleatorio
Console.WriteLine("Arreglo aleatorio: ");
burb.aleatorio(a);

//Cálculos y ordenación del arreglo
Tinicio = System.DateTime.Now.Millisecond; //Cálculo del tiempo inicial
burb.Burbuja(a); //Ordenación del arreglo
Tfinal = System.DateTime.Now.Millisecond; //Cálculo tiempo final
Ttotal = Tfinal - Tinicio; //Cálculo del tiempo Total en milisegundos

//Muestra del arreglo ordenado
Console.WriteLine();
Console.WriteLine("Arreglo ordenado: ");
burb.arregloOrdenado(a);

//Muestra del tiempo
Console.WriteLine();
Console.WriteLine("El tiempo inicial fue: " + Tinicio);
Console.WriteLine("El tiempo final fue: " + Tfinal);
Console.WriteLine("El tiempo total del procesamiento fue: " + Ttotal);

Console.ReadLine();
}

public int[] aleatorio(int[] a)
{

for (int i = 0; i < a.Length; i++)
{
Thread.Sleep(15); //Permite generar diferentes semillas para que

//no se repitan tanto los números aleatorios

Random r = new Random();
a[i] = r.Next(1000); //Genera un número aleatorio menor que 1000
Console.Write(a[i] + " | ");
}
return (a);

}

 

public int[] Burbuja(int[] a)
{

int temporal;
for (int i = 1; i < a.Length; i++)
{

for (int j = 0; j < a.Length-1; j++)
{

if (a[j] > a[j + 1])
{
temporal = a[j];
a[j] = a[j + 1];
a[j + 1] = temporal;
}

}

}
return (a);

}

 

public int[] arregloOrdenado(int[] a)

{

for(int i = 0;i < a.Length; i++ ){

Console.Write(a[i] + " | ");

}
return(a);

}

}
}

¿Existe un mejor método para implementar el algoritmo?

Escribe un programa para realizar el ordenamiento por burbuja. Diseña tu propio algoritmo y realiza un experimento para convencerte de que, en efecto, el desempeño medio del algoritmo es O(n^2).