Implementar el algoritmo de clasificación de combinación en C++

1. Implementar Merge Sort para el contenedor std::vector en C++
2. Analice la complejidad de la clasificación por fusión con mediciones de tiempo empíricas

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

Implementar Merge Sort para el contenedor std::vector en C++

Merge sort utiliza la estrategia de dividir y conquistar para alcanzar la eficiencia, y se puede utilizar como el algoritmo de clasificación de propósito general para listas grandes. La idea detrás del algoritmo es dividir el vector de entrada en múltiples vectores más pequeños y luego ordenar cada uno de esos vectores. Una vez que los vectores más pequeños están hechos, podemos fusionarlos en una sola lista, lo que resulta ser una operación relativamente más sencilla. Tenga en cuenta que el siguiente ejemplo de código implementa este método utilizando la recursividad, ya que es ideal para esta solución. Se utiliza un proceso recursivo para dividir el vector original varias veces hasta que obtengamos los vectores de dos elementos, donde se llamará a la función de comparación. Cuando se ordena cada par, se fusionan en vectores de cuatro elementos y así sucesivamente hasta que vuelve el nivel final de recursividad.

La función mergeSort es la parte central del proceso recursivo. Toma la referencia de vector como único argumento y verifica si el tamaño es menor que igual a uno. Si es así, el vector califica como ordenado y la función regresa. Cuando el vector contiene dos o más elementos, se divide en dos objetos vectoriales separados y se llama a la función mergeSort en cada uno de ellos. Observe que la última parte obliga a que la clasificación comience en los subvectores más pequeños. Una vez que la recursividad alcanza dicho nivel, ambas funciones mergeSort regresan y el siguiente código comienza a ejecutarse. Al principio, se borra el vector vec y luego se llama a la función merge. La función merge se implementa con un proceso iterativo que puede asimilarse con una observación atenta. En general, el último paso une los vectores ordenados más pequeños en un objeto vectorial.

#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 merge(vector<T> &vec, vector<T> &v1, vector<T> &v2) {
  auto siz1 = v1.size();
  auto siz2 = v2.size();
  size_t p1 = 0;
  size_t p2 = 0;

  while (p1 < siz1 && p2 < siz2) {
    if (v1.at(p1) < v2.at(p2))
      vec.push_back(v1.at(p1++));
    else
      vec.push_back(v2.at(p2++));
  }

  while (p1 < siz1) vec.push_back(v1.at(p1++));
  while (p2 < siz2) vec.push_back(v2.at(p2++));
}

template <typename T>
void mergeSort(vector<T> &vec) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort(v1);
  mergeSort(v2);

  vec.clear();
  merge(vec, v1, v2);
}

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

  printVector(vec1);
  mergeSort(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, se podría reescribir el código anterior usando el algoritmo STL std::merge que podría simplificar la lectura del código. Tenga en cuenta que la función std::merge sustituye a nuestra implementación de merge, y la combinación de vectores se puede lograr con una sola declaración en el cuerpo de la función mergeSort. Cuando el nivel final de recursividad devuelve dos vectores en la primera llamada de mergeSort, la última invocación de std::merge almacenará el contenido ordenado en el objeto vec original que se puede observar desde la función main.

#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 mergeSort2(vector<T> &vec) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort2(v1);
  mergeSort2(v2);

  vec.clear();
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
             std::back_inserter(vec));
}

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

  printVector(vec1);
  mergeSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Analice la complejidad de la clasificación por fusión con mediciones de tiempo empíricas

Merge sort ofrece O (n log n) en el peor de los casos de tiempo de ejecución, que resulta ser uno de los mejores entre los algoritmos de ordenación de propósito general contemporáneos. Tiene la complejidad del espacio lineal en el peor de los casos que es más de lo que ofrece el algoritmo de clasificación rápida. Este último tiende a ser relativamente más rápido en la práctica cuando la implementación utiliza métodos eficientes para elegir la variable pivote.

Aunque el método recursivo puede ser bastante complicado de comprender, siempre se puede usar un depurador para sumergirse en el meollo de cada paso. Sin embargo, en el nivel superior, podemos usar el siguiente ejemplo de código para contar las invocaciones de funciones recursivas entre diferentes tamaños de vector. Observe que la suma de las llamadas recursivas tiende a ser la función - 2n - 2 donde n corresponde al número de elementos del vector.

#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 mergeSort2(vector<T> &vec, int &level) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort2(v1, ++level);
  mergeSort2(v2, ++level);

  vec.clear();
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
             std::back_inserter(vec));
}

int main() {
  vector<int> vec3(100, 10);
  vector<int> vec4(200, 10);

  int recursion_level = 0;

  mergeSort2(vec3, recursion_level);
  cout << "recursion level: " << recursion_level << endl;

  recursion_level = 0;
  mergeSort2(vec4, recursion_level);
  cout << "recursion level: " << recursion_level << endl;

  return EXIT_SUCCESS;
}

Producción :

recursion level: 198
recursion level: 398