Resumen de Ordenamiento por inserción (insertion sort)
Ordenamiento por Inserción (Insertion Sort): Guía Completa
Entendiendo el Ordenamiento por Inserción
El ordenamiento por inserción es un algoritmo de ordenamiento simple y eficiente, especialmente útil para un número reducido de elementos o listas que ya están casi ordenadas. Su funcionamiento es bastante intuitivo y se asemeja a cómo una persona ordena un mazo de cartas de juego en su mano. La idea principal es construir una lista ordenada "una carta a la vez".
Imagina que tienes dos manos: en una tienes las cartas desordenadas y en la otra, un espacio para las cartas ordenadas. Tomas una carta de la pila desordenada y la insertas en la posición correcta entre las cartas que ya tienes ordenadas. Este proceso se repite hasta que todas las cartas han sido insertadas en su lugar adecuado, resultando en un mazo completamente ordenado.
Un algoritmo de ordenamiento es un conjunto de instrucciones que toma una lista de elementos como entrada y produce una salida que es una versión ordenada de esa lista.
Principio de Funcionamiento
El algoritmo de ordenamiento por inserción divide lógicamente la lista de elementos en dos partes:
- Sublista ordenada: Contiene los elementos que ya han sido colocados en su posición correcta.
- Sublista desordenada: Contiene los elementos que aún no han sido procesados.
Inicialmente, la sublista ordenada contiene solo el primer elemento de la lista original. Esto se debe a que un solo elemento se considera siempre ordenado. El resto de los elementos forman la sublista desordenada. El algoritmo procede de forma iterativa, tomando un elemento de la sublista desordenada (al que llamaremos la "clave") y lo "inserta" en su posición correcta dentro de la sublista ordenada.
Para encontrar la posición correcta de la clave, esta se compara con los elementos de la sublista ordenada, moviéndose de derecha a izquierda. Si un elemento en la sublista ordenada es mayor que la clave, se desplaza una posición a la derecha para hacer espacio. Este desplazamiento continúa hasta que se encuentra un elemento que es menor o igual que la clave, o hasta que se llega al principio de la sublista ordenada. Una vez que se ha hecho el espacio, la clave se inserta en esa posición.
El proceso se puede describir en los siguientes pasos:
- Considera el primer elemento de la lista como ya ordenado. La sublista ordenada es inicialmente de tamaño $1$.
- Para cada elemento restante en la lista (desde el segundo elemento hasta el último, es decir, para $i$ desde $1$ hasta $n-1$ donde $n$ es la longitud de la lista): a. Toma el elemento actual como la clave. Por ejemplo, $clave = lista[i]$. b. Inicializa un índice $j = i - 1$ para recorrer la sublista ordenada de derecha a izquierda. c. Mientras $j \geq 0$ y $lista[j] > clave$: (Este bucle busca la posición correcta y desplaza elementos) * Desplaza el elemento $lista[j]$ una posición a la derecha: $lista[j+1] = lista[j]$. * Decrementa $j$: $j = j - 1$. d. Inserta la clave en la posición vacía que se ha creado: $lista[j+1] = clave$.
- Repite el paso 2 hasta que todos los elementos de la lista desordenada hayan sido insertados en la sublista ordenada.
[5a, 2, 5b] y 5a aparece antes que 5b, en la lista ordenada 5a seguirá apareciendo antes que 5b.Ejemplo Detallado
Vamos a ordenar la siguiente lista de números enteros en orden ascendente: $[5, 2, 4, 6, 1, 3]$.
Paso 0: Inicialización
- Lista original: $[5, 2, 4, 6, 1, 3]$
- Sublista ordenada: $[5]$
- Sublista desordenada: $[2, 4, 6, 1, 3]$
Paso 1: Insertar el segundo elemento ($2$)
- Clave: $2$
- Comparamos $2$ con $5$. Como $2 < 5$, desplazamos $5$ a la derecha.
- Lista temporal: $[_, 5, 4, 6, 1, 3]$ (el guion bajo indica la posición vacía)
- Inse
Regístrate para el resumen completo¿Ya tienes cuenta? Iniciar sesión
Ordenamiento por Inserción
Klíčová slova: Ordenamiento por Inserción, Algoritmo de Ordenamiento por Inserción
Klíčové pojmy: El ordenamiento por inserción construye una lista ordenada un elemento a la vez, similar a ordenar cartas., Divide la lista en una sublista ordenada y otra desordenada., Cada elemento de la sublista desordenada (clave) se inserta en su posición correcta en la sublista ordenada., Los elementos mayores que la clave en la sublista ordenada se desplazan a la derecha para hacer espacio., La complejidad temporal es $O(n)$ en el mejor caso (lista ya ordenada) y $O(n^2)$ en el peor caso (lista inversamente ordenada)., La complejidad espacial es $O(1)$, lo que lo convierte en un algoritmo 'in-place'., Es ineficiente para grandes volúmenes de datos desordenados debido a su complejidad cuadrática., Es útil para ordenar listas pequeñas o casi ordenadas y como parte de algoritmos de ordenamiento híbridos., No confunda el 'desplazamiento' de elementos con el 'intercambio' en este algoritmo., Es un algoritmo de ordenamiento estable, preservando el orden relativo de elementos iguales.