1. Introduzione all'Ordinamento
L'ordinamento di una struttura dati sequenziale consiste nel disporre gli elementi in un ordine logico stabilito (crescente o decrescente). Gli algoritmi elementari presentano una complessità temporale nel caso peggiore pari a $\mathcal{O}(N^2)$ e sono ideali per dataset di ridotte dimensioni o per fini didattici.
2. Panoramica degli Algoritmi Elementari
- Bubble Sort: Scambia ripetutamente le coppie di elementi adiacenti se si trovano nell'ordine sbagliato, facendo "emergere" il valore massimo verso la fine del vettore. Complessità: $\mathcal{O}(N^2)$.
- Selection Sort: Seleziona iterativamente l'elemento minimo dalla porzione non ordinata e lo posiziona all'inizio del vettore. Complessità: $\mathcal{O}(N^2)$ in tutti i casi.
- Insertion Sort: Inserisce ciascun elemento nella sua posizione corretta all'interno della sotto-sequenza precedente già ordinata. Complessità nel caso migliore: $\mathcal{O}(N)$ se l'array è già ordinato.
// Implementazione del Bubble Sort in C++
#include <vector>
#include <algorithm>
void bubbleSort(std::vector<int>& v) {
int n = v.size();
bool swapped;
for (int i = 0; i < n - 1;
i++) {
swapped = false;
for (int j = 0; j < n - i -
1; j++) {
if (v[j] > v[j + 1]) {
std::swap(v[j], v[j + 1]);
swapped = true;
}
}
if (!swapped) break; // Ottimizzazione: se è già ordinato, esci
}
}
3. Simulatore Interattivo: Test Algoritmi di Ordinamento
Seleziona l'algoritmo desiderato e inserisci un vettore numerico per verificare l'ordinamento e le metriche di esecuzione.
sorting-engine@nexus-core:~#
Sorting Algorithms Simulator
> Configura il vettore e seleziona l'algoritmo per avviare la simulazione.