Bozosort

Reading time: 20 minutes | Coding time: 5 minutes

Bozosort is a random sorting algorithms where the key idea is to swap any two elements of the list randomly and check if the list is sorted. It is similar to BogoSort with distinct differences.

The average time complexity of Bozosort is O(N!) and the space complexity is O(1).

Steps

The key idea of Bozosort is the put more intelligence in the algorithm than BogoSort. For this, in Bozosort, we randomly swap two elements at a time and check if the list is sorted.

If the correct sets of elements are swapped, the list is infact sorted. Following are the general steps:

• Step 1: Get the list
• Step 2: Check if the list is sort. If not, go to step 3 or else, go to step 5.
• Step 3: Select two random elements and swap them
• Step 4: Go to step 2
• Step 5: The list is sorted. Enjoy.

A key concern can be the type of random function to be used. In fact, any pseudo random function will work well in this case. Truely random functions do not exist, so compilers can optimize the process as well.

Pseudocode

list // list of integers or other datatype
while( ! issorted(list))
{
    i, j = select two random elements in list
    swap i and j elements
}

Example

Consider the list:

[1, 3, 2]

Now the list is not sorted. So, in order to sort it using Bozosort, we have to choose two elements.

Let us assume we selected element 1 and 2 and swap them. With this, the list becomes:

[2, 3, 1]

Note that the list becomes more unsorted as just swapping 3 and 2 would have made the list sorted. As Bozosort is random, it may not be able to select the required elements at the first go.

Next, if we select 3 and 1 and swap them, we get the following list:

[2, 1, 3]

If Bozosort selects 2 and 1 at this point and swaps them, we get the list as sorted:

[1, 2, 3]

Complexity

The average time complexity of Bozosort is O(N!) and the space complexity is O(1).

Worst case time complexity: O(Infinity)
Average case time complexity: O(N!)
Best case time complexity: O(1)

The worst case is the case when the list is never sorted as the same subset of elements are swapped which makes the list stuck in a loop. This never leads to the list being sorted.

The best case is the case when the list is already sorted or the first swap makes the list sorted.

This algorithm does not use any extra memory so it is memory efficient. Bozosort has been explained by OpenGenus.

The exact analysis of why the average case time complexity is O(N!) is more difficult than Bogosort but you will get an idea by following these insights:

• There are N elements in the list
• There will be N! permutations (arrangements of the list)
• When two elements are swapped, it leads to a different permutation. It is expected in average case that all permutations will be reached a constant number of times.
• This leads to c * N! permutations where c is a constant. On average, c will be N.
• c will be N as the particular permutation can appear from 1 to K times for K. This leads to:

c = (K * (K+1) / 2 ] / K
c = (K+1)/2

K should be N as it is the total number of elements in the list.

• This leads to (N+1)! which is same as N! in terms of complexity.

Implementation

Following is the implementation in C programming language:

// Part of iq.OpenGenus.org
#include <time.h>
#include <stdlib.h>

_Bool issorted(int list[], int length)
{
    for(int i=0; i<length; i++)
    {
        if(list[i] > list[i+1])
            return 0;
    }
    return 1;
}

int main() 
{
	int list[] = {1, 3, 2};
	int length = sizeof(list)/sizeof(int);
	
	srand(time(NULL));
    int r = rand()%length;
    int opengenus = 0;
    
    while(!issorted(list, length))
    {
        // get two indexes (OpenGenus)
        int index_1 = rand()%length;
        int index_2 = rand()%length;
        
        // Swap the above two elements (OpenGenus)
        int temp = list[index_1];
        list[index_1] = list[index_2];
        list[index_2] = temp;
        ++opengenus;
    }
    printf("Required %d swaps to get the list sorted\n", opengenus);
	return 0;
}

Output:

Required 507 swaps to get the list sorted

Note that in this case, there could be a maximum of 3 distinct swaps and 1 swap would have been enough to get the list sorted but Bozosort took 107 swaps to get it sorted.

In specific runs, it will get the correct swap in the first try itself and for larger lists, these can go worse as well.

With this, you have the complete knowledge of Bozosort. Enjoy.