Algoritmo de ordenación por inserción con C, C++, Java, Python Ejemplos

¿Qué es la clasificación por inserción?

El algoritmo de ordenación por inserción es uno de los algoritmos de ordenación por comparación que se utilizan para ordenar elementos iterando sobre un elemento a la vez y colocando el elemento en su posición correcta dentro de una región ya ordenada.

Cada elemento se inserta secuencialmente en una lista ya ordenada. El tamaño inicial de la lista ordenada es uno. El algoritmo de ordenación por inserción garantiza que los primeros k elementos estén ordenados tras la k-ésima iteración del bucle externo.

Debido a que el algoritmo de ordenación por inserción construye el resultado de forma incremental, es intuitivo de enseñar, fácil de depurar y constituye una base sólida para entradas muy pequeñas donde los algoritmos más complejos añadirían una sobrecarga sin beneficios apreciables.

Características del algoritmo de clasificación por inserción

El algoritmo de ordenación por inserción tiene las siguientes características importantes que explican su comportamiento en cargas de trabajo reales:

• Es una técnica de clasificación estable, por lo que no cambia el orden relativo de elementos iguales.
• Es eficiente para conjuntos de datos pequeños, pero no es eficaz para listas más grandes donde predomina el crecimiento cuadrático.
• El algoritmo de ordenación por inserción es adaptativo, lo que reduce su número total de pasos si la entrada está parcialmente ordenada. Formación se proporciona como entrada para hacerlo eficiente porque el acceso aleatorio permite cambios de tiempo constante durante el bucle interno.
• Es un algoritmo que se ejecuta in situ, por lo que no requiere almacenamiento auxiliar proporcional al tamaño de la entrada.

Teniendo en cuenta estas características, la siguiente sección explica la operación de inserción principal que impulsa cada pasada del algoritmo.

¿Cómo se inserta? Opera¿Funciona?

En el algoritmo de ordenación por inserción, la operación de inserción se utiliza para ordenar elementos no ordenados. Permite insertar un nuevo elemento en una lista ya ordenada, preservando el orden existente de la región ordenada.

Pseudocódigo de la operación de inserción:

Considere una lista A de N elementos.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

En el ejemplo anterior, se inserta un nuevo elemento 6 en una lista ya ordenada. Los siguientes pasos trace el bucle interno a medida que el nuevo elemento migra hacia la izquierda hacia su posición correcta.

Paso 1) En comparación con el elemento adyacente izquierdo de A[5], 9 > 6, intercambiamos la posición de 9 y 6. Ahora el elemento 6 se mueve a A[4].

Paso 2) Ahora, comparamos A[4] y A[3], y encontramos que A[3] > A[4], así que volvemos a intercambiar la posición de 6 y 8.

Paso 3) Ahora compare A[3] y A[2]. Como A[2] > A[3], intercambiamos la posición de 7 y 6.

Paso 4) Comparamos A[1] y A[2]. Como A[1] < A[2], el elemento adyacente a la izquierda ya no es mayor. Concluimos que el 6 se insertó correctamente y detenemos el bucle interno aquí.

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

La operación de inserción descrita anteriormente es la base del algoritmo de ordenación por inserción. El procedimiento de inserción se ejecuta en cada elemento y, al final, obtenemos la lista ordenada, ya que la región ordenada crece en un elemento en cada pasada externa.

La figura anterior muestra el funcionamiento del algoritmo de ordenación por inserción en una estructura de datos. Inicialmente, solo hay un elemento en la sublista ordenada, es decir, 4. Después de insertar A[1], es decir, 3, el tamaño de la sublista ordenada aumenta a 2, y el algoritmo continúa este patrón hasta que se hayan colocado todos los elementos.

Con el flujo conceptual establecido, las siguientes secciones muestran implementaciones concretas en C++, C y Python para que puedas comparar estructuras de bucles entre diferentes lenguajes.

C++ Programa de clasificación por inserción

El C++ La implementación que se muestra a continuación utiliza dos bucles anidados: el bucle exterior selecciona el siguiente elemento sin ordenar, y el bucle interior lo desplaza hacia la izquierda hasta encontrar la posición correcta.

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

