Ordenación por Inserción

La ordenación por inserción es el último de los algoritmos sencillos. La ordenación por inserción inicialmente ordena los dos primeros elementos del

array, después el algoritmo inserta el tercer elemento en su posición correcta con respecto a los dos primeros elementos. A continuación el cuarto

elemento se inserta en la lista de tres elementos. El proceso continua hasta que todos los elementos han sido ordenados. Por ejemplo, en el array dcab,

cada paso de la ordenación por inserción se vería así:

Inicial  dcab

paso 1  cdab

paso 2  acdb

paso 3  abcd

El código de una ordenación por inserción seria el siguiente:

Option Explicit

Sub Insercion()
Dim cont As Long
Dim a As Long, b As Long, pos As Long
Dim t As Long
Dim items As Variant
Dim oTimer As New clsTimer

items = Application.Transpose(Range("A1").CurrentRegion.Value)

oTimer.StartTimer
cont = UBound(items)
For a = 2 To cont
  b = a
  While b >= 2
    If items(b) < items(b - 1) Then
      t = items(b)
      items(b) = items(b - 1)
      items(b - 1) = t
    End If
    b = b - 1
  Wend
Next
MsgBox oTimer.GetElapsedTime(Seconds)

Range("C1").Resize(10000, 1).Value = Application.Transpose(items)
End Sub

Al contrario que la ordenación de la burbuja y de la ordenación por selección,  el número de comparaciones que ocurren cuando utilizamos la ordenación

por inserción dependerá de cómo esté la lista ordenada inicialmente.

Así pues, el número en el caso peor es tan malo como el de las ordenaciones de la burbuja y por selección, y el número en el caso medio es sólo ligeramente mejor.

La ordenación por inserción tiene, sin embargo, dos ventajas. Primero, se comporta naturalmente: trabaja menos cuando el array está ordenado y si la lista está

inversamente ordenada es cuando más trabaja. Esto hace muy útil la ordenación por inserción en listas que están casi ordenadas.

Segundo, deja sin cambiar el orden de claves iguales: si una lista está ordenada utilizando dos claves, permanece ordenada según ambas claves después de la

ordenación por inserción.

Aunque el número de comparaciones puede ser bastante bueno para determinados conjuntos de datos, el hecho es que el array tiene que ser desplazado constantemente,

lo que significa que el número de movimientos puede ser significativo. Sin embargo, la ordenación por inserción todavía se comporta naturalmente, con menos

intercambios en una lista casi ordenada y el máximo número de intercambios en un array ordenado inversamente. A continuación les comparto el archivo con el código de ejemplo.

En el siguiente vídeo se puede apreciar visualmente como trabaja el algoritmo de ordenación por inserción: