lunes, 2 de junio de 2008

El método de la burbuja (para ordenar listas, claro).

MMmm... analizando los logs de google analytics, he visto que mucha (mucha de la poca se entiende xD), que entra al blog, lo hace a través de una búsqueda relacionada con... el algoritmo de ordenamiento de la burbuja! Así, que bueno... me he decidido a escribir algo sobre este algoritmo... al menos los pocos que llegan por aquí, que se queden contentos!! ;)

Por quien no conozca este algoritmo, diré que se trata de una forma no muy eficiente de ordenar los elementos de una lista. Eso sí, al menos tiene dos ventajas: és un método sencillo y además es un método sencillo. Y en que consiste???

Pues bueno, supongamos una lista de números, desordenada... por ejemplo 32,4,35,1 y queremos ordenarla de menor a mayor. Para ello cojemos el primer par de elementos (32 y 4) y:

  • Si el segundo es menor que el primero los intercambiamos
  • En caso contrario, los dejamos tal cual.
  • Repetimos el procedimiento, ahora con el segundo y tercer elemento de la lista... hasta llegar al final.
  • Luego volvemos a repetir todo el procedimiento, pero hasta llegar al penúltimo elemento... luego repetimos, pero llegamos hasta el antepenúltimo elemento, y así sucesivamente, hasta tener la lista ordenada.

En nuestro ejemplo (en negrita el par de elementos que comparamos y en cursiva los elementos que quedan fuera de la comparación):

32, 4, 35,1 => 4,32,35,1 => 4,32,35,1 => 4,32,1,35 => Repetimos desde el inicio, pero sin contar el último elemento

4,32,1,35 => 4,32,1,35 => 4,1,32,35 => Repetimos desde el inicio, pero sin contar los dos últimos elementos:

4,1,32,35 => 1,4,32,35 => Fin del algoritmo. Lista ordenada.

Bueno... el código en C# seria algo así como sigue (adaptación del código que podeis encontrar en "la tecla de escape"):

static void Burbuja(List<int> lst)

{

int iaux;

for (int i = 0; i < lst.Count - 1; i++)

{

for (int j = 0; j < lst.Count - i - 1; j++)

{

if (lst[j] > lst[j + 1])

{

iaux = lst[j];

lst[j] = lst[j + 1];

lst[j + 1] = iaux;

}

}

}

}


Qué sencillo, no???? Pues bueno... vamos ahora a hacer que el método ordene, no solo listas de ints, si no listas de cualquier tipo... uno podría pensar que igual basta declarar el método genérico... Lamentablemente si declaramos el método como:

static void Burbuja<T>(List<T> lst)

{

T iaux = default(T);

// El resto todo igual que antes...


El método no compila... el compilador se queja diciendo: Operator '>' cannot be applied to operands of type 'T' and 'T'. Este error es debido a que los parámetros genéricos son tratados como de tipo object... y el operador > no está definido para tipos object. Además usar una clausula where, no nos sirve en este caso (ya que where nos permite indicar que el parámetro template debe satisfacer una determinada interfaz, pero los operadores siempre se declaran como static en C# y por lo tanto nunca pueden declararse en una interfaz).

Entonces... estamos atrapados? Pues no... la solución pasa por usar un parámetro extra en nuestro método Burbuja, que le indique como debe ordenar los elementos. Es decir, un parámetro que le indique a nuestra función Burbuja, que método debe usar (en lugar de operador '>') para determinar si un elemento es "mayor" que otro. Además, eso es incluso más lógico que usar el operador '>', puesto que imaginemos que tenemos una lista de perros... igual nos interesa ordenarlos por tamaño, pero quizá lo queremos hacer por raza o color del pelo... entonces si tenemos que pasar un parámetro que apunte a un método... necesitamos un delegate.

Así deberiamos declarar un delegate que fuese algo parecido a:

delegate int Comparador<T> (T a1, T a2);


En este caso asumiremos que el delegate nos devuelve 1 si a1 es "mayor" que a2 y -1 si es al revés.

Y usar nuestro método Burbuja como sigue:

delegate int Comparador<T> (T a1, T a2);

class Program

{

static int ComparaDoubles(double d1, double d2)

{

if (d1 == d2) return 0;

return d1 > d2 ? 1 : -1;

}

static void Main(string[] args)

{

List<double> lista = new List<double>() { 32.3, 4.1, 35.2, 1.09 };

Burbuja(lista, new Comparador<double>(Program.ComparaDoubles));

}

static void Burbuja<T>(List<T> lst, Comparador<T> comparador)

{

T iaux = default(T);

for (int i = 0; i < lst.Count - 1; i++)

{

for (int j = 0; j < lst.Count - i - 1; j++)

{

if (comparador(lst[j], lst[j + 1]) == 1)

{

iaux = lst[j];

lst[j] = lst[j + 1];

lst[j + 1] = iaux;

}

}

}

}

}


Ale... solo teneis que cambiar el método al que apunta el delegate y podeis ordenar lo que os de la gana!

Bueno... y ahora que os he soltado el rollo... dos cosillas:

  1. El framework ya define un delegate como nuestro "Comparador", y se llama Comparison.
  2. La clase List<T> tiene un método Sort, que espera como parámetro... un delegate de tipo Comparison... :)

O sea que si quereis ordenar listas, lo mejor es algo del estilo:

lista.Sort (delegate (double d1, double d2)

{

if (d1 == d2) return 0;

return d1 > d2 ? 1 : -1;

} );


Bueno... espero que al menos los que aterrizais por aquí buscando información sobre el método de la burbuja... os haya servido este post!

Nos leemos! ;)

2 comentarios:

Jane B dijo...

very nice code explanation... thanks for sharing...

asp net web services

Unknown dijo...

como se hace con expresiones lambda este mismo metodo burbuja??