Sorting (Part 4.0): Bogo Sort

sorting
algorithm
bogosort

(oaktree) #1

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


#2

Couldn’t the Bogo Sort be a way of confusing a person who’d try to reverse engineer the program, or whatever it is that the
Bogo Sort is included in?


(oaktree) #3

What do you mean? Who’d reverse-engineer a sorting algo when the source code is all over the internet?


#4

Well, although it is all over the internet, I’m sure that’s never stopped people from making newer and better versions on the internet. Similarly to what you see with viruses today, many virus makers borrowed newer concepts from the older ones, in order to further improve their virus.


(oaktree) #5

Oh… I should clear this up: Bogo sort is a joke. Nobody uses it in the real world. It could technically take infinite time to finish.


#6

Well I guess then it’d be perfect for making someone confused, eh? I mean if someone was trying to reverse-engineer something, then the bogo sort would just be a waste of time for them to find out what it does. And if it really is a joke I guess it’d be fun to include it in your code just to poke some fun :stuck_out_tongue:


(oaktree) #7

Well, it’s code you’d never run nor use; a modern compiler would likely omit it from the object file (compiled program). Including it would be a waste, really, of your time only.


#8

Well said. Guess I was being ignorant to some extent on that one :blush:


(Command-Line Ninja) #9

No! Get out! Bogo would be perfect for a memory and CPU exhaustion program!


(Ne0_) #10

Leave it to Ruby programmers to use a question mark in a method name :smiley:

Anyway, Bogo Sort implementation are often part of a computer science course. So thank you for the introducton to this topic. You even used two different languages and all that, good work.


(oaktree) #11

Well, if you have it sort 1000 chars, you’ll be sitting there for a while… Also you could run the Ackermann function on large numbers (or negative numbers).


#12

h8ters gon h8te.

And technically, it’s the only sorting algorithm which can sort everything in one round.


(Command-Line Ninja) #13

LOL - DTM Knows whats going down…


(oaktree) #14

Lol @dtm yes, that is technically true. But us programmers are all caught up in the worst-case time complexity, which is infinity!


#15

Don’t let your dreams be dreams.


(random-man) #16

This just made my day :slight_smile: . What an ass backwards algorithm


(oaktree) #17

This topic was automatically closed after 30 days. New replies are no longer allowed.