Bogo Sort (also known as Nonsense sort or Permutation Sort) is an extremely ineffective random sorting algorithm that tries to sort a sequence that needs to be sorted by generating random permutations and making comparisons until the correct order is found. Bogo Sort originated as a joke algorithm and is not suitable for practical use.

Working Logic and Algorithm Steps:

The working logic of Bogo Sort is quite simple, but it works ineffectively:

1. A random permutation is generated.
2. It is checked whether the array is sequential or not.
3. If the sequence is not ordered, go back to step 1 and generate a new random permutation.
4. The algorithm terminates when the sequence is ordered.

Pros:

• It can be seen as a fun and interesting algorithm.
• It can work on any array because it doesn’t care if it’s sequential or not.

Cons:

• Bogo Sort is extremely inefficient as it generates random permutations. The number of steps required to correctly order the array at nearly every step can be average and, in the worst cases, astronomical.
• Not suitable for practical use. The running time of the algorithm increases rapidly as the size of the array increases.
• Does not have a good time and memory complexity.

Comparison of Time and Algorithm Complexity:

The mean and worst case time complexity of Bogo Sort is quite high. In the mean case n! steps may be required. Even in the best case it cannot provide O(n) time complexity.

Other sorting algorithms generally offer more efficient and practical results:

• Basic sorting algorithms like Bubble Sort, Selection Sort have at least O(n^2) time complexity, but they are better than Bogo Sort’s speed.
• More efficient algorithms such as Merge Sort, Quick Sort have O(n log n) time complexity and provide fast results even with larger arrays.
• Some special case-optimized algorithms can be used to achieve faster results (such as Counting Sort or Radix Sort).

In general, Bogo Sort is seen more as an algorithm for entertainment or education and is not a preferred sorting algorithm in real-world applications.

Implementation of Bogo Sort Algorithm in GoLang:

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

func isSorted(arr []int) bool {
	n := len(arr)
	for i := 1; i < n; i++ {
		if arr[i] < arr[i-1] {
			return false
		}
	}
	return true
}

func shuffle(arr []int) {
	n := len(arr)
	rand.Seed(time.Now().UnixNano())
	for i := n - 1; i > 0; i-- {
		j := rand.Intn(i + 1)
		arr[i], arr[j] = arr[j], arr[i]
	}
}

func bogoSort(arr []int) {
	for !isSorted(arr) {
		shuffle(arr)
	}
}

func main() {
	arr := []int{4, 2, 7, 1, 9, 3, 5}
	fmt.Println("Original Array:", arr)

	bogoSort(arr)
	fmt.Println("Sorted Array:", arr)

	// Checking with built-in sorting for verification
	sortedArr := []int{4, 2, 7, 1, 9, 3, 5}
	sort.Ints(sortedArr)
	fmt.Println("Sorted Array (using built-in sort):", sortedArr)
}

In this example, the bogoSort function implements the Bogo Sort algorithm. The isSorted function checks if an array is sorted. The shuffle function shuffles the array. An array is created in the main main function, which is first sorted with Bogo Sort, then sorted using Go’s built-in sort function for validation.

When the program is run, the output will be as follows.

Original Array: [4 2 7 1 9 3 5]
Sorted Array: [1 2 3 4 5 7 9]
Sorted Array (using built-in sort): [1 2 3 4 5 7 9]

The running version of the program can be accessed from here.

Resources

• https://en.wikipedia.org/wiki/Bogosort
• https://www.interviewkickstart.com/learn/bogo-sort-algorithm