Vai al contenuto
Home » Guide » Ordinare a caso: guida pratica al bogosort

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.

Lo studio del Bogosort, sebbene sia un algoritmo di ordinamento inefficace e impraticabile, può essere utile per diversi motivi. Ad esempio può essere un esercizio didattico utile per capire meglio i concetti di base degli algoritmi di ordinamento, anche se in pratica non è utilizzato in applicazioni reali a causa della sua estrema inefficienza. Serve anche a:

  1. Comprendere i limiti degli algoritmi: Studiare il Bogosort aiuta a capire meglio cosa rende un algoritmo efficiente o inefficiente. È un esempio estremo di un algoritmo molto inefficiente e fornisce un confronto con algoritmi di ordinamento efficienti come Quicksort o Mergesort.
  2. Approfondire la comprensione dei criteri di confronto: L’analisi del Bogosort può approfondire la comprensione dei criteri utilizzati per valutare le prestazioni degli algoritmi di ordinamento, come il tempo di esecuzione, la complessità computazionale e l’efficienza.
  3. Apprendere i concetti di casualità / probabilità: Il Bogosort utilizza il concetto di casualità per mescolare gli elementi. Studiarlo può aiutare a comprendere meglio i concetti di casualità e probabilità nell’informatica e nei processi decisionali.
  4. Finalità educative / divertimento: In un contesto educativo o ludico, l’apprendimento del Bogosort può essere utilizzato come esercizio per esplorare gli algoritmi e comprendere le differenze tra un approccio efficiente e uno inefficace.

Come funziona il bogosort

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 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:

  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×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:

  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.

👇 Da non perdere 👇



Questo sito esiste da 4544 giorni (12 anni), e contiene ad oggi 4099 articoli (circa 3.279.200 parole in tutto) e 18 servizi online gratuiti. – Leggi un altro articolo a caso
Non ha ancora votato nessuno.

Ti sembra utile o interessante? Vota e fammelo sapere.

Il nostro network: Lipercubo - Pagare - Trovalost
Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Questo sito contribuisce alla audience di sè stesso.