bogo Sort Algorithm
The Bogo Sort algorithm, also known as "stupid sort," "slow sort," or "random sort," is an immensely inefficient sorting algorithm that is based on the generate-and-test paradigm. The algorithm works by randomly shuffling the input sequence (an array or a list) and checking if the shuffled sequence is sorted. This process is repeated until a sorted sequence is obtained. It is mainly used as an educational tool or a satirical reference for inefficient algorithms and is not suitable for practical applications due to its incredibly poor performance.
The algorithm's name, "Bogo Sort," is derived from the word "bogosort," a blend of "bogus" and "sort," reflecting its impracticality. The average-case and worst-case time complexity of this algorithm is unbounded, as there is no guarantee it will ever finish due to the random nature of the shuffling. The best-case time complexity, however, is O(n), which occurs when the input sequence is already sorted. Because of its high time complexity, Bogo Sort is rarely used in real-world scenarios, and its primary purpose is to serve as a humorous example of an inefficient sorting technique.
/*
* A simple helper function that checks, if the array is
* sorted in ascending order.
*/
// > [].isSorted()
// true
// > [1].isSorted()
// true
// > [1,2,3].isSorted()
// true
// > [3,2,1].isSorted()
// false
/* eslint no-extend-native: ["off", { "exceptions": ["Object"] }] */
Array.prototype.isSorted = function () {
const length = this.length
for (let i = 0; i < length - 1; i++) {
if (this[i] > this[i + 1]) {
return false
}
}
return true
}
/*
* A simple helper function to shuffle the array randomly in place.
*/
Array.prototype.shuffle = function () {
for (let i = this.length - 1; i; i--) {
const m = Math.floor(Math.random() * i)
const n = this[i - 1]
this[i - 1] = this[m]
this[m] = n
}
}
/*
* Implementation of the bogosort algorithm. This sorting algorithm randomly
* rearranges the array until it is sorted.
* For more information see: https://en.wikipedia.org/wiki/Bogosort
*/
function bogoSort (items) {
while (!items.isSorted()) {
items.shuffle()
}
return items
}
// Implementation of bogoSort
var ar = [5, 6, 7, 8, 1, 2, 12, 14]
// Array before Sort
console.log(ar)
bogoSort(ar)
// Array after sort
console.log(ar)
