Ordenamiento por Inserción directa

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.
De forma gráfica el proceso que sigue el método de inserción directa es el siguiente:
 El método de Ordenamiento por inserción directa en Java es el siguiente:
 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
    }
}
En el peor de los casos, el tiempo de ejecución en O(n2).
En el mejor caso (cuando el array ya estaba ordenado), el tiempo de ejecución de este método de ordenamiento es O(n).
El caso medio dependerá de cómo están inicialmente distribuidos los elementos. Cuanto más ordenada esté inicialmente más se acerca a O(n) y cuanto más desordenada, más se acerca a O(n2).
El peor caso el método de inserción directa es igual que en los métodos de burbuja y selección, pero el mejor caso podemos tener ahorros en tiempo de ejecución.


11 comentarios:

  1. gracias me ayudaste :D pero tengo una pequeña duda ¿como podría hacer para que me imprima de mayor a menor ? u.u

    ResponderEliminar
    Respuestas
    1. Para que ordene de mayor a menor tan solo hay que cambiar el operador < por > en:
      aux < A[j].

      Eliminar
  2. mepuedes enviar un ejercicio de este metodo

    ResponderEliminar
  3. Y para hacer ese método pero con matrices ay como lo puedo hacer

    ResponderEliminar
  4. necesito el mismo método para matrices pero no se como hacerlo

    ResponderEliminar
  5. tengo una colsulta, como seria el tema si yo tengo los datos del vector en otra clase(digamosle principal) y quiero pasarlo a otra clase (ordenamiento) como haria, creo el metodo y le pongo de parametros el array o como seria el caso?

    ResponderEliminar
  6. amigo tu algoritmo no coge el primer item del arreglo

    ResponderEliminar
    Respuestas
    1. El primer item del arreglo se compara en la primera iteración, este método de ordenamiento consiste en comenzar tomando el segundo valor del array y compararlo con el que le precede, de cualquier modo no está bien escrito el código de todos modos.

      Eliminar
    2. César, el primer elemento si lo separas del resto se considera que ya está ordenado por eso ya no lo tomas en el ciclo y empiezas con el mecanismo de inserción a partir del segundo elemento del arreglo. En cada iteración tomas el siguiente elemento de la parte desordenada del arreglo y lo insertas en el primer bloque del arreglo que es la parte ordenada del arreglo.

      Eliminar
  7. Creo que si inicializas P = 0 contarías el primer elemento del arreglo, suerte.

    ResponderEliminar