Inserccion

Nombre: SAMUEL BUSTILLOS
Materia: 2-25 Fecha 19-052011
Método de Inserción
Explicación del Método
El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamentesencillo y se comporta razonablemente bien en gran cantidad de situaciones.
Completa la tripleta de los algoritmos de ordenación más básicos y de orden de complejidad cuadrático, junto conSelectionSort y BubbleSort.
Se basa en intentar construir una lista ordenada en el interior del array a ordenar.
De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza unacantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones.
 
Estealgoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro decomparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).
Es un algoritmo estable de ordenación interna y su complejidad temporal en el peor caso es de O(n2)y en el mejor caso -que el array ya esté totalmente ordenado- puede llegar a Ω(n) siendo n el tamaño del array a ordenar.
El algoritmo consiste en realizar varias pasadas sobre el array. En cadapasada se analiza un elemento, y se intenta encontrar su orden relativo entre los analizados en pasadas anteriores. Con esto se logra ir manteniendo una lista ordenada constantemente. Cada elemento aanalizar se desplaza por esa lista hasta encontrar su lugar. Cuando todos los elementos del array han sido analizados, la lista está completamente ordenada. Esa es una diferencia importante conBubbleSort y SelectionSort. En ellos, en cada pasada se colocaba una carta en su sitio definitivo. En InsertionSort, el array no está totalmente ordenado hasta que el algoritmo termina.
Por otro lado, en...