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**, **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 - [Conociendo el ordenamiento por mezcla (Merge Sort)](https://binary-coffee.dev/post/conociendo-el-ordenamiento-por-mezcla-merge-sort) ## Problemas de práctica: [**Lista de Orden Creciente (muy fácil)**](http://coj.uci.cu/24h/problem.xhtml?pid=1495) [**Sorting Cards (fácil)**](http://coj.uci.cu/24h/problem.xhtml?pid=1507)