Método de Inserción
¿Qué es?
La ordenación por inserción es un algoritmo de ordenación simple que funciona insertando iterativamente cada elemento de una lista desordenada en su posición correcta dentro de la sección ordenada de la lista. Es como ordenar naipes. Se dividen las cartas en dos grupos: las ordenadas y las desordenadas. Luego, se elige una carta del grupo desordenado y se coloca en el lugar correcto dentro del grupo ordenado.
- Comenzamos con el segundo elemento de la matriz, ya que se supone que el primer elemento está ordenado.
- Compare el segundo elemento con el primer elemento; si el segundo elemento es más pequeño, intercámbielos.
- Pase al tercer elemento, compárelo con los dos primeros elementos y colóquelo en su posición correcta.
- Repita hasta que toda la matriz esté ordenada.
Análisis de complejidad de la ordenación por inserción
Complejidad temporal
- Mejor caso: O(n) , si la lista ya está ordenada, donde n es el número de elementos de la lista.
- Caso promedio: O(n 2 ) , Si la lista está ordenada aleatoriamente.
- Peor caso: O(n 2 ) , si la lista está en orden inverso.
Complejidad espacial
- Espacio auxiliar: O(1), la ordenación por inserción requiere O(1) espacio adicional, lo que lo convierte en un algoritmo de ordenación que aprovecha el espacio eficientemente.
Ventajas y desventajas de la ordenación por inserción
Ventajas
- Simple y fácil de implementar.
- Algoritmo de clasificación estable .
- Eficiente para listas pequeñas y listas casi ordenadas.
- Ahorra espacio ya que es un algoritmo local.
- Adoptivo. El número de inversiones es directamente proporcional al número de intercambios. Por ejemplo, no se produce intercambio en una matriz ordenada y solo toma O(n) tiempo.
Desventajas
- Ineficiente para listas grandes.
- No es tan eficiente como otros algoritmos de clasificación (por ejemplo, clasificación por combinación, clasificación rápida) en la mayoría de los casos.
Aplicaciones de la ordenación por inserción
La ordenación por inserción se utiliza comúnmente en situaciones donde:
- La lista es pequeña o casi ordenada.
- La simplicidad y la estabilidad son importantes.
- Se utiliza como una subrutina en Bucket Sort
- Puede ser útil cuando la matriz ya está casi ordenada (muy pocas inversiones )
- Dado que el ordenamiento por inserción es adecuado para matrices pequeñas, se utiliza en algoritmos de ordenamiento híbrido junto con otros algoritmos eficientes como el ordenamiento rápido y el ordenamiento por combinación. Cuando el tamaño del subarreglo se reduce, se utiliza el ordenamiento por inserción en estos algoritmos recursivos. Por ejemplo, IntroSort y TimSort utilizan el ordenamiento por inserción.
Ejemplos en Lenguaje C:
Ejemplo 1:
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1; // Mover los elementos mayores que 'key' a la derecha // hasta encontrar la posición correcta para 'key'
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; j = j - 1; }
arr[j + 1] = key;
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6};
std::cout << "Arreglo original: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
insertionSort(arr);
std::cout << "Arreglo ordenado: ";
for (int num : arr) {
std::cout << num << " "; }
std::cout << std::endl;
return 0;
}