7 — Ordenamiento, Búsqueda e Intercalación Fernando Guspí Un gran descubrimiento resuelve un gran problema, pero en la solución de todo problema, hay cierto descubrimiento. George Polya 7.0.1 Introducción Presentar una lista o conjunto de elementos en un orden determinado, por ejemplo, alfabético o numérico, ascendente o descendente, es un problema que aparece con gran frecuencia en las aplicaciones de la Informática, así como la necesidad de buscar los elementos de un conjunto que cumplan determinada condición, donde el conjunto puede haber sido previamente ordenado o no. También es corriente tener que generar nuevos conjuntos a partir de otros ya ordenados, es así que los programas utilitarios generalmente contienen procedimientos para realizar estas tareas.En este capítulo estudiaremos los algoritmos que permiten resolver estos problemas y analizaremos su eficiencia, pues no en todos los casos los algoritmos llegan a los resultados esperados con igual facilidad o velocidad. 7.1 Ordenamiento En la vida cotidiana, muchas veces nos disponemos a colocar objetos de una manera es- pecial, siguiendo algún criterio, es decir, los ordenamos. Apilamos un conjunto de platos por tamaño, acomodamos varias carpetas por colores, clasificamos un conjunto de palabras por orden alfabético, acomodamos un mazo de cartas por palos o por números. En síntesis, clasificamos un conjunto finito de acuerdo con un criterio prefijado.Generalmente no nos detenemos a pensar cómo hacemos esto. Intuitivamente podemos decir que en una primera aproximación se deter- mina cuál es el objeto que, de acuerdo con el criterio de ordenamiento fijado, debe ocupar la primera posición, y lo descartamos del conjunto. Luego se procede de igual forma, descartando los objetos ya ordenados.Un análisis más fino mostrará que el criterio de ordenar posición por posición requiere muchas comparaciones y desplazamientos de objetos, y en definitiva los algoritmos obtenidos no son muy eficientes para casos generales con grandes cantidades de datos. Entonces, también vamos a desarrollar otro algoritmo más eficiente, donde el ordenamiento se basa en dividir cada vez el conjunto en dos subconjuntos y ordenarlos por separado.De esta manera, se pueden elaborar diferentes algoritmos de ordenamiento, algunos de los cuales presentaremos a continuación.A los efectos de describir los algoritmos trabajaremos sobre el problema de ordenar una estructura de datos sencilla: el arreglo unidimensional, a partir del