Bogo Sort

Look, Bogo Sort doesn't really sort anything out. In fact, it should never be used in practice for any reason I can think of and really only serves as a joke in the programming community. As far as jokes go, though, this one's pretty good.

So, here's how it goes: imagine you have an array of elements that you want sorted. One way to do it is to shuffle the array at random and hope that all the elements will be magically in order after shuffling. If they are not in order, just shuffle everything again. And then again. And again. In the best case, this algorithm runs with a complexity of , and in the worst, .

In code, it looks something like this:

function bogo_sort(a::Vector{Float64})
    while(!is_sorted(a))
        shuffle!(a)
    end
end
public static List<T> RunBogoSort<T>(List<T> list) where T : IComparable<T>
{
    while (!IsSorted(list))
        list = Shuffle(list, new Random());

    return list;
}
(defn bogo-sort [col func]
  "shuffle the collection untill it is sorted"
  (if (is-sorted col func)
    col
    (shuffle col)))
void bogo_sort(int *array, size_t n) {
    while (!is_sorted(array, n)) {
        shuffle(array, n);
    }
}
static void bogoSort(int[] arr) {
    while(!isSorted(arr)) {
        shuffle(arr);
    }
}
function bogoSort(arr) {
  while (!isSorted(arr)) {
    shuffle(arr);
  }
}
def bogo_sort(a):
    while not is_sorted(a):
        random.shuffle(a)
bogoSort :: (Ord a, RandomGen g) => g -> [a] -> [a]
bogoSort g a = fst $ head $
               filter (isSorted . fst) $
               iterate (uncurry fisherYates) (a, g)
function sorted_array = bogo_sort(array)
    while ~is_sorted(array)
        % create a list of random permutation indices
        i = randperm(length(array));
        array = array(i);
    end
    sorted_array = array;
end
template <class Iter, class Rng>
void bogo_sort(Iter const first, Iter const last, Rng& rng) {
  while (not std::is_sorted(first, last)) {
    std::shuffle(first, last, rng);
  }
}
fn bogo_sort(arr : &mut [i32]) {
    while !is_sorted(arr) {
        thread_rng().shuffle(arr);
    }
}
func bogoSort(sortArray: inout [Int]) -> [Int] {
    while(!isSorted(inputArray: sortArray)) {
        sortArray = shuffle(inputArray: &sortArray)
    }

    return sortArray
}

That's it. Ship it! We are done here!

Example Code

function is_sorted(a::Vector{Float64})
    for i = 1:length(a)-1
        if (a[i+1] > a[i])
            return false
        end
    end
    return true
end

function bogo_sort(a::Vector{Float64})
    while(!is_sorted(a))
        shuffle!(a)
    end
end

function main()
    a = [1., 3, 2,4]
    bogo_sort(a)
    println(a)
end

main()

BogoSort.cs

// submitted by Julian Schacher (jspp)
using System;
using System.Collections.Generic;

namespace BogoSort
{
    public static class BogoSort
    {
        public static List<T> RunBogoSort<T>(List<T> list) where T : IComparable<T>
        {
            while (!IsSorted(list))
                list = Shuffle(list, new Random());

            return list;
        }

        private static bool IsSorted<T>(List<T> list) where T : IComparable<T>
        {
            var sorted = true;

            for (int i = 0; i < list.Count - 1; i++)
            {
                if (!(0 >= list[i].CompareTo(list[i + 1])))
                    sorted = false;
            }
            if (!sorted)
            {
                sorted = true;
                for (int i = 0; i < list.Count - 1; i++)
                {
                    if (!(0 <= list[i].CompareTo(list[i + 1])))
                        sorted = false;
                }
            }

            return sorted;
        }

        private static List<T> Shuffle<T>(List<T> list, Random random)
        {
            for (int i = list.Count - 1; i > 0; i--)
            {
                var j = random.Next(0, i);
                var temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
            return list;
        }
    }
}

Program.cs

// submitted by Julian Schacher (jspp)
using System;
using System.Collections.Generic;

namespace BogoSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("BogoSort");
            var listBogo = new List<int>() { 1, 2, 6, 4, 9, 54, 3, 2, 7, 15 };
            Console.Write("unsorted: ");
            foreach (var number in listBogo)
                Console.Write(number + " ");
            Console.WriteLine();
            listBogo = BogoSort.RunBogoSort(listBogo);
            Console.Write("sorted: ");
            foreach (var number in listBogo)
                Console.Write(number + " ");
            Console.WriteLine();
        }
    }
}
;; earthfail
(defn is-sorted [col func]
  "return true of col is sorted in respect to func role
   like <,>,<=,>="
  (apply func col))

(defn bogo-sort [col func]
  "shuffle the collection untill it is sorted"
  (if (is-sorted col func)
    col
    (shuffle col)))
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stddef.h>

bool is_sorted(int *array, size_t n) {
    while (--n >= 1) {
        if (array[n] < array[n - 1]) {
            return false;
        }
    }

    return true;
}

void shuffle(int *array, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        int t = array[i];
        int r = rand() % n;
        array[i] = array[r];
        array[r] = t;
    }
}

void bogo_sort(int *array, size_t n) {
    while (!is_sorted(array, n)) {
        shuffle(array, n);
    }
}

int main() {
    int array[10] = {1, 3654, 78, 654, -234, -12, 4, 3, -6, -100};

    printf("Unsorted array:\n");
    for (int i = 0; i < 10; ++i) {
        printf("%d ", array[i]);
    }
    printf("\n\n");

    bogo_sort(array, 10);

    printf("Sorted array:\n");
    for (int i = 0; i < 10; ++i) {
        printf("%d ", array[i]);
    }
    printf("\n");
}
public class Bogo {
    static void bogoSort(int[] arr) {
        while(!isSorted(arr)) {
            shuffle(arr);
        }
    }

