INTRODUCCIÓN

Un algoritmo que ordena es aquel que acomoda en orden los elementos de un conjunto. Muchas de las aplicaciones más conocidas del paradigma de diseño de algoritmos Divide y Vencerás son algoritmos de ordenamiento.
Hay varias razones para estudiar los algoritmos de ordenamiento. La primera es que tienen utilidad práctica porque el ordenamiento es una actividad frecuente. El trabajo con conjuntos grandes de datos en las computadoras se facilita si los datos están ordenados. La segunda es que se ha ideado una buena cantidad de algoritmos para ordenar y porque es posible enfocar un problema dado desde muchos puntos de vista distintos. La tercera es que el ordenamiento es uno de los pocos problemas para los que es fácil deducir cotas inferiores firmes del comportamiento en el peor caso y en el caso promedio. Las cotas son firmes en el sentido de que existen algoritmos que efectúan aproximadamente la cantidad mínima de trabajo especificada. Por ello, tenemos algoritmos de ordenamiento prácticamente óptimos.
Al describir la mayor parte de los algoritmos, supondremos que el conjunto a ordenar está almacenado en forma de arreglo, de modo que se pueda acceder en cualquier momento a un elemento en cualquier posición; esto se denomina acceso aleatorio. No obstante, algunos de los algoritmos también son útiles para ordenar archivos y listas ligadas. Si el acceso al conjunto es exclusivamente secuencial, empleamos el término sucesión para hacer hincapié en que la estructura podría ser una lista ligada o un archivo secuencial, no sólo un arreglo.

Ejercicios:

Encuentre el algoritmo del algoritmo de Ford-Johnson para ordenar, que aparece en muchos libros de texto sobre algoritmos. Se demostró que este algoritmo es óptimo para n <= 12. Implemente este algoritmo en una computadora y compárelo con cualquier otro algoritmo de ordenamiento. ¿Le agrada este algoritmo? En caso negativo, intente determinar qué falla en el análisis.

Demuestre que para encontrar el número más grande en una lista de n números, por lo menos se requieren n - 1 comparaciones.

Demuestre que para encontrar el segundo elemento más grande de una lista de n números por lo menos se requieren n — 2 + log n comparaciones.
Sugerencia: No es posible determinar el segundo elemento más grande sin haber encontrado el primero. Así, el análisis puede efectuarse como sigue:
1. Demuestre que para encontrar el elemento más grande se requieren por lo menos n - 1 comparaciones.
2. Demuestre que siempre hay alguna secuencia de comparaciones que obliga a encontrar al segundo elemento más grande en log n — 1 comparaciones adicionales.