Ordinamenti. Se avete fatto un corso di algoritmi ne conoscerete sicuramente molti, se non l’avete fatto sappiate semplicemente che per ordinare una lista ci sono vari modi, più o meno efficienti. E solitamente chi vuole fare ordinamenti cerca il migliore.
Ma esiste anche un metodo dichiaratamente stupido per ordinare un array, ed è detto proprio “stupid sort”. Si basa su un principio semplice: Verificare se l’array è ordinato e se non lo è mischiarlo random.
Capirete che è completamente probabilistico: Il medesimo array si potrebbe ordinare in secondi, in minuti o addirittura mai. Giusto per esempio con un piccolo test ho ordinato il medesimo array, [21,7,55,13,22,49,190,19,39] , prima in 2’092’640 passi e poi in 236’903. Un ordine di grandezza di differenza.
Se volete prodigarvi a stupidsortare qualcosa ecco il breve codice python che lo implementa:
import random
a = []
i = 0
while (a != sorted(a)):
i = i+1
random.shuffle(a)
print(a)
print(i)
