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:
- Mescola casualmente l’intera lista.
- Verifica se la lista è ordinata.
- Se la lista non è ordinata, ripete il mescolamento casuale.
- Continua a ripetere il processo finché la lista non è ordinata.
Si tratta di un algoritmo interessante perchè l’uso di un rimescolamento casuale introduce un certo 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 3!=3×2×1=6:
Usa il codice
189ed7ca010140fc2065b06e3802bcd5
per ricevere 5 € dopo l'iscrizione
- 123
- 132
- 213
- 231
- 312
- 321
Se hai, ad esempio, 4 elementi distinti, i possibili ordini distinti sono 4!=4×3×2×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:
- 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.
- 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).
- 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.
👇 Contenuti da non perdere 👇
- Gratis 🎉
- Lavoro 🔧
- Programmare 🖥
- Reti 💻
- Sicurezza & Privacy 👁
- 💬 Il nostro canale Telegram: iscriviti
- 🔴 Domini .farm: come e dove registrarli
- 🟠 Cosa vuol dire match point
- 🟢 Come installare CloudFlare sul proprio sito