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
{
    while (!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.
    ]
bogo_sort() {
    local arr
    arr=("[email protected]")
    while [[ $(is_sorted "${arr[@]}") == 0 ]]; do
        arr=($(shuffle "${arr[@]}"))
    done
    echo ${arr[*]}
}
# rdi - array ptr
# rsi - array size
bogo_sort:
  push   r12
  push   r13
  mov    r12, rdi
  mov    r13, rsi
bogo_sort_loop:
  mov    rdi, r12                         # Check if the array is sorted
  mov    rsi, r13
  call   is_sorted
  test   rax, rax
  jnz    bogo_sort_done
  mov    rdi, r12                         # If not then shuffle
  mov    rsi, r13
  call   shuffle
  jmp    bogo_sort_loop
bogo_sort_done:
  pop    r13
  pop    r12
  ret
(defun bogo-sort (list)
  "Sorts a given list (eventually)"
  (if (sortedp list)
      list
      (bogo-sort (shuffle list))))
def bogo_sort!(a)
  while !is_sorted?(a)
    a.shuffle!
  end
end
bogo_sort <- function(a) {
  while(is.unsorted(a)) {
    a <- sample(a)
  }
  return(a)
}

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.0, 3.0, 2.0, 4.0]
    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
declare(strict_types=1);

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
{
    while (!is_sorted($array)) {
        shuffle($array);
    }

    return $array;
}


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

