Implementa l'algoritmo Quicksort in C++

1. Implementa Quicksort per il contenitore std::vector
2. Indaga sui livelli di ricorsione nell’implementazione di Quicksort

Questo articolo dimostrerà più metodi su come implementare l’algoritmo Quicksort in C++.

Implementa Quicksort per il contenitore std::vector

Quicksort è uno degli algoritmi di ordinamento generici più veloci utilizzati nelle basi di codice contemporanee. Utilizza la tecnica divide et impera simile all’algoritmo di merge sort. Sebbene, il primo dipenda da un’operazione comunemente chiamata partizionamento. Il vettore originale è diviso sull’elemento noto come pivot, che delimita gli elementi più piccoli prima e quelli più grandi dopo. Nota che questi confronti sono relativi al valore pivot, che l’utente dovrebbe scegliere. La scelta del valore pivot risulta essere il fattore critico per le prestazioni di questo algoritmo, che analizzeremo più avanti nell’articolo. A questo punto, supponiamo che l’elemento pivot sia il primo elemento nel vettore originale. Una volta ottenuto il metodo per la selezione pivot, possiamo partizionare il vettore in due vettori più piccoli che verranno ordinati in modo ricorsivo sul posto. Si noti che l’operazione Quicksort è simile all’ordinamento di unione in quanto suddivide anche i vettori più volte fino a quando le loro posizioni iniziali si incrociano.

Il codice di esempio seguente implementa l’algoritmo con una funzione ricorsiva sort che chiama la funzione partitionVec ogni volta che viene invocata. Il processo di partizionamento può essere eseguito in tempo lineare scambiando elementi nello stesso oggetto vettoriale. Quest’ultima operazione viene implementata utilizzando la funzione partitionVec, che funge anche da funzione di ordinamento in un certo modo.

#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>
T partitionVec(vector<T> &vec, size_t start, size_t end) {
  T pivot = vec.at(start);
  auto lh = start + 1;
  auto rh = end;

  while (true) {
    while (lh < rh && vec.at(rh) >= pivot) rh--;
    while (lh < rh && vec.at(lh) < pivot) lh++;

    if (lh == rh) break;

    T tmp = vec.at(lh);
    vec.at(lh) = vec.at(rh);
    vec.at(rh) = tmp;
  }

  if (vec.at(lh) >= pivot) return start;
  vec.at(start) = vec.at(lh);
  vec.at(lh) = pivot;
  return lh;
}

template <typename T>
void sort(vector<T> &vec, size_t start, size_t end) {
  if (start >= end) return;

  auto boundary = partitionVec(vec, start, end);

  sort(vec, start, boundary);
  sort(vec, boundary + 1, end);
}

template <typename T>
void quickSort(vector<T> &vec) {
  sort(vec, 0, vec.size() - 1);
}

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

  printVector(vec1);
  quickSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Produzione:

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

Indaga sui livelli di ricorsione nell’implementazione di Quicksort

Quicksort ha la complessità temporale media O(nlogn), che è alla pari con l’algoritmo di ordinamento di unione. Si noti, tuttavia, che l’algoritmo di ordinamento rapido dipende molto dal metodo di selezione del pivot. In questo caso, abbiamo scelto la versione ingenua per la scelta del valore pivot, che era il primo elemento nel vettore. Ciò può produrre tempi di esecuzione piuttosto negativi con O(n²) in determinati scenari. In pratica, la scelta del pivot casuale ha un’alta probabilità di ottenere le prestazioni O(nlogn). Tuttavia, si dovrebbe essere a conoscenza del metodo di selezione pivot basato sui dati di input se è richiesta la massima prestazione.

Possiamo osservare il processo ricorsivo nel frammento di codice precedente utilizzando l’argomento della funzione aggiuntiva che conta ogni invocazione della funzione sort. L’esempio seguente esegue un test simile su due vettori di dimensioni diverse e stampa le somme corrispondenti. Si noti che la somma delle chiamate ricorsive mette in relazione la dimensione del vettore con la seguente funzione - 2n - 1, dove n denota il numero di elementi.

#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>
auto partitionVec(vector<T> &vec, size_t start, size_t end) {
  T pivot = vec.at(start);
  auto lh = start + 1;
  auto rh = end;

  while (true) {
    while (lh < rh && vec.at(rh) >= pivot) rh--;
    while (lh < rh && vec.at(lh) < pivot) lh++;

    if (lh == rh) break;

    T tmp = vec.at(lh);
    vec.at(lh) = vec.at(rh);
    vec.at(rh) = tmp;
  }

  if (vec.at(lh) >= pivot) return start;
  vec.at(start) = vec.at(lh);
  vec.at(lh) = pivot;
  return lh;
}

template <typename T>
void sort(vector<T> &vec, size_t start, size_t end, int &level) {
  if (start >= end) return;

  auto boundary = partitionVec(vec, start, end);

  sort(vec, start, boundary, ++level);
  sort(vec, boundary + 1, end, ++level);
}

template <typename T>
void quickSort(vector<T> &vec, int &level) {
  sort(vec, 0, vec.size() - 1, ++level);
}

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

  int recursion_level = 0;

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

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

  return EXIT_SUCCESS;
}

Produzione:

level: 199
level: 399