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.

La figura siguiente muestra, de izquierda a derecha y de arriba abajo, las iteraciones de ordenación de menor a mayor del conjunto de números naturales S = {5,3,1,2}:

Nuestro algoritmo será implementado como una plantilla de función (function template) biparamétrica de signatura

   template<typename Bidirectional_iterator, typename Compare>    auto insertion_sort(Bidirectional_iterator first, Bidirectional_iterator last,                        Compare comp) -> void;

siendo [first,last) el rango a ordenar. Aquí, Bidirectional_iterator es un tipo cualquiera de iterador bidireccional, permitiendo las operaciones siguientes:

• Acceso (it->).
• Lectura (=*it) y escritura (*it=).
• Incremento (++) y descremento (--) en una unidad.
• Comparación (==,!=).

Sin embargo, es importante señalar que este tipo de iterador no permite ser incrementado o decrementado según un offset arbitrario, como sí permite un iterador de acceso aleatorio. Por su parte, Compare denota el tipo de objeto de comparación (predicado binario) utilizado en la ordenación. Puede tratarse de la dirección en memoria de una función o, más en general, de un objeto función que tome dos argumentos del tipo referenciado por Bidirectional_iterator, devolviendo una variable booleana.

Atendiendo a las restricciones de funcionamiento señaladas para los iteradores binarios, una posible implementación del algoritmo sería la siguiente:

   template<typename Bidirectional_iterator, typename Compare>    auto insertion_sort(Bidirectional_iterator first, Bidirectional_iterator last,                        Compare comp) -> void    {       if (first == last) // rango a ordenar vacío          return;       auto p = first;       ++p; // p apunta a S[1] o *last       while (p != last) {          auto val = std::move(*p); // inferencia automática del tipo           auto q = p;          // encontremos la localización apropiada para val = S[i]          // dentro del subconjunto {S[0],..,S[i-1]} que lo precede:          do {             auto previous = q;             --previous;             if (comp(*previous, val))                break;             *q = std::move(*previous);             --q;          }          while (q != first);          // ubiquemos a val = S[i] en su posición correcta:          *q = std::move(val);          ++p; // avancemos al siguiente elemento a ordenar, i.e., S[i+1]       }    }

Destaquemos el hecho de que el algoritmo desconoce el tipo de contenedor que almacena los datos a ordenar, siendo el iterador el único intermediario (canal de comunicación) entre la estructura de datos y la función.

Siendo habitual ordenar elementos de menor a mayor, puede resultar conveniente proporcionar una sobrecarga de la función insertion_sort() donde el comparador sea, por defecto, un objeto de la plantilla de clase std::less<> que invoque al operador operator< para objetos del tipo referenciado por Bidirectional_iterator. Dicho tipo puede obtenerse a partir de la expresión decltype(*first):

   template<typename Bidirectional_iterator>    auto insertion_sort(Bidirectional_iterator first, Bidirectional_iterator last) -> void    {       insertion_sort(first, last, std::less<decltype(*first)>{});    }

Equivalentemente, en lugar del objeto std::less<>, podría utilizarse una función lambda genérica de la forma [](auto const& obj_1, auto const& obj_2) { return obj_1 < obj_2; }.

A modo de ejemplo, y una vez implementado correctamente el algoritmo, podemos ordenar una lista de enteros de mayor a menor en la forma siguiente:

   auto v = std::list{1, -5, 0, 4, 6, -2};    insertion_sort(v.begin(), v.end(), [](int a, int b){ return a > b; });