ESTUDIO DE ALGORITMOS DE ORDENAMIENTO ADAPTATIVOS: IMPLEMENTACIÓN Y COMPARACIÓN EXPERIMENTAL

Abstract

Un algoritmo de ordenamiento es adaptativo, si ordena secuencias que estáncasi ordenadas más rápido que secuencias aleatorias. El orden de una secuenciaestá determinada por cierta medida de preordenamiento, las cuales han sido expuestasen diversos artículos y libros al pasar de los años. Además se ha logradorelacionarlas entre sí, de modo que si un algoritmo se adapta óptimamente a unamedida M1 lo haga también para una medida M2. Sin embargo, son escasos losestudios donde se implementen estos algoritmos adaptativos y sean comparadoscon los algoritmos de ordenamiento clásicos. En esta memoria, se implementanalgoritmos de ordenamiento adaptativos mencionados en la literatura, y se realizauna comparación de tiempos de ejecución contra los algoritmos clásicos. Estosalgoritmos efectuarán su ordenamiento para diversos tamaños de secuencias denúmeros enteros y tipos de secuencias, es decir, secuencias aleatorias y con ciertasmedidas 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.