Ordenamiento por inserción

1. Algoritmo de ordenamiento por inserción
2. Ejemplo de ordenamiento por inserción
3. Implementación del algoritmo de ordenamiento por inserción
4. Complejidad del algoritmo de ordenamiento por inserción

La ordenamiento por inserción es un algoritmo de ordenación simple basado en la comparación. En este algoritmo, mantenemos dos submatrices: una ordenada y otra sin ordenar. Un elemento de la subarray sin ordenar encuentra su posición correcta en la subarray ordenada y se inserta allí. Es análogo a la forma en que alguien ordena una baraja de cartas en su mano. Se llama ordenamiento por inserción porque funciona insertando un elemento en su posición correcta. Este algoritmo es eficiente para conjuntos de datos pequeños pero no es adecuado para conjuntos de datos grandes.

Algoritmo de ordenamiento por inserción

Supongamos que tenemos un array sin ordenar A[] que contiene n elementos. El primer elemento, A[0], ya está ordenado y se encuentra en la subarray ordenada.

Ejemplo de ordenamiento por inserción

Supongamos que tenemos el array (5,3,4,2,1). Vamos a ordenarlo utilizando el algoritmo de ordenamiento por inserción.

• Primera Iteración

Clave : A[1] = 3

• Segunda Iteración

Clave : A[2] = 4

• Tercera Iteración

Clave : A[3] = 2

• Cuarta Iteración

Clave : A[4] = 1

Implementación del algoritmo de ordenamiento por inserción

#include <iostream>
using namespace std;

void insertion_sort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      int key = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = key;
      j--;
    }
  }
}

int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  insertion_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo de ordenamiento por inserción

Complejidad temporal

• Caso medio

Por término medio, se realizan i comparaciones en la quinta pasada de la ordenamiento por inserción. Por tanto, si hay n iteraciones, la complejidad temporal media puede ser la siguiente.

1 + 2 + 3 + ... + (n-1) = n*(n-1)/2

Por lo tanto, la complejidad temporal es del orden de [Big Theta]: O(n²).

• El peor caso

El peor caso se produce cuando el array está ordenado de forma inversa, y hay que realizar el máximo número de comparaciones e intercambios.

La complejidad temporal del peor caso es [Big O]: O(n²).

• El mejor caso

El mejor caso ocurre cuando el array ya está ordenado, y entonces sólo se ejecuta el bucle exterior n veces.

La complejidad temporal del mejor caso es [Big Omega]: O(n).

Complejidad espacial

La complejidad espacial del algoritmo de ordenamiento por inserción es O(n) porque no se necesita más memoria que la de una variable temporal.