Insertion sort (inserción)
El método de ordenamiento por inserción (Insertion Sort) es un algoritmo simple y eficiente para ordenar pequeñas listas.
Funcionamiento
El ordenamiento por inserción construye la lista ordenada de uno en uno, insertando cada nuevo elemento en su posición correcta dentro de la lista ya ordenada. Aquí tienes un paso a paso:
Inicialización: Comienza con el segundo elemento de la lista (el primer elemento se considera ya ordenado).
Comparación: Compara el elemento actual con los elementos anteriores en la lista ordenada.
Desplazamiento: Desplaza los elementos mayores hacia la derecha para hacer espacio para el nuevo elemento.
Inserción: Inserta el nuevo elemento en su posición correcta.
Repetición: Repite los pasos 2-4 para todos los elementos de la lista.
Ejemplo en lenguaje C
#include <stdio.h>
// Función para realizar el ordenamiento por inserción
void ordenamientoPorInsercion(int arr[], int n) {
int i, clave, j;
for (i = 1; i < n; i++) {
clave = arr[i];
j = i - 1;
// Mover los elementos del arreglo que son mayores que la clave
// a una posición adelante de su posición actual
while (j >= 0 && arr[j] > clave) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = clave;
}
}
// Función para imprimir un arreglo
void imprimirArreglo(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Arreglo original: \n");
imprimirArreglo(arr, n);
ordenamientoPorInsercion(arr, n);
printf("Arreglo ordenado: \n");
imprimirArreglo(arr, n);
return 0;
}
Pseudocódigo
para i = 1 hasta n-1
clave = lista[i]
j = i - 1
mientras j >= 0 y lista[j] > clave
lista[j + 1] = lista[j]
j = j - 1
lista[j + 1] = clave
Ejemplo
Imagina que tienes la lista [12, 11, 13, 5, 6]:
Comienza con el segundo elemento (11), compáralo con 12 y colócalo antes: [11, 12, 13, 5, 6]
Toma el siguiente elemento (13), ya está en su lugar: [11, 12, 13, 5, 6]
Toma 5, desplaza 13, 12, y 11 hacia la derecha y colócalo al inicio: [5, 11, 12, 13, 6]
Finalmente, toma 6, desplaza 13, 12, y colócalo después de 5: [5, 6, 11, 12, 13]
Ventajas y Desventajas
Ventajas:
- Fácil de implementar y entender.
- Eficiente para listas pequeñas o casi ordenadas.
- Ordena en tiempo lineal para listas que ya están casi ordenadas.
Desventajas:
- No es eficiente para listas grandes, con una complejidad de O(n2)
- en el peor de los casos.
- No es adecuado para listas muy grandes debido a su ineficiencia comparada con otros algoritmos como Quick Sort o Merge Sort.
Aplicaciones
El ordenamiento por inserción es útil en situaciones donde:
- La lista es pequeña.
- La lista está casi ordenada.
- Se requiere un algoritmo simple y fácil de implementar.