Programacion

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 que utilicemospara 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 a losalgoritmos 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 siguiente clasificació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 ellos condetenimiento, 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 dedicado también unasecció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 centraremos en laordenació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 ser fácilmente reducidoal 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 tantodeban residir en dispositivos externos. Aunque este problema, denominado ordenación externa, presenta ciertas dificultades específicas (véase [AHO87]), los métodos utilizados para resolverlo se basan...