Python de ordenación por inserción

Funciones y métodos de Python

La ordenación por inserción de Python funciona como la ordenación de tarjetas de juego. Para utilizar la ordenación por inserción, cree dos listas: una lista ordenada y una lista sin ordenar. Compara cada elemento de la lista sin clasificar hasta que clasifica ese elemento. El ordenamiento por inserción es un algoritmo estándar común en el lenguaje Python.

¿Alguna vez ha ordenado naipes en su mano? Esa es una forma de pensar sobre el concepto de ordenación por inserción de Python. Cuando necesitas ordenar una lista con solo unos pocos elementos, la ordenación por inserción te respalda.

Las ordenaciones por inserción colocan un elemento sin clasificar en su lugar correcto después de cada iteración en una matriz.

En esta guía, vamos a hablar sobre qué son los tipos de inserción y cómo funcionan. Analizaremos cómo implementar una ordenación por inserción en Python, con referencia a un ejemplo, para que pueda comenzar con este algoritmo de ordenación.




¿Qué es una ordenación por inserción de Python?

Una ordenación por inserción divide una lista en dos sublistas: ordenadas y no ordenadas. Luego compara cada elemento de la lista no ordenada y continúa haciéndolo hasta que se ordena cada elemento de la lista.

Un algoritmo de ordenación por inserción mueve un elemento ordenado a la sublista ordenada y lo elimina de la sublista no ordenada. Ambas sublistas son parte de la misma matriz, pero distinguen si un elemento está ordenado.

Puedes pensar en tipos de inserción como cómo clasificarías un juego de cartas en tu mano en un juego de cartas.

Te moverías una por una a través de la lista de cartas y las compararías entre sí. Las cartas ordenadas aparecerían a la izquierda de tu mano. Las tarjetas sin clasificar aparecerían a la derecha hasta que las clasificara todas.

El 81% de los participantes afirmaron que se sentían más seguros acerca de sus perspectivas laborales después de asistir a un campamento de entrenamiento. Asigne a un bootcamp hoy mismo.

El graduado promedio de un bootcamp pasó menos de seis meses en la transición profesional, desde comenzar un bootcamp hasta encontrar su primer trabajo.

Empecemos a business y ordenar una matriz mediante el algoritmo de ordenación por inserción. Considere la siguiente matriz sin clasificar:


9 4 3 5

En una ordenación por inserción, el primer elemento se considera ordenado. El segundo elemento se almacena en su propia variable . Llamaremos a esta variable número_actual .

Ordenado número_actual

9 4 3 5

Necesitamos compare current_number con el elemento en la primera posición en la matriz. Si current_number es mayor que el primer elemento, permanece en el mismo lugar. De lo contrario, current_number se mueve al delante del primer elemento.

4 no es mayor que 9, por lo que estos dos elementos intercambian lugares.

 
4 9 3 5

Los dos primeros elementos de nuestra lista están ordenados. A continuación, cambiamos el valor de current_number al tercer elemento de la lista y lo comparamos con todos los elementos de la izquierda.

Nuestro current_number se convierte en 3. Necesitamos comparar:

  • ¿3 es mayor que 9? No, entonces 3 se inserta antes de 9.
  • ¿Es 3 mayor que 4? No, entonces 3 se mueve antes que 4.

Nuestra lista ahora se ve así:

Este proceso se repite hasta que se ordena la lista. Nuestra lista solo tiene un conjunto más de comparaciones para realizar porque solo contiene cuatro valores. En la siguiente iteración, 5 se convierte en número_actual.

  • ¿Es 5 mayor que 9? No, entonces 5 jugadas antes de 9.

ser usado tNo se hacen más comparaciones porque 5 es el último número en nuestra lista ordenada. Después de esta iteración, nuestra matriz ha sido ordenada:

3 4 5 9

¡Es así de simple! En nuestro orden de inserción, siempre mantuvimos los valores ordenados a la izquierda de la lista. Los valores sin clasificar aparecieron a la derecha.

Para cada iteración en la lista, comparamos current_number con todos los elementos sin clasificar. Este proceso se repitió hasta que nuestra lista fue ordenada.




Cómo escribir un ordenamiento por inserción en Python

