© BEST-BACKGROUNDS/Shutterstock.com
Cuando se trata de clasificar una matriz de datos, existen muchos algoritmos de clasificación que puede utilizar. Uno de los algoritmos más fáciles de usar es el ordenamiento por inserción, debido a su relativa simplicidad y naturaleza intuitiva. Continúe leyendo para explorar exactamente qué es la ordenación por inserción, cómo se implementa y para qué se puede usar, con un ejemplo.
¿Qué es la ordenación por inserción?
La ordenación por inserción es una ordenación algoritmo, uno de los métodos que puede utilizar para ordenar una matriz. La forma en que funciona no es demasiado complicada de entender y se puede comparar en gran medida con la forma en que clasificaría una baraja de cartas.
En En este caso, comenzaríamos asumiendo que la primera carta del mazo ya está clasificada. Luego, seleccionamos una tarjeta sin clasificar y la ordenamos. Esto se hace comparándola con la primera carta. Si la carta seleccionada es mayor que la carta clasificada, se coloca en una posición a la derecha de la primera carta. Si la carta en cuestión es menor que la carta clasificada, se coloca en una posición a la izquierda.
Este proceso continúa hasta que todas las cartas sin ordenar se colocan en sus posiciones correctas. La ordenación por inserción funciona de manera muy similar. Cada valor de datos sin ordenar se ordena a través del mismo tipo de proceso iterativo.
Dado que la ordenación por inserción es un algoritmo bastante simple, se usa mejor para conjuntos de datos relativamente pequeños, así como para aquellos que ya están algo ordenados. De esta manera, se le conoce como un algoritmo adaptativo y eficiente. A continuación, repasaremos la teoría detrás de cómo funciona la ordenación por inserción.
El algoritmo detrás de la ordenación por inserción
El método de ordenación por inserción se puede representar de manera concisa con el siguiente pseudocódigo:
inserciónSort(matriz) marca el primer elemento como ordenado para cada elemento no ordenado X’extrae’el elemento X para j-lastSortedIndex hasta 0 si el elemento actual j > X mueve el elemento ordenado a la derecha 1 bucle de interrupción e inserta X aquí al final insertSort
En términos simples, esto significa que se supone que el primer elemento está ordenado. Cada elemento subsiguiente se compara con el primer elemento. Si es más pequeño que el elemento ordenado, se mueve hacia abajo a la primera posición o a la posición 0. Si es mayor, se desplaza una posición a la derecha. Las iteraciones continúan hasta que se han ordenado todos los elementos.
El funcionamiento interno de la ordenación por inserción
Ahora que hemos cubierto cómo funciona la ordenación por inserción y la teoría detrás de ella, es hora de ilustrar el proceso. con una matriz adecuada. Si consideramos el siguiente conjunto de datos:
Podemos suponer que el primer elemento, 10, ya está ordenado. Después de esto, tomamos el segundo elemento, 14, y lo almacenamos por separado. Comparando 14 con 10, podemos ver que es mayor, por lo que conserva su posición como segundo elemento. Esta es la primera iteración, conocida como el primer paso. El primer elemento, 10, se almacena en un subarreglo.
Donde verde=matriz ordenada
Para el segundo paso, pasamos al tercer elemento, que es 5. Este es en comparación con los elementos anteriores. Podemos decir que es más pequeño que el elemento anterior, 14, por lo que cambia de lugar con 14.
El algoritmo luego lo compara con los elementos en el subarreglo ordenado. 5 también es más pequeño que 10, por lo que se mueve al principio del subarreglo. La matriz ordenada ahora tiene 2 elementos: 5 y 10.
Ahora, pasamos al tercer paso. En este caso, 7 es el elemento seleccionado. Esto es más pequeño que 14, por lo que se mueve una posición hacia la izquierda y hacia la matriz ordenada. Sin embargo, esta no es la posición correcta, ya que 7 es menor que 10 pero mayor que 5. Por lo tanto, se movió otra posición a la izquierda.
Para el cuarto paso, estamos viendo el cuarto elemento, que es 14. Esto ya está ordenado, por lo que ahora la matriz ordenada incluye 5, 7, 10 y 14.
El resultado final
Por último, para el quinto paso, tomamos el quinto elemento, que es 1. Esto es claramente más pequeño que 14, por lo que se intercambia la posición. También es más pequeño que 10, por lo que la posición se intercambia nuevamente. Esto continúa dos veces más, ya que 1 es el elemento más pequeño de la matriz. Por lo tanto, terminamos con una matriz ordenada de la siguiente manera:
La implementación de la ordenación por inserción
La ordenación por inserción se puede implementar con una variedad de lenguajes de programación, desde C, C# y C++ a Java, Python, PHP y Javascript. Para fines ilustrativos, vamos a trabajar con Python. Todo el proceso se puede representar en el siguiente código:
def inserciónSort(arr): if (n:=len(arr))=1: return for i in range(1, n): key=arr[i ] j=i-1 while j >=0 y tecla arr[j]: arr[j+1]=arr[j] j-=1 arr[j+1]=tecla arr=[10, 14, 5, 7, 1] tipoinserción(arr) print(arr)
Primero, estamos definiendo el tipo de inserción como una función del arreglo, (arr). Entonces, estamos diciendo que, si la matriz tiene una longitud de 1 o menos, se devuelve la matriz. A continuación, estamos definiendo el elemento en la i-ésima posición de una matriz de longitud n como clave.
Estamos poniendo restricciones en el cálculo para que j solo se opere cuando sea mayor o igual al índice 0. J se considera el valor a la izquierda de cualquier elemento que estemos viendo, como por j=i-1. Si su valor es mayor que la clave, su posición se desplaza a la derecha.
La línea final, arr[j+1]=clave, dicta que el valor a la derecha de este valor j se convierte en la nueva clave. Por lo tanto, el resto de los números se intercambian según sea necesario. Este proceso continúa desde el principio, hasta que todos los números se ordenan correctamente.
Ordenación por inserción en Python: Implementación
Veamos cómo se implementa esto en Python dentro del entorno de Spyder. Usaremos la misma matriz que antes para ilustrar esto claramente. Vea el código implementado a continuación:
Implementación de ordenación por inserción en Python.
©”TNGD”.com
Un punto clave es que la sangría es crítica cuando se usa Python. Si la sangría no se utiliza correctamente, recibirá un mensaje de error similar al siguiente.
Recibiendo un mensaje de error.
©”TNGD”.com
Mejores y peores casos de uso de clasificación por inserción
Si bien la ordenación por inserción es útil para muchos propósitos, como con cualquier algoritmo, tiene sus mejores y peores casos. Esto se debe principalmente a la complejidad de tiempo y espacio.
Complejidad de tiempo con ordenación por inserción
La complejidad de tiempo en cada caso se puede describir en la siguiente tabla:
Puedes ver que, en el mejor de los casos, la complejidad temporal es igual a O(n). Esto significa que no se requiere ordenar, ya que la matriz ya está ordenada. Debido a que el algoritmo tiene que verificar cada valor en secuencia antes de que pueda determinar que la matriz está ordenada, la complejidad del tiempo es lineal. Es decir, la complejidad es linealmente proporcional al tamaño de la entrada.
Sin embargo, en el promedio y en el peor de los casos, la complejidad es igual a O(n2). Un caso promedio sería donde los elementos de la matriz están desordenados, ni ascendentes ni descendentes. En el peor de los casos, los elementos tendrían que ordenarse a la inversa.
Esto se debe a que ya están en orden ascendente o descendente y necesita el orden opuesto. Este tipo de complejidad se conoce como tiempo cuadrático porque depende de n2. Por ejemplo, si el tamaño de la entrada es 4, el número de operaciones sería 16.
Complejidad espacial con clasificación por inserción
El otro tipo de complejidad es la complejidad espacial. Esto se refiere a la cantidad de espacio de memoria requerido para ejecutar el algoritmo. Una complejidad de O(1) significa que la cantidad de memoria necesaria es constante, independientemente del tamaño de entrada.
Esto es cierto en el caso de la ordenación por inserción porque solo está usando una variable temporal con cada operación. En otras palabras, solo se ordena un valor a la vez, por lo que el uso de la memoria es constante.
Cabe señalar que la ordenación por inserción se considera un algoritmo estable, lo que significa que el orden relativo de los elementos con valores iguales es Preservado. Esto es útil si necesita conservar el orden de elementos específicos o necesita ordenar arreglos que ya están parcialmente ordenados. Esto se debe a que los elementos no se intercambian con la clave si son equivalentes a ella.
Conclusión
Hemos cubierto qué es la ordenación por inserción y cuándo es apropiado usarla. Además de esto, hemos considerado su complejidad de tiempo y espacio y hemos mostrado su representación e implementación de código en Python. Si está buscando ordenar una matriz relativamente pequeña, particularmente una donde algunos elementos ya están ordenados, la ordenación por inserción es uno de los mejores métodos para usar.
A continuación
Qué es ¿Ordenación por inserción y cómo funciona? (Con ejemplos) Preguntas frecuentes (FAQ)
¿Qué es la ordenación por inserción?
La ordenación por inserción es un algoritmo que se puede usar para ordenar conjuntos de datos en orden ascendente o descendente. Es similar a cómo clasificaría una baraja de cartas en sus manos, ya que el primer elemento se considera clasificado.
Cada elemento subsiguiente se compara con el primer elemento y se coloca en la posición correcta, ya sea dejándolo donde está o moviéndolo una posición a la derecha. Esto se repite para cada elemento, y luego el proceso continúa desde el principio hasta que se ordenan todos los elementos.
¿Cuándo debe usar la ordenación por inserción?
La ordenación por inserción se usa mejor para conjuntos de datos pequeños y aquellos en los que los valores ya están parcialmente ordenados.
¿Qué lenguajes de programación pueden implementar la ordenación por inserción?
Muchos de los lenguajes de programación pueden implementar la ordenación por inserción, incluidos C, C++, C#, Java, Javascript, PHP y Python.
¿Cuáles son las ventajas de la ordenación por inserción?
Las ventajas del ordenamiento por inserción son que es simple, el orden relativo de las claves no cambia, es eficiente para pequeños conjuntos de datos y el hecho de que puede ordenar una lista mientras se recibe.
¿Cómo se optimiza la ordenación por inserción?
La ordenación por inserción se optimiza mediante la creación de un subarreglo almacenado, donde los valores ordenados se almacenan temporalmente. Esto significa que no se requiere un intercambio completo de los elementos de la matriz durante cada iteración, ya que los elementos se intercambian uno a la vez.
¿Cuántas iteraciones hay en la ordenación por inserción?
Con una matriz de longitud n, se necesitan n-1 iteraciones para ordenar la matriz completa.
¿Cómo se puede modificar la ordenación por inserción?
La ordenación por inserción se puede modificar mediante la ordenación por inserción binaria. Esto es similar a la ordenación por inserción en que es un algoritmo estable, pero reduce la cantidad de comparaciones que deben realizarse.
La complejidad del tiempo se reduce de O(n) a O(log n) porque utiliza búsqueda binaria en lugar de búsqueda lineal. Cada valor se compara con los valores del subarreglo ordenado para determinar qué valor es justo mayor que el valor seleccionado. Esto acorta el número de operaciones.
¿Cuáles son los inconvenientes de la ordenación por inserción?
La ordenación por inserción no es apropiada para conjuntos de datos particularmente grandes, ya que la complejidad temporal en el caso promedio y peor es cuadrática.
¿Cuáles son las alternativas a la ordenación por inserción?
Con conjuntos de datos grandes y confusos, alternativas más apropiadas son ordenación rápida, ordenación por combinación u ordenación en montón.
¿La ordenación por inserción es un algoritmo estable?
Sí, la ordenación por inserción se considera un algoritmo de ordenación estable, porque los elementos no se modifican si son iguales a la clave. El orden de los elementos también se conserva si son equivalentes entre sí.