Come ordinare stupidamente un array

di | 15 Gennaio 2020

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)

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *