Los algoritmos de ordenación, como su propio nombre apunta, sirven para ordenar datos. Hay unos cuantos, y son bien conocidos y estudiados por la algoritmia... Que si la burbuja, que si el quicksort... La mayor parte de ellos son sencillos de entender y codificar. Pero muchas veces no se utilizan con un criterio claro.

En éste artículo vamos a intentar hablar sobre ellos, en qué se basan, qué consideraciones debemos conocer para utilizarlos y una breve clasificación general.

Poco a poco, iremos escribiendo nuevos artículos sobre este tema, uno para cada método de ordenación de entre los más populares y simples con ejemplos sencillos en C#.

¿Qué son?

Vamos a empezar hablando de qué son exactamente los algoritmos de ordenación.

Básicamente son algoritmos que cogen una lista de datos ordenables y los van cambiando de lugar, de tal manera que cuando el algoritmo finaliza, si recorremos esa lista, los datos mantienen cada uno con el siguiente un cierto orden.

Normalmente, se utilizan con arrays, cuyos elementos, en principio, no tienen por qué estar ordenados. Un algoritmo de ordenación aplicado sobre ese array, cambia de sitio los elementos hasta lograr que estén ordenados.

¿En qué se basan?

Estos algoritmos se basan en dos operaciones básicas:

• La comparación: el algoritmo de ordenación tiene que ser capaz de disponer de una operación tal que dados dos datos cualesquiera, la operación de comparación indique si están en orden o no.
• El intercambio de datos: el algoritmo debe ser capaz de intercambiar dos elementos de la lista.

El hecho de necesitar estas dos operaciones, nos lleva a una serie de consideraciones:

Empecemos por la segunda. Primeramente, aclarar que al hablar de lista, simplemente me refiero a un conjunto de valores que están colocados cada uno en una posición concreta, y que pueden ser identificados por esa posición. Por ejemplo, los libros de una librería, vistos de izquierda a derecha forman una lista:

Hay un libro que ocupa la primera posición, otro la segunda... etc. Sin embargo, si tiro esos libros al suelo y los dejo caer a su aire, no formarán una lista, porque ninguno ocupará una posición concreta.

Volvamos a los datos. El hecho de que tengamos que poder intercambiar dos valores de una lista implica que leemos uno de ellos y lo copiamos en una variable temporal, luego cogemos el segundo elemento y lo copiamos en la posición del primero ("machacando" su valor, pero no pasa nada, porque lo hemos cogido en una variable temporal), y finalmente copiamos el valor de la variable temporal (que tenía el valor del primero) a la posición del segundo. Realmente hemos hecho tres operaciones de asignación de variables, pero el resultado final es que hemos logrado intercambiar valores. Si habláramos de los libros de arriba y quisiera intercambiar, por ejemplo, el segundo con el cuarto, cogería el segundo en mi mano, dejando así un hueco en segundo lugar (el libro está fuera de la lista, en mi mano: mi mano es una variable temporal), pasaría el cuarto al sitio del segundo, que ahora está vacío y finalmente, dejaría el libro que tengo en mi mano en el lugar del cuarto. (También podría haberlo hecho al revés, sacando el cuarto en primer lugar).

Mover un dato de un lugar a otro implica que nuestro conjuto de datos está almacenado en alguna estructura de datos que nos permite obtener un dato y escribirlo en una posición concreta de la estructura de datos. Ambas operaciones, de lectura y escritura de un dato deben poder realizarse con un coste constante... es decir, el tiempo que se tarde en leer o escribir un dato no debe depender de la cantidad de datos que estemos intentando ordenar, dicho de otro modo, de la cantidad de datos de la lista que manejemos.

Esto no se puede tomar a la ligera, ya que hay muchas estructuras de datos capaces de almacenar una lista de valores, pero muy pocas ofrecen un coste de lectura y escritura constante. Típicamente, la estructura por antonomasia que ofrece esa característica es el array (también llamado arreglo o vector, según la literatura que escojas). En otras estructuras, como listas enlazadas, doblemente enlazadas, etc, cuando se accede a una determinada posición, antes deben recorrer un buen número de posiciones.

Es decir, en un array de 10000 elementos, accecer al elemento de la posición 9000, bien sea para obtener su valor o para asignárselo "tarda" lo mismo que para el de la posicion 900. Sin embargo, en una lista enlazada típica no: acceder al 9000 tardará bastante más que acceder al 900, porque internamente, en una lista enlazada, antes de acceder a una posición, se recorren todas las anteriores.

Como los algoritmos de ordenación hacen muchas de estas operaciones (para lograr los intercambios), si en lugar de un array utilizamos, por ejemplo una lista enlazada, haremos que el coste del acceso a un elemento de la lista enlazada (típicamente del orden de O(n)) multiplique al propio coste del algoritmo de ordenación.

Los algoritmos de ordenación típicos sólo se aplican a estructuras de datos cuyo coste de acceso a un elemento (tanto para leer su valor como para escribir uno nuevo) sea constante. Normalmente, arrays.

