Orden de inserci贸n en Python

    Introducci贸n

    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.

    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 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

    9 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.

    Esencialmente, 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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *