Introducción
Contenido
Si se está especializando en Ciencias de la Computación, el Ordenamiento por inserción es probablemente uno de los primeros algoritmos de clasificación de los que ha oído hablar. Es intuitivo y fácil de implementar, pero es muy lento en arreglos grandes y casi nunca se usa para ordenarlos.
La clasificación por inserción se ilustra a menudo comparándola con clasificar una mano de cartas mientras se juega al rummy. Para aquellos de ustedes que no estén familiarizados con el juego, la mayoría de los jugadores quieren que las cartas en su mano estén ordenadas en orden ascendente para que puedan ver rápidamente qué combinaciones tienen a su disposición.
El crupier te reparte 14 cartas, las recoges una por una y las pones en tu mano en el orden correcto. Durante todo este proceso, su mano sostiene el «subarreglo» ordenado de sus cartas, mientras que las cartas que quedan boca abajo en la mesa no están clasificadas, de las cuales toma las cartas una por una y las pone en su mano.
Insertion Sort es muy simple e intuitivo de implementar, que es una de las razones por las que generalmente se enseña en una etapa temprana de la programación. Es un algoritmo estable e in situ que funciona muy bien para matrices pequeñas o casi ordenadas.
Elaboremos estos términos:
- en su lugar: Requiere un espacio adicional pequeño y constante (sin importar el tamaño de entrada de la colección), pero reescribe las ubicaciones de memoria originales de los elementos de la colección.
- estable: El algoritmo mantiene el orden relativo de objetos iguales de la matriz inicial. En otras palabras, supongamos que la base de datos de empleados de su empresa devuelve «Dave Watson» y «Dave Brown» como dos empleados, en ese orden específico. Si tuviera que ordenarlos por su nombre (compartido), un algoritmo estable garantizaría que este orden permanezca sin cambios.
Otra cosa a tener en cuenta: la ordenación por inserción no necesita conocer toda la matriz de antemano antes de ordenar. El algoritmo puede recibir un elemento a la vez. Lo cual es genial si queremos agregar más elementos para ordenar: el algoritmo solo inserta ese elemento en su lugar apropiado sin «rehacer» todo el orden.
La ordenación por inserción se utiliza con bastante frecuencia en la práctica, debido a su eficacia para conjuntos de datos pequeños (~ 10 elementos). Hablaremos más de eso más adelante.
Cómo funciona el ordenamiento por inserción
Un arreglo se divide en un subarreglo «ordenado» y un subarreglo «sin clasificar». Al principio, el subarreglo ordenado contiene solo el primer elemento de nuestro arreglo original.
El primer elemento de la matriz no ordenada se evalúa para que podamos insertarlo en su lugar adecuado en la submatriz ordenada.
Te puede interesar:Trabajando con Redis en Python con DjangoLa inserción se realiza moviendo todos los elementos más grandes que el nuevo elemento una posición a la derecha.
Continúe haciendo esto hasta que toda nuestra matriz esté ordenada.
Sin embargo, tenga en cuenta que cuando decimos que un elemento es más grande o más pequeño que otro elemento, no necesariamente significa números enteros más grandes o más pequeños.
Podemos definir las palabras «más grande» y «más pequeño» como queramos cuando usamos objetos personalizados. Por ejemplo, el punto A puede ser «más grande» que el punto B si está más lejos del centro del sistema de coordenadas.
Marcaremos el subarreglo ordenado con números en negrita y usaremos el siguiente arreglo para ilustrar el algoritmo:
8, 5, 4, 10, 9
El primer paso sería «agregar» 8 a nuestro subarreglo ordenado.
8, 5, 4, 10, 9
Ahora echamos un vistazo al primer elemento sin clasificar: 5. Mantenemos ese valor en una variable separada, por ejemplo current, para su custodia. 5 es menor que 8. Movemos 8 un lugar a la derecha, sobrescribiendo efectivamente el 5 que se almacenó previamente allí (de ahí la variable separada para su custodia):
8, 8, 4, 10, 9 (current = 5)
5 es menor que todos los elementos de nuestro subarreglo ordenado, así que lo insertamos en la primera posición:
5, 8, 4, 10, 9
A continuación, miramos el número 4. Guardamos ese valor en current. 4 es menor que 8, por lo que movemos 8 hacia la derecha y hacemos lo mismo con 5.
5, 5, 8, 10, 9 (current = 4)
Nuevamente, hemos encontrado un elemento menor que todo nuestro subarreglo ordenado, por lo que lo colocamos en la primera posición:
4, 5, 8, 10, 9
10 es mayor que nuestro elemento más a la derecha en el subarreglo ordenado y, por lo tanto, es más grande que cualquiera de los elementos a la izquierda de 8. Así que simplemente pasamos al siguiente elemento:
4, 5, 8, 10, 9
Te puede interesar:Convertir bytes en cadenas en Python9 es menor que 10, por lo que movemos 10 a la derecha:
4, 5, 8, 10, 10 (current = 9)
Sin embargo, 9 es mayor que 8, por lo que simplemente insertamos 9 justo después de 8.
4, 5, 8, 9, 10
Implementación
Como hemos mencionado anteriormente, Insertion Sort es bastante fácil de implementar. Lo implementaremos primero en una matriz simple de números enteros y luego en algunos objetos personalizados.
En la práctica, es mucho más probable que trabaje con objetos y los ordene según ciertos criterios.
Ordenación de matrices
def insertion_sort(array):
# We start from 1 since the first element is trivially sorted
for index in range(1, len(array)):
currentValue = array[index]
currentPosition = index
# As long as we haven't reached the beginning and there is an element
# in our sorted array larger than the one we're trying to insert - move
# that element to the right
while currentPosition > 0 and array[currentPosition - 1] > currentValue:
array[currentPosition] = array[currentPosition -1]
currentPosition = currentPosition - 1
# We have either reached the beginning of the array or we have found
# an element of the sorted array that is smaller than the element
# we're trying to insert at index currentPosition - 1.
# Either way - we insert the element at currentPosition
array[currentPosition] = currentValue
Completemos una matriz simple y ordénela:
array = [4, 22, 41, 40, 27, 30, 36, 16, 42, 37, 14, 39, 3, 6, 34, 9, 21, 2, 29, 47]
insertion_sort(array)
print("sorted array: " + str(array))
Salida:
sorted array: [2, 3, 4, 6, 9, 14, 16, 21, 22, 27, 29, 30, 34, 36, 37, 39, 40, 41, 42, 47]
Nota: Habría sido técnicamente incorrecto si hubiéramos invertido el orden de las condiciones en nuestro while lazo. Es decir, si primero comprobamos si array[currentPosition-1] > currentValue antes de comprobar si currentPosition > 0.
Esto significaría que si efectivamente alcanzáramos el elemento 0, primero verificaríamos si array[-1] > currentValue. En Python esto está «bien», aunque técnicamente incorrecto, ya que no provocaría que el bucle finalizara prematuramente o continuara cuando no debería.
Esto se debe a que si hubiéramos alcanzado el elemento cero, la segunda condición de currentPosition > 0 fallaría independientemente de la primera condición y provocaría la rotura del bucle. En Python array[-1] > currentValue es equivalente a array[len(array) - 2] > currentValue y el intérprete no se quejaría, pero esta no es una comparación que realmente queremos que ocurra.
Este orden inverso de condiciones es una mala idea. En muchos casos, puede dar lugar a resultados inesperados que pueden ser difíciles de depurar porque no hay ningún error sintáctico o semántico. La mayoría de los lenguajes de programación se «quejan» por intentar acceder al -1st elemento, pero Python no se quejará y es fácil pasar por alto tal error.
El consejo para llevar de esto es verificar siempre si el índice es válido antes de usarlo para acceder a los elementos.
Clasificación de objetos personalizados
Hemos mencionado antes que podemos definir «mayor que» y «menor que» como queramos, que la definición no necesita depender únicamente de números enteros. Hay varias formas en que podemos cambiar nuestro algoritmo para que funcione con objetos personalizados.
Podríamos redefinir los operadores de comparación reales para nuestra clase personalizada y mantener el mismo código de algoritmo que el anterior. Sin embargo, eso significaría que tendríamos que sobrecargar esos operadores si quisiéramos ordenar los objetos de nuestra clase de una manera diferente.
Podría decirse que la mejor manera de usar la ordenación por inserción para clases personalizadas es pasar otro argumento al insertion_sort método – específicamente un método de comparación. La forma más conveniente de hacer esto es usando una función lambda personalizada al llamar al método de clasificación.
En esta implementación, ordenaremos los puntos donde un punto «más pequeño» es el que tiene una menor x coordinar.
Primero definiremos nuestro Point clase:
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __str__(self):
return str.format("({},{})", self.x, self.y)
Luego hacemos un ligero cambio en nuestro insertion_sort método para adaptarse a la clasificación personalizada:
def insertion_sort(array, compare_function):
for index in range(1, len(array)):
currentValue = array[index]
currentPosition = index
while currentPosition > 0 and compare_function(array[currentPosition - 1], currentValue):
array[currentPosition] = array[currentPosition - 1]
currentPosition = currentPosition - 1
array[currentPosition] = currentValue
Finalmente probamos el programa:
A = Point(1,2)
B = Point(4,4)
C = Point(3,1)
D = Point(10,0)
array = [A,B,C,D]
# We sort by the x coordinate, ascending
insertion_sort(array, lambda a, b: a.x > b.x)
for point in array:
print(point)
Obtenemos la salida:
(1,2)
(3,1)
(4,4)
(10,0)
Este algoritmo ahora funcionará para cualquier tipo de matriz, siempre que proporcionemos una función de comparación adecuada.
Orden de inserción en la práctica
La ordenación por inserción puede parecer un algoritmo lento y, de hecho, en la mayoría de los casos es demasiado lento para cualquier uso práctico con su complejidad de tiempo O (n2). Sin embargo, como hemos mencionado, es muy eficiente en arreglos pequeños y en arreglos casi ordenados.
Esto hace que Insertion Sort sea muy relevante para su uso en combinación con algoritmos que funcionan bien en grandes conjuntos de datos.
Por ejemplo, Java utilizó una clasificación rápida de doble pivote como algoritmo de clasificación principal, pero utilizó la clasificación por inserción siempre que la matriz (o submatriz creada por la clasificación rápida) tenía menos de 7 elementos.
Otra combinación eficiente es simplemente ignorar todos los subarreglos pequeños creados por Quick Sort y luego pasar el arreglo final, casi ordenado, a través de Insertion Sort.
Otro lugar donde Insertion Sort dejó su huella es con un algoritmo muy popular llamado Shell Sort. Shell Sort funciona llamando a Insertion Sort para ordenar pares de elementos muy separados entre sí, y luego reducir gradualmente la brecha entre los elementos que se deben comparar.
Te puede interesar:Matplotlib: Cambiar el tamaño del marcador del gráfico de dispersiónEsencialmente, hacer muchas llamadas de ordenación por inserción a arreglos primero pequeños y luego casi ordenados más grandes, aprovechando todas las ventajas posibles.
Conclusión
La ordenación por inserción es un algoritmo muy simple, generalmente ineficiente que, no obstante, tiene varias ventajas específicas que lo hacen relevante incluso después de que se hayan desarrollado muchos otros algoritmos generalmente más eficientes.
Sigue siendo un gran algoritmo para introducir a los futuros desarrolladores de software en el mundo de los algoritmos de clasificación, y todavía se utiliza en la práctica para escenarios específicos en los que brilla.
