Derandomizing Bogosort: A Very Serious Webpage

Bogosort is an algorithm famous for its average-case runtime complexity of of about $\mathcal{O}((n+1)!)$, and its conceptual simplicity. Roughly speaking, the alggorithm is:

def bogosort(L):
    while not is_sorted(L):
        L = random_shuffle(L)
    
    return L[:]

Derandomization is the process of removing the randomness element from an algorithm. As it happens, randomness is not essential to Bogosort: we can use enumeration to derandomize it.

def all_permutations(L):
    if len(L) == 0:
        return [[]]
    
    res = []
    for i in range(len(L)):
        all_i = all_permutations(L[:i] + L[i+1:])
        for p in all_i:
            res.append([L[i]]+p)
    return res
    
def is_sorted(L):
    for i in range(1, len(L)):
        if L[i] < L[i-1]:
            return False
    return True

def derandomized_bogosort(L):
    perms = all_permutations(L)
    for perm in perms:
        if is_sorted(perm):
            return perm
            

Same algorithm, but without the randomness! It works, too:

derandomized_bogosort([102, 180, 194, 103, 101])

[101, 102, 103, 180, 194]

Derandomizing Bozosort

Bozosort is easier to implement than Bogosort: instead of randomly shuffling the array, we randomly swap two if its elements.

def bozosort(L):
    while not is_sorted(L):
        i, j = random.random(), random.random()
        L[i], L[j] = L[j], L[i]
    return L

Can Bozosort be derandomized?

Yes, although it's not as easy.

The Steinhaus–Johnson–Trotter algorithm allows us to enumerate all the permutation of our array by constructing Hamiltonian path through the graph all permutations of the array where permutations are connected if they are one element swap apart.