DAA: ordenación por inserción

La ordenación por inserción es un método muy simple para ordenar números en orden ascendente o descendente. Este método sigue el método incremental. Se puede comparar con la técnica de cómo se clasifican las cartas en el momento de jugar un juego.

Los números, que deben ordenarse, se conocen como keys. Aquí está el algoritmo del método de ordenación por inserción.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Análisis

El tiempo de ejecución de este algoritmo depende en gran medida de la entrada dada.

Si los números dados están ordenados, este algoritmo se ejecuta en O(n)hora. Si los números dados están en orden inverso, el algoritmo se ejecuta enO(n²) hora.

Ejemplo

Unsorted list:

2 13 5 18 14

1^st iteration:

Clave = a [2] = 13

a [1] = 2 <13

Swap, no swap

2 13 5 18 14

2^nd iteration:

Clave = a [3] = 5

a [2] = 13> 5

Intercambiar 5 y 13

2 5 13 18 14

A continuación, a [1] = 2 <13

Swap, no swap

2 5 13 18 14

3^rd iteration:

Clave = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Swap, no swap

2 5 13 18 14

4^th iteration:

Clave = a [5] = 14

a [4] = 18> 14

Intercambiar 18 y 14

2 5 13 14 18

A continuación, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Entonces, sin intercambio

2 5 13 14 18

Finalmente,

the sorted list is

2 5 13 14 18