Algoritmo di ordinamento a bolle in C++

1. Implementa l’ordinamento a bolle per il contenitore std::vector
2. Analizza la complessità del Bubble Sort con misurazioni temporali empiriche

Questo articolo spiegherà diversi metodi su come implementare l’algoritmo di ordinamento a bolle in C++.

Implementa l’ordinamento a bolle per il contenitore std::vector

Il Bubble sort è uno degli algoritmi di ordinamento più semplici. Itera nella lista di oggetti confrontando ciascuna coppia adiacente e, se non sono ordinati, gli elementi vengono scambiati. È classificato come algoritmo di ordinamento per confronto, poiché l’unica lettura degli elementi viene eseguita utilizzando l’espressione di confronto. Nel seguente codice di esempio, implementiamo il bubble sort per lavorare su oggetti vector generici. Una sola funzione denominata bubbleSort è sufficiente per definire l’intera routine di ordinamento. La funzione è modellizzata e prende un riferimento a un vettore come unico argomento.

bubbleSort include due cicli for annidati per scorrere gli elementi vector finché non vengono ordinati in ordine crescente. Nota che ogni iterazione del cicli for esterno memorizza un elemento in una posizione corretta. Quest’ultimo elemento è memorizzato alla fine del vettore e sembra essere l’elemento più grande nella parte del vettore che viene attraversata nel bucle interno. Nota che abbiamo utilizzato l’algoritmo std::swap per semplificare l’implementazione e renderla più leggibile.

#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 bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

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

  printVector(vec1);
  bubbleSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Produzione:

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

Analizza la complessità del Bubble Sort con misurazioni temporali empiriche

L’ordinamento a bolle appartiene a una classe di esecuzione quadratica. In effetti, il tempo medio e le prestazioni nel caso peggiore di questo algoritmo sono entrambi quadratici - O(n²). Pertanto, questo metodo diventa del tutto inefficiente per grandi insiemi di dati di input. Praticamente non viene utilizzato proprio per questo motivo. Ad esempio, se aumentiamo la lunghezza del vettore di input di 10, il tempo di esecuzione aumenterà all’incirca di un fattore di 100. Nota, tuttavia, il bubble sort può essere abbastanza efficiente per un caso speciale quando gli elementi nel vettore di input sono fuori ordine di una sola posizione (ad es., sequenza 1032547698). Quest’ultimo caso renderebbe lineare la complessità dell’algoritmo. L’esempio di codice seguente misura il tempo di esecuzione per due vettori diversi utilizzando la funzione gettimeofday e invia i risultati alla console.

#include <sys/time.h>

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

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

template <typename T>
void bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

int main() {
  struct timeval start {};
  struct timeval end {};

  vector<int> vec3(100, 10);
  vector<int> vec4(1000, 10);

  gettimeofday(&start, nullptr);
  bubbleSort(vec3);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec3.size(),
         time_diff(&start, &end));

  gettimeofday(&start, nullptr);
  bubbleSort(vec4);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec4.size(),
         time_diff(&start, &end));

  return EXIT_SUCCESS;
}

Produzione:

bubbleSort 100 elements: 0.00002500 sec
bubbleSort 1000 elements: 0.00184900 sec