Algoritmos de Ordenación Adaptativos

Hoy toca hablar de un tipo muy concreto de Algoritmos de Ordenación: los Algoritmos de Ordenación Adaptativos. Se trata de algoritmos altamente especializados que ordenan ciertas secuencias de manera más eficiente que los algoritmos de ordenación de propósito general.

Algoritmos de Ordenación Adaptativos

De la misma manera que cuando hablamos de Teoría de la Información, cuando se trata de ordenar una secuencia de objetos tenemos que distinguir el caso equiprobable de otros más sesgados.

Con esto me refiero a que, si bien existe un límite teórico que nos dice que no podemos ordenar completamente una secuencia cualquiera de N elementos en menos de O(N·log(N)) pasos nada nos impide crear un algoritmo que ordene algunas secuencias de N elementos con mayor eficiencia.

Así, los algoritmos que tardan O(N) en ordenar algunas secuencias predeterminadas se llaman Algoritmos de Ordenación Adaptativos y se clasifican según el tipo de secuencia que ordenan eficientemente.

Ejemplo

El algoritmo de Ordenación por Burbuja es en general muy poco eficiente. Tarda O(N²) pasos en ordenar una secuencia cualquiera de N elementos.

Sin embargo, es un algoritmo tremendamente eficiente cuando la secuencia está casi ordenada. Concretamente, si podemos garantizar que cada elemento está a menos de k posiciones de su lugar definitivo el algoritmo de ordenación por Burbuja tarda O(k·N) que, para un k fijado de antemano, es en realidad O(N).

Algoritmos de Ordenación Adaptativos Perfectos

En el ejemplo anterior tenemos un algoritmo que en general lo hace peor que los algoritmos óptimos pero en unos cuantos casos lo hace mucho mejor. Podríamos pensar que para obtener un algoritmo de ordenación adaptativo es necesario sacrificar el caso medio. Pues bien, resulta que no es así.

Yo llamo Algoritmos de Ordenación Adaptativos Perfectos a aquellos algoritmos de Ordenación que son O(N) en el caso mejor y O(N·log(N)) en el caso peor. Obviamente en este último caso no serán tan eficientes como los algoritmos óptimos de carácter general (Quicksort, Mergesort y Heapsort) pero si sabemos que el caso mejor se va a dar con frecuencia vale la pena utilizarlos.

Un interesante ejemplo de algoritmo de ordenación adaptativo perfecto es el Smoothsort de Dijkstra (si, ese Dijkstra). Python usa otro algoritmo de ordenación adaptativo perfecto llamado Timsort.

Aplicaciones

Los algoritmos de ordenación adaptativos se usan cuando se tiene información previa de los datos que hay que ordenar. Por ejemplo, en una baraja ordenada a la que se le añaden unas cuantas cartas al final (dichas cartas están desordenadas) no es realmente necesario realizar tanto trabajo como en una baraja de la que no sabemos nada.

En una librería, donde la gente coge y deja los libros es posible que se cometan pequeños errores pero para ordenarla podemos usar lo que sabemos: la mayoría de libros está en su sitio o a poca distancia.

Si la secuencia de elementos está formada por largas secuencias crecientes (o decrecientes) podemos usar algoritmos específicos que explotan estas pequeñas regiones pre-ordenadas.

En grandes bases de datos y en programas de suficiente complejidad el beneficio obtenido con estos algoritmos (respecto al uso de los normales) puede ser enorme.

Bubble 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 09/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://...)