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
local function shuffle(arr)
  for i = 1, #arr-1 do
    local rand = math.random(i,#arr)
    arr[i], arr[rand] = arr[rand], arr[i]
  end
end

local function issorted(arr)
  for i = 1,#arr-1 do
    if arr[i] > arr[i+1] then
      return false
    end
  end
  return true
end

function bogosort(arr)
  while not issorted(arr) do
    shuffle(arr)
  end
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()
    }

    return sortArray
}
function bogo_sort(array $array): array
{
  if (!is_sorted($array)) shuffle($array);

  return $array;
}
proc bogo_sort(a: var openArray[int]) =
    while not is_sorted(a):
        shuffle(a)

puts "Unsorted"
p a

bogo_sort a
🐇 ❗️ 🔀 numbers 🍨🐚💯🍆 🍇
  🔁 ❎ 📶🐇🥇 numbers❗️❗️ 🍇
    🐹 numbers❗️
  🍉
🍉
USING: random ;
: bogosort ( seq -- seq' )
  ! `dup` duplicates the array, because `sorted?` pops its reference to it
SUBROUTINE bogo_sort(array)
    REAL(8), DIMENSION(:), INTENT(INOUT) :: array

    DO WHILE (is_sorted(array) .EQV. .FALSE.)

        CALL shuffle(array)

    END DO
END SUBROUTINE bogo_sort
(define (bogo_sort l)
  (if (is_sorted? l)
      l
      (bogo_sort (shuffle l))
    )
 )
SequenceableCollection>>bogoSort
    "A simple bogosort."
    [ self isSorted ] whileFalse: [ 
        self shuffle.
    ]

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

Example Code

using Random

function is_sorted(a::Vector{Float64})
    for i = 1:length(a)-1
        if (a[i] > a[i + 1])
            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;
  }
}

function main() {
  const testArray = [4, 5, 123, 24, 34, -5];
  bogoSort(testArray);
  console.log(testArray);
}

main();
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
local function shuffle(arr)
  for i = 1, #arr-1 do
    local rand = math.random(i,#arr)
    arr[i], arr[rand] = arr[rand], arr[i]
  end
end

local function issorted(arr)
  for i = 1,#arr-1 do
    if arr[i] > arr[i+1] then
      return false
    end
  end
  return true
end

function bogosort(arr)
  while not issorted(arr) do
    shuffle(arr)
  end
end

local arr = {1, 45, 756, 4569, 56, 3, 8, 5, -10, -4}
print(("Unsorted array: {%s}"):format(table.concat(arr,", ")))

bogosort(arr)

print(("Sorted array: {%s}"):format(table.concat(arr,", ")))
#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 << ", " << d; });
  }

  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 bogoSort(sortArray: inout [Int]) -> [Int] {
    while(!isSorted(inputArray: sortArray)) {
        sortArray.shuffle()
    }

    return sortArray
}

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

main()
<?php

function is_sorted(array $array): bool
{
  for ($i = 0, $count = count($array); $i < $count - 1; $i++)
    if ($array[$i] < $array[$i + 1]) return false;

  return true;
}

function bogo_sort(array $array): array
{
  if (!is_sorted($array)) shuffle($array);

  return $array;
}


$unsorted = [10, 7, 3, 1, 4, 8, 5, 6, 9, 2];
$bogo_sorted = bogo_sort($unsorted);

echo sprintf('Unsorted: %s%s', implode(',', $unsorted), PHP_EOL);
echo sprintf('Sorted: %s%s', implode(',', $bogo_sorted), PHP_EOL);
import random

randomize()

proc print_array(a: openArray[int]) =
    for n in 0 .. len(a)-1:
        echo a[n]

proc is_sorted(a: openArray[int]): bool =
    for n in 1 .. len(a)-1:
        if a[n] > a[n-1]:
            return false

    return true

proc bogo_sort(a: var openArray[int]) =
    while not is_sorted(a):
        shuffle(a)


var x: array[10,int] =  [32,32,64,16,128,8,256,4,512,2]

print_array(x)
bogo_sort(x)
echo "\n"
print_array(x)
#!/usr/bin/env ruby

def is_sorted(a)
  a.each_cons(2).all? { |(l, r)| l <= r }
end

def bogo_sort(a)
  a.shuffle! until is_sorted a
end

a = [1, 1, 0, 3, 7]

puts "Unsorted"
p a