    static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if(arr[i] > arr[i + 1]) {
                return false;
            }
        }

        return true;
    }

    static void shuffle(int[] arr) {
        for (int r = arr.length - 1; r > 0; r--) {
            int i = (int) Math.floor(Math.random() * r);
            int tmp = arr[i];
            arr[i] = arr[r];
            arr[r] = tmp;
        }
    }


    public static void main(String[] args) {
        int[] test = new int[]{20, -3, 50, 1, -6, 59};

        System.out.println("Unsorted array :");
        for (int i = 0; i < test.length; i++) {
            System.out.print(test[i] + " ");
        }


        bogoSort(test);


        System.out.println("\n\nSorted array :");
        for (int i = 0; i < test.length; i++) {
            System.out.print(test[i] + " ");
        }
    System.out.println("");
    }
}
function isSorted(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      return false;
    }
  }

  return true;
}

function bogoSort(arr) {
  while (!isSorted(arr)) {
    shuffle(arr);
  }
}

function shuffle(arr) {
  for (let r = arr.length -1; r > 0; r--) {
    let i = Math.floor(Math.random() * r);
    let tmp = arr[i];
    arr[i] = arr[r];
    arr[r] = tmp;
  }
}
import random


def is_sorted(a):
    for i in range(len(a)-1):
        if a[i+1] < a[i]:
            return False
    return True

def bogo_sort(a):
    while not is_sorted(a):
        random.shuffle(a)

def main():
    a = [1., 3, 2, 4]
    bogo_sort(a)
    print(a)

main()
import           System.Random
import qualified Data.Map as M
import           Data.Map ((!))

fisherYates :: RandomGen g => [a] -> g -> ([a], g)
fisherYates a gen = shuffle 1 gen m
  where m = M.fromList $ zip [1..] a
        shuffle i g k
          | i == M.size m = (M.elems k, g)
          | otherwise     = let (j, g') = randomR (i, M.size m) g
                                k' = M.insert i (k!j) $ M.insert j (k!i) k
                            in shuffle (i+1) g' k'

isSorted :: Ord a => [a] -> Bool
isSorted = all (uncurry (<=)) . (zip <*> tail)

bogoSort :: (Ord a, RandomGen g) => g -> [a] -> [a]
bogoSort g a = fst $ head $
               filter (isSorted . fst) $
               iterate (uncurry fisherYates) (a, g)

main = do
  g <- newStdGen
  print $ bogoSort g [9, 4, 3, 2, 5, 8, 6, 1, 7]
function main()
    array = floor( rand(1,7)*100 );
    disp('Before Sorting:')
    disp(array)

    array = bogo_sort(array);
    disp('After Sorting')
    disp(array)
end

function retval = is_sorted(array)
    for i=1:length(array)-1
        if array(i) > array(i+1)
            retval = false;
            return
        end
    end
    retval = true;
end

function sorted_array = bogo_sort(array)
    while ~is_sorted(array)
        % create a list of random permutation indices
        i = randperm(length(array));
        array = array(i);
    end
    sorted_array = array;
end
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <random>

using std::begin;
using std::end;

template <class Rng>
std::vector<float> generate_input(std::size_t size, Rng& rng) {
  auto dist = std::uniform_real_distribution<>(0.0, 1.0);

  auto ret = std::vector<float>();
  std::generate_n(std::back_inserter(ret), size,
    [&rng, &dist] { return dist(rng); });

  return ret;
}

template <class Iter>
void print_range(std::ostream& os, Iter const first, Iter const last) {
  os << '{';

  if (first != last) {
    os << *first;
    std::for_each(first + 1, last, [&os] (double d) { os << ", " << *it; });
  }

  os << "}\n";
}

template <class Iter, class Rng>
void bogo_sort(Iter const first, Iter const last, Rng& rng) {
  while (not std::is_sorted(first, last)) {
    std::shuffle(first, last, rng);
  }
}

int main() {
  std::random_device random_device;
  auto rng = std::mt19937(random_device());

  auto input = generate_input(5, rng);

  print_range(std::cout, begin(input), end(input));

  bogo_sort(begin(input), end(input), rng);

  print_range(std::cout, begin(input), end(input));
}
// Submitted by jess 3jane

extern crate rand;

use rand::{thread_rng, Rng};

fn is_sorted(arr : &[i32]) -> bool {
    for i in 1..arr.len() {
        if arr[i-1] > arr[i] {
            return false;
        }
    }
    true
}

fn bogo_sort(arr : &mut [i32]) {
    while !is_sorted(arr) {
        thread_rng().shuffle(arr);
    }
}

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];
    thread_rng().shuffle(&mut v);
    println!("Original array: {:?}", v);
    bogo_sort(&mut v);
    println!("Sorted array: {:?}", v);
}
import Foundation

func isSorted(inputArray: [Int]) -> Bool {
    for i in 0..<inputArray.count-1 {
        if inputArray[i] > inputArray[i+1] {
            return false
        }
    }

    return true
}

func shuffle(inputArray: inout [Int]) -> [Int] {
    var shuffledArray = [Int]()

    for _ in 0..<inputArray.count {
        let rand = Int(arc4random_uniform(UInt32(inputArray.count)))
        shuffledArray.append(inputArray[rand])
        inputArray.remove(at: rand)
    }

    return shuffledArray
}

func bogoSort(sortArray: inout [Int]) -> [Int] {
    while(!isSorted(inputArray: sortArray)) {
        sortArray = shuffle(inputArray: &sortArray)
    }

    return sortArray
}

func main() {
    var testArray = [4,5,123,24,34,-5]
    print(bogoSort(sortArray: &testArray))
}

main()

results matching ""

    No results matching ""