Algoritmos de Ordenación

Dentro del amplio campo de la Algorítmica hay un problema que podríamos considerar clásico por su antigüedad e importancia: ¿Cómo ordenar de manera eficiente una secuencia de objetos?

El problema

Para entender las dificultades con las que se encuentra alguien que quiere programar un Algoritmo de Ordenación es preciso establecer un modelo computacional que nos indique qué operaciones tenemos disponibles. Ahí va el mío:

Imaginemos que el objetivo es ordenar un mazo que contiene N cartas. Sabemos que las cartas tienen escrito en el anverso un número real cualquiera mientras que son indistinguibles por su reverso. El problema está en que los números están escritos en un sistema de numeración desconocido. Afortunadamente disponemos de una máquina a la que podemos introducirle dos cartas y una moneda para que nos responda cual de las dos es la mayor (no hay cartas repetidas).

Mover una carta desde su posición actual a un espacio vació o intercambiar un par de cartas de sitio dentro del mazo también nos cuesta una moneda.

¿Cómo podemos ordenarlas de la manera más barata posible?

Evidentemente en el campo de la algorítmica el precio que se paga es el tiempo que le dedicamos a resolver el problema pero por lo demás el modelo es bastante parecido a lo que se encuentra un programador en su día a día.

Propiedades

Un algoritmo de ordenación debe terminar en un tiempo finito y devolver el mazo de cartas perfectamente ordenado. Si además le pedimos que sea eficiente es necesario que el conjunto de operaciones realizadas sean lo más baratas posible (el algoritmo sea lo más rápido posible).

El primer problema surge cuando intentamos definir qué significa “lo más baratas posibles” dado que la cantidad de operaciones necesarias dependerá no sólo del algoritmo sino también de cuan desordenado esté el mazo inicialmente.

Hay N! maneras de ordenar N cartas. Si asumimos que cualquiera de ellas puede ser la que nos den al principio deberíamos calcular cuanto gastará nuestro algoritmo con cada una de esas ordenaciones y luego hacer la media. Ese es el gasto en el caso medio del algoritmo. Si, por el contrario, nos fijamos en la ordenación que nos hace gastar más o en la ordenación que nos hace gastar menos tenemos el gasto en el caso peor y el gasto en el caso mejor respectivamente.

En lo sucesivo hablaremos únicamente de el gasto en el caso medio si bien el gasto en el caso peor es de suma importancia a la hora de diseñar algoritmos robustos mientras que el gasto en el caso mejor es fundamental para hablar de algoritmos adaptativos.

Otra de las propiedades que conviene tener en cuenta es el espacio utilizado por nuestro algoritmo. Imaginemos que por cada espacio de más que queramos tener disponible debemos pagar otra moneda. Es decir, supongamos que el mazo de cartas nos lo dan extendido horizontalmente sobre una mesa. Debajo de cada carta hay un rectángulo y toda carta debe estar siempre sobre uno de los rectángulos. Para mover una carta es necesario tener un espacio vació donde colocarla inmediatamente o, en su defecto, otra carta con la que intercambiar las posición. Es algo así como un parquing.

Pues bien, al principio disponemos de N espacios y por cada espacio adicional que compremos deberemos pagar una moneda. Este precio representa el gasto de memoria que tiene nuestro algoritmo y, de nuevo, puede considerarse su caso mejor, su caso medio o su caso peor pero todos ellos suelen coincidir bastante.

Ejemplos

Uno de los primeros algoritmos que se te pueden ocurrir es el algoritmo de Selección que consiste en formar un nuevo mazo con elementos ordenados buscando el siguiente elemento cada vez. Empezaríamos buscando el más pequeño, luego el segundo más pequeño, luego el tercero, etc.

Este algoritmo tiene un gasto medio de O(N²) comparaciones y O(N) movimientos mientras que si se implementa con cuidado puede tener un gasto de memoria O(1).

Algoritmos más sofisticados pueden ser más eficientes que el Algoritmo de Selección. Por ejemplo el MergeSort (que fue inventado por mi admirado John von Neumann) tan sólo necesita O(N·log(N)) operaciones y O(N) espacios adicionales para funcionar siendo, aún así, muy sencillo.

Mi preferido es, sin duda, el retorcido HepSort que tarda lo mismo que MergeSort pero no precisa espacio adicional (y es deliciosamente contraintuitivo). Sin embargo, la mayoría de veces se usa alguna variante sofisticada del QuickSort (espero no ser el único que piensa que tener un nombre así de comercial es uno de los principales motivos para que la gente elija este infame algoritmo).

¿Podemos hacerlo mejor?

No: Hace mucho que se demostró que cualquier algoritmo que ordene una secuencia de N elementos con las operaciones que tenemos disponibles (comparar 2 a 2 y mover elementos) requiere, de media, O(N·log(N)) operaciones para ordenarla completamente.

A groso modo la idea es que ordenar una secuencia de N elementos es equivalente a decidir cual de las N! posibles entradas es la que nos han dado. Y como ya vimos, en el caso equiprobable (cualquiera de las N! opciones puede darse con igual probabilidad) eso requiere O(log(N!)) preguntas. Y por la fórmula de Stirling tenemos que O(log(N!))O(log(N^N)) = O(N·log(N)) que es lo que ya consiguen los últimos 3 algoritmos (y alguno más).

Pero… aunque no podamos ordenar mejor de media sí podemos ordenar un poco más rápido en algunos casos concretos. Los algoritmos que funcionan excepcionalmente bien bajo algunos supuestos se llaman Algoritmos Adaptativos y hablaremos de ellos mañana.

Otra manera de mejorar los resultados mostrados hasta ahora consiste en permitir ciertos errores en el resultado. Es decir, olvidarnos del ordenarla completamente y exigir tan sólo que la ordenen un poco. De los Algoritmos de Pseudoordenación que hacen esto hablaremos pasado mañana mientras que el viernes entraremos de lleno en lo que puede significar ordenar un poco una secuencia.

Como es obvio en ningún caso podremos hacer menos de O(N) operaciones porque, como mínimo, tendremos que mirar/comparar cada carta una vez para poder ubicarla con cierto criterio. Así pues no podemos esperar grandes ahorros en el día a día pero cuando hablamos de programar supercomputadores, de gestionar grandes bases de datos o de hacer grandes simulaciones científicas (o militares), cada centésima de segundo cuenta.

Si, lo sé, va a ser una semana densa. ;-)

Selection Sort

BOLAEXTRA: Este post pertenece a una serie especial de 5 artículos relacionados:

  1. Eficiencia Algorítmica y Notación Asintótica
  2. Algoritmos de Ordenación
  3. Algoritmos de Ordenación Adaptativos
  4. Algoritmos de Pseudoordenación
  5. Medidas del Orden de una Secuencia

Te recomiendo encarecidamente que leas los 5 en orden ya que cada uno de ellos depende fuertemente de los anteriores.

Escrito en 08/12/09 10:00 por Carlos Luna en las categorías:

Comentarios

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)