bogo_sort a

puts "Sorted" 
p a
🐇 🥇 🍇
  🐇 ❗️ 🔀 numbers 🍨🐚💯🍆 🍇
    🔁 ❎ 📶🐇🥇 numbers❗️❗️ 🍇
      🐹 numbers❗️
    🍉
  🍉

  🐇 ❗️ 📶 numbers 🍨🐚💯🍆 ➡️ 👌 🍇
    🔂 i 🆕⏩⏩️ 1 🐔 numbers❗️❗️ 🍇
      ↪️ 🐽 numbers i ➖ 1❗️ ▶️ 🐽 numbers i❗️ 🍇
        ↩️ 👎
      🍉
    🍉
    ↩️ 👍
  🍉
🍉

🏁 🍇
  🍨 1.7 -3.0 2.5 2.0 7.0 1.5 -4.3 0.3 🍆  ➡️ numbers

  😀 🔤unordered:🔤❗️
  🔂 number numbers 🍇
    😀 🔡 number 10❗️❗️
  🍉

  🔀🐇🥇 numbers❗️

  😀 🔤ordered:🔤❗️
  🔂 number numbers 🍇
    😀 🔡 number 10❗️❗️
  🍉
🍉
! There's no built-in "is sorted" function, so let's make one:
USING: locals ;
: sorted? ( seq -- ? )
  2 clump ! split it up into overlapping pairs
  ! so now, for example, { 1 2 3 } has turned into { { 1 2 } { 2 3 } }
  ! and now we make sure that for every pair, the latter is >= the former
  [| pair | pair first pair last <= ] all?
;

USING: random ;
: bogosort ( seq -- seq' )
  ! `dup` duplicates the array, because `sorted?` pops its reference to it
  ! randomize works in-place
  ! so we `randomize` `until` it's `sorted?`
  [ dup sorted? ] [ randomize ] until
;

! WARNING: Increasing this number beyond 5 or so will make this take a very long time.
!          That said, if you have an afternoon to kill...
5 <iota> >array randomize ! generate a random array to demo
dup .                     ! show the array
bogosort                  ! bogosort it
.                         ! show it again
PROGRAM bogo
    IMPLICIT NONE
    REAL(8), DIMENSION(5) :: array

    array = (/ 1d0, 1d0, 0d0, 3d0, 7d0 /)

    CALL bogo_sort(array)

    WRITE(*,*) array 

contaINs

    LOGICAL FUNCTION is_sorted(array) 
        REAL(8), DIMENSION(:), INTENT(IN) :: array
        INTEGER                           :: i

         DO i = 1, SIZE(array)
            IF (array(i+1) < array(i)) THEN
                is_sorted = .FALSE.
            END IF
         END DO
    END FUNCTION is_sorted

    SUBROUTINE bogo_sort(array)
        REAL(8), DIMENSION(:), INTENT(INOUT) :: array

        DO WHILE (is_sorted(array) .EQV. .FALSE.)

            CALL shuffle(array)

        END DO
    END SUBROUTINE bogo_sort

    SUBROUTINE shuffle(array)
        REAL(8), DIMENSION(:), INTENT(INOUT) :: array
        INTEGER                              :: i, randpos
        REAL(8)                              :: r, temp

        DO i = size(array), 2, -1
            CALL RANDOM_NUMBER(r)
            randpos    = INT(r * i) + 1
            temp       = array(randpos)
            array(randpos) = array(i)
            array(i)       = temp
        END DO

    END SUBROUTINE shuffle
END PROGRAM bogo
#lang racket

(define (bogo_sort l)
  (if (is_sorted? l)
      l
      (bogo_sort (shuffle l))
    )
 )

(define (is_sorted? l)
  (if (> (length l) 1)
      (if (> (first l) (second l))
             false
             (is_sorted? (rest l))
         )
      true
     )
 )

(define unsorted_list '(20 -3 50 1 -6 59))
(display "unsorted list: ")
(displayln unsorted_list)
(display "sorted list: ")
(displayln (bogo_sort unsorted_list))
"Add this to the SequenceableCollection: "
SequenceableCollection>>bogoSort
    "A simple bogosort."
    [ self isSorted ] whileFalse: [ 
        self shuffle.
    ]

"Then you can run this anywhere: "
#(4 3 2 1 6 5) bogoSort "#(1 2 3 4 5 6)"

results matching ""

    No results matching ""