Tipo de inserción

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de noviembre de 2019; las comprobaciones requieren 20 ediciones .

Tipo de inserción
Ejemplo de clasificación por inserción
objetivo	Algoritmo de clasificación
Estructura de datos	formación
peor momento	O( n 2 ) comparaciones, intercambios
Mejor tiempo	O( n ) comparaciones, 0 intercambios
Tiempo promedio	O( n 2 ) comparaciones, intercambios
costo de memoria	O( n ) total, O( 1 ) auxiliar
Archivos multimedia en Wikimedia Commons

La ordenación por inserción es un algoritmo de ordenación en el que los elementos de la secuencia de entrada se examinan uno por uno, y cada nuevo elemento entrante se coloca en un lugar adecuado entre los elementos ordenados previamente [1] . Complejidad computacional - . $O(n^{2})$

Descripción

La entrada del algoritmo es una secuencia de números: . Los números que se ordenan también se denominan claves . La secuencia de entrada se representa en la práctica como una matriz con elementos. En la salida, el algoritmo debe devolver una permutación de la secuencia original , de modo que se cumpla la siguiente relación [2] . $norte$ $a_{1},a_{2},...,a_{n}$ $norte$ $a_{{1}}^{{'}},a_{{2}}^{{'}},...,a_{{n}}^{{'}}$ $a_{{1}}^{{'}}\leqslant a_{{2}}^{{'}}\leqslant ...\leqslant a_{{n}}^{{'}}$

Inicialmente, la secuencia ordenada está vacía. En cada paso del algoritmo, se selecciona uno de los elementos de datos de entrada y se coloca en la posición deseada en la secuencia ya ordenada hasta que se agota el conjunto de datos de entrada. En cualquier momento de la secuencia ordenada, los elementos cumplen los requisitos para la salida del algoritmo [3] .

Este algoritmo se puede acelerar utilizando la búsqueda binaria para encontrar la ubicación del elemento actual en la parte ordenada. El problema con un desplazamiento largo de la matriz hacia la derecha se resuelve cambiando los punteros [4] .

Pseudocódigo

La entrada al procedimiento de clasificación es una matriz que consta de los elementos de la secuencia que deben clasificarse. corresponde al tamaño de la matriz original. Ordenar no requiere memoria adicional, a excepción de un valor constante para un elemento, ya que la permutación se realiza dentro de la matriz. Como resultado de la operación del procedimiento, la secuencia de elementos de salida requerida aparece en la matriz de entrada [5] . $A[1..n]$ $A[1],A[2],...,A[n]$ $norte$ $A.\mathrm {longitud}$

Pseudocódigo del algoritmo:

para j = 2 a A. longitud do tecla = A[j] yo = j-1 while (int i >= 0 y A[i] > tecla) do A[yo + 1] = A[yo] yo = yo - 1 terminar mientras A[i+1] = tecla fin [5]

para i = 2 a n hacer x = A[i] j = yo mientras que (int j > 1 y A[j-1] > x) sí A[j] = A[j-1] j = j - 1 terminar mientras A[j] = x fin para [6]

A [0] = - para i = 2 an hacer

\infty

j = yo while (j > 0 y A[j] < A[j - 1]) intercambia ( A[j], A[j - 1]) j = j - 1 fin mientras fin para [7] [8]

En la última versión, el intercambio x = A[j]; A[j] = A[j-1]; A[j-1] = xestá representado por la operación de intercambio, por lo que es un poco más lento. El valor del A[0] ingresado es menor que cualquier valor de los otros elementos [8] .

Análisis de algoritmos

El tiempo de ejecución del algoritmo depende de los datos de entrada: cuanto mayor sea el conjunto a ordenar, más tiempo llevará ordenar. El orden inicial de la matriz también afecta el tiempo de ejecución. El tiempo de ejecución del algoritmo para diferentes entradas del mismo tamaño depende de las operaciones elementales, o pasos, que deben realizarse [9] .

Para cada instrucción del algoritmo, introducimos el costo de tiempo y el número de repeticiones, donde está el número de comprobaciones de condición en el ciclo interno while [ 10] : $t_{j}$

El código	Precio	repeticiones
para j = 2 a A.longitud	$c_{1}$	$norte$
tecla = A[j]	$c_{2}$	$n-1$
yo = j - 1	$c_{3}$	$n-1$
mientras i > 0 y A[i] > tecla	$c_{4}$	$\sum _{{j=2}}^{n}t_{j}$
A[i+1] = A[i]	$c_{5}$	$\sum_{{j=2}}^{n}(t_{j}-1)$
yo = yo - 1	$c_{6}$	$\sum_{{j=2}}^{n}(t_{j}-1)$
A[i+1] = tecla	$c_{7}$	$n-1$

El tiempo de ejecución del algoritmo de clasificación por inserción es la suma de los tiempos de ejecución de cada paso [11] : . $T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\sum_{{j=2}}^{n}t_ {j}+c_{5}\sum_{{j=2}}^{n}(t_{j}-1)+c_{6}\sum_{{j=2}}^{n}( t_{j}-1)+c_{7}(n-1)$

El caso más favorable es una matriz ordenada. Además, todos los bucles internos constan de una sola iteración, es decir, para todos . Entonces el tiempo de ejecución del algoritmo será . El tiempo de ejecución depende linealmente del tamaño de los datos de entrada [12] . $t_{j}=1$ $j$ $T(n)=(c_{1}+c_{2}+c_{3}+c_{4}+c_{7})n-(c_{2}+c_{3}+c_{4 }+c_{7})=O(n)$

Análisis del peor de los casos

