Tesis de Rodrigo Raposo
Tesis de Rodrigo Raposo
Tesis de Rodrigo Raposo
Industrial e Informática
Departamento de Ingenierı́a Eléctrica
y de Sistemas y Automática
TESIS DOCTORAL
Meta-algoritmos de ordenación
Resumen
Escuela de Ingenierı́as Industrial e Informática
Departamento de Ingenierı́a Eléctrica y de Sistemas y Automática
Meta-algoritmos de ordenación
Rodrigo Raposo
Abstract
Escuela de Ingenierı́as Industrial e Informática
Departamento de Ingenierı́a Eléctrica y de Sistemas y Automática
Sorting meta-algorithms
Rodrigo Raposo
A todos los compañeros y amigos por los buenos ratos y experiencias vivi-
das. Juntos hemos disfrutado momentos inolvidables, aunque sin duda alguna
los mejores son los que están por llegar.
A toda mi familia, sin la cual jamás 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án
conmigo: todos vosotros formáis mi vida y mis recuerdos. Con vuestra ayuda
y comprensión los momentos difı́ciles se hacen mucho más llevaderos.
GRACIAS
Índice general
Resumen III
Abstract V
Agradecimientos VII
Dedicatoria XXIII
1. Introducción 1
1.1. Fundamentos de ordenación: Breve reseña histórica . . . . . . . 1
ix
Índice general. x
4. Meta-algoritmo descendente 71
4.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2. Cómo empezó todo . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3. Definiciones básicas . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4. Versión intuitiva . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5. Representación gráfica . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.1. Primera fase: creación del árbol de procesos . . . . . . . 76
4.5.2. Segunda fase: recuperación de elementos . . . . . . . . . 79
4.6. Versión formal . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.7. Corrección del meta-algoritmo descendente: versión informal . . 85
4.8. Corrección del meta-algoritmo descendente: versión formal . . . 86
4.8.1. El proceso termina . . . . . . . . . . . . . . . . . . . . . 86
4.8.2. La condición invariante . . . . . . . . . . . . . . . . . . 88
4.8.3. El estado inicial cumple el invariante . . . . . . . . . . . 88
4.8.4. Las transiciones conservan el invariante . . . . . . . . . 88
4.8.5. En los estados finales el objetivo se satisface . . . . . . . 88
4.8.6. Indeterminaciones . . . . . . . . . . . . . . . . . . . . . 88
4.9. Optimizaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.10. Derivación de Quicksort . . . . . . . . . . . . . . . . . . . . . . 89
4.11. Derivación en Binario . . . . . . . . . . . . . . . . . . . . . . . 95
4.12. Simetrı́a o dualidad entre Quicksort y Binario . . . . . . . . . 96
4.13. Optimizaciones especı́ficas . . . . . . . . . . . . . . . . . . . . . 96
4.13.1. Binario . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.13.2. Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.14. Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . 97
5. Meta-algoritmo ascendente 99
5.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.2. Versión intuitiva . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3. Representación gráfica . . . . . . . . . . . . . . . . . . . . . . . 101
5.3.1. Primera fase: Distribución de elementos . . . . . . . . . 101
5.3.2. Segunda fase: fusión de elementos . . . . . . . . . . . . . 103
5.4. Versión formal . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Índice general. xii
6. Esquemas 117
6.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.2. Esquemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.3. Germen de la idea . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.4. Esquemas generales . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.4.1. Resultado de la comparación a < b . . . . . . . . . . . . 121
6.4.2. Resultado de la comparación a > b . . . . . . . . . . . . 122
6.4.3. Algoritmo Burbuja . . . . . . . . . . . . . . . . . . . . . 125
6.5. Esquemas de árboles . . . . . . . . . . . . . . . . . . . . . . . . 127
6.5.1. Ejemplo con elementos almacenados de forma secuencial 128
6.5.1.1. Primera posibilidad: x < y . . . . . . . . . . . 129
6.5.1.2. Segunda posibilidad: x > y . . . . . . . . . . . 131
6.5.2. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . 132
6.6. Esquemas de cadenas . . . . . . . . . . . . . . . . . . . . . . . . 133
6.7. Esquemas de cadena única . . . . . . . . . . . . . . . . . . . . . 133
6.8. Una jerarquı́a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.9. Acciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7. Miscelánea 135
7.1. Dualidad entre meta-algoritmos . . . . . . . . . . . . . . . . . . 135
7.1.1. Dualidad en el propio proceso . . . . . . . . . . . . . . . 135
7.1.2. Descendente . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.1.3. Quicksort y Binario . . . . . . . . . . . . . . . . . . . . 137
7.1.4. Ascendente . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.1.5. Dualidad en la forma de abordar el problema . . . . . . 137
7.1.5.1. Asimetrı́as . . . . . . . . . . . . . . . . . . . . 138
7.1.5.2. Inserción de elementos . . . . . . . . . . . . . . 138
Índice general. xiii
8. Conclusiones 163
8.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.2. Desarrollos futuros . . . . . . . . . . . . . . . . . . . . . . . . . 164
Apéndices 166
Índice general. xiv
Bibliografı́a 227
xvii
Índice de figuras. xviii
7.1. (A) Merge antes de la última fusión (B) Quicksort tras la pri-
mera división . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.2. Burbuja: información almacenada tras k iteraciones . . . . . . . 146
7.3. Burbuja: grafo que representa la situación tras k pasadas . . . 146
7.4. Burbuja: información real obtenida tras k comparaciones . . . . 147
7.5. Burbuja: grafo que refleja toda la información obtenida . . . . 147
7.6. Burbuja optimizada: grafo de una situación intermedia . . . . . 148
7.7. Burbuja optimizada: se compara Y con Z . . . . . . . . . . . . 149
7.8. Burbuja optimizada: nueva situación si y < z . . . . . . . . . . 149
7.9. Burbuja optimizada: nueva situación si y > z . . . . . . . . . . 149
xxi
palabra
Dedicado a mi familia, en especial
a mis dos amores: Marta y Gabriel
Capı́tulo 1
Introducción
1
Capı́tulo 1. Introducción 2
orden buscada.
Coste de las comunicaciones entre procesos, para los que no hay una
medida satisfactoria. Las comparaciones dejan de ser las operaciones
crı́ticas: lo realmente importante es el número de operaciones internas
de un procesador junto con el coste de las comunicaciones entre ellos, lo
que afecta a varios (o todos) los procesadores.
Ordenación clásica:
fundamentos básicos
The price of realibility is the pursuit of the utmost simplicity.
It is a price which the very rich find most hard to pay.
5
Capı́tulo 2. Ordenación clásica: Un poco de historia 6
5. Dos ejecuciones diferentes del algoritmo que dispongan del mismo con-
junto de datos en su entrada, deben obtener idéntico resultado en su
salida. Aquı́ se establecen dos visiones diferentes: una visión determinis-
ta, que acepta varios estados finales que sean igualmente válidos. Una
visión no determinista, que aceptada salidas distintas que son igualmen-
te válidas, en tanto en cuanto satisfacen la postcondición final.
1
Principio fundamental de los meta-algoritmos definidos en los capı́tulos 4 y 5.
Capı́tulo 2. Ordenación clásica: Un poco de historia 8
la ordenación de elementos.
Aquellos algoritmos de ordenación que realizan su tarea sobre la memoria
central del ordenador se denominan algoritmos de ordenación interna.
Por las caracterı́sticas de almacenamiento y acceso de dicha memoria, el
acceso al conjunto de elementos se realiza de forma aleatoria y directa, por lo
que su gestión y tiempo de procesamiento es muy rápido.
2
Proporcionalmente a la velocidad de trabajo del resto del sistema informático.
Capı́tulo 2. Ordenación clásica: Un poco de historia 11
Los algoritmos más eficientes que realizan su trabajo en serie, son co-
nocidos por la cualidad de poder ordenar n valores en una media del orden
O(n log n) comparaciones. Este es el lı́mite lógico para la resolución del pro-
blema que se aborda.
De forma particular, los algoritmos de ordenación son examinados minu-
ciosamente evaluando su comportamiento respecto a la ocupación de memoria
(cantidad de memoria adicional requerida para ser ejecutados, añadida esta a
la memoria que utiliza la secuencia original para la ordenación), estabilidad
(requisito por el cual los elementos iguales van a mantener su orden relati-
vo original) y un especial cuidado con la distribución de valores iniciales (en
particular la complejidad del mejor y el peor de los casos posibles para cada
algoritmo).
Situaciones de contingencia.
Comparaciones en paralelo.
Analizando la situación con más detalle, cada vez que finalicen 2 pasadas
completas del algoritmo Burbuja, se necesita un procesador menos: en uno de
los extremos se encuentran los 2 valores (máximos o mı́nimos) del conjunto de
elementos tratado.
M = n/p
2.5.2. Alternativa
En este punto se describe una posible alternativa para el algoritmo de
bloque en paralelo. Se toma como punto de partida la premisa de disponer de
4 procesadores (p0 , p1 , p2 , y p3 ), actuando todos ellos sobre la misma memoria
compartida. El tamaño de la citada memoria debe ser al menos 4 × M , siendo
M el valor del bloque tal y como se describe en el anterior apartado (M = n/p).
Meta-algoritmos de
ordenación: pilares
fundamentales
Maestro, no tengo nada en mi mente, ¿qué debo hacer?.
Tı́ralo fuera.
Pero si ya no tengo nada.
Entonces, quédatelo.
Filosofı́a Zen
3.1. Introducción
¿Qué se entiende por meta-algoritmo de ordenación?.
La primera parte de la expresión, meta-algoritmo, parece dejar claro en
la propia definición que se trata de un concepto que engloba a otros algoritmos,
situándose un paso por encima de estos. Desde el punto de vista conceptual los
algoritmos contenidos son particularizaciones del meta-algoritmo. Este posee
unas condiciones mı́nimas pero completas que establecen los mı́nimos requi-
sitos para resolver un problema. Esta nomenclatura (basada en la aplicación
del concepto abstracción) trata de sugerir que un meta-algoritmo1 pretende
realizar idéntica tarea que un conjunto de algoritmos, deshaciéndose de todo
aquello que sea considerado superfluo centrándose exclusivamente en la raı́z
del problema a resolver.
1
meta-: Prefijo utilizado para indicar que un concepto es una abstracción tomando otro
concepto como base.
25
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 26
3.2. Abstracción
3.2.1. El papel de la abstracción
A lo largo de la historia de la informática, analistas, diseñadores y cons-
tructores de aplicaciones software, se han enfrentado en no pocas ocasiones a
la tarea de resolver problemas cuya complejidad podı́a ser considerada como
“muy elevada”. En todos los casos se debı́a encontrar soluciones con las he-
rramientas disponibles en cada época. En multitud de ocasiones la solución
propuesta al problema se debı́a adaptar, obligatoriamente, a las restricciones
hardware de la máquina en que iba a ser ejecutada, a los lenguajes de pro-
gramación disponibles en cada época (habitualmente a los que están más “de
moda”) y a sus estructuras de datos predeterminadas e inflexibles.
Afortunadamente el paso del tiempo y sobre todo la experiencia, han
ocasionado un cambio en la mentalidad de los desarrolladores en el momento
de representar las soluciones de la forma más independiente posible de aquellas
restricciones que no tienen nada que ver con el problema que se aborda. Esto
ha posibilitado la introducción del concepto abstracción en la ingenierı́a del
software, con todas las ventajas que ello conlleva al detallar las soluciones.
Como bien describe Wulft: ((Los humanos hemos desarrollado una técni-
ca excepcionalmente potente para tratar la complejidad: abstraernos de ella.
Incapaces de dominar en su totalidad los objetos complejos, se ignoran los
detalles no esenciales, tratando en su lugar con el modelo ideal del objeto y
centrándonos, exclusivamente, en el estudio de sus aspectos esenciales)).
Se puede afirmar que en la resolución de problemas complejos por parte
de la ingenierı́a del software, la introducción del concepto abstracción[8] per-
mite añadir la capacidad de encapsular y aislar la información del diseño y
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 28
Para que sean útiles y aportar sentido (cada uno dentro del contexto
que proceda) los modelos mentales han de resultar más sencillos que el siste-
ma que tratan de imitar o recrear. Si no se sigue dicho principio, el modelo
generado con toda probabilidad, resulte inútil. A continuación se muestra un
ejemplo sencillo: consideremos un mapa como el modelo de un territorio. Con
el fin de que este sea útil debe representar de forma sencilla el territorio que
modela. Un mapa bien abstraı́do y modelado sirve de gran ayuda. Transmite
la información precisa y esencial de las caracterı́sticas del territorio que mode-
la: caracterı́sticas que se antojan como básicas y fundamentales para realizar
desplazamientos de forma eficiente por el terreno modelado.
Del mismo modo que un mapa ha de ser más pequeño (significativa-
mente) que el territorio al que representa y sólo ha de incluir información
que ha sido seleccionada minuciosamente, los modelos mentales abstraen las
caracterı́sticas de un sistema para que sea comprendido, ignorando aquellos
detalles considerados como irrelevantes. Este proceso de abstracción es psi-
cológicamente necesario y natural, siendo crucial para comprender el complejo
mundo en que vivimos.
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 29
operaciones que se realizan sobre ella, definen las únicas operaciones permiti-
das sobre las instancias de dicha estructura de datos. De esta forma se tienen
controlados en todo momento los elementos que componen la pila, al permi-
tirse únicamente sobre ella las operaciones predefinidas. Con estas condiciones
se garantiza la integridad de la estructura de datos elegida.
1.- Permite una mejor conceptualización y modelado del mundo real. Mejora
la representación y la comprensibilidad. Clarifica los objetos basados en
estructuras y comportamientos comunes.
6.- Recoge mejor la semántica del tipo. Los TAD agrupan o localizan las
operaciones y la representación de atributos.
Ese es uno de los pilares fundamentales sobre los que se apoya el desa-
rrollo de esta Tesis: tratar de eliminar cualquier imposición o restricción en la
búsqueda de una solución. Restricciones que por norma general resultan ajenas
a la naturaleza del problema, considerándose superfluas e innecesarias para su
resolución. Sin embargo marcan y condicionan el camino a seguir hacia una
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 34
3.4.1. Ángulos
La anteriormente citada correspondencia biyectiva es vista en ambos
sentidos: desde el punto de vista de un elemento encontrar la posición final
que ha de ocupar. O bien, desde el punto de vista de todas las posiciones
disponibles encontrar para cada una el elemento que le corresponde.
2
En cuanto al establecimiento de la relación de orden.
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 35
3
El número natural que indica su posición.
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 36
3.4.1.3. Para-algoritmos
Con la descripción anterior que define un meta-algoritmo se imponen una
serie de restricciones que, lógicamente han de seguir respetando las premisas
iniciales sobre las cuales fue diseñado.
Entre esas restricciones se encuentra el establecer una imposición en el
orden de actuación de los procesos. Dicha restricción lo único que hace es
concretar más el meta-algoritmo, pero no lo invalida. La imposición de dichas
restricciones hacen que se pase de un meta-algoritmo a un para-algoritmo. En
este caso, las estructuras de control ya quedan fijadas al ser impuesto el orden
de actuación de los procesos.
3.5. Convenciones
Para desarrollar el meta-algoritmo es necesario definir una serie de pre-
misas básicas sobre las que apoyarse relacionadas con los posibles resultados
obtenidos al comparar los elementos a procesar.
Según la interpretación elegida al realizar la comparación se obtienen di-
ferentes estados finales en el orden de los elementos, siendo en cualquier caso
todos ellos equivalentes. Las convenciones establecidas en este apartado y si-
guientes pueden ser alteradas sin que, por ello, cambie en absoluto el resultado
final proporcionado por el meta-algoritmo: basta con alterar la interpretación
que se realiza de la solución proporcionada por este sin perdida alguna de
generalidad.
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 40
α Φ β ⇒ α, si α > β
α Φ β ⇒ β, si α < β
α Φ β ⇒ Iguales, si α = β
Por este motivo la elección de una clave secundaria lo más sencilla y rápida de
comparar posible, se considera un aspecto fundamental en el proceso inicial
de definición. Algunas de las claves secundarias más sencillas que se proponen
son las siguientes:
Utilizar la posición relativa que ocupa cada elemento dentro del conjunto
a tratar. De esta forma, en caso de igualdad es considerado como ele-
mento ganador aquel que ocupe una posición precedente dentro de dicho
conjunto.
Repetir preguntas.
8
Puesto que la pregunta sólo tiene dos respuestas posibles, es la que da más información
según establece la teorı́a de información de Shannon.
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 47
3.8.1. Estrategias
Para realizar la pregunta más inteligente se establecen dos estrategias:
3.8.2. Consideraciones
El trabajo está delimitado por la restricción (consideración) de que todas
las acciones reducen la incertidumbre. Hay dos consideraciones que justifican
esta decisión:
Las acciones de este tipo pueden ser consideradas como acciones de man-
tenimiento9 y colisionan con las acciones útiles, desapareciendo del pro-
ceso como tales.
Si x < y, se obtiene un 0.
Si x > y, se obtiene un 1.
A medida que se avanza hacia un estado final los vértices del conjunto V
se relacionan mediante las aristas del conjunto A. En el proceso de ejecución el
número de vértices V permanece invariable, mientras que el número de aristas
del conjunto A ha de ir creciendo hasta encontrar la solución.
En un cualquier punto intermedio del proceso (como por ejemplo el
representado en la figura 3.3) la cardinalidad del conjunto V permanece inva-
riable con respecto a su valor inicial (#V =#E), y el conjunto de aristas tiene
una cardinalidad superior a la inicial (salvo que al inicio #V =0 o #V =1, con
lo que #A=0 para toda la ejecución). El número de aristas, o lo que es lo mis-
mo #A, debe estar comprendido durante toda la ejecución entre los valores
[0, #V −1].
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 53
Los grados del nodo raı́z son G(e) = 0 y G(s) = 1, y los del único nodo
hoja G(e) = 1 y G(s) = 0.
(a) (b)
Figura 3.6: (A) Matriz estado inicial (B) Matriz estado final
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 56
(a) (b)
Por la forma en que se define la matriz de incidencia resulta muy útil para
seleccionar los candidatos con los que continuar el proceso de comparación,
evitando la repetición de preguntas cuya respuesta se conoce de antemano.
Aquellos elementos de la matriz cuyo valor sea igual a cero se encuentran
entre los posibles candidatos para la siguiente comparación.
El proceso de búsqueda de la relación de orden total finaliza cuando la
mitad superior de la matriz se encuentra completa, lo que se traduce en que
todos los valores por encima de la diagonal son iguales a 113 (situación que se
muestra en la figura 3.16).
El orden final de los elementos coincide con la posición relativa de
fila/columna que ocupa cada elemento en la matriz de incidencia.
13
Realmente al finalizar disponen de valor absoluto uno todos los elementos de la matriz.
Los situados en la diagonal desde el inicio. Los situados por debajo de la diagonal, por
reflexividad, desde el momento en que disponga de dicho valor su elemento simétrico situado
encima de la diagonal.
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 63
3.10. Transitividad
La propiedad de transitividad permite sacar el máximo provecho de las
comparaciones que se realizan en la búsqueda del orden total. En ocasiones
bajo determinadas circunstancias, cuando se comparan dos elementos del con-
junto E, la información obtenida no sólo arroja información sobre el orden de
ambos, sino que aplicando la propiedad de transitividad es posible obtener la
relación con otros elementos del conjunto. Esta información es desperdicia-
da en muchas ocasiones, haciendo que en un futuro no lejano se tengan que
realizar preguntas cuya respuesta podrı́a haber sido deducida.
Si entre los elementos del conjunto {a, b, c} ∈ E es conocida la informa-
ción de que a < b y b < c, es innecesario preguntar en un futuro si a < c, puesto
que aun no habiéndose realizado la comparación, la respuesta es deducible por
el resto de información que se dispone.
Tal y como se describe en el apartado 3.9.2, la obtención del orden total
se refleja en la matriz de incidencia cuando todos los elementos por encima
de su diagonal dispongan de un valor igual a 1. Por tanto avanzar hacia la
solución, consiste en obtener en cada paso el mayor número de unos posible
en la matriz.
Cuando se realiza la comparación entre dos elementos es deseable no
sólo reflejar la información obtenida de forma directa tras la comparación,
sino también aprovechar aquella que se obtiene de forma indirecta, con el fin
de evitar en futuras comparaciones preguntas cuya respuesta era deducible.
Representada la información directa obtenida por comparación de dos ele-
mentos en la matriz de incidencia y, una vez realizada la clausura transitiva a
esta, los ceros en la matriz de incidencia representan posibles comparaciones
útiles, mientras que los unos representan las preguntas superfluas.
En los siguientes ejemplos se muestran dos algoritmos de ordenación
en sus vertientes opuestas respecto al concepto de transitividad: en primer
lugar un algoritmo que se olvida del concepto y lo desaprovecha: Burbuja. En
Capı́tulo 3. Meta-algoritmos de ordenación: conceptos básicos 66
segundo lugar uno de los múltiples algoritmos que sı́ lo aprovecha: Binario.14
En cada pasada del algoritmo, cada elemento es comparado con los n−1
elementos restantes hasta ocupar la posición que le corresponde, por lo que
cada pasada del algoritmo coloca de forma definitiva un elemento: ocupa la
menor posición el elemento vencedor de la última comparación de cada pasada.
Sin embargo en la misma pasada es muy probable que existan elementos que
hayan ganado comparaciones parciales, cuyos resultados tras la comparación
son despreciados por el algoritmo debiendo repetir comparaciones en futuras
pasadas, con el consiguiente desperdicio de tiempo de ejecución.
Supongamos un elemento ai que va ganando varias comparaciones en el
proceso de ejecución hasta tropezar con un bi que resulta ser menor que él,
y menor que todos los elementos. De forma efectiva en esa pasada el elemen-
to bi pasa a ocupar la posición definitiva en el orden final, pero de toda la
información de las “victorias” obtenidas por ai no queda rastro alguno. En
la siguiente pasada ai vuelve a ser comparado con elementos cuyo resultado
de la operación ya es conocido. Este hecho se produce porque el algoritmo
desaprovecha la información que se obtiene por transitividad.
Meta-algoritmo descendente
Nikolay Lobachevsky
4.1. Introducción
El concepto de meta-algoritmo de ordenación descrito en el capı́tulo 3,
junto con los componentes necesarios para su ejecución, permiten construir dos
meta-algoritmos que se diferencian únicamente en las mı́nimas estructuras de
control necesarias.
Este capı́tulo se centra en el estudio de lo que se ha denominado meta-
algoritmo descendente. A la expresión meta-algoritmo ya detallada, se añade
ahora el calificativo de descendente. Utilizando la máxima de “divide y ven-
cerás” para la resolución de problemas y haciendo una analogı́a con las me-
todologı́as incluidas en dicha máxima, el problema es abordado mediante una
metodologı́a de división de problemas, de refinamientos sucesivos, aplicando
una filosofı́a top-down.
71
Capı́tulo 4. Meta-algoritmo descendente 72
una estructura común más profunda subyacente. Los puntos en común, salvo
por matices de implementación final, permiten afirmar que ambos algoritmos
trabajan de idéntica forma: en cada iteración uno de los elementos del conjun-
to a tratar pasa a ocupar su posición definitiva respecto al resto de elementos,
que en las siguientes iteraciones ocupan el lugar que les corresponde en la
relación de orden final.
En el caso del algoritmo Quicksort, dicho elemento es el denominado
“pivote”, y es el encargado de marcar el valor por el cual se ha de realizar la
división de cada conjunto de elementos. En el caso del algoritmo Binario es la
propia construcción del árbol de búsqueda quien se encarga de proporcionar
la citada división.
tiempo, pero todos los elementos son comparados con el primero escogido, de-
rivándose hacia el subárbol derecho o el izquierdo según sea el resultado de la
comparación.
Este proceso se repite con cada uno de los conjuntos obtenidos, y se
sigue realizando de forma recursiva hasta encontrar la relación de orden final
para el conjunto de elementos inicial.
En resumen, ambos algoritmos realizan las mismas acciones esenciales
aunque las distribuyen en el tiempo de forma diferente.
2. El elemento que se toma como pivote al activar un proceso (de entre los
elementos presentes en ese momento en el componente de entrada).
C ⊂ E es un conjunto de elementos.
e ∈ {a, b, c} representa el estado del proceso, con el siguiente signi-
ficado:
◦ a significa creado: sin pivote seleccionado aún.
◦ b significa activo: el proceso P ya dispone de pivote.
◦ c significa terminado: su entrada está vacı́a y no tendrá más
elementos en el futuro.
v ∈{} ∪ E es el pivote, si lo hay.
Q, R ∈{λ} ∪ P los subprocesos, si los hay.
S ∈{λ} ∪ P la salida que es una cola, y estará vacı́a salvo cuando
el estado sea c.
1. Cuando se crea el proceso, no hay pivote y los enlaces a los hijos son
nulos, por lo tanto si e = a, v ha de ser {}, P y Q han de ser λ, y S ha
de ser ∅, lo que se traduce en:
C=
6 ∅ y v ∈C
⇒ P 0 = (C −{v}, b, v, λ, λ, ∅)
Capı́tulo 4. Meta-algoritmo descendente 81
Sea w < v.
⇒ P 0 = ( C −{w}, b, v, Q, R, S)
donde si Q = λ
Q0 = ({w}, a, {}, λ, λ, ∅)
y si Q = (C 0 , x, y, Z, T, S 0 )
Q0 = (C 0 ∪ {w}, x, y, Z, T, S 0 )
Sea w > v.
⇒ P 0 = ( C −{w}, b, v, Q, R, S)
donde si R = λ
Capı́tulo 4. Meta-algoritmo descendente 82
R0 = ({w}, a, {}, λ, λ, ∅)
y si R = (C 0 , x, y, Z, T, S 0 )
R0 = (C 0 ∪ {w}, x, y, Z, T, S 0 )
⇒ (∅, c, v, Q, R, S)
⇒ P = (∅, c, v, P 0 , Q0 , S 0 )
Capı́tulo 4. Meta-algoritmo descendente 83
⇒ Q = (∅, c, v, P 0 , Q0 , S 0 )
7. Si P = (∅, c, v, Q, R, S) entonces:
4.8.6. Indeterminaciones
Las indeterminaciones de secuencia dinámica que no afectan a la validez
del proceso y que se utilizan como grados de libertad en las implementaciones
son:
Como los procesos sólo se comunican por las entradas y salidas, las po-
sibilidades de paralelismo son múltiples con tal de que se respete la
exclusión en el acceso a esos recursos que se comparten.
4.9. Optimizaciones
Hay una serie de optimizaciones aplicables a cualquier implementación,
por ejemplo:
Como las entradas y salidas tienen vidas activas (útiles) disjuntas (las
entradas se utilizan en estado “a” [creado] y “b” [activo], mientras que las
salidas se usan en el estado “c” [finalizado]), en cualquier implementación
pueden compartir recursos fı́sicos. Pero esas dos vistas han de respetar las
exigencias de cada una: como entrada es un conjunto sin más condiciones,
mientras que como salida ha de ser gestionada como una cola.
∀ a ∈ C1 , a < e.
∀ b ∈ C2 , b > e.
por transitividad los valores matriciales pasan a ser los mostrados en la figura
4.23.
1.- Inicial,
4.13.2. Quicksort
Aplicando una técnica similar a la del problema de la bandera holandesa,
es posible utilizar una estructura de datos secuencial que permita el intercam-
bio de elementos (es la única operación necesaria para el mantenimiento de
esa estructura de datos y su significado).
Como un proceso actúa hasta que se detiene definitivamente, los estados
“a” y “b” son innecesarios.
La entrada se produce por los elementos ya colocados en la estructura
de datos. La salida es innecesaria, puesto que el estado final de la estructura
secuencial representa perfectamente el orden final: es decir, la estructura lineal
cubre las funciones de las entradas y salidas de los procesos.
En ambos casos se renuncia a ciertas posibilidades de paralelismo, a
cambio de una simplificación de la estructura que de todas formas está presente
o en la estructura del árbol binario o en la dinámica de la recursividad.
Meta-algoritmo ascendente
C.A.R. Hoare
5.1. Introducción
Al considerar los algoritmos clásicos de Fusión y Torneo se observan
unas similitudes entre ellos que sugieren un enfoque que los engloba.
Ambos algoritmos construyen en una primera fase (explı́cita o implı́ci-
tamente) un árbol binario de procesos distribuyendo en él los elementos a
99
Capı́tulo 5. Meta-algoritmo ascendente 100
estado final. Un proceso en estado final con la salida vacı́a puede ser eliminado
del procedimiento puesto que ya no tiene actividad posible.
Esta mecánica es la utilizada por los procesos del árbol hasta finalizar
todos y cada uno de ellos. Cuando un proceso transfiere la salida a su proceso
padre y sus procesos hijo ya no disponen de elementos en sus salidas, el proceso
puede ser eliminado del árbol.
Al finalizar la ejecución del meta-algoritmo, el proceso raı́z dispone en su
salida (gestionada como una cola) de todos los elementos que se encontraban
en su entrada al comienzo de la ejecución, garantizando que se encuentran en
la relación de orden deseada. El resto de procesos son eliminados liberando
la correspondiente memoria ocupada. La figura 5.5 muestra el resultado al
finalizar.
Capı́tulo 5. Meta-algoritmo ascendente 105
P ⊂ E es un conjunto de elementos.
e ∈ {a, b, c} representa el estado del proceso, con idéntica descripción
a la realizada en el capı́tulo 4 apartado 4.62 .
Q, R ∈{λ} ∪ P los subprocesos, si los hay.
S ∈ {λ} ∪ P se corresponde con la salida gestionada como una cola,
que está vacı́a salvo cuando el estado del proceso sea finalizado.
Las transiciones permitidas desde este estado inicial son las que posi-
bilitan el proceso de ejecución del meta-algoritmo a través de sus dos fases
(distribución y fusión).
Las transiciones permitidas desde el estado inicial para el proceso P son
las siguientes:
⇒ (∅, c, λ, λ, (g))
5.7. Indeterminaciones
Los grados de libertad que se pueden ejercer en este meta-algoritmo son:
5.9. Derivaciones
La ejecución del meta-algoritmo permite derivar algoritmos secuenciales
dando prioridad a unos procesos sobre otros, obteniendo los diferentes algorit-
mos clásicos en él contenidos y que son cristalizados mediante una implemen-
tación concreta y detallada.
Se hace necesario recordar en este punto que el árbol binario que se
construye a lo largo de la primera fase de la ejecución, es un árbol binario de
procesos, no de elementos. Eso permite la posibilidad de aplicar paralelismo
entre los diferentes procesos que componen el árbol.
Es verdad que no siempre será posible llevar a cabo varias tareas en
simultáneo o, por decirlo de otra forma, es posible que la aportación obteni-
da por el paralelismo no sea la deseada de no ser puesta en práctica con un
análisis previo de la forma de funcionamiento del meta-algoritmo.
5.11.2. Fusión
En el caso del algoritmo Fusión, al dar prioridad a los procesos situados
en zonas inferiores del árbol un proceso no comienza a actuar mientras sus
procesos hijo se encuentren activos.
Por ello se consideran como superfluos los estados de los procesos siendo
simplificados, ya que el estado en que se encuentra cada proceso realmente
queda determinado por la dinámica local.
Capı́tulo 6
Esquemas
Hilbert
6.1. Introducción
6.2. Esquemas
Los esquemas son un paso más de la abstracción. Si los meta-algoritmos
prescinden de la implementación de la estructura de control definiendo sólo
las acciones necesarias, los esquemas prescinden de la implementación de las
estructuras de datos, limitándose a considerarlas de forma abstracta con las
operaciones que son mı́nimamente necesarias y limitan la estructura de control
a la mı́nima precedencia entre operaciones. En buena parte la presencia de la
estructura de control perturba el punto de vista desviando la atención hacia
la eficiencia real o pretendida, mientras que lo esencial que es la corrección
queda desatendida.
117
Capı́tulo 6. Esquemas 118
En una situación dada, sea fácil determinar las acciones adecuadas (efec-
tivas) a realizar.
de datos final será un grafo conexo, sin disponer de orden alguno, que contie-
ne a todas las letras iniciales “entrelazadas”de una forma totalmente aleatoria.
Figura 6.6: Zonas que no se tocan (rojo) y sobre la que se trabaja (verde)
El número de hijos.
a.NumeroDeHijos := a.NumeroDeHijos - 1
x.NumeroDeHijos := x.NumeroDeHijos + 1
x.UltimoDescendiente := y.UltimoDescendiente
a.NumeroDeHijos := a.NumeroDeHijos - 1
y.NumeroDeHijos := y.NumeroDeHijos + 1
y.UltimoDescendiente := x.UltimoDescendiente
6.5.2. Conclusiones
El trabajo con esquemas de árboles no tiene por qué ser complicado
ni costoso. El mantenimiento que se ha de realizar en los esquemas incluso
genéricos no tiene por qué ser especialmente oneroso, como se ha mostrado.
Realizar el almacenamiento de la información de la estructura arbórea
en preorden no es una condición necesaria: se puede utilizar cualquier otro tipo
de orden y la estructura sigue siendo igualmente válida. Se ha elegido preorden
por comodidad al considerarse el más intuitivo para realizar el análisis.
Capı́tulo 6. Esquemas 133
6.9. Acciones
Las acciones tienen como objetivo principal incorporar al esquema la
información obtenida por una comparación. Por lo tanto cada comparación
que se produce no ha de haberse realizado con anterioridad, ni ha de poder ser
deducida (por transitividad) de las comparaciones ya realizadas. La violación
de la primera condición puede dar lugar a un bucle sin salida, mientras que la
violación de la segunda da lugar a acciones perfectamente inútiles.
La primera condición garantiza que el objetivo final se alcanza con un
número finito de acciones, mientras que la segunda sólo pretende que cada
acción aproxime la situación actual al objetivo final.
Miscelánea
La simplicidad es un prerrequisito
para la fiabilidad.
Edsger W. Dijkstra
135
Capı́tulo 7. Miscelánea 136
una relación de orden total entre los elementos del conjunto de entrada, aso-
ciando a cada elemento una posición final en la citada relación. Los procedi-
mientos locales han de responder a uno de estos dos planteamientos:
7.1.2. Descendente
En el meta-algoritmo descendente los procedimientos que resuelven el
problema son descritos como de descomposición de este en otros problemas
menores. Cada paso nos acerca a la solución final dividiendo un problema de
gran envergadura en otros de menor tamaño y mayor facilidad de resolución.
Puede decirse que se sitúan encuadrados dentro de una dinámica de bifurca-
ción y progreso hacia acciones menores. Las diversas formas de materializar
dichas acciones es lo que da lugar a la variedad de representaciones finales.
7.1.4. Ascendente
De manera análoga este meta-algoritmo construye soluciones parciales
locales que deben ser combinadas de forma ascendente. Al combinar problemas
menores que se tratan de manera independiente, la posibilidad de paralelis-
mo se presenta en la fase ascendente y su principal caracterı́stica es la de
sincronización.
En los primeros pasos no es posible llevar a cabo el paralelismo, ya que
para iniciar la composición de soluciones parciales es necesario que previamente
estas hayan sido construidas.
Al igual que el descendente, el procedimiento completo también consta
de dos fases:
Dicho de otra forma, todos los algoritmos que se incluyen dentro del
meta-algoritmo ascendente sincronizan subproblemas, mientras que aquellos
que se incluyen dentro del meta-algoritmo descendente bifurcan en subproble-
mas.
7.1.5.1. Asimetrı́as
Continuando con un análisis exhaustivo sobre la forma de trabajo de
ambos meta-algoritmos, en este apartado se muestran las asimetrı́as que se
producen en ambos procesos de ejecución: aspectos fundamentales que mues-
tran como el punto fuerte de un meta-algoritmo se convierte en el punto débil
de su homólogo, y viceversa.
(a) (b)
Figura 7.1:
(A) Merge antes de la última fusión
(B) Quicksort tras la primera división
1
Se elige el punto por el que realizar la división de cada conjunto en dos subconjun-
tos de menor tamaño. Siempre que se tenga posibilidad de elección la mejor alternativa es
seleccionar el punto medio, como se demuestra en el apéndice D
Capı́tulo 7. Miscelánea 140
7.2.2. Situaciones
Unas situaciones tı́picas que se suelen dar son:
Para cualquiera de estos casos, llevar a cabo la solución por fuerza bruta
es poco eficiente en tiempo y desde luego completamente ineficiente en espacio.
Si se piensa en textos de varias páginas, la solución por fuerza bruta pudiera
incluso funcionar con las citadas limitaciones, pero si se piensa en analizar
una biblioteca completa entonces la fuerza bruta se califica simplemente como
inaceptable.
3. En el resto de los casos, al pivote se le asocia una lista con los lugares
de aparición que se actualiza con la incorporación de un nuevo lugar de
aparición cuando el pivote sea comparado con un elemento que posea
idéntica palabra.
Por norma general la lista construida se ha de proporcionar ordenada,
tarea que se puede hacer posteriormente o (lo más habitual) si los elementos
se generan con los lugares de aparición ordenados, basta con procesarlos por
Capı́tulo 7. Miscelánea 143
7.2.4. Conclusiones
Para resolver un problema de ordenación de elementos, en principio, se
puede utilizar cualquier algoritmo puesto que todos ellos cumplen eficazmente
con la tarea encomendada. Lógicamente la eficiencia y utilización de recursos
(ası́ como su disponibilidad) no resulta ser la misma en unos y otros casos.
Con este ejemplo se pretende mostrar como circunstancias externas aje-
nas al problema a resolver y completamente independientes del concepto de
ordenación en sı́ mismo, dan preferencia a un par de algoritmos concretos
permitiendo obtener una solución más clara y sencilla tanto en el proceso de
ejecución como en el mantenimiento de las estructuras de datos.
7.3.3. Análisis
En cada ejecución del bucle interior el elemento menor de los que están
en las posiciones (i .. n) se intercambia con su inmediato anterior hasta situarse
en la posición i.
Las condiciones de verificación son ası́ fáciles de definir:
1.- El bucle externo en cada iteración con ı́ndice i, tiene como condición
inicial que los elementos de 1 .. i−1 son los menores y están ordenados.
para el ı́ndice i se obtienen no sólo los primeros i elementos sino algunos más,
en ejecuciones posteriores del bucle se realizan comparaciones innecesarias.
El método clásico considera que la información de que dispone al cabo de
k ejecuciones del bucle exterior es la que se representa en el gráfico mediante
la matriz de incidencia de la figura 7.2.
Realizando la representación como grafo (árbol) la imagen es la repre-
sentada en la figura 7.3.
Mientras que la información deducible por comparaciones representada
en la matriz de incidencia, se muestra en la figura 7.4.
Y el árbol que representa la misma información se corresponde con el de
la imagen 7.5.
Capı́tulo 7. Miscelánea 147
estado(n):=1;
ultimo:=1;
loop
for j in reverse ultimo..n-1 loop
if (estado(j)=0) and (estado(j+1)=1) then
if (elemento(j) > elemento(j+1) then
estado(j):=1;
else
swap(elemento(j), elemento(j+1));
swap(estado(j), estado(j+1));
end if;
end if;
end loop;
estado(n):=1;
z:=ultimo;
for j in ultimo..n-1 loop
if estado(j)=0 then
z:=j;
exit;
end if;
exit when (z=ultimo);
end loop;
ultimo:=z;
end loop;
Los elementos en estado 1 son considerados como los procesos del meta-
algoritmo descendente.
Por otro lado, el propio pivote del proceso que realiza la comparación.
Capı́tulo 7. Miscelánea 152
a ser mejor que los métodos “tradicionales”, sobre todo si los elementos son
voluminosos.
Por otro, se calcula el espacio necesario tanto para la ejecución del algo-
ritmo como para el almacenamiento de los datos6 (espacio).
Pero no son sólo estos factores los que influyen en la eficiencia de un algo-
ritmo. Existen una serie de factores externos ajenos a la naturaleza intrı́nseca
del propio algoritmo y del conjunto de elementos a ordenar, que condicionan
la eficiencia definitiva de la ejecución.
La arquitectura en la que este sea ejecutado, encargada de la gestión de
los recursos disponibles (gestión de memoria, gestión de periféricos...) condi-
ciona en gran medida la preferencia por uno u otro algoritmo. Si además se
introduce el concepto de paralelismo, es necesario tener en cuenta la concu-
rrencia de procesos sobre el mismo conjunto de elementos y el intercambio de
información entre diferentes procesadores. Todos estos requisitos impuestos
por el entorno nada tienen que ver con la propia naturaleza del proceso de
ordenación.
Actualizaciones de la estructura.
6
Tanto los resultados finales como los parciales.
Capı́tulo 7. Miscelánea 157
En los procesos que nos atañen, las limitaciones lógicas a las que tiene
que acomodarse el módulo de ordenación son:
Por tanto existen situaciones en que los requisitos externos imponen unas
condiciones que dan preferencia a unos procedimientos sobre otros al poder
atender esos requisitos con más facilidad.
En la anterior situación descrita en que la tarea que “ordena” ha de pro-
porcionar los elementos ordenados a otra, es deseable que esta segunda tarea
no tenga que esperar a que se complete el proceso de ordenación. Mientras la
segunda tarea procesa los elementos que recibe, la primera realiza la ordena-
ción. Para esta situación, lo deseable es que los elementos sean proporcionados
por orden lo antes posible y poder ası́ iniciar su tratamiento posterior.
A continuación se realiza un análisis de esta posible situación, tratan-
do de obtener una simultaneidad en los principales algoritmos que han sido
descritos o analizados.
7.9.1. Quicksort
El algoritmo de ordenación clásico Quicksort[16] ha de comparar todos
y cada uno de los elementos con el pivote inicial, por lo que en este caso no se
puede simultanear el proceso de producción con la ordenación.
En este algoritmo el proceso raı́z encargado de dividir el conjunto de
entrada en dos subconjuntos puede comenzar su tarea aún cuando no dispon-
ga en la entrada de todos los elementos, pero no pueden iniciar la tarea de
ordenación sus procesos hijo hasta que no haya sido repartida por completo la
entrada del proceso raı́z. La consecuencia de esta situación es que se retrasa
el proceso de ordenación, como mı́nimo, a la completa recepción de elementos
procedentes del módulo productor.
7.9.2. Binario
El algoritmo Binario, por las caracterı́sticas intrı́nsecas en su proce-
so de ejecución, puede simultanear el trabajo de ordenación con el módulo
productor[17]. Esto es debido a que procesa los elementos según los va reci-
biendo, por lo tanto no es necesario que disponga al inicio de la ejecución del
conjunto completo de elementos a tratar.
Iniciado el proceso de ordenación, si la velocidad del productor es lenta
este algoritmo es el más adecuado, puesto que en el tiempo que transcurre
entre la llegada de elementos el proceso coloca en su lugar a cada elemento
que va tratando. En el momento que se produce la llegada del último ele-
mento y es colocado donde le corresponde, este algoritmo devuelve la salida
completamente ordenada de todo el conjunto de elementos.
Por las caracterı́sticas descritas es posible afirmar que el entendimiento
de este algoritmo con el módulo productor es máximo, mientras que con el
módulo consumidor es nulo ya que cuando recibe el último elemento y lo
procesa, no entrega sólo el primer elemento o conjunto de elementos menores
sino que entrega la salida completa y ordenada, por lo que no existe ningún tipo
de posible paralelismo entre ambos. Para cuando entrega el primer elemento
ya no le queda nada por hacer.
7.10. Observaciones
Es posible que en determinadas ocasiones y con el fin de no mantener
detenida la tarea consumidora, se permita que esta consuma elementos aunque
no sean los primeros, pero prefiriéndolos. Un posible ejemplo se encuentra al
tratar de gestionar una cola de tareas con prioridades.
En otras situaciones en que se necesita obligatoriamente que los elemen-
tos sean tratados en orden, a modo de resumen, los algoritmos clásicos se
comportan del modo que se describe a continuación.
Conclusiones
8.1. Conclusiones
Se ha definido una nueva taxonomı́a de algoritmos de ordenación ba-
sada exclusivamente en las caracterı́sticas y detalles del concepto ordenación,
alejada de cualquier detalle impuesto por las implementaciones. Las bases fun-
damentales para su definición se encuentran en el concepto de abstracción, a
base de eliminar en los algoritmos clásicos de ordenación la implementación
de la estructura de control y la estructura de datos.
163
Capı́tulo 8. Conclusiones 164
enfrentar los costes de espera con procesador inactivo con los costes de retra-
so global. (Un ejemplo de la aplicación es la utilización del paralelismo para
realizar la inserción de elementos mediante el uso de un procesador vectorial,
que es el tipo de paralelismo más simple).
Inserción de un elemento en
una cadena
167
Apéndice A. Inserción de un elemento en una cadena 168
s=p+1−s
2s = p + 1
p+1
s=
2
169
Apéndice B. Binaria vs Secuencial: numero medio de comparaciones 170
p+1
X
i−1 (p + 1)(p + 2)
−1 (p + 1)(p + 2) − 2 p+2
i=1
= 2 = ≈
p+1 p+1 2(p + 1) 2
B.3. Conclusiones
El número medio de comparaciones en la inserción binaria presenta una
función logarı́tmica, mientras que la misma situación realizada mediante inser-
ción secuencial presenta unos valores próximos a una función lineal: por tanto
el número medio de comparaciones es mucho menor en la inserción binaria
que en la secuencial como se aprecia en el gráfico comparativo B.1 para ambas
funciones.
Apéndice B. Binaria vs Secuencial: numero medio de comparaciones 171
C.1. Introducción
Cuando se necesita realizar la inserción de un elemento en una cadena
de elementos la cual posee una relación de orden, en principio si no se dispone
de más información que facilite la selección, el elemento elegido de la cadena
con el que realizar la comparación puede ser cualquiera.
Por tanto la cuestión que se plantea es: de todos los elementos (posicio-
nes) que forman la cadena en la que insertar el nuevo elemento, ¿existe algún
elemento (posición) que proporcione una mayor información que la del resto
de elementos que forman dicha cadena?.
Para responder a esta pregunta, en los siguientes apartados se desarro-
llan con ayuda de la teorı́a de la información una serie de cálculos basados
en el principio de entropı́a, también denominado entropı́a de la información o
entropı́a de Shannon.
173
Apéndice C. Inserción por la cabeza vs central 174
1
log2 (p + 1) − log2 p + log2 p
p+1
log2 (p + 1) − log2 p ≈ 0
Por lo que resta por analizar únicamente la segunda parte del resultado:
1
log2 p
p+1
Apéndice C. Inserción por la cabeza vs central 176
p+1
2 1
C2 ⇒ =
p+1 2
Aplicando el principio de entropı́a de Shannon:
1 1
H= log2 2 + log2 2 = 1
2 2
En esta situación la información obtenida en el proceso de comparación
es mucho mejor que la situación anterior, ya que el resultado nos da 1 bit de
información.
C.5. Conclusiones
Realizar la inserción por la cabeza es equiparable a realizar la inserción
de forma secuencial y realizar la inserción eligiendo un punto medio de la
cadena a la inserción binaria. Utilizando dichos términos, se afirma que realizar
la inserción binaria es un proceso óptimo mientras que realizar el proceso
utilizando inserción secuencial, pésimo.
Por los resultados obtenidos parece claro que siempre que sea posible y
no existan circunstancias externas que lo impidan, se recomienda realizar la
inserción por el punto medio de la cadena. Desde el punto de vista de la teorı́a
de la información esta es siempre la mejor opción.
Más uniformes sean las partes en que se divide el conjunto inicial. Esta
afirmación se cumple perfectamente en este caso: la peor situación se
produce cuando el conjunto inicial que dispone de p+1 posibilidades de
inserción se divide en dos subconjuntos, uno de tamaño p y otro formado
por un único elemento. En la mejor situación ambos conjuntos poseen
p+1
un tamaño similar, disponiendo cada subconjuto de elementos.
2
Apéndice D
Optimalidad de la
equipartición en Fusión
179
Apéndice D. Optimalidad de la equipartición en Fusión 180
respectivamente es la siguiente:
log2 n + 1 − log2 (n − x) − 1 = 0
log2 n = log2 (n − x)
x=n−x
n
x=
2
3.- Repetir las acciones de los pasos 1 y 2 (selección e inserción) con los
(q − i) elementos restantes de la cadena Q hasta completar la fusión de
ambas (instante en que longitud de la cadena Q pasa a ser 0).
181
Apéndice E. Inserción binaria elemento de cabeza vs elemento medio 182
La figura E.1 muestra de forma gráfica las dos situaciones que se plan-
tean.
Apéndice E. Inserción binaria elemento de cabeza vs elemento medio 183
Situación A.-
s · (q − 1)
Situación B.-
(q − 1) (q − 1) (q − 1)
r· +s· =p·
2 2 2
p
En término medio se puede decir que r ≈ s ≈ por lo que ambas
2
situaciones A y B son equivalentes en:
Según el resultado obtenido parece que nada tiene que ver la posición
en la que se encuentre x en la cadena Q, al menos desde el punto de vista de
la teorı́a de la información.
Situación A.-
Elementos hasta f in de P + q − 1
q−1
Situación B.-
q − 1 q − 1
P − elementos hasta f in de P + Elementos hasta f in de P +
2 · 2
P − elementos hasta f in de P Elementos hasta f in de P
Apéndice E. Inserción binaria elemento de cabeza vs elemento medio 186
E.3. Conclusiones
Se parte de una cuestión que al menos desde el punto de vista de la
lógica, parecı́a conducir de forma inmediata a una clara respuesta sobre el
elemento a seleccionar en una cadena que se pretende fusionar con otra: la
elección del elemento medio parece ser siempre preferida frente al elemento
situado en cualquier extremo.
Sin embargo el resultado no ha sido tan sencillo de obtener, más cuando
la teorı́a de la información arroja el resultado de que para valores de p grandes
(cadena formada por un elevado número de elementos) ambas situaciones son
idénticas.
Aún ası́ se busca otro punto de vista al problema: se analiza el resultado
según el número de partes en que divide cada situación, ası́ como el número
de elementos que compone cada una. Bajo este nuevo prisma las situaciones
son diametralmente opuestas. El número de divisiones es idéntico para ambas
situaciones, sin embargo el tamaño de cada parte es mucho más homogéneo al
seleccionar un elemento que se encuentra en una posición central de la cadena
Q (siempre en términos estadı́sticos).
189
Apéndice F. Ordenación por Selección 190
191
Apéndice G. Ordenación por intercambio o Burbuja 192
3.- El proceso continúa hasta que cada elemento del vector ha sido compara-
do con sus elementos adyacentes y se han realizado todos los intercambios
necesarios.
(n − 1)(n − 1) = (n − 1)2
195
Apéndice H. Ordenación por Inserción 196
n(n − 1)
2
n(n − 1)
Como (n − 1) + (n − 2) + ... + 3 + 2 + 1 = es una progre-
2
sión aritmética, esto da como resultado el siguiente valor para el número de
comparaciones medias:
(n − 1) + (n − 1) n2 n2 + n − 2
=
2 4
Apéndice I
Algoritmo de ordenación
Shell
199
Apéndice I. Algoritmo de ordenación Shell 200
un valor de salto = 1. Por lo tanto para este caso concreto son necesarias 5
comparaciones. Si se utilizase el algoritmo de Shell con un valor de salto = 2,
se realizan 3 comparaciones.
Algoritmo de ordenación
Quicksort
203
Apéndice J. Algoritmo de ordenación Quicksort 204
Al realizar las mismas acciones una vez más, las exploraciones de los 2
extremos vienen juntas sin encontrar ningún futuro valor que esté “fuera de
lugar”. En este punto se sabe que todos los valores a la derecha del “pivote”
son mayores que todos los situados a su izquierda. Por tanto se ha realizado
una partición de la lista original que ha quedado dividida en 2 sublistas más
pequeñas, representadas en la figura J.4.
Supongamos que la lista que se desea partir es A[1], A[2], ... , A[n]. Los
ı́ndices que representan los extremos izquierdo y derecho de la lista son L y R.
En el refinamiento del algoritmo se elige un valor arbitrario x suponiendo que
el valor central de la lista es tan bueno como cualquier elemento arbitrario,
y tan malo como cualquier otro. Los ı́ndices i, j exploran desde los extremos
el conjunto de elementos. Un posible refinamiento del anterior algoritmo que
incluye un mayor número de detalles es el siguiente:
Apéndice J. Algoritmo de ordenación Quicksort 208
Algoritmo de ordenación
Heap
209
Apéndice K. Algoritmo de ordenación Heap 210
1: Algoritmo Heap
2:
3: FiltradoDescendente (Dato *A, int i, int N )
4: {Queremos que se respete el orden M AX del montı́culo}
5: Dato tmp := A[ i ]
6: int hijo := 2 ∗ i;
7: Si (( hijo < N ) y ( A[ hijo + 1 ] > A[ hijo ] )) entonces
8: hijo := hijo + 1;
9: fin Si
10: Mientras (( hijo ≤ N ) y ( tmp < A[ hijo ])) hacer
11: Si (( hijo < N ) y ( A[ hijo + 1 ] > A[ hijo ])) entonces
12: hijo := hijo + 1;
13: fin Si
14: A[ i ] := A[ hijo ];
15: i := hijo;
16: hijo := 2 ∗ i;
17: fin Mientras
18: A[ i ] := tmp;
19: FinFiltradoDescendente
20:
21: Intercambiar (Dato *A, int i, int j)
22: Dato tmp := A[ i ];
23: A[ i ] := A[ j ];
24: A[ j ] := tmp;
25: FinIntercambiar
26:
27: Heap (Dato *A, int N )
28: int i;
29: {Se introducen los datos en el montı́culo}
n
30: Para (i := ; i ≥ 0; i := i − 1) hacer
2
31: F iltradoDescendente ( A, i, N );
32: fin Para
33: {Se sacan datos y se guardan al final para obtener el array ordenado}
34: Para (i := N − 1; i > 0; i := i − 1) hacer
35: Intercambiar ( A, 0, i);
36: F iltradoDescendente ( A, 0, i − 1);
37: fin Para
38: finAlgoritmo
Algoritmo 13: Pseudocódigo algoritmo Heap
Apéndice K. Algoritmo de ordenación Heap 212
Una vez colocado dicho elemento en el nodo raı́z se procede con la tarea
de mantenimiento que permite reorganizar nuevamente los elementos del árbol
para que este siga conservando la propiedad del montı́culo. Para ello al insertar
el elemento con valor 3, se comprueba que su primer hijo con valor 8 es mayor
que él, por lo que se procede a realizar el intercambio de ambos elementos
obteniendo como nodo raı́z el de valor 8. Se continua descendiendo por el
árbol y nuevamente el elemento con valor 3 es comparado con su primer hijo,
resultando de la comparación el elemento 3 como menor, por lo que ambos
nodos intercambian sus valores 3 y 7 respectivamente como se muestra en la
figura K.4.
En la siguiente comparación todos los hijos del nodo 3 son menores que
él. Finalizan los intercambios y el árbol vuelve a disfrutar de la propiedad del
montı́culo Max, lo que permite finalizar las tareas rutinarias de mantenimiento
Apéndice K. Algoritmo de ordenación Heap 214
(a) (b)
(c) (d)
(e) (f)
(a) (b)
(c) (d)
(e) (f)
(g) (h)
Algoritmo de ordenación
Merge
a) Una lista pequeña necesita menos pasos para ser ordenada que una lista
grande.
b) Son necesarios menos pasos para fusionar dos sublistas que ya estén en
orden que 2 sublistas que se encuentren completamente desordenadas.
Sólo es necesario entrelazar cada sublista una vez que ambas se encuen-
tran ordenadas.
217
Apéndice L. Algoritmo de ordenación Merge 218
Algoritmo de ordenación
utilizando árbol Binario
Todas las claves del subárbol izquierdo del nodo son menores que
la clave del nodo.
Todas las claves del subárbol derecho del nodo son mayores que la
clave del nodo.
Ambos subárboles (izquierdo y derecho) son árboles binarios de
búsqueda.
219
Apéndice M. Algoritmo de ordenación utilizando árbol Binario 220
1.- Se toma un elemento del conjunto a tratar. Si no existe nodo raı́z con
el que compararlo se crea el nodo, pasando a ocupar dicho elemento esa
posición y se toma el siguiente elemento.
3.- Se repite proceso de comparación del punto 2 hasta que este encuentre
el hueco en el árbol en que ha de ser insertado y se selecciona el siguiente
elemento.
Operaciones:
M.2. Implementación
La implementación que se propone está basada en memoria dinámica.
Cuando se trata de plasmar algoritmos que trabajan con árboles, resulta de
gran utilidad la posibilidad de “devolver” un árbol como resultado. Esto es
fácil de conseguir definiendo el tipo árbol binario como un puntero a una
estructura de datos que representa el nodo raı́z del árbol.
8: FinSegun
9: Si no
10: {Se alcanza una hoja, A es vacı́o, insertar aquı́}
11: A:= CrearABB(c, ABBVacio, ABBVacio);
12: fin Si
13: FinProcedimiento
Algoritmo 18: Insertar elemento en árbol binario de búsqueda
Algoritmo de Torneo
225
Apéndice N. Algoritmo de Torneo 226
[1] D.E. Knuth. The art of computer programming, vol. 3: Sorting and sear-
ching. Addison-Wesley, 1973.
[3] Peter Amey. Logic versus magic in critical systems. 6th Ada-Europe
International Conference, Leuven, Belgium, may 14-18, 2001, 2001.
[5] Alan Burns and Andy Wellings. Sistemas de tiempo real y lenguajes de
programación, 3rd Edición. Addison Wesley, 2003.
[7] Dina Bitton, David J. Dewitt, David K. Hsiao, and Jaishankar Menon.
A taxonomy of parallel sorting. ACM Computing Surveys (CSUR).
[10] Peter Amey. Closing the loop - the influence of code analysis on design.
7th Ada-Europe International Conference, Vienna, Austria, June 2002,
2002.
[11] Klaas Sikkel. Parsing schemata: A framework for Specification and Analy-
sis of Parsing Algorithms. Springer, 1997.
227
Bibliografı́a 228
[13] Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson International
Edition, 2006.
[14] Volker Strassen. Gaussian elimination is not optimal. Numer. Math, 13:
354–356, 1969.
[15] Huberto Comon, Max Dauchet, RMI Gilleron, Florent Jazquemard, Denis
Lugiez, Sophie Tison, and Marc Tomasi. Tree automata techniques and
applications. 2007. release October, 12th 2007.
[18] Luis Joyanes Aguilar, Luis Rodrı́guez Buena, and Matilde Fernández
Azuela. Fundamentos de programación. McGraw-Hill, 2008.
[19] Luis Joyanes Aguilar and Ignacio Zahonero. Estructura de datos, algorit-
mos, abstracción y objetos, 3ra Edición. McGraw-Hill, 1999.
[21] Christian Lenganer, Charles Consel, and Martin Odersky. Domain specific
program generation. International Seminar, Dagstuhl Castle, Germany,
March 23-28, 2003, Revised Papers, 2003.
[22] John Barnes. High integrity software. The Spark approach to safety and
security. Addison-Wesley, 2003.
[27] Alekseyev V.E. On certain algorithms for sorting with minimun memory.
1969.
[30] Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen.
Modern Compiler Design, 2nd Edition. Springer, 2012.
[32] M.H. Alsuaiyel. Design techniques and Analysis. World Scientific, 1999.
[33] Alfred V. Aho and Jeffrey D. Ullman. The Theory of Parsing, translation
and compiling. Prentice Hall, 1973.
[35] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman.
Compilers.- Principles, Techniques & Tools, 2nd Edition. Addison Wes-
ley, 2007.
[37] R.C.T. Lee, S.S. Tseng, R.C. Chang, and Y.T. Tsai. Introducción al
diseño y análisis de algoritmos. Un enfoque estratégico. McGraw-Hill,
2007.
[38] George Coulouris, Jean Dollimore, and Tim Kindberg. Sistemas distri-
buı́dos. Conceptos y diseño. Addison Wesley, 2007.
230
Bibliografı́a 231
Elementos Fundamentos, 37
Primero con rapidez, 161 Meta-algoritmo ascendente
Productor lento, 162 Derivaciones, 112
Entropı́a, 174 Fusión, 113
Esquemas Primera fase, 101
Acciones, 134 Representación, 101
Definición, 117 Segunda fase, 103
Idea, 118 Torneo, 114
Jerarquı́a, 134 Versión formal, 110
Esquemas de árboles, 127 Versión indeterminaciones, 111
Burbuja, 152 Versión informal, 109
Conclusiones, 132 Versión intuitiva, 100
Esquemas de cadena única, 133 Meta-algoritmo descendente
Esquemas de cadenas, 133 Binario, 95
Burbuja, 152 Burbuja, 151
Esquemas generales, 120 Corrección, 86
Burbuja, 125 Definiciones básicas, 73
Inicios, 72
Grafo, 51 Primera fase, 76
Ejemplo, 51 Quicksort, 89
Representación, 76
Inserción
Segunda fase, 79
Binaria, 169
Versión formal, 80
Cabeza, 181
Versión informal, 85
Central, 181
Versión intuitiva, 74
Binaria vs secuencial, 169
Cabeza, 174 Optimalidad
Cabeza vs central, 173 Merge, 179
Central, 176 Optimización
Elemento, 167 Binario, 96
Elemento en cadena, 167 Fusión, 115
Secuencial, 170 Meta-algoritmo ascendente, 111
Intercambiar, 190 Quicksort, 97
Torneo, 115
Matriz de incidencia, 54
Ordenación
Ejemplo, 60
Ángulos, 34
Propiedades, 63
Abstracción, 1
Meta-algoritmo
Análisis, 34
Ascendente, 99
Binario, 219
Consideraciones, 47
Convenciones, 39
Definición, 25
En bloque, 19
Descendente, 71
Estrategias, 47
Bibliografı́a 232
Externa, 9
Interna, 8
Introducción, 1
Invertir, 45
Mejoras, 35
Optimalidad, 43
Pregunta, 46
Repeticiones, 41
Serie y paralelo, 10
Ordenación paralelo, 10
Burbuja, 15
En serie, 14
Fusión, 17
Hardware, 22
Ordenación en bloque, 19
Software, 24
Para-algoritmo, 38
Procedimiento
Ascendente, 137
Descendente, 136
Representaciones, 49
Grafo, 51
Matriz de incidencia, 54
Strassen, 44
Tesis
Conclusiones, 163
Desarrollos futuros, 164
Tipos de datos
Definición, 30
Ventajas, 30
Transitividad, 65
Binario, 66
Burbuja, 66