What is bogo sort?

Bogo sort, also known as “monkey sort,” is one of the most inefficient sorting algorithms designed. It’s often used humorously to emphasize the importance of using efficient sorting algorithms for practical purposes. The name “bogo” is derived from the words “bogus” and “go,” indicating the randomness and inefficiency of this algorithm. Bogo sort has two implementations: the randomized and deterministic approaches.

Randomized bogo sort

The working principle of randomized bogo sort is as follows:

1. Random shuffling: Start by randomly shuffling the elements in the list. This step involves permuting the elements into a new, random order.

2. Check for sorting: After shuffling, check if the elements are sorted in ascending order. If they are, the sorting is complete, and the algorithm terminates.

3. Repeat until sorted: If the elements aren’t sorted, repeat the process from step 1. Continue shuffling and checking until, by pure chance, the elements happen to be sorted.

Here’s an example of the randomized bogo sort algorithm:

In the code above, the function bogo_sort takes the arr list and returns a sorted list.

• Lines 3–6: The is_sorted function is defined to check if a list is sorted in ascending order. It uses list comprehension and the all function to compare adjacent elements.

• Lines 7–10: The bogo_sort function takes the unsorted arr list as input and repeatedly shuffles the elements until the list is sorted. Inside the while loop, we check if the list is sorted using the is_sorted helper function. If it’s not sorted, we shuffle the elements using random.shuffle(arr). The loop continues until, by pure chance, the shuffled list happens to be sorted.

Deterministic bogo sort

In the deterministic approach, the randomness is replaced by a systematic generation of all possible permutations of the input list. While this deterministic approach removes the unpredictability, it amplifies the inefficiency, making it even less suitable for any serious application. The working principle of deterministic bogo sort is as follows:

1. Permutation generation: Start by generating all possible permutations of the input list using built-in permutation functions.

2. Sorting check: For each generated permutation, check which of the generated permutations is fully sorted.

3. Update list: If a sorted permutation is found, it updates the original list with the sorted permutation and terminates the process.

Here’s an example of the deterministic bogo sort algorithm:

In the code above, the deterministic_bogo_sort function takes the lst list and returns a sorted list.

• Line 1: The itertools module is imported, specifically the permutations function, which is later used to generate all possible permutations of a given sequence.

• Lines 3–5: The is_sorted function is defined utilizing a concise list comprehension and the all function to determine if a provided list is sorted in ascending order.

• Lines 7–10: The main sorting function, deterministic_bogo_sort, takes an input list and systematically explores all possible permutations using a loop. For each permutation, it checks if it’s sorted using the previously defined is_sorted function. Upon finding a sorted permutation, the original list is updated, and the function terminates with the return statement.

Complexity

Randomized

Randomized bogo sort has an average time complexity of $O((n+1)!)$, where $n$ is the number of elements in the input list. The randomness introduced by shuffling the elements until a sorted permutation is found contributes to the high time complexity. In the worst case, the algorithm could potentially run indefinitely, making it impractical for any real-world application. The space complexity is $O(1)$, as the algorithm shuffles the existing list in place without requiring additional space.

Deterministic

Deterministic bogo sort shares a similar time complexity to the randomized version, with an average case of $O(N!)$, where $N$ is the number of elements in the list. The deterministic approach systematically explores all possible permutations until a sorted one is discovered. This exhaustive search makes it highly inefficient, especially as the input size increases. Similar to the randomized version, the space complexity of deterministic bogo sort is $O(1)$ since it modifies the input list in place during the permutation generation process.

Advantages and disadvantages of bogo sort

Advantages:

• Simplicity: Bogo sort is extremely simple to understand and implement.

• Amusement: It can be fun to watch as it randomly shuffles and eventually sorts elements.

Disadvantages:

• Inefficiency: Bogo sort has an astronomically high average-case time complexity. In fact, it might never be completed for practical purposes, making it unusable for sorting tasks.

• Unpredictability: The algorithm’s runtime is entirely unpredictable, making it unsuitable for any real-world applications.

Conclusion

Bogo sort is an amusing and absurd sorting algorithm that serves as a humorous reminder of the importance of using efficient sorting algorithms for practical tasks. While it might be entertaining to watch bogo sort attempt to sort a list, it isn’t a reliable or efficient choice for actual data sorting.

In real-world scenarios, it’s essential to use well-established and efficient sorting algorithms like quick sort, merge sort, or even the built-in sorting functions provided by programming languages. These algorithms are designed to handle large datasets efficiently and reliably, making them invaluable tools in data processing and computer science.