- 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 96En 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 96El 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 algoritmoAunque 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 SubC#
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
Categoría:- Algoritmos de ordenamiento
Wikimedia foundation. 2010.
