Escuela de Ingenier´ıas Industrial e Informa´tica Departamento de Ingenier´ıa El´ectrica y de Sistemas y Autom´atica TESIS DOCTORAL Meta-algoritmos de ordenacio´n Tesis dirigida por el ´ Dr. D. Honorino A. Mielgo Alvarez Rodrigo Raposo Garc´ıa Le´on, Noviembre de 2015 palabra UNIVERSIDAD DE LEO´N Resumen Escuela de Ingenier´ıas Industrial e Inform´atica Departamento de Ingenier´ıa El´ectrica y de Sistemas y Autom´atica Meta-algoritmos de ordenaci´on Rodrigo Raposo Unadelastareasfundamentalesdelossistemasdeinformaci´oneslaordenaci´on, clasificaci´onybu´squedadedatos,alaquededicanentreel25yel50porciento de su tiempo. Habitualmente la ordenacio´n no es un fin en s´ı mismo, sino m´as bien una tarea fundamental que se encuentra entre dos procesos: un productor que genera elementos para un consumidor que los demanda segu´n un orden preestablecido. Esta Tesis analiza minuciosamente la forma de trabajo de los algoritmos cl´asicos de ordenaci´on, y define una nueva taxonom´ıa basada en la abstracci´on de sus respectivas implementaciones de las estructuras de control y de datos. Se aborda el concepto ordenaci´on en su forma m´as amplia y pura, describiendo la soluci´on de forma independiente a la arquitectura hardware del sistema y al lenguaje de programacio´n elegido. palabra UNIVERSIDAD DE LEO´N Abstract Escuela de Ingenier´ıas Industrial e Inform´atica Departamento de Ingenier´ıa El´ectrica y de Sistemas y Autom´atica Sorting meta-algorithms Rodrigo Raposo The fundamental core task in Information Systems is to sort, classify and search data, which spend between 25 and 50 percent of his time. Usually the sort task is not and end in itself, but rather a fundamental task that lies bet- ween two processes: a producer that generates elements for a consumer which demand it according to an predeterminated order. This Thesis thoroughly analyses how sort classic algorithms work, and defines a new taxonomy based on abstract their respective implementation of control and data structures. Sorting is addressed in its broadest and pure form and a solution is offe- red independently of the hardware architecture and the chosen programming language. Agradecimientos En primer lugar quiero mostrar el mayor agradecimiento a m´ı director de Tesis D.HonorinoA.MielgoA´lvarezportodaslashorasinvertidasordenando, desordenandoyreordenandonuevamenteelementos.Sinsuayuda,orientacio´n y apoyo esta Tesis no hubiera sido posible. A todos los profesores que he tenido a lo largo de mi vida acad´emica por la transmisi´on de conocimientos y valores fundamentales para la vida. De entre todos, me gustar´ıa recordar con un carin˜o especial a Mario Hern´andez por su fe y aliento para con todos sus alumnos. Descansa en paz, Maestro. Atodosloscompan˜erosyamigosporlosbuenosratosyexperienciasvivi- das. Juntos hemos disfrutado momentos inolvidables, aunque sin duda alguna los mejores son los que est´an por llegar. A toda mi familia, sin la cual jam´as habr´ıa sido posible llegar hasta aqu´ı. A los que tengo la suerte de tener cada d´ıa a m´ı lado y a los que ya no est´an conmigo: todos vosotros forma´is mi vida y mis recuerdos. Con vuestra ayuda y comprensi´on los momentos dif´ıciles se hacen mucho ma´s llevaderos. A todos y cada uno de vosotros so´lo puedo deciros sinceramente GRACIAS ´ Indice general Resumen III Abstract V Agradecimientos VII ´Indice general VIII ´Indice de figuras XVII ´Indice de algoritmos XXI Dedicatoria XXIII 1. Introducci´on 1 1.1. Fundamentos de ordenaci´on: Breve resen˜a histo´rica . . . . . . . 1 2. Ordenaci´on cl´asica: fundamentos b´asicos 5 2.1. Algoritmo: definici´on . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.0.1. Algoritmos de ordenacio´n cla´sicos . . . . . . . 6 2.2. Un poco de historia . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1. Una visi´on cl´asica . . . . . . . . . . . . . . . . . . . . . 7 2.2.2. Ordenacio´n interna . . . . . . . . . . . . . . . . . . . . . 8 2.2.3. Ordenacio´n externa . . . . . . . . . . . . . . . . . . . . 9 2.3. Ordenacio´n serie y paralelo . . . . . . . . . . . . . . . . . . . . 10 2.3.1. Introduccio´n . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4. Algoritmos de ordenaci´on serie en paralelo . . . . . . . . . . . . 14 2.4.1. Procesamiento paralelo del algoritmo serie Burbuja . . . 15 ix I´ndice general. x 2.4.2. Procesamiento paralelo del algoritmo serie Fusi´on . . . 17 2.5. Algoritmos de ordenaci´on en bloque . . . . . . . . . . . . . . . 19 2.5.1. Una visi´on inicial . . . . . . . . . . . . . . . . . . . . . . 19 2.5.2. Alternativa . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.3. Reflexiones sobre la parte hardware introducida en el algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5.4. Reflexionessobrelasmejorasintroducidasenelsoftware del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 24 3. Meta-algoritmos de ordenaci´on: pilares fundamentales 25 3.1. Introduccio´n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2. Abstraccio´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.1. El papel de la abstraccio´n . . . . . . . . . . . . . . . . . 27 3.2.1.1. La abstracci´on como un proceso mental natural 28 3.2.1.2. La abstracci´on en la ingenier´ıa del software . . 29 3.2.1.3. Tipos de datos . . . . . . . . . . . . . . . . . . 30 3.2.1.4. Ventajas de los tipos abstractos de datos . . . 30 3.3. Construcci´on de meta-algoritmos . . . . . . . . . . . . . . . . . 31 3.3.1. La abstracci´on como principio fundamental . . . . . . . 31 3.3.1.1. Fundamentos de la investigacio´n . . . . . . . . 32 3.4. Ana´lisis del problema . . . . . . . . . . . . . . . . . . . . . . . 34 3.4.1. A´ngulos . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4.1.1. Primeros intentos del proceso de mejora . . . . 35 3.4.1.2. Meta-algoritmos de ordenacio´n: fundamentos . 37 3.4.1.3. Para-algoritmos . . . . . . . . . . . . . . . . . 38 3.5. Convenciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.5.1. Elementos repetidos: una restriccio´n que no es tal . . . 41 3.6. Optimalidad frente a simplicidad y seguridad . . . . . . . . . . 43 3.6.1. Situacio´n de Strassen . . . . . . . . . . . . . . . . . . . 44 3.7. Obtencio´n de resultados en orden inverso . . . . . . . . . . . . 45 3.8. La pregunta ma´s inteligente . . . . . . . . . . . . . . . . . . . . 46 3.8.1. Estrategias . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.8.2. Consideraciones . . . . . . . . . . . . . . . . . . . . . . . 47 3.9. Visio´n relacional del problema: representaciones . . . . . . . . . 49 3.9.1. Grafo dirigido ac´ıclico . . . . . . . . . . . . . . . . . . . 51 3.9.1.1. Ejemplodeconstruccio´ndegrafodirigidoac´ıclico 51 3.9.2. Matriz de incidencia . . . . . . . . . . . . . . . . . . . . 54 3.9.2.1. Ejemplo de representacio´n mediante la matriz de incidencia . . . . . . . . . . . . . . . . . . . 60