printf('Unsorted: %s', implode(',', $unsorted));
echo PHP_EOL;
printf('Sorted: %s', implode(',', $bogo_sorted));
echo 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)"
#!/usr/bin/env bash
is_sorted() {
    local arr
    local len
    local i
    local sorted
    arr=("[email protected]")
    (( len = ${#arr[@]} - 1))
    (( sorted = 1 ))

    for (( i = len; i > 0; i-- )); do
        if (( arr[i] < arr[(( i - 1 ))] )); then
            (( sorted = 0 ))
            break
        fi
    done
    printf "%d" $sorted
}

shuffle() {
    local arr
    local len
    local i
    local tmp
    local rand
    arr=("[email protected]")
    (( len = ${#arr[@]} ))

    for (( i = 0; i < len; i++ )); do
        (( rand = RANDOM % len ))
        (( tmp = arr[rand] ))
        (( arr[rand] = arr[i] ))
        (( arr[i] = tmp ))
    done
    echo ${arr[*]}
}

bogo_sort() {
    local arr
    arr=("[email protected]")
    while [[ $(is_sorted "${arr[@]}") == 0 ]]; do
        arr=($(shuffle "${arr[@]}"))
    done
    echo ${arr[*]}
}

arr=(1 3654 78 654 -234 -12 4 3 -6 -100)
echo "Unsorted array: ${arr[*]}"
arr=("$(bogo_sort "${arr[@]}")")
echo "Sorted array: ${arr[*]}"
.intel_syntax noprefix

.section .rodata
  array:
    .align 16
    .int 1, 3654, 78, 654, -234, -12, 4, 3, -6, -100
    .equ array_len, (.-array) / 4
  array_fmt: .string "%d "
  lf:        .string "\n"
  unsorted:  .string "Unsorted array: "
  sorted:    .string "Sorted array: "

.section .text
  .global main
  .extern printf, rand, srand

# rdi - array ptr
# rsi - array size
print_array:
  push   r12
  push   r13
  mov    r12, rdi                 # Loop variable
  lea    r13, [rdi + 4 * rsi]     # Pointer after the last element
print_array_loop:
  cmp    r12, r13                 # If we're done iterating over the array then bail
  jge    print_array_done
  mov    rdi, OFFSET array_fmt    # Otherwise print the current value
  mov    esi, DWORD PTR [r12]
  xor    rax, rax
  call   printf
  lea    r12, [r12 + 4]           # And increment the loop variable pointer
  jmp    print_array_loop
print_array_done:
  mov    rdi, OFFSET lf           # Print a closing newline
  xor    rax, rax
  call   printf
  pop    r13
  pop    r12
  ret

# rdi - array ptr
# rsi - array size
# RET rax - boolean
is_sorted:
  sub    rsi, 1                   # Getting array + n and *array + n - 1
  lea    rcx, [rsi - 1]
  lea    rcx, [rdi + 4 * rcx]
  lea    rsi, [rdi + 4 * rsi]
is_sorted_loop:
  cmp    rsi, rdi                 # Check if array + n - 1 == array
  je     is_sorted_done
  mov    edx, DWORD PTR [rsi]     # Load value to register
  xor    rax, rax                 # Set rax to 0
  cmp    edx, DWORD PTR [rcx]     # Check if array[n] < array[n - 1]
  jl     is_sorted_return
  sub    rcx, 4                   # If not make pointers go to down an element
  sub    rsi, 4
  jmp    is_sorted_loop
is_sorted_done:
  mov    rax, 1                   # If sorted then set rax to 1
is_sorted_return:
  ret                             # Return

# rdi - array ptr
# rsi - array size
shuffle:
  push   r12
  push   r13
  push   r14
  push   r15
  mov    r12, rdi                          # Save parameters
  mov    r13, rsi
  xor    r14, r14
shuffle_loop:
  cmp    r14, r13                          # Check if i == array size
  je     shuffle_done
  mov    r15d, DWORD PTR [r12 + r14 * 4]   # Save array[i]
  call   rand                              # Swap a random element with array[i]
  xor    edx, edx
  div    r13                               # Mod random number to keep in array
  mov    eax, DWORD PTR [r12 + rdx * 4]
  mov    DWORD PTR [r12 + r14 * 4], eax
  mov    DWORD PTR [r12 + rdx * 4], r15d
  add    r14, 1                            # increment then repeat
  jmp    shuffle_loop
shuffle_done:
  pop    r15
  pop    r14
  pop    r13
  pop    r12
  ret

# rdi - array ptr
# rsi - array size
bogo_sort:
  push   r12
  push   r13
  mov    r12, rdi
  mov    r13, rsi
bogo_sort_loop:
  mov    rdi, r12                         # Check if the array is sorted
  mov    rsi, r13
  call   is_sorted
  test   rax, rax
  jnz    bogo_sort_done
  mov    rdi, r12                         # If not then shuffle
  mov    rsi, r13
  call   shuffle
  jmp    bogo_sort_loop
bogo_sort_done:
  pop    r13
  pop    r12
  ret

main:
  # Set up our stack
  sub    rsp, 40
  # We load the array in chunks onto the stack
  movaps xmm0, XMMWORD PTR [array]
  movaps XMMWORD PTR [rsp], xmm0
  movaps xmm0, XMMWORD PTR [array + 16]
  movaps XMMWORD PTR [rsp + 16], xmm0
  mov    rax, QWORD PTR [array + 32]
  mov    QWORD PTR [rsp + 32], rax
  # Print the unsorted array
  mov    rdi, OFFSET unsorted
  xor    rax, rax
  call   printf
  mov    rdi, rsp
  mov    rsi, array_len
  call   print_array
  # Sort
  mov    rdi, rsp
  mov    rsi, array_len
  call   bogo_sort
  # Print the sorted array
  mov    rdi, OFFSET sorted
  xor    rax, rax
  call   printf
  mov    rdi, rsp
  mov    rsi, array_len
  call   print_array
  # Restore the stack pointer, set return value to 0
  add    rsp, 40
  xor    rax, rax
  ret
;;;; Bogo sort implementation

(defun sortedp (list)
  "Checks if a list is sorted"
  (if (< (length list) 2)
      t
      (if (<= (first list) (second list))
          (sortedp (rest list))
          nil)))

(defun shuffle (list)
  "Returns a shuffled list using the Fisher-Yates method"
  (loop for i from (1- (length list)) downto 0
    do
      (rotatef 
        (nth i list)
        (nth (random (1+ i)) list))
    finally (return list)))

(defun bogo-sort (list)
  "Sorts a given list (eventually)"
  (if (sortedp list)
      list
      (bogo-sort (shuffle list))))

(print (bogo-sort (list 1 3 2 4)))
def is_sorted?(a)
  0.upto(a.size - 2) do |i|
    if a[i] > a[i + 1]
      return false
    end
  end
  true
end

def bogo_sort!(a)
  while !is_sorted?(a)
    a.shuffle!
  end
end

def main
  a = [1.0, 3.0, 2.0, 4.0]
  bogo_sort!(a)
  puts a
end

main
bogo_sort <- function(a) {
  while(is.unsorted(a)) {
    a <- sample(a)
  }
  return(a)
}

test <- c(20, -3, 50, 1, -6, 59)

print("unsorted list")
print(test)

print("sorted list")
print(bogo_sort(test))

results matching ""

    No results matching ""