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