Implementare l'algoritmo di ordinamento della selezione in C++

Questo articolo spiegherà come implementare l’algoritmo di ordinamento di selezione in C++.

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

Tra i semplici algoritmi di ordinamento, puoi considerare l’ordinamento per selezione come uno dei più semplici da implementare; sebbene abbia la complessità O(n²) e lo rende del tutto inefficiente su vettori di grandi dimensioni.

L’ordinamento della selezione può essere specificato come la seguente routine: All’inizio, troviamo il valore minimo nel vettore e lo scambiamo con il primo elemento. Quindi, spostiamo il puntatore sul secondo elemento e troviamo il valore minimo dal sotto-vettore rimanente da scambiare con il secondo elemento. Continuiamo i passaggi precedenti per il resto del vettore mentre avanziamo il puntatore un elemento alla volta.

Una spiegazione alternativa per l’ordinamento di selezione potrebbe dire di dividere il vettore di input in due partiL: il primo è un sottovettore ordinato e il secondo è il sottovettore rimanente di elementi non ordinati (che è nell’ordine originale). Poiché non si può presumere che il sottovettore ordinato sia presente nel vettore dato, dovremmo scegliere il primo elemento come divisore tra i sottovettori ordinati e non ordinati. Quindi, quando iniziamo a scambiare i valori minimi con gli elementi nelle posizioni di partenza. Il vettore sarà naturalmente diviso in parti ordinate e non ordinate.

Nell’esempio seguente, implementiamo la funzione selectionSort che prende il riferimento all’oggetto std::vector ed esegue una modifica sul posto degli elementi. Abbiamo utilizzato l’algoritmo std::min_element per trovare il valore minimo su ogni iterazione; questo aiuta a capire meglio l’algoritmo per la prima volta.

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

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

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

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::swap(*it, *std::min_element(it, vec.end()));
  }
}

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

  printVector(vec1);
  selectionSort(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, possiamo riscrivere la funzione selectionSort con il secondo cicli for che trova il valore minimo per il sotto-vettore non ordinato rimanente di ogni iterazione. Questa versione è adatta per l’analisi della complessità dell’algoritmo. Anche se l’algoritmo di ordinamento di selezione ha un tempo di esecuzione quadratico, può essere sorprendentemente efficiente su vettori più piccoli rispetto agli algoritmi O(nlogn), come il merge sort o l’heapsort. Si noti che utilizziamo ancora una funzione STL, std::swap, che in questo caso è un’operazione a tempo costante ed è utile che l’esempio di codice sia conciso.

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

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

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

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

    for (auto i = it + 1; i != vec.end(); ++i) {
      if (*i < *min) min = i;
    }

    std::swap(*it, *min);
  }
}

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

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Produzione:

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