Algoritmos (I)

Algoritmos, contenedores e iteradores. Insertion Sort

Última actualización de la serie: Diciembre de 2019

Consideremos el problema de implementar un algoritmo de ordenación simple, por ejemplo el bien conocido método de inserción, de manera que éste pueda emplearse tanto con matrices unidimensinales (arrays con elementos adyacentes en memoria) como con listas doblemente enlazadas.

Sea S un conjunto cualquiera a ordenar de acuerdo con un determinado predicado binario C, que deberá establecer un orden débil estricto sobre los operandos que compare. El orden C debe cumplir, por tanto, las siguientes propiedades:

• Irreflexiva: not C(a,a).
• Antisimétrica: C(a,b) implica not C(b,a).
• Transitiva: C(a,b) y C(b,c) implica C(a,c).

Consideremos un caso genérico en el que el conjunto posea al menos dos elementos. El método de inserción deberá ordenar, en su primera iteración, los dos primeros elementos del conjunto S. Es decir, si C(S[0],S[1]) se evalúa como falso, ambos elementos deberán intercambiarse; en caso contrario, permanecerán en sus posiciones originales. A continuación, insertaremos el tercer elemento S[2] del conjunto (si existe) en la posición correcta dentro del subconjunto ya ordenado {S[0],S[1]}. Los tres primeros elementos del conjunto S quedan, así, ordenados adecuadamente. A continuación, se insertará el cuarto elemento S[3] (si existe) en la posición correcta con respecto al subconjunto ya ordenado {S[0],S[1],S[2]}, y así sucesivamente hasta que el conjunto S quede ordenado en su totalidad.

Puedes consultar un estudio detallado de la complejidad algorítmica de este método en Cormen T. H., et al., "Introduction to Algorithms" (3rd Edition, MIT Press). En particular, el algoritmo es O(n) en el caso más favorable (lista ya ordenada) y O(n²) en los casos medio y menos favorable (conjunto de partida en orden inverso al deseado), siendo n el número de elementos a ordenar.

Ciertamente, el interés por la implementación del método de inserción descansa en su relativa facilidad de codificación, recomendándose el uso de algoritmos de ordenación más eficientes en código real, tales como quick-sort o merge-sort.