Sorting algorithms are a must-know for any software engineer preparing for a technical interview. They will help you crack many questions during your coding round.
Bogo sort, while not necessarily a useful or effective sorting algorithm, is an interesting algorithm to learn in theory. In this article, we’ll give you a refresher on the bogo sort algorithm:
What Is Bogo Sort?
How Does Bogo Sort Work?
Bogo Sort Algorithm
Bogo Sort Pseudocode
Bogo Sort Code
Bogo Sort Complexities
Advantages of Bogo Sort
Disadvantages of Bogo Sort
FAQs on Bogo Sort
What Is Bogo Sort?
Bogo sort is an algorithm used to sort the elements of an array by randomly generating different permutations of an array and then checking whether it is sorted or not. It’s based on the generate-and-test paradigm. Other names for bogo sort include permutation sort, stupid sort, slow sort, shotgun sort, or monkey sort.
Although bogo sort is a highly inefficient sorting algorithm, it finds some use in quantum computing — check out “Quantum Bogo Sort” if you’re intrigued.
How Does Bogo Sort Work?
Let’s assume that the array Arr[] = {2, 3, 1, 2, 4} is to be sorted using bogo sort.
First, we check if the array is already sorted (which it isn’t, in the above case).
We then generate a random permutation of the array and check again if the array is sorted or not. This is repeated until we get a sorted array.
For example:
In the above example, we got the sorted array in the third permutation, However, this might not be the case always. The number of permutations or steps taken to get the sorted array may be anywhere between 1 and infinity.
There’s no guarantee that we will get the sorted array after shuffling the array a certain number of times. However, the probability of it running infinitely is very low. Given enough time, bogo sort will eventually return the sorted array.
Also note, permutations 1 and 2 seen in the above example will differ every time the program is run, even for the same array, as they are generated randomly.
Bogo Sort Algorithm
Repeat the below two steps until the array is sorted:
Step 1: Check if the array is already sorted or not. If yes, then print the array, else Step 2: Generate a random permutation (not necessarily different from previously generated) and go to Step 1.
Bogo Sort Pseudocode
Bogo sort being a simple method, the pseudocode for it is just three lines!
while is_sorted(Arr) is false do
random_shuffle(Arr)
return Arr
Bogo Sort Code
We’ve used C++ to demonstrate how bogo sort works. Use this as a reference code to code in C, Java, Python, or any programming language of your choice.
#include<bits/stdc++.h>
using namespace std;
bool isSorted(int Arr[], int N)
{
for(int i=1; i<N; i++)
{
if(Arr[i] < Arr[i-1])
return false;
}
return true;
}
void randomly_shuffle(int Arr[], int N)
{
for(int i = 0; i < N; i++)
{
swap(Arr[i], Arr[rand() % N]);
}
}
int main()
{
int N = 4;
int Arr[N] = {2, 13, 7, 1};
// isSorted() function return true if array
// is sorted else it returns false
while(!isSorted(Arr, N))
{
// randomly_shuffle() function generates a
// random permutation of array
randomly_shuffle(Arr, N);
}
for(int i = 0; i < N; i++)
cout << Arr[i] << " ";
return 0;
}
Output:
1 2 7 13
Bogo Sort Complexities
Time Complexity
Worst-case time complexity: O(infinite)
It is not guaranteed that we get the sorted permutation at some point after shuffling the array a certain number of times. Although its probability is infinitesimally low, there’s a chance that we do not get the sorted order even after gazillions of shuffling.
Average-case time complexity: O(n! * n)
There are n! permutations, only one of which is sorted. So, we would expect to get the correct answer after about O(n!) iterations. And each shuffle/check operation is itself O(n).
Best-case time complexity: O(n)
When the given array is already sorted, the program terminates just after checking if the array is sorted once, which takes O(n) time to execute.
Space Complexity
Bogo sort algorithm does not require any extra space for sorting the input array.
Thus, its auxiliary space is O(1).
FAQs on Bogo Sort
Question 1: Is bogo sort stable?
Answer: No, bogo sort is not an example of a stable sorting algorithm, as there is no guarantee that randomly generated sorted permutations have the same relative order of elements of the same value as in the input or not.
Question 2: Is bogo sort an in-place sorting algorithm?
Answer: Yes, bogo sort is an in-place sorting algorithm as it takes only O(1) auxiliary space.
Question3: Why is using bogo sort not practical?
Answer: Since the worst-case time complexity of bogo sort is O(infinite), there is no practical use of bogo sort.
As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
.png)
