Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Interview Kickstart has enabled over 3500 engineers to uplevel.

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

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:**

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

- 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.

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*

Attend our webinar on

"How to nail your next tech interview" and learn

Hosted By

Ryan Valles

Founder, Interview Kickstart

Our tried & tested strategy for cracking interviews

The 4 areas you must prepare for

How you can accelerate your learnings