Ordenamiento por inserción

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.

Contenido

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++) {
         j=i;
         aux = v[i];
         for (j=i-1; j>=0 && v[j]>aux; j--){
            v[j+1] = v[j];
            v[j] = 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
    i=0
    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;
                }
        }

Véase también

Enlaces externos


Wikimedia foundation. 2010.

См. также в других словарях:

  • Ordenamiento por inserción — 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. Inicialmente se tiene un solo elemento, que… …   Enciclopedia Universal

  • Ordenamiento por mezcla — El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n). Contenido 1 Descripción 2 Implementaciones 2.1 Perl …   Wikipedia Español

  • Ordenamiento por casilleros — Los elementos se distribuyen en cubos Luego se ordenan los elementos de cada cubo El ordenamiento por casilleros (bucket sort en inglés) es un algoritmo de ordenamiento que distribuye todos los elementos a ordenar entre un número finito de… …   Wikipedia Español

  • Ordenamiento por selección — Animación del Selection Sort El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos. Su funcionamiento es el siguiente: Buscar el mínimo… …   Wikipedia Español

  • Ordenamiento — puede referise a: En derecho: Ordenamiento jurídico, el conjunto de normas globales que rigen en una determinada época y en un lugar determinado. Ordenamiento jurídico de la Orden de Malta, el Ordenamiento jurídico especial de la Orden de Malta.… …   Wikipedia Español

  • Ordenamiento Shell — El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio… …   Wikipedia Español

  • Ordenamiento de burbuja — La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es… …   Wikipedia Español

  • Algoritmo de ordenamiento — Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por …   Wikipedia Español

  • Comb sort — En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo… …   Wikipedia Español

  • Montículo suave — Para otros usos de este término, véase Montículo (desambiguación). En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos montículo. Fue concebida por Bernard Chazelle en el año 2000. Al corromper… …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»