Recursivididad Ordenada

RECURSIVIDAD ORDENADA
La ordenación o clasificación de datos (sort en ingles) es un operación consiste en disponer un conjunto de datos en algún determinado orden con respecto a uno de los campos deelementos del conjunto. Por ejemplo, cada elementó del dato de una guía telefónica tiene un campo dirección y un campo numero de teléfono; la guía telefónica esta dispuesta en orden alfabética denombres; los elementos numéricos se pueden ordenar en orden creciente o decreciente de acuerdo al valor numérico del elemento.
En terminología de ordenación, el elemento por lo cual esta ordenado unconjunto de datos se denomina clave.
Una colección de datos puede ser almacenados en un archivo un array de registros un alista en lazadas o un árbol se denomina ordenación interna.

Análisis delordenamiento por fusión

El ordenamiento por fusión es un ejemplo clásico de las técnicas usadas para
analizar programas recursivos. Escribiremos una relación de recurrencia para el
calculo deltiempo de ejecución.
Asumimos n es potencia de 2 de modo que siempre dividimos la entrada en
dos mitades. Para n = 1 el tiempo es constante, luego lo denotaremos por 1.
En otro caso el tiempo deordenar n números es igual al tiempo de realizar dos
ordenamientos recursivos de tamaño n=2, mas el tiempo de fusión que es lineal.



RECURSIVIDAD BUSQUEDA
Considérese un arreglo de elementos enel cual los objetos sean colocados en cierto orden. Tomando de ejemplo, un directorio puede considerarse un arreglo cuyas entradas se encuentran en orden alfabético, pretendemos buscar un nombre eldirectorio, el proceso usado para encontrar esta entrada se llama búsqueda.

En la búsqueda secuencial o lineal, en la cual se examina cada elemento del arreglo uno a la vez y se compara con elelemento buscado hasta que ocurra una coincidencia. Si la lista no se encuentra en orden y se desarrollo nada mas al azar, la búsqueda lineal puede ser la única forma de encontrar algo ( a menos que la...