metodos de ordenamiento

El método de ordenación por inserción directa consiste en recorrer todo el array comenzando desde el segundo elemento hasta el final. Para cada elemento, se trata de colocarlo en el lugar correcto entre todos los elementos anteriores a él o sea entre los elementos a su izquierda en el array.

Dada una posición actual p, el algoritmo se basa en que los elementos A[0], A[1], ..., A[p-1] ya están ordenados.

public static void insercionDirecta(int A[]){

    int p, j;

    int aux;

    for (p = 1; p < A.length; p++){ // desde el segundo elemento hasta

              aux = A[p]; // el final, guardamos el elemento y

              j = p - 1; // empezamos a comprobar con el anterior

              while ((j >= 0) && (aux < A[j])){ // mientras queden posiciones y el

                                                                    // valor de aux sea menor que los

                             A[j + 1] = A[j];       // de la izquierda, se desplaza a

                             j--;                   // la derecha

              }

              A[j + 1] = aux; // colocamos aux en su sitio

    }

} asi seria un ejemplo 

El método de inserción directa es el que generalmente utilizan los jugadores de cartas cuando ordenan éstas, de ahí que también se conozca con el nombre de método de la baraja.

La idea central de este algoritmo consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento. 
Ejemplo:
Se desean ordenarse las siguientes clave del arreglo A: 15, 67, 08, 16, 44, 27, 12, 35
Primera pasadaA[2] < A[1] 67 < 15 No hay intercambio
A: 15, 67, 08, 16, 44, 27, 12, 35
Segunda pasadaA[3] < A[2] 08 < 67 Si hay intercambio
A[2] < A[1] 08 < 15 Si hay
A: 15, 08, 67, 16, 44, 27, 12, 35
Tercera pasada
A[4] < A[3] 08 < 15 Si hay intercambio
A[3] < A[2] 08 < 15 Si hay intercambio
A= 08, 15, 67, 16, 44, 27, 12, 35
Hasta la septima pasada el arreglo queda ordenado: 08, 12, 15, 16, 27, 35, 44, 67

ANÁLISIS DE EFICIENCIA DEL MÉTODO DE INSERCIÓN DIRECTA 

El número máximo de comparaciones y movimientos se produce cuando los elementos del arreglo están en orden inverso Cmax = 1+2+3+............+(n-1) = n*(n-1)/2 Cmax= (n2-n)/2 
El número de comparaciones promedio que es cuando los elementos aparecen en el arreglo en forma aleatoria, puede ser calculado mediante la suma de las comparaciones mínimas y máximas divididas entre 2.

Cmed = [(n-1) + (n2-n)/2]/2

Al hacer la operación, nos queda:
Cmed = (n2+n-2)/4
 R
especto al número de movimientos Knuth obtiene los siguiente:
Mmin = 0 Mmed = (n2-n)/4 Mmax = (n2-n)/2 

El tiempo necesario para ejecutar el algoritmo es proporcionar a n2, O(n2). A pesar de ser un método ineficiente y recomendable solo cuando n es pequeña, el método de inserción directa se comporta mejor que el método de intercambio directo analizado anteriormente.

BIBLIOGRAFIA: http://www.angelfire.com/wy2/est_info/insercion.html
NOTA: se encuentra un ejercicio en este link


Mas informacion