Generates an approximation of a sorted list of integers using Simulated Annealing. Faster than Bogosort in many cases!

simulated_sort.py

#!/usr/bin/env python3
from random import random, randint, sample
from math import exp
from copy import deepcopy
from time import time


class SimulatedSort():
    def __init__(self):
        self.T = [300.0, 100.0, 70.0, 30.0, 10.0, 7.0, 3.0, 1.0]
        self.t_steps = 100

    def __call__(self, to_sort):
        self.conf = Configuration(to_sort)
        self.simulated_annealing()
        return self.conf.conf

    def simulated_annealing(self):
        new_conf = self.conf
        best_conf = deepcopy(self.conf)
        for t in self.T:
            for i in range(self.t_steps):
                old_f = new_conf.f
                new_conf.change()
                if new_conf.f < old_f or random() < exp(-(new_conf.f - old_f) / t):
                    if new_conf.f < best_conf.f:
                        best_conf = deepcopy(new_conf)
                else:
                    new_conf.revert_last_change()
            print(t, self.conf.conf, self.conf.f)


class Configuration():
    def __init__(self, conf):
        self.conf = conf
        self.update_penalty()

    def update_penalty(self):
        p = 0
        for i in range(len(self.conf) - 1):
            p += abs(self.conf[i] - self.conf[i + 1])
        self.f = p

    def change(self):
        self.x = randint(0, len(self.conf) - 1)
        self.y = randint(0, len(self.conf) - 1)
        self.conf[self.x], self.conf[self.y] = self.conf[self.y], self.conf[self.x]
        self.update_penalty()

    def revert_last_change(self):
        self.conf[self.x], self.conf[self.y] = self.conf[self.y], self.conf[self.x]
        self.update_penalty()


if __name__ == "__main__":
    l = sample(range(0, 1000), 10)
    print(l)
    a = SimulatedSort()

    start = time()
    s = a(l)
    end = time()
    sa_time = end-start
    print("finished after {:.3f}s".format(sa_time))

    print(s)
    if all(s[i] <= s[i+1] for i in range(len(s)-1)) 
            or all(s[i] >= s[i+1] for i in range(len(s)-1)):
        print("list is sorted!")
    else:
        print("not sorted!")

    start = time()
    s = sorted(l)
    end = time()
    tim_time = end-start
    print("timsort would have needed: "
          "{:.8f}s ({:.0f} times faster)".format(tim_time, sa_time/tim_time))