Bogo Sort in Kotlin

BogoSort also known as permutation sort, stupid sort, slow sort, shotgun sort or monkey sort is a particularly ineffective algorithm based on generate and test paradigm. The algorithm successively generates permutations of its input until it finds one that is sorted.

Bogosort is an algorithm used as a demonstration of the least effective approach to sort a list of values. The Bogosort is only a theoretical concept, which has no use in practical applications.

The algorithm keeps generating permutations of its input until it find the sorted one. The algorithm consider every permutation, it has O(N!) running time complexity. There are two ways of generating the permutations:

  • deterministic version: enumerate all permutations until it hits a sorted one
  • stochastic: we generate the permutations at random

So let’s see a concrete illustration. We have 5 integers we want to sort with bogo sort. We generate random permutations of the integers.

How many possible permutations are there?
For 5 numbers, there are 5! permutations. So in worst case scenario, we have to consider all of the 120 possible solutions.

bogo-sort-kotlin

Complexity

  • Worst case time complexity: O((N+1)!)
  • Average case time complexity: O((N+1)!)
  • Best case time complexity: O(N)
  • Space complexity: O(1)

Strand Sort

Let’ take a look at the implementation. As you may guess it is quite easy to implement bogo sort in kotlin. We have a one-dimensional array we want to sort. So we keep generating new permutations with the shuffle() method.

The only problematic part of the code is the shuffle method. Here we use Fisher-Yates algorithm to do so. Let’s take a look at the implementation of this approach.

Compete program of Bogo sort in kotlin


const val RAND_MAX = 32768 // big enough for this
val rand = java.util.Random()

fun isSorted(a: IntArray): Boolean {
    val n = a.size
    if (n < 2) return true
    for (i in 1 until n) {
        if (a[i] < a[i - 1]) return false
    }
    return true
}

fun shuffle(a: IntArray) {
    val n = a.size
    if (n < 2) return
    for (i in 0 until n) {
        val t = a[i]
        val r = rand.nextInt(RAND_MAX) % n
        a[i] = a[r]
        a[r] = t
    }
}

fun bogosort(a: IntArray) {
    while (!isSorted(a)) shuffle(a)
}

fun main(args: Array<String>) {
    val a = intArrayOf(1, 10, 9,  7, 3, 0)
    println("Before sorting : ${a.contentToString()}")
    bogosort(a)
    println("After sorting  : ${a.contentToString()}")
}


Output of the Bogo sort in kotlin


Before sorting : [1, 10, 9, 7, 3, 0]
After sorting  : [0, 1, 3, 7, 9, 10]	

Generic Constraints in Kotlin

Gnome Sort

Conclusion of Bogosort with Kotlin

OK, so we have come to the conclusion that it is very slow algorithm. Why are we talking about it? Because it is a good example to highlight the difference between classical and quantuum computers. This highly inefficient algorithm proves to be a very good algorithm on quantuum computers because of entanglement.

Quantuum entanglement will enable us to check the permutations simultaneously instead of checking one after another sequentially. So on quantuum computers, bogo sort will have O(1) running time!

Pigeonhole Sort

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group