Binary Coffee

Conociendo el ordenamiento por inserci贸n (Insertion Sort)

algorithms icpc

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, 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;
}

Art铆culos relacionados

Problemas de pr谩ctica:

Opiniones
noavatar
Implementaci贸n en Python: https://gist.github.com/frarteaga/d1e94c782028b86f0999916f80f1d677