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
1
Confronta
Coppie di elementi adiacenti
2
Scambia
Se l'elemento precedente è maggiore del successivo
3
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: •
tempmemorizza temporaneamente il valore dia•ariceve il valore dib•briceve il valore originale diadatemp
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
1
Cerca
L'elemento più piccolo nella parte non ordinata
2
Scambia
Con il primo elemento della parte non ordinata
3
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! 🚀
Esercitazioni Pratiche C++
Metti in pratica ciò che hai imparato con queste esercitazioni complete
Tutte le Esercitazioni
12 esercitazioni complete per padroneggiare il C++