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
Problemas de pr谩ctica:
