Búsquedas binarias y ordenaciones en .NET

Una de las enormes ventajas del .NET es la facilidad con la que se realizan tareas que de otro modo hubieran llevado mucho más tiempo... aunque a veces descubrir cómo funcionan supone gastar casi más tiempo que el supuestamente ahorrado.

Todas las clases que heredan de la clase abstracta Array tienen la propiedad de realizar búsquedas binarias y de ordenarse a sí misma. Este es un aspecto bastante interesante, porque podemos tener casi cualquier objeto enlazado, heredado o contenido dentro de sus herederos, como es el caso de ArrayList, que puede contener un array con elementos de cualquier otro objeto.

El mantener un array ordenado de cadenas es algo trivial, y de hecho existe una clase para ello, StringList. Pero tener un array ordenado de objetos más complejos es harina de otro costal, sobre todo a la hora de ordenarlos... más que nada por la decisión de qué elemento dentro del objeto es el que va a generarnos la ordenación. En el mundo nativo, en C++, existe la función qsort a la que se le pasa un puntero a función que devolverá cuál de los dos elementos pasados es mayor, y así, qsort será capaz de ordenarlos realizando repetidas llamadas a esa función.

Pero en el mundo .NET eso está prohibido, aparte de que es un potencial fallo de seguridad, de contención de memoria y.. y.. casi de todo. En el mundo .NET podemos pasar un comparador, de forma parecida a como se hace en la STL.

La clase Array dispone de un método Sort sobrecargado con diferentes parámetros. A nosotros nos interesa aquellos a los que podemos pasar un comparador, o mejor dicho, un objeto heredado del interfaz IComparer. El método BinarySearch también puede recibir varios parámetros y, al igual que el anterior, también podemos pasarle un comparador.

Este "comparador" es el elemento que determinará cómo se realizará la ordenación, así como el resultado de las búsquedas binarias realizadas. Pero hagamoslo con un ejemplo sencillo.

Supongamos que tenemos una estructura que contiene una cadena y un valor que se corresponde con un índice de otro sitio. En lugar de definirla del modo clásico, lo haremos así:

ref struct SectionItem:System::Collections::IComparer
{
String ^SectionName;
int Line;
virtual int Compare(System::Object o1,System::Object 02)
{
SectionItem ^s=(SectionItem ^)o1;
return String::Compare(s->SectionName,(String ^)02,true);
}
};

Tenemos una estructura que posee un método Compare que se encarga de realizar la comparación respecto al nombre. Ahora, ordenar por el nombre o realizar una búsqueda binaria es un asunto bastante trivial. Supongamos que sections es un ArrayList que contiene una serie de objetos del tipo SectionItem.

System::Collections::IComparer ^comparer=gcnew SectionItem;
sections->Sort(comparer);
int index=sections->BinarySearch("valorPrueba",comparer);

Hemos definido el comparador dentro de la definición de la propia estructura, pero nada ni nadie nos impide crearnos nuestras propias clases herederas del interfaz IComparer independientes de la estructura y que sean capaces de realizar comparaciones con los criterios que consideremos oportunos.