Salida:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code para ordenación por inserción

La misma lógica se traduce directamente a C. El estándar printf Las llamadas reemplazan la salida del flujo, pero el patrón de intercambio dentro del bucle interno es idéntico al de la C++ versión.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Salida:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Programa de clasificación por inserción

Python admite intercambio de tuplasping en una sola expresión, por lo que el bucle interno es más compacto que su C y C++ contrapartes, manteniendo el mismo comportamiento algorítmico.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Salida:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Propiedades del ordenamiento por inserción

A continuación, se presentan propiedades importantes del algoritmo de ordenación por inserción que le ayudarán a decidir cuándo es la herramienta adecuada:

• En línea: El algoritmo de ordenación por inserción ordena los elementos a medida que los recibe. Si ya hemos ordenado una lista de elementos y añadimos más, no es necesario volver a ejecutar todo el proceso de ordenación. En su lugar, solo iteramos sobre los elementos recién añadidos.
• En su lugar: La complejidad espacial del algoritmo de ordenación por inserción es constante y no requiere espacio adicional. Este algoritmo ordena los elementos in situ.
• Estable: En el algoritmo de ordenación por inserción, no se intercambian elementos si sus valores son iguales. Por ejemplo, si dos elementos, x e y, son iguales y x aparece antes que y en la lista sin ordenar, entonces en la lista ordenada, x seguirá apareciendo antes que y. Esto hace que el algoritmo de ordenación por inserción sea estable.
• Adaptado: A algoritmo de clasificación Un algoritmo es adaptativo si requiere menos tiempo cuando los elementos de entrada o un subconjunto de ellos ya están ordenados. Como se mencionó anteriormente, el mejor tiempo de ejecución del algoritmo de ordenación por inserción es O(N), y el peor es O(N²). La ordenación por inserción es uno de los algoritmos de ordenación adaptativos.

Complejidad de la ordenación por inserción

La discusión sobre la complejidad que se presenta a continuación abarca tanto el uso de memoria como el tiempo de ejecución, de modo que pueda comparar el algoritmo de ordenación por inserción con alternativas como: Bubble Ordenar y Ordenación rápida.

Complejidad espacial

El algoritmo de ordenación por inserción no requiere espacio adicional para ordenar los elementos. La complejidad espacial es constante, es decir, O(1), ya que solo se utilizan unas pocas variables temporales, independientemente del tamaño de la entrada.

Complejidad de tiempo

Debido a que el algoritmo de ordenación por inserción itera un elemento a la vez, requiere N-1 pasadas para ordenar N elementos. En cada pasada, puede que no realice ningún intercambio si los elementos ya están ordenados, o puede que necesite muchos intercambios si los elementos están ordenados de forma descendente.

• Para el pase 1, los swaps mínimos requeridos son cero y los swaps máximos requeridos son 1.
• Para el pase 2, los swaps mínimos requeridos son cero y los swaps máximos requeridos son 2.
• Para el pase N, el swap mínimo requerido es cero y el swap máximo requerido es N.
• El intercambio mínimo es cero, por lo que la mejor complejidad temporal es O(N) para iterar N pases.
• El número máximo total de intercambios es (1+2+3+4+…+N), es decir, N(N+1)/2, por lo que la complejidad temporal en el peor de los casos es O(N^2).

Aquí se muestra la complejidad temporal importante del algoritmo de ordenación por inserción:

• Complejidad del peor caso: O(n^2): Ordenar un array en orden descendente cuando se requiere que sea ascendente es el peor escenario posible.
• Mejora la complejidad del caso: O(n): El mejor caso se da cuando el arreglo ya está ordenado; el bucle externo se ejecuta n veces, mientras que el bucle interno no se ejecuta en absoluto. Solo hay n comparaciones, por lo que la complejidad es lineal.
• Complejidad media del caso: O(n^2): Esto ocurre cuando los elementos del arreglo aparecen en un orden desordenado que no es ni ascendente ni descendente.

Preguntas Frecuentes