Ordenar por inserción en Python

La clasificación por inserción es un algoritmo de clasificación simple que funciona de maravilla en colecciones pequeñas. A menudo se usa junto con Quicksort y Merge Sort en las etapas finales. En este artículo, implementaremos la ordenación por inserción en Python.

Introducción

Si te estás especializando en Informática, Ordenación por inserción es probablemente uno de los primeros algoritmos de clasificación de los que has 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 ordenación por inserción a menudo se ilustra comparándola con la ordenación de 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 ordenar las cartas en su mano 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 contiene el "subarreglo" clasificado de sus cartas, mientras que las cartas restantes boca abajo en la mesa están sin clasificar, de las cuales toma las cartas una por una y las pone en su mano.

La ordenación por inserción es muy simple e intuitiva de implementar, lo cual es una de las razones por las que generalmente se enseña en una etapa temprana de la programación. Es un algoritmo estable, in situ, que funciona muy bien para arreglos pequeños o casi ordenados.

Vamos a elaborar estos términos:

  • in situ: requiere un espacio adicional pequeño y constante (independientemente del 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 desde la matriz inicial. En otras palabras, digamos 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 la matriz completa de antemano antes de ordenar. El algoritmo puede recibir un elemento a la vez. Lo cual es excelente si queremos agregar más elementos para ordenar: el algoritmo solo inserta ese elemento en su lugar adecuado sin "rehacer" todo el orden.

La ordenación por inserción se usa con bastante frecuencia en la práctica, debido a lo eficiente que es para conjuntos de datos pequeños (~10 elementos). Hablaremos más de eso luego.

Cómo funciona la ordenación por inserción

Un arreglo se divide en un subarreglo "ordenado" y un subarreglo "sin ordenar". Al principio, el subarreglo ordenado contiene solo el primer elemento de nuestro arreglo original.

El primer elemento en la matriz no ordenada se evalúa para que podamos insertar en su lugar adecuado en la subarreglo ordenado.

La 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 significa necesariamente 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 alejado 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, “actual”, 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 (actual = 5)

5 es menor que todos los elementos de nuestro subarreglo ordenado, por lo 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 actual. 4 es menor que 8, así que movemos 8 a la derecha y hacemos lo mismo con 5.

5, 5, 8, 10, 9 (actual = 4)

Una vez más, hemos encontrado un elemento menor que nuestro subarreglo ordenado completo, 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 mayor que cualquiera de los elementos a la izquierda de 8. Así que simplemente pasamos al siguiente elemento:

4, 5, 8, 10, 9

9 es menor que 10, entonces movemos 10 a la derecha:

4, 5, 8, 10, 10 (actual = 9)

Sin embargo, 9 es mayor que 8, así que simplemente insertamos 9 justo después de 8.

4, 5, 8, 9, 10

Implementación

Como mencionamos anteriormente, la ordenación por inserción es bastante fácil de implementar. Lo implementaremos primero en una matriz simple de enteros y luego en algunos objetos personalizados.

En la práctica, es mucho más probable que trabaje con objetos y los clasifique según ciertos criterios.

Clasificación de matrices {#clasificación de matrices}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

Vamos a llenar una matriz simple y ordenarla:

1
2
3
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))

Producción:

1
sorted array: [2, 3, 4, 6, 9, 14, 16, 21, 22, 27, 29, 30, 34, 36, 37, 39, 40, 41, 42, 47]

Nota: Hubiera sido técnicamente incorrecto si invirtiéramos el orden de las condiciones en nuestro bucle while. Es decir, si comprobamos primero si matriz[posición actual-1] > valor actual antes de comprobar si posición actual > 0.

Esto significaría que si realmente llegamos al elemento 0, primero verificaríamos si array[-1] > currentValue. En Python esto está "bien", aunque técnicamente incorrecto, ya que no causaría que el ciclo terminara prematuramente o continuara cuando no debería.

Esto se debe a que si hubiéramos llegado al elemento cero, la segunda condición de posición actual > 0 fallaría independientemente de la primera condición y provocaría la ruptura 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 suceda.

Este orden inverso de condiciones es una mala idea. En muchos casos, puede generar 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 “quejarían” por intentar acceder al elemento -1st, pero Python no se quejará y es fácil pasar por alto ese error.

El consejo para llevar de esto es siempre verificar 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 necesitaba basarse únicamente en números enteros. Hay varias formas en que podemos cambiar nuestro algoritmo para trabajar 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 necesitaríamos sobrecargar esos operadores si quisiéramos ordenar los objetos de nuestra clase de una manera diferente.

Podría decirse que la mejor forma de utilizar la ordenación por inserción para clases personalizadas es pasar otro argumento al método insertion_sort, 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 coordenada x más baja.

Primero definiremos nuestra clase Punto:

1
2
3
4
5
6
7
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 pequeño cambio en nuestro método insertion_sort para acomodar la clasificación personalizada:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
4
(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.

Clasificación por 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(n^2^). Sin embargo, como hemos mencionado, es muy eficiente en arreglos pequeños y en arreglos casi ordenados.

Esto hace que Ordenar por inserción sea muy relevante para usar en combinación con algoritmos que funcionan bien en grandes conjuntos de datos.

Por ejemplo, Java usó un Dual Pivot Ordenación rápida como el algoritmo de clasificación principal, pero usó la clasificación por inserción siempre que la matriz (o subarreglo creado por Quick Sort) tenía menos de 7 elementos.

Otra combinación eficiente es simplemente ignorar todos los pequeños subarreglos 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 marca es con un algoritmo muy popular llamado Shell Sort. Shell Sort funciona llamando a Insertion Sort para ordenar pares de elementos separados entre sí, y luego reduce gradualmente la brecha entre los elementos que deben compararse.

Esencialmente, hacer muchas llamadas de ordenación por inserción primero a arreglos pequeños y luego casi ordenados a arreglos más grandes, aprovechando todas las ventajas que puede.

Conclusión

La ordenación por inserción es un algoritmo muy simple, generalmente ineficiente que, sin embargo, 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 usa en la práctica para escenarios específicos en los que brilla.