BOGO sort also known as stupid sort , slow sort ,monkey sort , shotgun sort and monkey sort . the name stupid is given to this sort because of its working ,
BOGO sort, short for "Bogosort," is a highly inefficient and humorously named sorting algorithm that serves more as a joke or a parody of sorting algorithms than a practical sorting method. In fact, it is often referred to as "stupid sort" precisely because of its absurdly inefficient nature.
Here's how Bogo sort works:
- Start with an unsorted list of elements that need to be sorted.
- Randomly shuffle the elements in the list.
- Check if the list is sorted. If it is, stop; otherwise, go back to step 2
- Repeat steps 2 and 3 until the list becomes sorted.
" my college pc crashes .when I run this algo on that pc for
around 1000 of data"
#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;
}
TIME COMPLEXITY
Worst-case time complexity: O(infinite)
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.
Top comments (0)