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) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

Implementación

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

C

void ordIns(int vector[], int n) 
{
   int i, j, indice;
 
   for (i=1;    i < n; i++) 
   {
      indice = vector[i];
 
      for (j=i-1;j >= 0 && vector[j] > indice;j--) 
      {
         vector[j + 1] = vector[j];
      }
      vector[j+1] = indice;
 
   }
}

C++

template <class T> void insertionSort(std::vector<T>& v, int fin) {
    int i, j;
    T index(); //El objeto debe tener constructor por defecto
    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);
    }
}

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] = aux;
         }
      }
}

Java

 public void insertionSort(int[] vector){
  for (int i=1; i < vector.length; i++){
    int temp = vector[i];
    int j;
 
    for (j=i-1;j >= 0 && vector[j] > temp;j--){
      vector[j + 1] = vector[j];
 
    }
 
    vector[j+1] = temp;
  } 
}

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 );                  # ejemplo
insercion(\@array);
say "@array";                                           # 0 1 2 3 4 4 7 7 8 9
 
sub insercion {
    my $array_ref = shift;                              # el primer argumento 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 si ya están ordenados
 
        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!
    }
}

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 := 2 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

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