Implementar algoritmo de mesclagem de classificação em C++

1. Implementar Merge Sort para o container std::vector em C++
2. Analise a complexidade da mesclagem de classificação com medições de tempo empíricas

Este artigo apresentará como implementar um algoritmo de classificação por mesclagem em C++.

Implementar Merge Sort para o container std::vector em C++

A classificação de mesclagem utiliza a estratégia de dividir e conquistar para alcançar a eficiência e pode ser usada como o algoritmo de classificação de propósito geral para listas grandes. A ideia por trás do algoritmo é dividir o vetor de entrada em vários vetores menores e, em seguida, classificar cada um desses vetores. Assim que os vetores menores estiverem prontos, podemos mesclá-los em uma única lista, o que por acaso é uma operação relativamente mais direta. Observe que o exemplo de código a seguir implementa esse método usando a recursão, pois é ideal para esta solução. Um processo recursivo é usado para dividir o vetor original várias vezes até obtermos os vetores de dois elementos, onde a função de comparação será chamada. Quando cada par é classificado, eles são mesclados em vetores de quatro elementos e assim por diante até que o nível final de recursão retorne.

A função mergeSort é a parte central do processo recursivo. Ele usa a referência de vetor como o único argumento e verifica se o tamanho é menor que um. Nesse caso, o vetor se qualifica como classificado e a função retorna. Quando o vetor contém dois ou mais elementos, ele é dividido em dois objetos vetoriais separados, e a função mergeSort é chamada em cada um deles. Observe que a última parte força o início da classificação nos menores subvetores. Uma vez que a recursão atinge esse nível, ambas as funções mergeSort retornam e o código a seguir inicia a execução. Primeiro, o vetor vec é apagado e, em seguida, a função merge é chamada. A função merge é implementada com um processo iterativo que pode ser grokked com observação próxima. Em geral, a última etapa une os menores vetores classificados em um objeto vetorial.

#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;
}

Resultado:

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

Alternativamente, pode-se reescrever o código anterior usando o algoritmo STL std::merge que pode simplificar o código para leitura. Observe que a função std::merge substitui nossa implementação merge, e a fusão de vetores pode ser realizada com uma única instrução no corpo da função mergeSort. Quando o nível final de recursão retorna dois vetores na primeira chamada de mergeSort, a última invocação de std::merge irá armazenar o conteúdo classificado no objeto vec original que pode ser observado a partir da função 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;
}

Analise a complexidade da mesclagem de classificação com medições de tempo empíricas

A ordenação por mesclagem oferece O (n log n) tempo de execução do pior caso, que por acaso é um dos melhores entre os algoritmos contemporâneos de ordenação de propósito geral. Ele tem a complexidade do espaço linear em um cenário de pior caso que é mais do que o algoritmo de classificação rápida oferece. Este último tende a ser relativamente mais rápido na prática quando a implementação utiliza métodos eficientes para escolher a variável pivô.

Mesmo que o método recursivo possa ser bem complicado de compreender, sempre é possível usar um depurador para mergulhar nos detalhes de cada etapa. No nível superior, porém, podemos usar o seguinte exemplo de código para contar as invocações de função recursiva entre diferentes tamanhos de vetor. Observe que a soma das chamadas recursivas tende a ser a função - 2n - 2 onde n corresponde ao número de elementos no vetor.

#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;
}

Resultado:

recursion level: 198
recursion level: 398