Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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.
For example, if bogosort is used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, one would throw the deck into the air, pick the cards up at random, and repeat the process until the deck is sorted.
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)
Implementation
Implementation of Linear search algorithm in 5 languages that includes C, C++, Java, Go and Swift.
- C
- C++
- Java
- Go
- Swift
C
/* Part of cosmos by OpenGenus Foundation */
/*
* bogo_sort.c
* created by Riya
*/
#include <stdio.h>
#include <stdlib.h>
int
main()
{
int num[10]={1, 4, 7, 5, 9, 2, 6, 3, 8, 0};
int i;
bogosort(num, 10);
printf("The array after sorting is:");
for (i = 0;i < 10;i++) {
printf("%d\n", num[i]);
} printf("\n");
}
int
is_sorted(int *a, int n)
{
while ( --n >= 1 ) {
if ( a[n] < a[n-1] )
return (0);
}
return (1);
}
void
shuffle(int *a, int n)
{
int i, t, temp;
for (i = 0;i < n;i++) {
t = a[i];
temp = rand() % n;
a[i] = a[temp];
a[temp] = t;
}
}
void
bogosort(int *a, int n)
{
while ( !is_sorted(a, n) )
shuffle(a, n);
}
C++
/* Part of Cosmos by OpenGenus Foundation */
// C++ implementation of BogoSort by ldaw
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
bool isSorted(const std::vector<int> &v)
{
int i = v.size();
while (--i > 0)
if (v[i] < v[i-1])
return false;
return true;
}
void shuffle(std::vector<int> &v)
{
for (size_t i = 0; i < v.size(); i++)
std::swap( v[i], v[ rand() % v.size() ] );
}
void bogoSort(std::vector<int> &v)
{
while ( !isSorted(v) )
shuffle(v);
}
int main()
{
std::srand(time(NULL));
std::vector<int> v = {2, 4, 1, 3, 6, 7, 8, 5};
// Please note, initializer lists are a C++11 feature
bogoSort(v);
for(size_t i = 0; i < v.size(); ++i)
std::cout << v[i] << " ";
return 0;
}
Java
public class Bogosort {
public static void main(String[] args) {
if (args.length == 1) {
String[] arr = args[0].split(",");
Integer[] intArr = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
intArr[i] = Integer.parseInt(arr[i]);
}
intArr = sort(intArr);
for (int i = 0; i < arr.length; i++) {
arr[i] = intArr[i].toString();
}
System.out.println(String.join(", ", arr));
} else {
System.out.println("An array needs to be passed in!");
}
}
public static boolean isSorted(Integer[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
};
public static Integer[] shuffle(Integer[] arr) {
String[] strArr = new String[arr.length];
Integer count = arr.length, temp, index;
while (count > 0) {
index = (int)(Math.random() * count);
count--;
temp = arr[count];
arr[count] = arr[index];
arr[index] = temp;
}
for (int i = 0; i < arr.length; i++) {
strArr[i] = arr[i].toString();
}
System.out.println(String.join(", ", strArr));
return arr;
}
public static Integer[] sort(Integer[] arr) {
boolean sorted = false;
while (!sorted) {
arr = shuffle(arr);
sorted = isSorted(arr);
}
return arr;
}
}
Go
//Part of Cosmos Project by OpenGenus Foundation
//Bogo Sort implementation on golang
//Written by Guilherme Lucas(guilhermeslucas)
package main
import (
"fmt"
"sort"
"math/rand"
)
func shuffle(arr []int) []int {
for i := range arr {
j := rand.Intn(i + 1)
arr[i], arr[j] = arr[j], arr[i]
}
return arr
}
func bogoSort (array []int) []int {
for {
if sort.IntsAreSorted(array) {
return array
}
array = shuffle(array[:])
}
}
func main() {
var array = []int{1,5,8,2,6,9}
sorted := bogoSort(array)
fmt.Println("Sorted sequence is:", sorted)
}
Swift
/* Part of Cosmos by OpenGenus Foundation */
//
// bogo_sort.swift
// Created by DaiPei on 2017/10/14.
//
import Foundation
func bogoSort(_ array: inout [Int]) {
while !isSorted(array) {
shuffle(&array)
}
}
private func shuffle(_ array: inout [Int]) {
for i in 0..<array.count {
let j = Int(arc4random()) % array.count
swap(&array, at: i, and: j)
}
}
private func isSorted(_ array: [Int]) -> Bool {
if array.count <= 1 {
return true
}
for i in 1..<array.count {
if array[i] < array[i - 1] {
return false
}
}
return true
}
private func swap(_ array: inout [Int], at indexA: Int, and indexB: Int) {
let tmp = array[indexA]
array[indexA] = array[indexB]
array[indexB] = tmp
}