En cuanto a lo de la comparación, también tiene su importancia. Cuando estudiamos un algoritmo de ordenación en un libro o cualquier otro texto técnico, casi siempre nos lo presentan ordenando un vector de enteros. Yo muchas veces me he preguntado ¿Y para qué puñetas quiero yo un puñado de enteros en orden?... Para nada, normalmente.

Realmente, en los libros nos enseñan a ordenar un array de enteros porque los enteros es un conjunto que tiene un orden entre sus elementos que tenemos muy asimilado... Si nos presentan dos enteros cualesquiera, inmediatamente sabemos cuál de los dos es "menor".

Sin embargo, hay otros casos donde la cosa no está tan clara... por ejemplo, las cadenas. Si te presento estas dos cadenas de texto, ¿Cuál de ellas va antes?: "HOLA" y "caracola"... Pues depende... si utilizo el orden alfabético, debería ir antes "caracola", pero si utilizo el orden de la tabla ASCII , debería ir antes "HOLA", ya que en ASCII las mayúsculas van antes que las minúsculas.

Y aún hay más... ¿Y si en lugar de un dato simples, como enteros o cadenas, estamos intentando ordenar datos compuestos, como structs (registros, en los lenguajes pascaloides) u objetos de una clase.

Piensa en esto:

class Persona {
int codigo;
String nombre;
String apellidos;
double altura; //altura en metros
double peso; //peso en kilogramos
}

¿Cuál de las dos va antes?

...
...

Pues.... ¡¡¡ Depende !!!

En efecto, depende... los objetos de la clase Persona no tienen un orden implícito. Podemos ordenar a las personas por su altura, por sus apellidos, por su nombre, por su código.... y no sólo eso, sino por cualquier combinación de esos datos que se nos ocurra... por ejemplo, por el índice de masa corporal , que es el peso dividido por la altura al cuadrado.

Así pues, podemos utilizar los algoritmos de ordenación para ordenar un conjunto de cualquier tipo de dato, pero necesitaremos un criterio de ordenación.

Es posible (y relativamente frecuente) que una misma lista de datos sea susceptible de ser ordenada por distintos criterios. Cada aplicación del algoritmo se hace con un único criterio.

Antes de aplicar un algoritmo de ordenación, debemos tener claro un criterio de ordenacion, es decir, una función, método u operador tal que dados dos elementos nos diga al menos si están en orden o no, siempre según el criterio que hayamos decidido.

Por otro lado, si estamos ordenando structs (o records de los lenguajes pascaloides) u objetos, éstos ocupan gran cantidad de memoria comparados con los tipos primitivos (enteros, reales...). Realizar los intercambios puede suponer un gran trasiego de bytes. Cuando éste es el caso, normalmente no interesa hacer el intercambio del struct u objeto entero, sino utilizar un array de punteros o referencias, e intercambiar realmente el puntero o la referencia.

En lenguajes como C# o Java, donde las referencias son fundamentales (algunos dicen que las referencias son ciudadanos de primer orden), al crear un array cuyos elementos son objetos, éstos lenguajes crean realmente un array de referencias a objetos.

En otros lenguajes, como C++, en los que las referencias no existen o no son importantes, el programador puede crear un array de objetos o structs, o bien un array de punteros a objetos o structs. En el primer caso (un array de objetos o structs), al aplicar un algoritmo de ordenación, durante los intercambios se intercambia todo el contenido de una posición del array, es decir, un objeto o struct completo, con todos sus bytes. En el segundo (un array de punteros a objetos o structs), sólo se intercambian los punteros, que normalmente ocupan muy pocos bytes. El objeto o struct sigue en la misma posición de memoria.

Cutre-animación:

Cuando aplicamos un algoritmo de ordenación sobre un vector, debemos tener claro si estamos intercambiando objetos enteros de posición (o structs o records) o bien punteros o referencias a éstos. Intercambiar punteros o referencias es mucho más eficiente. Algunos lenguajes manejan todos los objetos con referencias por defecto, y otros manejan los objetos enteros por defecto.

Por último, comentar que como en todo, hay excepciones. Algunos algoritmos se ahorran las comparaciones, pero utilizan otras operaciones aritmético-lógicas, relacionadas con la propia estructura de los datos. Otros algoritmos "simplifican" varias operaciones de intercambio, realizando menos movimientos en memoria.

Para qué NO valen

Hay principalmente dos utilizaciones de los algoritmos de ordenación que no son nada correctas, y que muchas veces estamos tentados de utilizar:

• Para ordenar una estructura de datos cuyo coste de acceso a un elemento no sea constante. Ésto ya lo hemos comentado: acceder al primer elemento de la estructura o al último debe tardar lo mismo.
• Para insertar un elemento en orden en una estructura cuyos elementos ya están en orden. Esto lo he visto hacer muchas veces: a la hora de insertar un elemento nuevo en una lista que ya tiene orden, se puede aplicar la idea feliz de añadir el nuevo elemento por el principio o por el final, y luego pasar un algoritmo de ordenación para que lo coloque en su sitio... Funcionar, funciona... pero con un coste en tiempo absurdo. En estos casos, lo mejor es hacer una inserción lineal (que tiene un coste O(n)), o mejor todavía, una inserción dicotómica.
  La inserción lineal consiste en ir recorriendo la lista secuencialmente hasta encontrar el lugar que debería ocupar el nuevo elemento. Después se abre un hueco y se inserta ahí el nuevo elemento. La inserción dicotómica consiste en hacer una búsqueda dicotómica para encontar el lugar del nuevo elemento y luego abrir hueco ahí e insertar el nuevo elemento.

