Estudio de algoritmos de ordenamiento adaptativos: implementación y comparación experimental

Abstract

Un algoritmo de ordenamiento es adaptativo si ordena secuencias que están casi ordenadas más rápido que secuencias aleatorias. El orden de una secuencia está determinado por cierta medida de preordenamiento, las cuales han sido expuestas en diversos artículos y libros al pasar de los años. Además, se ha logrado relacionarlas entre sí, de modo que si un algoritmo se adapta óptimamente a una medida M1, lo haga también para una medida M2. Sin embargo, son escasos los estudios donde se implementen estos algoritmos adaptativos y sean comparados con los algoritmos de ordenamiento clásicos. En esta memoria se implementan algoritmos de ordenamiento adaptativos mencionados en la literatura y se realiza una comparación de tiempos de ejecución contra los algoritmos clásicos. Estos algoritmos efectuarán su ordenamiento para diversos tamaños de secuencias de números enteros y tipos de secuencias, es decir, secuencias aleatorias y con ciertas medidas de desorden que las caractericen.

A sorting algorithm is adaptive if it sorts nearly sorted sequences faster thanrandom sequences. The order of the sequence is determined by some measure ofpresortedness, which have been exhibited in various articles and books throughthe years. Furthermore it has been possible to relate these measures, so that if analgorithm is optimally adapted to a measure M1 also will be optimally adaptedto a measure M2. However, there are just few studies where these adaptive algorithmsare implemented and compared against classic sorting algorithms. In thiswork, sorting adaptive algorithms, mentioned in literature, are implemented andcompared against classic algorithms. These algorithms will do their sorting withdierent sequences size of integers and sequences types, i.e., random sequencesand with some measure of presortedness that caracterize those sequences.