Explicación

El algoritmo de Ordenamiento por Inserción construye la lista ordenada de uno en uno. Comienza con el segundo elemento, comparándolo con los elementos anteriores y desplazándolos hacia la derecha si son mayores, hasta encontrar la posición correcta para el elemento actual. Este proceso se repite hasta que toda la lista esté ordenada.

Ejemplo:

Posición inicial:

La posición está indicada por la flecha, que solo aumenta.

| 5 | 3 | 4 | 1 | 2 |

Posición 0:
No hay nada a la izquierda del primer elemento, así que está ordenado. Avanza.

Posición 1:

| 5 | 3 | 4 | 1 | 2 |

si
numeroIzq > numeroActual
cambio

| 3 | 5 | 4 | 1 | 2 |

Posición 2:

| 3 | 5 | 4 | 1 | 2 |

si
numeroIzq > numeroActual
cambio

| 3 | 4 | 5 | 1 | 2 |

Posición 3:

| 3 | 4 | 5 | 1 | 2 |

si
numeroIzq > numeroActual
cambio

| 3 | 4 | 1 | 5 | 2 |

si
numeroIzq > numeroActual
cambio

| 3 | 1 | 4 | 5 | 2 |

si
numeroIzq > numeroActual
cambio

| 1 | 3 | 4 | 5 | 2 |

Posición 4:

| 1 | 3 | 4 | 5 | 2 |

si
numeroIzq > numeroActual
cambio

| 1 | 3 | 4 | 2 | 5 |

si
numeroIzq > numeroActual
cambio

| 1 | 3 | 2 | 4 | 5 |

si
numeroIzq > numeroActual
cambio

| 1 | 2 | 3 | 4 | 5 |

numeroIzq > numeroActual
no lo es

Lista Ordenada:

| 1 | 2 | 3 | 4 | 5 |

Implementación en C++

Aquí tienes la implementación del algoritmo de Ordenamiento por Inserción en C++:

// Ordenamiento por Inserción
#include <iostream>
#include <conio.h>

using namespace std;

int main() {
    int numeros[] = {4, 2, 3, 1, 5};
    int n = 5; // Tamaño del array
    int aux, pos;

    // Algoritmo del ordenamiento por inserción
    for (int i = 1; i < n; i++) {
        pos = i; // Pos representa la posición de la flecha
        aux = numeros[i]; // Representa el número actual

        while ((pos > 0) && (numeros[pos - 1] > aux)) {
            numeros[pos] = numeros[pos - 1];
            pos--;
        }
        numeros[pos] = aux;
    }

    // Imprimir array ordenado en orden ascendente
    cout << "Orden Ascendente: \n";
    for (int i = 0; i < n; i++) {
        cout << numeros[i] << " ";
    }

    cout << "\nOrden Descendente: \n";
    for (int i = n - 1; i >= 0; i--) {
        cout << numeros[i] << " ";
    }

    getch();
    return 0;
}

Notas

  • Eficiencia: El Ordenamiento por Inserción tiene una complejidad temporal de $O(n^2)$, lo que lo hace ineficiente para listas grandes, pero eficiente para listas pequeñas o casi ordenadas.
  • Aplicación: Es útil para conjuntos de datos pequeños y cuando se añaden elementos a una lista ordenada de manera incremental.