Algoritmo di ordinamento a bolle in C++
-
Implementa l’ordinamento a bolle per il contenitore
std::vector
- Analizza la complessità del Bubble Sort con misurazioni temporali empiriche
![Algoritmo di ordinamento a bolle in C++](/img/Cpp/feature-image---bubble-sort-in-cpp.webp)
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(n2). 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
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook