Ordinare 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.

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.

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.