Implementare l'algoritmo di ordinamento per inserimento in C++

Questo articolo dimostrerà come implementare un algoritmo di ordinamento per inserimento in C++.

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

In questa guida, ti mostreremo come implementare l’ordinamento per inserzione come una funzione separata che prende un riferimento all’oggetto std::vector e modifica i contenuti sul posto. L’ordinamento di inserimento scorre ogni elemento nel vettore. Si assicura che tutti gli elementi prima della posizione corrente siano ordinati confrontando l’elemento corrente con i precedenti in ordine a ritroso.

In generale, l’ordine di confronto non ha molta importanza nelle prestazioni dell’algoritmo, ma assumiamo l’ordine all’indietro e implementiamo il codice di conseguenza. Assumeremo anche di ordinare gli elementi in ordine crescente. Tuttavia, nei casi reali, l’algoritmo di ordinamento generico dovrebbe essere in grado di accettare una funzione di confronto personalizzata come argomento. Si noti che l’operazione di confronto spesso forza lo spostamento a destra dell’elemento se l’elemento corrente è minore di quello precedente. Quest’ultima operazione viene implementata utilizzando un altro cicli for annidato, che invoca la funzione std::swap su elementi che sono nell’ordine sbagliato.

Il seguente frammento di codice include la funzione insertionSort in cui il bucle esterno for è responsabile dell’intero attraversamento dell’array. Inizializziamo l’iteratore sul secondo elemento nel vettore perché i passaggi successivi includono il confronto con i precedenti: il bucle interno scorre dall’elemento corrente al primo per confrontarli. Se la funzione di confronto restituisce true, la coppia viene scambiata. Si noti che l’espressione else forza l’interruzione del bucle interno quando almeno un elemento precedente risulta essere inferiore all’elemento corrente.

#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 insertionSort(vector<T> &vec) {
  for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
    auto key = it;

    for (auto i = it - 1; i >= vec.begin(); --i) {
      if (*i > *key) {
        std::swap(*i, *key);
        key--;
      } else {
        break;
      }
    }
  }
}

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

  printVector(vec1);
  insertionSort(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 reimplementare la funzione insertionSort usando i costrutti del cicli while se quest’ultimo è preferito come forma più leggibile per l’utente. Due algoritmi seguono una logica di implementazione simile ed entrambi utilizzano la funzione std::swap per spostare gli elementi. L’ordinamento per inserimento è un algoritmo piuttosto inefficiente su grandi insiemi di dati e le sue prestazioni medie sono O(n²).

L’ordinamento per inserimento è simile a un altro algoritmo quadratico chiamato ordinamento per selezione; entrambi iterano attraverso il vettore. Dopo le n iterazioni, vengono ordinati i primi n elementi. Tuttavia, l’ordinamento di selezione valuta gli elementi in avanti dalla posizione corrente in contrasto con l’ordinamento di inserimento.

#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 insertionSort2(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

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

  printVector(vec1);
  insertionSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Produzione:

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

L’ordinamento per inserimento può essere in pratica più efficiente rispetto ad altri algoritmi O(n²) perché non ha sempre bisogno di confrontare l’elemento corrente con tutti quelli precedenti. Nel frattempo, l’ordinamento di selezione deve sempre cercare in ogni elemento della sottomatrice non ordinata per trovare l’elemento più piccolo (o più grande). Si noti che possiamo utilizzare sia l’implementazione della funzione insertSort sul vettore di std::string poiché quest’ultima classe implementa gli overload dell’operatore di confronto. L’esempio successivo mostra il suo utilizzo di base con il vettore di stringa e stampa la lista ordinato di parole.

#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 insertionSort(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<string> vec2 = {"highway", "song",  "work",
                         "borland", "death", "woman"};

  printVector(vec2);
  insertionSort(vec2);
  printVector(vec2);

  return EXIT_SUCCESS;
}

Produzione:

highway;
song;
work;
borland;
death;
woman;
borland;
death;
highway;
song;
woman;
work;