algorithm
Tipo de inserción
Buscar..
Observaciones
Cuando analizamos el rendimiento del algoritmo de clasificación, nos interesamos principalmente en el número de comparación e intercambio.
Media de intercambio
Sea E n el número promedio total de intercambio para ordenar la matriz del elemento N. E 1 = 0 (no necesitamos ningún intercambio para la matriz con un elemento). El número promedio de intercambio para ordenar la matriz de elementos N es la suma del número promedio de intercambio para ordenar la matriz de elementos N-1 con el intercambio promedio para insertar el último elemento en la matriz de elementos N-1.
Simplificar la suma (serie aritmética).
Expande el termino
Simplifica la suma de nuevo (series aritméticas)
Comparación de promedios
Sea C n el número promedio total de comparación para ordenar la matriz del elemento N. C 1 = 0 (no necesitamos ninguna comparación en una matriz de elementos). El número promedio de comparación para ordenar la matriz de elementos N es la suma del número promedio de comparación para ordenar la matriz de elementos N-1 con la comparación promedio para insertar el último elemento en la matriz de elementos N-1. Si el último elemento es el elemento más grande, solo necesitamos una comparación, si el último elemento es el segundo elemento más pequeño, necesitamos la comparación N-1. Sin embargo, si el último elemento es el elemento más pequeño, no necesitamos la comparación N. Todavía solo necesitamos la comparación N-1. Es por eso que eliminamos 1 / N en la siguiente ecuación.
Simplificar la suma (serie aritmética).
Ampliar el término
Simplifique nuevamente la suma (serie aritmética y número de armónicos)
Fundamentos del algoritmo
La ordenación por inserción es un algoritmo de clasificación en sitio, muy simple y estable. Se desempeña bien en secuencias pequeñas, pero es mucho menos eficiente en listas grandes. En cada paso, los algoritmos consideran el elemento i-th de la secuencia dada, moviéndolo hacia la izquierda hasta que esté en la posición correcta.
Ilustracion grafica
Pseudocódigo
for j = 1 to length(A)
n = A[j]
i = j - 1
while j > 0 and A[i] > n
A[i + 1] = A[i]
i = i - 1
A[i + 1] = n
Ejemplo
Considere la siguiente lista de enteros:
[5, 2, 4, 6, 1, 3]
El algoritmo realizará los siguientes pasos:
-
[5, 2, 4, 6, 1, 3] -
[2, 5, 4, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[1, 2, 4, 5, 6, 3] -
[1, 2, 3, 4, 5, 6]
Implementación de C #
public class InsertionSort
{
public static void SortInsertion(int[] input, int n)
{
for (int i = 0; i < n; i++)
{
int x = input[i];
int j = i - 1;
while (j >= 0 && input[j] > x)
{
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = x;
}
}
public static int[] Main(int[] input)
{
SortInsertion(input, input.Length);
return input;
}
}
Espacio auxiliar: O(1)
Complejidad del tiempo: O(n)
Implementación Haskell
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x = (n:x:xs)
| otherwise = x:insert n xs