Author
Dipen Dadhaniya
Engineering Manager at Interview Kickstart
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:
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.
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:
<figure “>
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.
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 being a simple method, the pseudocode for it is just three lines!
while is_sorted(Arr) is false do
random_shuffle(Arr)
return Arr
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
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.
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).
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.
Bogo sort algorithm does not require any extra space for sorting the input array.
Thus, its auxiliary space is O(1).
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.
Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar.Â
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!
———-
Article contributed by Abhinav Tiwari
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
