Ordenamiento por Inserción
Última actualización
El ordenamiento por inserción construye el arreglo ordenado un elemento a la vez. Toma el siguiente elemento no ordenado (la "clave") y desplaza cada elemento mayor de la región ordenada un espacio a la derecha, luego coloca la clave en el hueco. Es exactamente como la mayoría de la gente ordena una mano de cartas. Pulsa reproducir arriba para ver cómo se inserta cada clave, o avanza los desplazamientos uno a uno.
El ordenamiento por inserción es muy rápido con entradas pequeñas o casi ordenadas - se ejecuta en O(n) cuando los datos ya están ordenados - por lo que muchos ordenamientos híbridos recurren a él para subarreglos pequeños.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Mejor caso | O(n) | Ya ordenado |
| Caso promedio | O(n²) | Orden aleatorio |
| Peor caso | O(n²) | Orden inverso |
| Espacio | O(1) | In situ |
| Estable | Sí | Los elementos iguales conservan su orden relativo |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Considera el primer elemento como una región ordenada de tamaño uno. |
| 2 | Toma el siguiente elemento como la clave. |
| 3 | Desplaza cada elemento ordenado mayor que la clave un espacio a la derecha. |
| 4 | Inserta la clave en el hueco abierto. |
| 5 | Repite hasta que se hayan insertado todos los elementos. |
Ejemplo resuelto
Ordenando [5, 2, 4, 1]:
| Pasada | Arreglo | Acción |
|---|---|---|
| Inicio | [5, 2, 4, 1] | 5 es la región ordenada inicial de tamaño uno. |
| 1 | [2, 5, 4, 1] | Clave 2: desplaza 5 a la derecha, inserta 2 al principio. |
| 2 | [2, 4, 5, 1] | Clave 4: desplaza 5 a la derecha, 2 es menor así que detén, inserta 4. |
| 3 | [1, 2, 4, 5] | Clave 1: desplaza 5, 4, 2 a la derecha, inserta 1 al principio. |
| Fin | [1, 2, 4, 5] | Todos los elementos insertados; el arreglo está ordenado. |
Cuándo usar el ordenamiento por inserción
| Úsalo cuando | Evítalo cuando |
|---|---|
El arreglo es pequeño (aproximadamente n < 20). | El arreglo es grande y está ordenado al azar. |
Los datos ya están casi ordenados, dando el mejor caso O(n). | Necesitas un peor caso garantizado de O(n log n). |
Necesitas un ordenamiento estable, in situ y con espacio extra O(1). | Mover elementos es costoso, ya que realiza muchos desplazamientos. |
| Los datos llegan de forma incremental y deben mantenerse ordenados en línea. | La entrada está en orden inverso, su peor caso O(n²). |
Código de Insertion Sort
Una implementación limpia y ejecutable de Insertion Sort en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Insertion Sort en Python
Python
1def insertion_sort(a):2 for i in range(1, len(a)):3 key = a[i]4 j = i - 15 # Shift larger elements one slot to the right6 while j >= 0 and a[j] > key:7 a[j + 1] = a[j]8 j -= 19 a[j + 1] = key10 return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)Código de Insertion Sort en JavaScript
JavaScript
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 const key = a[i];4 let j = i - 1;5 // Shift larger elements right to open a slot for key6 while (j >= 0 && a[j] > key) {7 a[j + 1] = a[j];8 j--;9 }10 a[j + 1] = key;11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));Código de Insertion Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void insertionSort(int[] arr) {5 for (int i = 1; i < arr.length; i++) {6 int key = arr[i];7 int j = i - 1;8 // Shift larger elements one slot to the right9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 arr[j + 1] = key;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {7, 3, 9, 1, 5, 8, 2};19 System.out.println("Before: " + Arrays.toString(arr));20 insertionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Código de Insertion Sort en C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10 for (size_t i = 1; i < a.size(); ++i) {11 int key = a[i];12 int j = static_cast<int>(i) - 1;13 // Shift larger elements one slot to the right14 while (j >= 0 && a[j] > key) {15 a[j + 1] = a[j];16 --j;17 }18 a[j + 1] = key;19 }20}21
22int main() {23 std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24 std::cout << "Before: ";25 printVec(data);26 insertionSort(data);27 std::cout << "After: ";28 printVec(data);29 return 0;30}Código de Insertion Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void insertionSort(int a[], int n) {9 for (int i = 1; i < n; i++) {10 int key = a[i];11 int j = i - 1;12 // Shift larger elements one slot to the right13 while (j >= 0 && a[j] > key) {14 a[j + 1] = a[j];15 j--;16 }17 a[j + 1] = key;18 }19}20
21int main(void) {22 int data[] = {7, 3, 9, 1, 5, 8, 2};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 insertionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Preguntas frecuentes sobre el ordenamiento por inserción
¿Cuál es la complejidad temporal del ordenamiento por inserción?
El ordenamiento por inserción es
O(n²) en promedio y en el peor caso, pero O(n) en un arreglo ya ordenado o casi ordenado. Usa espacio extra O(1).¿Es estable el ordenamiento por inserción?
Sí. El ordenamiento por inserción solo desplaza los elementos estrictamente mayores que la clave, por lo que los elementos iguales nunca se cruzan y se conserva su orden relativo.
¿Cuándo debería usar el ordenamiento por inserción?
Úsalo para arreglos pequeños o datos que ya están casi ordenados. Por su bajo costo y su mejor caso adaptativo, algoritmos híbridos como Timsort lo usan para tramos pequeños.
¿Cuál es la diferencia entre el ordenamiento por inserción y el ordenamiento de burbuja?
Ambos son ordenamientos por comparación
O(n²), pero el ordenamiento por inserción desplaza elementos para abrir un hueco para la clave, mientras que el de burbuja intercambia repetidamente pares adyacentes desordenados. El de inserción suele hacer menos escrituras y rinde mejor en la práctica, sobre todo con datos casi ordenados donde alcanza su mejor caso O(n).¿Por qué el ordenamiento por inserción es más rápido que merge sort en arreglos pequeños?
El ordenamiento por inserción tiene un costo constante muy bajo y no usa recursión ni memoria extra, así que en entradas pequeñas supera a los ordenamientos
O(n log n) pese a su peor complejidad asintótica. Por eso los ordenamientos híbridos como Timsort e introsort cambian al ordenamiento por inserción para subarreglos pequeños.¿El ordenamiento por inserción funciona mejor con una lista enlazada o un arreglo?
El ordenamiento por inserción normalmente se escribe para arreglos, donde desplazar elementos es el costo principal. En una lista enlazada evitas el desplazamiento insertando el nodo en su lugar, pero pierdes el acceso aleatorio rápido, así que encontrar el punto de inserción sigue costando tiempo lineal por elemento y el costo total sigue siendo
O(n²).Recursos relacionados
Más visualizaciones