Taxonomía

Siempre me ha gustado esta palabra: taxonomía . Significa clasificación, pero dicho de manera más pedante :-)

En fin... hay mucha gente que ha perdido su tiempo en clasificar los algoritmos de ordenación. Vamos a echar un vistazo rápido al resultado.

---Según sirvar para ordenar datos en memoria primaria o secundaria

Prácticamente todos los algoritmos de ordenación pueden aplicarse para ordenar datos en memoria principal (típicamente en arrays) o en memoria secundaria (discos, disquetes, pendrives...), eso sí. siempre que ésta última sea a través de ficheros de acceso aleatorio (hoy en día, prácticamente toda).

No obstante, la naturaleza de la memoria secundaria es distinta a la principal, aún hablando de acceso aleatorio. La memoria secundaria es, en general, varios miles de veces más lenta en los accesos, y además, por sus limitaciones físicas, aunque se pueda acceder aleatoriamente a una determinada parte de un fichero, los dispositivos suelen acceder a grandes bloques de bytes, y es el sistema operativo el que con gran esfuerzo nos da la impresión de que podemos acceder a un byte concreto. Así pues, en general los algoritmos de ordenación no se comportan bien en la memoria secundaria, y para ello han sido creados a propósito algunos que funcionan mucho mejor en esos entornos. Así, hablamos de algoritmos de ordenación

• Internos: cuando ordenan estructuras almacenadas en memoria principal
• Externos: cuando ordenan estructuras almacenas en memoria secundaria (ficheros binarios, sean de acceso aleatorio o secuencial).

---Segun mantengan en el mismo orden dos datos iguales.

Imagina esta lista de personas y edades:

Pepe:42, Luis:21, Antonia:50, María:7, Bernardo:21, Catalina:32

Fíjate en que si pretendemos ordenar a estas personas por edad de menor a mayor hay dos posibles clasificaciones:

Maria:7, Bernardo:21, Luis:21, Catalina:32, Pepe:42, Antonia:50
Maria:7, Luis:21, Bernardo:21, Catalina:32, Pepe:42, Antonia:50

Bernardo y Luis tienen la misma edad... Está claro que deben ocupar la segunda y tercera posición, pero ¿Cuál va antes? Pues habrá veces que eso no tenga ninguna importancia y habrá veces en las que sí la tenga (pocas, la verdad).

Algunos algoritmos de ordenación no tienen eso en cuenta, y podrían ordenar el array de una manera o de la otra indistintamente.

Otros, nos garantizan si se presenta un caso como éste, siempre devolveran la segunda solución, porque en ella va Luis delante, al igual que en la lista original antes de ser ordenada.

Así pues, hablamos de algoritmos de ordenación

• Estables: cuando garantizan que dos elementos que podrían ocupar la misma posición se colocan manteniendo el orden relativo que tenían entre ellos antes de aplicar el algoritmo
• No estables: cuando el algortimo no garantiza eso, y en caso de que se produzca, los elementos mantendrán una posición correcta, pero sin orden alguno entre ellos.

---Según utilicen memoria extra

Algunos algoritmos requieren una cantidad de memoria fija temporal independientemente de la cantidad de datos que tengan que ordenar. Otros, por el contrario, requieren una cantidad de memoria temporal que depende en alguna medida de la cantidad de datos que tengan que ordenar.

• No necesitan memoria extra: cuando la cantidad de memoria temporal es fija, independientemente del número de datos a ordenar (a este tipo de algoritmos, a menudo se les llama algoritmos in-situ)
• Sí necesitan memoria extra: cuando la cantidad de memoria temporal es variable, y es mayor cuanto mayor sea el número de datos a ordenar.

El hecho de que sea de un tipo u otro está relacionado en cierta manera con la complejidad del algoritmo. Los algortimos de menor complejidad temporal (en el peor caso) suelen gastar memoria extra.

---Según su complejidad temporal

Los algoritmos de ordenación están profundamente estudidados desde el punto de vista de la complejidad temporal. No es algo que deba obsesionar, pero está muy bien conocerla, al menos, en el peor caso.

• Cuadrática (O(n²)): es la complejidad de los algorimos más sencillos
• N-Logarítmica (O(n logn)): es la complejidad de algunos algo más avanzados, y que suelen consumir memoria extra. (Aumentan la complejidad espacial y reducen la temporal)
• Lineales (O(n)): son los que se aprovechan de alguna característica aritmética de los datos, evitando las comparaciones (una de las excepciones que comentábamos antes)

---Según realicen comparaciones o no

Finalmente, como algunos algoritmos no realizan las comparaciones, pues también se pueden clasificar en

• Los que realizan comparaciones
• Los que no lo hacen (ya hemos comentado que se basan en alguna propiedad aritmética de los datos)