Ordenamiento por inserción

Ejemplo de ordenamiento por inserción ordenando una lista de números aleatorios.

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n2) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

Ejemplo de funcionamiento

En el siguiente ejemplo, 32 debe ser insertado entre 26 y 47, y por lo tanto 47, 59 y 96 deben ser desplazados.

               k+1
11 26 47 59 96 32 
11 26    47 59 96
11 26 32 47 59 96

En la implementación computacional, el elemento k+1 va comparándose de atrás para adelante, deteniéndose con el primer elemento menor. Simultáneamente se van haciendo los desplazamientos.

11 26 47 59 96 32
11 26 47 59    96
11 26 47    59 96
11 26    47 59 96
11 26 32 47 59 96

El algoritmo en pseudocódigo (con listas que empiezan por 0) debería ser como el siguiente:

algoritmo insertSort( A : lista de elementos ordenables )
    para i=1 hasta longitud(A) hacer
         index=A[i]
         j=i-1
         mientras j>=0 y A[j]>index hacer
              A[j + 1] = A[j]
              j = j - 1
         fin mientras
         A[j + 1] = index
    fin para
fin algoritmo

Aunque este algoritmo tiene un mejor orden de complejidad que el de burbuja, es muy ineficiente al compararlo con otros algoritmos como quicksort. Sin embargo, para listas relativamente pequeñas el orden por inserción es una buena elección, no sólo porque puede ser más rápido para cantidades pequeñas de elementos sino particularmente debido a su facilidad de programación.

Implementación

A continuación se muestra el Ordenamiento por inserción en distintos lenguajes de programación:

• C

void insertionSort(int numbers[], int array_size) {
   int i, j, index;

   for (i=1; i < array_size; i++) {
      index = numbers[i];
      j = i-1;
      
      while (j >= 0 && numbers[j] > index) {
         numbers[j + 1] = numbers[j];
         j--;
      }
      
      numbers[j+1] = index;
   }
}

• C++

template <class T> void insertionSort(std::vector<T>& v, int fin) {
    int i, j, index;
    for (i=1; i <fin; i++) {
        index = v.at(i);
        j = i-1;
        while (j >= 0 && v.at(j)>index) {
            v.at(j+1)=v.at(j);
            j--;
        }
        v.erase(v.begin()+j+1);
        v.insert(v.begin()+j+1,index);
    }
}

• Java

public static void insertSort (int[] v) {
      for (int i=1; i<v.length; i++) {
         int aux = v[i];
         int j;
         for (j=i-1; j>=0 && v[j]>aux; j--)
            v[j+1] = v[j];
         v[j+1] = aux;
      }
   }

• JavaScript

for (var i=1; i < vector.length; i++) {
      var temp = vector[i];
      j = i-1;
 
      while (var j >= 0 && vector[j] > temp) {
         vector[j + 1] = vector[j];
         j--;
      }
      vector[j+1] = temp;
   }

• Perl

sub insercion {
    my $array = shift;    # Recibimos una referencia a un array

    my $i;    # Índice del elemento a comparar
    my $j;    # Índice del valor mínimo a encontrar

    for ( $i = 1; $i < @$array; $i++ ) {
        my $x = $array->[$i];             # Elemento $i-ésimo

        # Comparamos este elemento con todos los anteriores,
        # hasta que lleguemos al principio de la lista o encontremos
        # un elemento que sea menor o igual que él.
        for ( $j = $i; $j > 0 and $array->[$j-1] > $x; $j-- ) {
            ;
        }

        # Hacemos la inserción del elemento a comparar (posición $i) en la
        # nueva posición encontrada (posición $j), pero sólo si son distintas
        # posiciones.
        # El uso de splice (extraer/insertar) permite que la solución sea mucho
        # más rápida que el movimiento de los elementos uno a uno.
        splice(@$array, $j, 0, splice(@$array, $i, 1))
            if $i != $j;
    }
}

• PHP

function insert_sort($arr){
    $count = count($arr);
    for($i=1; $i<$count; $i++){
        $tmp = $arr[$i];
        for ($j=$i-1; $j>=0 && $arr[$j] > $tmp; $j--)
            $arr[$j+1] = $arr[$j];
        $arr[$j+1] = $tmp;
    }
    return $arr;
}

• Pascal

Procedure InsertionSort(var insertion:Array_integer; array_size: Integer);
Var
   i, j, index : Integer;

Begin
 For i := 1 to array_size do
  Begin
   index := insertion[i];
   j := i-1;
   While ((j >= 0) AND (insertion[j] > index)) do
    Begin
     insertion[j+1] := insertion[j];
     j := j - 1;
    End;
   insertion[j+1] := index;
  End;

End;

• Visual Basic .NET

    Private Sub insertionSort(ByVal numbers() As Integer) ' Es una función, debemos pasarle el array de números desde el Sub Main()

        Dim i, j, index As Integer
        i = 1

        Do
            index = numbers(i)
            j = i - 1

            While ((j >= 0) And (numbers(j) > index))
                numbers(j + 1) = numbers(j)
                j = j - 1
            End While
            numbers(j + 1) = index
            i = i + 1
        Loop Until i > (UBound(v))
    End Sub

Véase también

• Algoritmo de ordenamiento

Enlaces externos

• InsertionSort en PHP, C + +, C #, Java