Todo está bien y bien recorrer el ordenamiento por inserción en papel. Ahora es el momento de entrar en el meollo del asunto e implementar una ordenación por inserción en Python.


Escribir una función de clasificación

Comenzaremos escribiendo una función Python que realiza nuestra clasificación:

 def sortNumbers (toSort): para el número en el rango (1, len (toSort)): current_number = toSort [número] i = número - 1 while i & gt; = 0 y current_number & lt; toSort [i]: toSort [i + 1] = toSort [i] i - = 1 toSort [i + 1] = current_number 

Veamos cómo funciona esto. En nuestra función sortNumbers creamos un Python for loop que recorre todos los números de la lista. Luego, configuramos el primer elemento de la lista como un valor ordenado asignándolo a la variable de Python current_number .

Repasamos cada elemento en el < a href = "/ python-array/">lista de Python (cada elemento después de current_number). Luego, comparamos current_number con cada número a su izquierda. Después de que esto suceda, establecemos el valor de current_number para que sea igual al elemento que le sigue en la lista.

Escribir un programa principal

Hemos tengo que escribir un programa principal que ejecute nuestro orden de inserción:

 números = [9, 4, 3, 5 ] sortNumbers (números) print (números) 

Nuestro código devuelve:

 [3, 4, 5, 9] 

¡Nuestra lista ha sido ordenada en orden ascendente! Felicitaciones por llegar tan lejos.

"Career Karma entró en mi vida cuando más lo necesitaba y rápidamente me ayudó a combinar con un bootcamp. Dos meses después de graduarme, encontré el trabajo de mis sueños que se alineaba con mis valores y objetivos. en la vida! "

Venus, ingeniero de software de Rockbot

Los tipos de inserción pueden clasificar los números en orden descendente. Para lograr esto, debe invertir el & ldquo; menos de & rdquo; (& gt;) inicie sesión en el bucle while y conviértalo en un signo mayor que:

while i & gt; = 0 y current_number & gt; toSort [i]:

Esta línea de código, sustituida en nuestro ejemplo anterior, ordenará los elementos en una lista en orden inverso.




¿Cuándo debería usar un ¿Ordenación por inserción?

Las clasificaciones por inserción se utilizan mejor cuando los datos de una lista están casi ordenados o cuando está ordenando una lista pequeña. Existen algoritmos más eficientes que puede utilizar para ordenar listas grandes. Por ejemplo, una clasificación por combinación o una clasificación rápida es más rápida.


Las clasificaciones de inserción son más rápidas que las clasificaciones de burbujas.

Es útil conocer las clasificaciones de inserción de todos modos. Saber cómo implementar una clasificación de inserción le brinda otro tipo de clasificación que puede usar.

Las ordenaciones de inserción son menos complicadas que otros algoritmos de ordenación. Una vez que haya aprendido a escribir una ordenación de inserción, estará más cerca de aprender sobre ordenaciones más complejas como las ordenaciones de combinación.




Ordenación de inserción de Python : Análisis de complejidad

Como todos los algoritmos, es importante tener en cuenta las complejidades mejores, peores y promedio. Esto nos dará una idea de cuán efectivo es el algoritmo para hacer su trabajo: en este caso , ordenando listas.

El peor caso y las complejidades promedio son O (n2). Esto significa que el algoritmo crecerá exponencialmente más lento a medida que agregue más valores para ordenar en su lista.

El mejor escenario es Sobre). Esto sucede cuando ejecutamos el algoritmo en una lista ordenada. El algoritmo verifica que los elementos estén ordenados y luego deja de ejecutarse.

Puede obtener más información sobre cómo representamos la complejidad del algoritmo en nuestra serie de dos partes en Notación Big O .




Conclusión

Los tipos de inserción son como ordenar una lista de cartas en tu mano en un juego de cartas. Mantiene dos listas: una lista de elementos ordenados y una lista de elementos para ordenar. Luego, recorre la lista de elementos sin clasificar y baraja sus posiciones hasta que estén todos ordenados.

¿Está buscando más recursos del lenguaje de programación Python? Consulte nuestra guía completa sobre cómo aprender Python . Encontrará los mejores consejos sobre cómo aprender Python y una lista de cursos, libros y otros recursos en línea.





Python de ordenación por inserción: StackOverflow Questions

Tutorials