Ordinamento dei Dati in C++

Bubble Sort e Selection Sort: algoritmi fondamentali per organizzare i dati

L’ordinamento dei dati è un concetto fondamentale nell’informatica con numerose applicazioni pratiche, dalla gestione di database alla visualizzazione efficiente dei dati.

1. Bubble Sort

📌 Caratteristiche: Algoritmo semplice ma inefficiente per grandi dataset. Ideale per apprendere i concetti di base dell’ordinamento.

1.1 Funzionamento dell’Algoritmo

Confronta

Coppie di elementi adiacenti

Scambia

Se l’elemento precedente è maggiore del successivo

Ripeti

Fino a quando l’array è completamente ordinato

1.2 Implementazione in C++

#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
// Scambio manuale senza swap()
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

1.3 Esempio di Scambio Senza swap()

#include <iostream>
using namespace std;
int main() {
int a = 5, b = 3;
cout << “Prima dello scambio: a = “ << a << “, b = “ << b << endl;
if (a > b) {
int temp = a;  // Salva il valore di a
a = b;         // Assegna b ad a
b = temp;      // Assegna il valore originale di a a b
}
cout << “Dopo lo scambio: a = “ << a << “, b = “ << b << endl;
return 0;
}

💡 Spiegazione dello scambio:
• temp memorizza temporaneamente il valore di a
• a riceve il valore di b
• b riceve il valore originale di a da temp

1.4 Esempio Pratico Completo

#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int voti[] = {85, 92, 78, 90, 65, 88, 72};
int n = 7;
cout << “Voti prima dell’ordinamento: “;
for (int i = 0; i < n; i++) {
cout << voti[i] << ” “;
}
cout << endl;
bubbleSort(voti, n);
cout << “Voti dopo l’ordinamento: “;
for (int i = 0; i < n; i++) {
cout << voti[i] << ” “;
}
cout << endl;
cout << “Primo della classe: “ << voti[n-1] << endl;
return 0;
}

2. Selection Sort

📌 Caratteristiche: Divide l’array in parti ordinate e non ordinate. Più efficiente del Bubble Sort per piccoli dataset.

2.1 Funzionamento dell’Algoritmo

Cerca

L’elemento più piccolo nella parte non ordinata

Scambia

Con il primo elemento della parte non ordinata

Espandi

La parte ordinata e ripeti

2.2 Implementazione in C++

#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
int minIndex = i;
// Trova l’elemento più piccolo nella parte non ordinata
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Scambia l’elemento più piccolo con il primo della parte non ordinata
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

2.3 Esempio Pratico Completo

#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
int main() {
int punteggi[] = {45, 78, 92, 34, 67, 88, 56};
int n = 7;
cout << “Punteggi candidati prima dell’ordinamento: “;
for (int i = 0; i < n; i++) {
cout << punteggi[i] << ” “;
}
cout << endl;
selectionSort(punteggi, n);
cout << “Punteggi candidati dopo l’ordinamento: “;
for (int i = 0; i < n; i++) {
cout << punteggi[i] << ” “;
}
cout << endl;
cout << “Migliori 3 candidati: “;
for (int i = n-1; i >= n-3; i–) {
cout << punteggi[i] << ” “;
}
cout << endl;
return 0;
}

3. Confronto tra Algoritmi

B
Bubble Sort

Complessità: O(n²) nel caso peggiore e medio

Memoria: O(1) – ordinamento in loco

Stabilità: Sì

Uso: Didattico, piccoli array

Facile da implementare

S
Selection Sort

Complessità: O(n²) in tutti i casi

Memoria: O(1) – ordinamento in loco

Stabilità: No

Uso: Piccoli array, memoria limitata

Meno scambi del Bubble Sort

🎯 Esercitazioni Guidate

Esempi pratici per comprendere meglio gli algoritmi di ordinamento

Esercizio 1: Bubble Sort con Visualizzazione

Obiettivo: Mostrare ogni passaggio dell’ordinamento per comprendere il processo.

