Implementar el algoritmo de ordenación por inserción en C++

Este artículo demostrará cómo implementar un algoritmo de ordenación por inserción en C++.

Implementar la ordenación por inserción para el contenedor std::vector en C++

En esta guía, le mostraremos cómo implementar la ordenación por inserción como una función separada que toma una referencia al objeto std::vector y modifica el contenido en su lugar. La ordenación por inserción itera a través de cada elemento del vector. Se asegura de que todos los elementos antes de la posición actual estén ordenados comparando el elemento actual con los anteriores en orden inverso.

Generalmente, el orden de comparación no importa mucho en el rendimiento del algoritmo, pero asumimos el orden inverso e implementamos el código correspondientemente. También asumiremos que estamos ordenando los elementos en orden ascendente. Aún así, en casos reales, el algoritmo de clasificación genérico debería poder tomar una función de comparación personalizada como argumento. Tenga en cuenta que la operación de comparación a menudo obliga al elemento a desplazarse hacia la derecha si el elemento actual es menor que el anterior. La última operación se implementa utilizando otro bucle for anidado, que invoca la función std::swap en elementos que están en el orden incorrecto.

El siguiente fragmento de código incluye la función insertionSort donde el bucle externo for es responsable de todo el recorrido del array. Inicializamos el iterador al segundo elemento en el vector porque los siguientes pasos incluyen la comparación con los anteriores: el bucle interno itera desde el elemento actual hasta el primero para compararlos. Si la función de comparación evalúa true, el par se intercambia. Tenga en cuenta que la expresión else obliga al bucle interno a romperse cuando al menos un elemento anterior resulta ser menor que el elemento actual.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort(vector<T> &vec) {
  for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
    auto key = it;

    for (auto i = it - 1; i >= vec.begin(); --i) {
      if (*i > *key) {
        std::swap(*i, *key);
        key--;
      } else {
        break;
      }
    }
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  insertionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Producción :

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Alternativamente, podemos reimplementar la función insertionSort usando construcciones de bucle while si se prefiere esta última como una forma más legible para el usuario. Dos algoritmos siguen una lógica de implementación similar, y ambos utilizan la función std::swap para cambiar elementos. La ordenación por inserción es un algoritmo bastante ineficiente en conjuntos de datos grandes y su rendimiento promedio es O (n²).

La ordenación por inserción es similar a otro algoritmo cuadrático llamado ordenación por selección; ambos iteran a través del vector. Después de las n iteraciones, se ordenan los primeros n elementos. Sin embargo, la clasificación de selección evalúa los elementos hacia adelante desde la posición actual en contraste con la clasificación de inserción.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort2(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  insertionSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Producción :

43; 5; 123; 94; 359; -23; 2; -1; 
-23; -1; 2; 5; 43; 94; 123; 359; 

La ordenación por inserción puede ser más eficiente en la práctica en comparación con otros algoritmos O (n²) porque no siempre es necesario comparar el elemento actual con todos los anteriores. Mientras tanto, la ordenación por selección siempre debe buscar en todos los elementos del subarray sin clasificar para encontrar el elemento más pequeño (o más grande). Observe que podemos utilizar tanto la implementación de la función insertionSort en el vector de std::string como la última clase implementa las sobrecargas del operador de comparación. El siguiente ejemplo demuestra su uso básico con el vector de cadena e imprime la lista ordenada de palabras.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<string> vec2 = {"highway", "song",  "work",
                         "borland", "death", "woman"};

  printVector(vec2);
  insertionSort(vec2);
  printVector(vec2);

  return EXIT_SUCCESS;
}

Producción :

highway; song; work; borland; death; woman;
borland; death; highway; song; woman; work;