What Is Bogo Sort?
Bogo Sort is a sorting algorithm that is not used in production at all. Why? Because it’s extremely stupid. Some even call it “Stupid Sort.”
The algorithm works by generating random permutations of an inputted array-to-sort. Then, it checks to see if the randomly generated permutation is sorted. If so, it returns that sorted array and exits; otherwise, it makes another permutation.
Worst-Case Time Complexity: O( (n+1)! ) because of all the possible permuting.
Best-Case Time Complexity: o(n) if the array-to-sort is already sorted.
Note: Bogo Sort can generate the same permutation more than once in a run, thus wasting even more of our time.
Ruby Implementation
class Array
def sorted?
### goes thru array and checks if all elements are in order
for i in 1...self.length
return false if self[i-1] > self[i]
end
return true
end
def bogosort
### randomly shuffles until sorted
self.shuffle! until self.sorted?
return self #return sorted array
end
end
puts "give me a string"
str = gets.chomp.split('')
puts str.bogosort.join('')
I’ll tell you that I got inspiration for this implementation from various parts of the internet – and probably Wikipedia.
So, anyway, I’ve extended Ruby’s Array class to have a few extra methods: sorted? and bogosort.
I hope that you all can infer what sorted? does; yet, if not, I’ll tell you that it ensures that all the elements are in order… and, yes, I’m that guy who uses for loops in Ruby.
Okay, so bogosort basically just uses a built-in shuffle method to get a new permutation of the array-to-sort and stops shuffling when the array-to-sort is sorted. Simple enough.
C++ Version
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
bool is_sorted(const vector<char>& vec) {
for (int i = 1, n = vec.size(); i < n; i++) {
if (vec[i-1] > vec[i]) return false;
// returns false if an element is smaller than one to its left
}
return true;
}
void shuffle(vector<char>& vec) {
int i,n, tmp, rand_idx;
for(i = 0, n = vec.size(); i < n; i++) {
tmp = vec[i]; // store temporarily
rand_idx = rand() % n; // pick a random index in the vector/array
// swap each element in vector/array with another one that is chosen randomly
vec[i] = vec[rand_idx];
vec[rand_idx] = tmp;
}
}
void bogosort(vector<char>& vec) {
while( !is_sorted(vec) ) shuffle(vec);
}
int main() {
cout << "give me a string" << endl;
string s; getline(cin, s);
vector<char> vec(s.begin(), s.end());
if (!vec.empty()) bogosort(vec);
string str(vec.begin(), vec.end());
cout << str << endl;
return 0;
}
The deal is the same for is_sorted(...) as it was for our Ruby implementation’s sorted?.
In our C++ implementation, however, I actually define my own shuffle function. Basically, it swaps an element in our vector/array with another, randomly-chosen one to create a fresh permutation. Of course, it could potentially do the same thing twice.
The actual bogosort(...) function does the same thing in this C++ version as our Ruby version did.
Conclusion
That’s it for Bogo/Stupid/Monkey Sort.
You can check out this cool Stack Overflow post for some more crazy sorting algorithms.
Leave a comment if you have a question.
See you all later,
oaktree
. What an ass backwards algorithm