Bubble Sort

1. Cos'è il Bubble Sort?

Il Bubble Sort (ordinamento a bolle) è uno degli algoritmi di ordinamento più intuitivi e didattici. Il suo funzionamento si basa sul confronto ripetuto di coppie di elementi adiacenti all'interno di un vettore: se due elementi si trovano nell'ordine sbagliato (ad esempio il sinistro è maggiore del destro in un ordinamento crescente), l'algoritmo li scambia.

A ogni passaggio completo attraverso il vettore, l'elemento di valore massimo "risale" progressivamente verso la fine della struttura, comportandosi come una bolla d'aria in acqua (da qui il nome Bubble Sort).

2. Meccanismo di Funzionamento e Ottimizzazione

L'algoritmo impiega due cicli annidati: il ciclo esterno gestisce le passate (fino a un massimo di $N-1$ passate), mentre il ciclo interno esegue i confronti adiacenti.

Ottimizzazione del flag di scambio (`swapped`): Se durante una passata completa non viene effettuato alcuno scambio, significa che il vettore risulta già interamente ordinato. In tal caso, l'algoritmo può interrompersi anticipatamente, migliorando l'efficienza nel caso migliore.

                // Implementazione ottimizzata del Bubble Sort in C++
                #include <vector>
                #include <algorithm>
                #include <iostream>

                void bubbleSortOttimizzato(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;
                }
                }
                // Se non ci sono stati scambi, il vettore è già ordinato
                if (!swapped) {
                break;
                }
                }
                }
            

3. Analisi della Complessità

Complessità Temporale nel Caso Peggiore $\mathcal{O}(N^2)$: Si verifica quando il vettore è ordinato al contrario, richiedendo il numero massimo di confronti e scambi.
Complessità Temporale nel Caso Migliore $\mathcal{O}(N)$: Si verifica quando il vettore di partenza è già ordinato, grazie all'interruzione anticipata garantita dal flag `swapped`.
Complessità Spaziale $\mathcal{O}(1)$: L'ordinamento avviene in-place, senza richiedere strutture di supporto aggiuntive.

4. Simulatore Interattivo: Esecuzione Bubble Sort

Inserisci una sequenza di numeri interi separati da virgola per testare l'ordinamento a bolle e verificare i passaggi eseguiti.

bubble-sort@nexus-core:~# Bubble Sort Simulator

Vettore Numerico (separato da virgole):

> Configura il vettore numerico per avviare la simulazione interattiva dell'algoritmo a bolle.

1. Cos'è il Bubble Sort?

2. Meccanismo di Funzionamento e Ottimizzazione

3. Analisi della Complessità

4. Simulatore Interattivo: Esecuzione Bubble Sort

Gestione della Privacy e dei Cookie