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(n²) 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, a, index;
 
   for (i=1; i < array_size; i++) 
   {
      index = numbers[i];
 
      for (a=i-1;a >= 0 && numbers[a] > index;a--) 
      {
         numbers[a + 1] = numbers[a];
      }
      numbers[a+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) {
      int aux;
      int j;
      for (int i=1; i<v.length; i++) {
         aux = v[i];
         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];
      var j = i-1;
 
      while (j >= 0 && vector[j] > temp) {
         vector[j + 1] = vector[j];
         j--;
      }
      vector[j+1] = temp;
   }

Perl

#!/usr/bin/perl
use v5.12;
 
my @array
    = qw(
            1 7 4 9 4 7 2 3 0 8
    );
 
insercion(\@array);
 
say "@array";
 
sub insercion {
 
    my $array_ref = shift;                              # 1 arg. es una ref. a un array
 
    for my $i (1 .. $#$array_ref) {                     # para todos los índices
 
        my $j = $i - 1;                                 # índice anterior
        my $x = $array_ref->[$i];                       # elemento a comparar
 
        next if $array_ref->[$j] <= $x;                 # salida rápida
 
        do {
            $j--;                                       # buscamos
        } while ($j >= 0  and  $array_ref->[$j] > $x);
 
        splice @$array_ref, $j+1, 0, splice @$array_ref, $i, 1;   # ¡extracción e inserción!
    }
}
 
__END__
0 1 2 3 4 4 7 7 8 9

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;

Python

def insertionSort(numeros): #numeros es una lista
    tama = len(numeros) #creamos una variable igual al tamaño de la lista
    for i in range(tama):
      indice = numeros[i]
      a = i-1
      while (a >= 0 and numeros[a] > indice):
         numeros[a+1] = numeros[a]
         a = a-1
      numeros[a+1] = indice
    print (numeros) #imprime la lista ordenada

Ruby

def insertion_sort(array)
  for j in 1...array.size
    key = array[j]
    i = j - 1
    while i >= 0 and array[i] > key
      array[i + 1] = array[i]
      i = i - 1
    end
    array[i + 1] = key
  end
  array
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

C#

class Program 
        {
                public static void Main(string[] args)
                {
                        int x=0;
                        do{
                                Leer leer=new Leer();
                                leer.dato();
                                Console.WriteLine("Repitiendo...");
                        }while(x==0);
                        Console.ReadKey(true);
                }
        }
 
        public class Inserccion_Directa {
 
                private static int temporal, posicion=0;                
                static int[] x=new int[15];
 
                public int ordenar(int entrada){
                        x[posicion]=entrada;
                        posicion++;
                        for(int y=1;y<posicion;y++){
                                temporal=x[y];
                                for(int z=y-1;z>=0 && x[z]>temporal; z--){
                                x[z+1] = x[z];
                                        x[z] = temporal;
                                }
                        }
                        for(int m=0;m<x.Length;m++){
                                Console.WriteLine("Contenido  "+x[m]);
                        }
                        return 0;
                }
        }
 
        public class Leer{
                int cadena;
                public int dato(){
                        cadena=Convert.ToInt32(Console.ReadLine());
                        Inserccion_Directa objeto1=new Inserccion_Directa();
                        objeto1.ordenar(cadena);
                        return  cadena;
                }
        }

Prolog

insercion([],[]).
insercion(XS,YS):-
        insercion_aux(XS,[],YS).
 
insercion_aux([],YS,YS).
insercion_aux([X|XS],AC,YS):-
        inserta(X,AC,AC1),
        insercion_aux(XS,AC1,YS).
 
inserta(X,[],[X]).
inserta(X,[Y|YS],[X,Y|YS]):-
        X<Y.
inserta(X,[Y|YS],[Y|XS]):-
        X>=Y,
        inserta(X,YS,XS).

Véase también

• Algoritmo de ordenamiento

Enlaces externos

• InsertionSort en PHP, C + +, C #, Java
• InsertionSort en Python
• Ordenación por Inserción - From Scratch