El peor de los casos es una matriz ordenada en orden inverso. En este caso, cada nuevo elemento se compara con todos los de la secuencia ordenada. Esto significa que todos los bucles internos constan de j iteraciones, es decir, para todos . Entonces el tiempo de ejecución del algoritmo será: $t_{j}=j$ $j$

$T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\sum_{{j=2}}^{n}j +c_{5}\sum_{{j=2}}^{n}(j-1)+c_{6}\sum_{{j=2}}^{n}(j-1)+c_ {7}(n-1)$

$T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\left({\frac {n(n+1) ) )}{2}}-1\right)+c_{5}{\frac {n(n-1)}{2}}+c_{6}{\frac {n(n-1)}{2 } }+c_{7}(n-1)=O(n^{2})$ .

El tiempo de ejecución es una función cuadrática del tamaño de los datos de entrada [13] .

Análisis de casos promedio

Para analizar el caso promedio, debe calcular el número promedio de comparaciones necesarias para determinar la posición del siguiente elemento. Al agregar un nuevo elemento, se requiere al menos una comparación, incluso si el elemento está en la posición correcta. El enésimo elemento a añadir puede ocupar una de las posiciones. Suponiendo entradas aleatorias, es igualmente probable que el nuevo elemento termine en cualquier posición [14] . Número promedio de comparaciones para insertar el elemento -ésimo [15] : $i$ $yo+1$ $i$

$T_{i}={\frac {1}{i+1}}\left(\sum _{p=1}^{i}p+i\right)={\frac {1}{i +1}}\left({\frac {i(i+1)}{2}}+i\right)={\frac {i}{2}}+1-{\frac {1}{i+ uno }}$

Para estimar el tiempo de ejecución promedio para n elementos, debe sumar [16] :

$T(n)=\sum_{i=1}^{n-1}T_{i}=\sum_{i=1}^{n-1}\left({\frac {i} {2}}+1-{\frac {1}{i+1}}\right)=\sum _{i=1}^{n-1}{\frac {i}{2}}+\sum _{i=1}^{n-1}1-\sum_i=1}^{n-1}\left({\frac {1}{i+1}}\right)$

$T(n)\approx {\frac {n^{2}-n}{4}}+(n-1)-(\ln(n)-1)=O(n^{2})$

La complejidad temporal del algoritmo es . Sin embargo, debido a factores constantes y términos de orden inferior, un algoritmo de orden de crecimiento superior puede ejecutarse más rápido con entradas pequeñas que un algoritmo de orden de crecimiento inferior [17] . $O(n^{2})$

Véase también

Notas

↑ Knut D. E. 5.2 Clasificación interna // El arte de la programación. Volumen 3. Clasificación y búsqueda = El arte de la programación informática. Tomo 3. Ordenar y buscar / ed. V. T. Tertyshny (cap. 5) e I. V. Krasikov (cap. 6). - 2ª ed. - Moscú: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
↑ Kormen, 2013 , pág. 38.
↑ Kormen, 2013 , pág. 39.
↑ Knut D. E. 5.2.1 Clasificación por inserciones // El arte de la programación. Volumen 3. Clasificación y búsqueda = El arte de la programación informática. Tomo 3. Ordenar y buscar / ed. V. T. Tertyshny (cap. 5) e I. V. Krasikov (cap. 6). - 2ª ed. - Moscú: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
↑ 1 2 Cormen, 2013 , pág. 39-40.
↑ N. With. Algoritmos y estructuras de datos. - M. : DMK Press, 2010. - S. 74. - 272 p. - ISBN 987-5-94074-584-6.
↑ Skiena S. Algoritmos. Guía de desarrollo. - 2do. - San Petersburgo. : BHV-Petersburg, 2014. - S. 137. - 720 p. - ISBN 978-5-9775-0560-4 .
↑ 12 Aho, 2000 , pág. 237.
↑ Kormen, 2013 , pág. 47.
↑ Kormen, 2013 , pág. 48.
↑ Kormen, 2013 , pág. 48-49.
↑ Kormen, 2013 , pág. 49.
↑ Kormen, 2013 , pág. 49-50.
↑ McConnell, 2004 , pág. 74.
↑ McConnell, 2004 , pág. 75.
↑ McConnell, 2004 , pág. 75-76.
↑ Kormen, 2013 , pág. 51.

Literatura

Aho A. V., Hopcroft D. E., Ulman D. D. Estructuras de datos y algoritmos = Estructuras de datos y algoritmos / Ed. A. A. Minko. - M. : Williams, 2000. - S. 231. - ISBN 5-8459-0122-7 .
Knut D. E. 5.2.1 Clasificación por inserciones // El arte de la programación. Volumen 3. Clasificación y búsqueda = El arte de la programación informática. Tomo 3. Ordenar y buscar / ed. V. T. Tertyshny (cap. 5) e I. V. Krasikov (cap. 6). - 2ª ed. - Moscú: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 2.1. Clasificación por inserción // Algoritmos: construcción y análisis = Introducción a los Algoritmos / Ed. I. V. Krasikova. - 3ra ed. - M. : Williams, 2013. - S. 38-45. — ISBN 5-8459-1794-8 .
McConnell J. Fundamentos de algoritmos modernos = Análisis de algoritmos: un enfoque de aprendizaje activo / Ed. S. K. Lando. - M. : Technosfera, 2004. - S. 72-76. — ISBN 5-94836-005-9 .

Enlaces

Algoritmos de clasificación
Teoría	Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio	burbuja Emocionante enanos Rápido Peine Clasificación par-impar bit a bit
Elección	Elección Piramidal Suave
inserciones	inserciones cáscara árbol
fusión	fusión
sin comparaciones	Contando bloquear
híbrido	introsorteo Timsort
Otro	topológico redes bitón
poco práctico	Bogosort Tipo de títere tortita lento