Ordinare letteralmente a caso: guida pratica al bogosort

Lo chiamano bogosort per non chiamarlo stupid sort, ordinamento stupido, il che potrebbe suonare grottesco o aggressivo agli occhi di qualche studente. In effetti il Bogosort è un algoritmo di ordinamento molto inefficiente e non pratico, tanto che ci si chiede a cosa possa servire nella pratica. Funziona seguendo un metodo casuale: consiste nel mescolare casualmente l’intera lista e verificare, ad ogni tentativo, se è ordinata. Se la lista non è ordinata, il processo di mescolamento casuale viene ripetuto fino a quando la lista è ordinata.

Ordinare a caso, fino a quando (forse)è ordinato

Hai mai desiderato un algoritmo che incarnasse l’entropia dell’universo? Ti presentiamo il Bogosort: l’algoritmo che dice “E se provassimo a mischiare tutto finché per miracolo è ordinato?”

In altri termini, l’algoritmo Bogosort funziona in questo modo:

1. Mescola casualmente l’intera lista.
2. Verifica se la lista è ordinata.
3. Se la lista non è ordinata, ripete il mescolamento casuale.
4. Continua a ripetere il processo finché la lista non è ordinata.

Se preferisci:

1. 
   

   Prendi una lista di numeri o di elementi ordinabili (due elementi sono ordinabili se esiste un criterio per cui uno è maggiore dell’altro).

   
   
2. 
   

   Controlla se è ordinata. Lo è?

   
   
3. 
   

   Se non lo è, mischiala a caso.

   
   
4. 
   

   Ripeti dal punto 2, finché il cosmo si allinea l’algoritmo ha finito l’ordinamento per puro caso.

   
   

Si tratta di un algoritmo interessante perchè l’uso di un rimescolamento casuale introduce non determinismo e questo, naturalmente, cambia in modo radicale l’approccio algoritmico: che è deterministico quando stabiliamo che la somma di 2+2 è 4, comunque decidiamo di calcolarlo, e diventa non deterministico se introduciamo un evento non prevedibile come il rimescolamento casuale degli elementi.

Cosa che, alla prova dei fatti, è difficile anche da prevedere come esito, poichè la probabilità di ordinare N elementi casualmente è ben più alta del numero di combinazioni casuali ottenibili. Che sono N! (N fattoriale), per inciso: per cui se hai 3 elementi distinti (1, 2, 3), i possibili ordini distinti sono $in\; tutto,\; ovvero$:

1. 123
2. 132
3. 213
4. 231
5. 312
6. 321

Se hai, ad esempio, 4 elementi distinti, i possibili ordini distinti sono $4!=4\times 3\times 2\times 1=24$ ordini distinti. In un caso solo 1 combinazione su 6 sarà corretta (24% di probabilità di ordinare al primo colpo), nel caso di N=4 avremo 1 su 24 probabilità di trovare la combinazione ordinata (4% circa).

Poiché il mescolamento casuale è completamente non deterministico, nel bogosort, non c’è alcuna garanzia che l’ordinamento avverrà in un tempo ragionevole. La complessità temporale dell’algoritmo bogosort è estremamente alta, può arrivare ad essere O(N!) e può richiedere un tempo indefinito, nella pratica, per ordinare la lista non ordinata.

Bogosort in C++

Ecco un esempio di come si potrebbe implementare il Bogosort in C++

#include <iostream>
#include <algorithm>
#include <random>

// Funzione per verificare se la lista è ordinata
bool isSorted(int arr[], int size) {
for (int i = 1; i < size; ++i) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
}

// Funzione per mescolare casualmente la lista
void shuffle(int arr[], int size) {
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(arr, arr + size, g);
}

// Implementazione dell'algoritmo Bogosort
void bogoSort(int arr[], int size) {
while (!isSorted(arr, size)) {
shuffle(arr, size);
}
}

// Funzione di stampa della lista
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}

int main() {
int arr[] = {3, 1, 4, 5, 2}; // Lista da ordinare
int size = sizeof(arr) / sizeof(arr[0]);

std::cout << "Lista non ordinata: ";
printArray(arr, size);

// Ordina la lista utilizzando Bogosort
bogoSort(arr, size);

std::cout << "Lista ordinata: ";
printArray(arr, size);

return 0;
}

La funzione shuffle utilizza le funzioni fornite dalla libreria standard di C++ ( e ) per eseguire il mescolamento casuale dell’array. In breve tale funzione prende un array di numeri e li mescola casualmente utilizzando un generatore di numeri casuali, modificando così l’ordine originale.

Ecco cosa fa esattamente:

1. std::random_device rd; crea un oggetto random_device che serve come seme per il generatore di numeri casuali. Questo aiuta a generare numeri casuali veri e propri.
2. std::mt19937 g(rd()); crea un generatore di numeri casuali mt19937 (Mersenne twister) utilizzando rd() come seme. mt19937 è un motore di generazione di numeri casuali di alta qualità, usato molto spesso nella pratica (e anche, ad esempio, per generare numeri casuali in Excel).
3. std::shuffle(arr, arr + size, g); utilizza la funzione shuffle della libreria standard di C++ (che ha 4 argomenti, da non confondersi coi 3 della funzione creata). Prende l’array arr e il suo numero di elementi size e utilizza il generatore di numeri casuali g per mescolare gli elementi dell’array in modo casuale.