ordenamiento por insercion

MÉTODOS DE ORDENAMIENTO
Introducción.-
En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numéricoy el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.
Objetivos.-
Poder conocer un poco de lo que trata el ordenamiento por inserción.
Determinar lasventajas y desventajas que nos puede traer a la hora de programar.
Determinar en qué situaciones nos puede ser de gran utilidad este tipo de algoritmo.
Marco teórico.-
¿Qué es ordenamiento?
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
El ordenamiento se efectúa con base en el valor de algún campo en un registro.
Elpropósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
Ej. de ordenamientos:
Dir. Telefónico, bibliotecas y diccionarios, etc.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente odescendente.
¿Cuándo conviene usar un método de ordenamiento?
Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
Los internos:
Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo quese requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc).
Los externos:
Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc).
Método de ordenamiento porinserción.-
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elementok+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos loselementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.
Este algoritmo también es bastante sencillo. ¿Has jugado cartas? ¿Cómo las vas ordenando cuando las recibes? Generalmente se hace de esta manera: setoma la primera y se coloca en la mano. Luego se toma la segunda y la comparo con las que ya se tiene: si es mayor, la pongo a la derecha, y si es menor a la izquierda. Después se toma la tercera y la comparo con las que se tiene en la mano, desplazándola hasta que quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que se tenga todasen orden.
Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.
En...