CONSTRUYENDO ALGORITMOS

Capítulo 2
ORDENACIÓN

2.1 INTRODUCCIÓN
Dado un conjunto de n elementos a1, a2,..., an y una relación de orden total (≤)
sobre ellos, el problema de la ordenación consiste en encontrar unapermutación de
esos elementos ordenada de forma creciente.
Aunque tanto el tipo y tamaño de los elementos como el dispositivo en donde se
encuentran almacenados pueden influir en el método queutilicemos para
ordenarlos, en este tema vamos a solucionar el caso en que los elementos son
números enteros y se encuentran almacenados en un vector.
Si bien existen distintos criterios para clasificar alos algoritmos de ordenación,
una posibilidad es atendiendo a su eficiencia. De esta forma, en función de la
complejidad que presentan en el caso medio, podemos establecer la siguienteclasificación:
• Θ(n2): Burbuja, Inserción, Selección.
• Θ(nlogn): Mezcla, Montículos, Quicksort.
• Otros: Incrementos Θ(n1.25), Cubetas Θ(n), Residuos Θ(n).
En el presente capítulo desarrollaremos todos elloscon detenimiento, prestando
especial atención a su complejidad, no sólo en el caso medio sino también en los
casos mejor y peor, pues para algunos existen diferencias significativas. Hemos
dedicadotambién una sección a problemas, que recogen muchas de las cuestiones y
variaciones que se plantean durante el estudio de los distintos métodos.
Como hemos mencionado anteriormente, nos centraremosen la ordenación de
enteros, muchos de los problemas de ordenación que nos encontramos en la
práctica son de ordenación de registros mucho más complicados. Sin embargo este
problema puede serfácilmente reducido al de ordenación de números enteros
utilizando las claves de los registros, o bien índices. Por otro lado, puede que los
datos a ordenar excedan la capacidad de memoria del ordenador,y por tanto deban
residir en dispositivos externos. Aunque este problema, denominado ordenación
externa, presenta ciertas dificultades específicas (véase [AHO87]), los métodos
utilizados para...