Hacker News new | ask | show | jobs
by im2w1l 3782 days ago
Has anyone analyzed the MCMC version?

    while not sorted:
        swap(a[rand(n)], a[rand(n)])
2 comments
rwmj 3782 days ago
IIUC that's covered in the paper, as bozo-sort (or bozo-sort+ if the two random numbers are different).
link
im2w1l 3782 days ago
I think it may helpful to decompose the permutation into circles, and create an equation system of time left from different states.
link