Implementa l'algoritmo di ordinamento di unione in C++

1. Implementare l’ordinamento di unione per il contenitore std::vector in C++
2. Analizza la complessità dell’ordinamento di unione con misurazioni temporali empiriche

Questo articolo introdurrà come implementare un algoritmo di ordinamento di unione in C++.

Implementare l’ordinamento di unione per il contenitore std::vector in C++

Merge sort utilizza la strategia divide et impera per raggiungere l’efficienza e può essere utilizzato come algoritmo di ordinamento generico per elenchi di grandi dimensioni. L’idea alla base dell’algoritmo è dividere il vettore di input in più vettori più piccoli e quindi ordinare ciascuno di quei vettori. Una volta che i vettori più piccoli sono stati completati, possiamo unirli in un unico elenco che risulta essere un’operazione relativamente più semplice. Si noti che l’esempio di codice seguente implementa questo metodo utilizzando la ricorsione poiché è particolarmente adatto per questa soluzione. Un processo ricorsivo viene utilizzato per dividere il vettore originale più volte fino a ottenere i vettori a due elementi, in cui verrà chiamata la funzione di confronto. Quando ogni coppia viene ordinata, vengono fusi in vettori di quattro elementi e così via fino al ritorno del livello finale di ricorsione.

La funzione mergeSort è la parte centrale del processo ricorsivo. Prende il riferimento vettoriale come unico argomento e controlla se la dimensione è inferiore a uno. In tal caso, il vettore si qualifica come ordinato e la funzione restituisce. Quando il vettore contiene due o più elementi, viene diviso in due oggetti vettoriali separati e su ciascuno di essi viene chiamata la funzione mergeSort. Notare che quest’ultima parte forza l’inizio dell’ordinamento sui sottovettori più piccoli. Una volta che la ricorsione raggiunge tale livello, entrambe le funzioni mergeSort ritornano e il codice successivo inizia l’esecuzione. All’inizio viene cancellato il vettore vec, quindi viene chiamata la funzione merge. La funzione merge è implementata con un processo iterativo che può essere analizzato con una stretta osservazione. In generale, quest’ultimo passaggio unisce i vettori ordinati più piccoli in un oggetto vettoriale.

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

Produzione:

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

In alternativa, si potrebbe riscrivere il codice precedente utilizzando l’algoritmo STL std::merge che potrebbe semplificare il codice per la lettura. Nota che la funzione std::merge sostituisce la nostra implementazione merge e la fusione vettoriale può essere eseguita con una singola istruzione nel corpo della funzione mergeSort. Quando il livello finale di ricorsione restituisce due vettori nella prima chiamata di mergeSort, l’ultima invocazione di std::merge memorizzerà i contenuti ordinati nell’oggetto vec originale che può essere osservato dalla funzione 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;
}

Analizza la complessità dell’ordinamento di unione con misurazioni temporali empiriche

Merge sort offre un tempo di esecuzione O(nlogn) nel caso peggiore, che risulta essere uno dei migliori tra gli algoritmi di ordinamento generici contemporanei. Ha la complessità dello spazio lineare nello scenario peggiore che è più di quanto offre l’algoritmo di ordinamento rapido. Quest’ultimo tende ad essere relativamente più veloce in pratica quando l’implementazione utilizza metodi efficienti per scegliere la variabile pivot.

Anche se il metodo ricorsivo può essere piuttosto complicato da comprendere, è sempre possibile utilizzare un debugger per immergersi nel nocciolo di ogni passaggio. Al livello più alto, tuttavia, possiamo usare il seguente esempio di codice per contare le chiamate di funzioni ricorsive tra diverse dimensioni di vettore. Si noti che la somma delle chiamate ricorsive tende ad essere la funzione - 2n - 2 dove n corrisponde al numero di elementi nel vettore.

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

Produzione:

recursion level: 198
recursion level: 398