#include <iostream>
using namespace std;
void bubbleSortVisual(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
cout << “Passo “ << i + 1 << “: “;
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// Stampa l’array dopo ogni iterazione esterna
for (int k = 0; k < n; k++) {
cout << arr[k] << ” “;
}
cout << endl;
}
}
int main() {
int numeri[] = {64, 34, 25, 12, 22, 11, 90};
int n = 7;
cout << “Array originale: “;
for (int i = 0; i < n; i++) {
cout << numeri[i] << ” “;
}
cout << endl << endl;
bubbleSortVisual(numeri, n);
cout << endl << “Array ordinato: “;
for (int i = 0; i < n; i++) {
cout << numeri[i] << ” “;
}
cout << endl;
return 0;
}

Esercizio 2: Selection Sort su Stringhe

Obiettivo: Ordinare una lista di nomi in ordine alfabetico.

#include <iostream>
#include <string>
using namespace std;
void selectionSortString(string arr[], int n) {
for (int i = 0; i < n – 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
string temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
int main() {
string nomi[] = {“Marco”, “Anna”, “Luca”, “Zoe”, “Bruno”, “Sofia”};
int n = 6;
cout << “Nomi prima dell’ordinamento: “;
for (int i = 0; i < n; i++) {
cout << nomi[i] << ” “;
}
cout << endl;
selectionSortString(nomi, n);
cout << “Nomi dopo l’ordinamento: “;
for (int i = 0; i < n; i++) {
cout << nomi[i] << ” “;
}
cout << endl;
return 0;
}

Esercizio 3: Confronto Prestazioni

Obiettivo: Confrontare il numero di operazioni degli algoritmi.

#include <iostream>
using namespace std;
void bubbleSortCount(int arr[], int n, int &counter) {
counter = 0;
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
counter++; // Conta ogni confronto
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void selectionSortCount(int arr[], int n, int &counter) {
counter = 0;
for (int i = 0; i < n – 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
counter++; // Conta ogni confronto
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
int n = 7;
int countBubble, countSelection;
bubbleSortCount(arr1, n, countBubble);
selectionSortCount(arr2, n, countSelection);
cout << “Bubble Sort – Numero di confronti: “ << countBubble << endl;
cout << “Selection Sort – Numero di confronti: “ << countSelection << endl;
return 0;
}

5. Esercizi Avanzati

Esercizio 4: Bubble Sort Ottimizzato

Obiettivo: Implementare una versione ottimizzata che si ferma se l’array è già ordinato.

#include <iostream>
using namespace std;
void bubbleSortOttimizzato(int arr[], int n) {
bool scambiato;
for (int i = 0; i < n – 1; i++) {
scambiato = false;
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
scambiato = true;
}
}
// Se non ci sono stati scambi, l’array è ordinato
if (!scambiato) {
break;
}
}
}
int main() {
int numeri[] = {1, 2, 3, 4, 5, 6, 7}; // Già ordinato
int n = 7;
bubbleSortOttimizzato(numeri, n);
cout << “Array ordinato: “;
for (int i = 0; i < n; i++) {
cout << numeri[i] << ” “;
}
cout << endl;
return 0;
}

Esercizio 5: Ordinamento Decrescente

Obiettivo: Modificare gli algoritmi per ordinare in ordine decrescente.

#include <iostream>
using namespace std;
void bubbleSortDecrescente(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
// Cambiato il confronto per ordinamento decrescente
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void selectionSortDecrescente(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
int maxIndex = i; // Cerca il massimo invece del minimo
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}

Conclusioni

Punti chiave:

✅ Importanza dell’Ordinamento

Operazione fondamentale per la gestione efficiente dei dati in numerose applicazioni pratiche

✅ Bubble Sort

Semplice da implementare ma inefficiente per grandi quantità di dati. Ottimo per apprendimento

✅ Selection Sort

Leggermente più efficiente del Bubble Sort, utile quando gli scambi sono costosi

Comprendere il funzionamento degli algoritmi di ordinamento è essenziale per migliorare l’efficienza dei programmi. Con le esercitazioni proposte, potrai sperimentare direttamente questi concetti e affinare le tue competenze in C++. Buon coding! 🚀