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 finds the sorted one. The algorithm considers 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 the 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.

The 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()}")
}


The 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 a very slow algorithm. Why are we talking about it? Because it is a good example to highlight the difference between classical and quantum computers. This highly inefficient algorithm proves to be a very good algorithm on quantum computers because of entanglement.

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

Pigeonhole Sort

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions