Conociendo el ordenamiento por inserción (Insertion Sort)

Insertion Sort

El Insertion Sort o Ordenamiento por Inserción es un algoritmo sencillo de ordenamiento, no muy eficiente comparado con otros mucho más rápidos como Heap Sort, Quick Sort o Merge Sort, pero muy simple de comprender e implementar, por lo que puede ser muy útil en ciertos escenarios.

Algoritmo

El algoritmo recibe un arreglo o lista de objetos comparables y retorna el mismo ordenado, para esto realiza un ciclo comenzando desde la segunda posición y terminando en N (última posición), entonces toma cada elemento del arreglo[i] y lo inserta en su lugar correspondiente de la secuencia previamente ordenada arreglo[1...i-1]. Y de esta manera elemento a elemento vamos ordenando el arreglo.

Ejemplo:

Marcado en negrita está la lista ordenada en cada momento y el elemento a insertar el primero que no lo esté.

3, 1, 15, 4, 2

1, 3, 15, 4, 2

1, 3, 4, 15, 2

1, 2, 3, 4, 15

Complejidad temporal

La complejidad temporal del algoritmo descrito es O(N^2) en el peor de los casos (cuando el arreglo está ordenado en orden inverso), pero puede tener un mejor comportamiento ( O(NK) ) en arreglos parcialmente ordenados, donde cada elemento esté a lo sumo K posiciones de su lugar correspondiente.

Estabilidad

Se dice que un algoritmo de ordenamiento es estable cuando elementos iguales mantienen el orden relativo que llevaban en el preorden. El Insertion Sort lo mantiene por tanto es estable.

Código en C++

vector <int> InsertionSort( vector <int> arreglo ) {
    // Comenzamos desde el segundo elemento ( índice 1 )    
    for( int i = 1 ; i < arreglo.size() ; i++ )
    {
        // Obtenemos el elemento pivote que vamos a insertar
        int elemento = arreglo[i];
        int j = i;
        // Verificamos si aún no estamos en la posición que le corresponde al elemento
        for( ; j >= 1 && arreglo[j-1] > elemento ; j-- )
            // Hacemos un corrimiento del elemento en j-1 a j ya que este es mayor que el pivote
            arreglo[j] = arreglo[j-1];
        // Colocamos al pivote en su posición correspondiente
        arreglo[j] = elemento;
    }
    return arreglo;
}