Instruction

Code for Bogosort

Python

You'll need a load.py file saved in the same directory as the bogosort.py file, with the following contents:

# You call this function with the path to a file you want to load.
# It loads the file contents, converts each line from a string to
# an integer, and returns them all as a Python list.
def load_numbers(file_name):
  numbers = []
  with open(file_name) as f:
    for line in f:
      numbers.append(int(line))
  return numbers

Here's the code for bogosort.py itself:

# The function that randomizes the order of the list is kept in the
# "random" module, so we need to import that here.
import random
# The sys.argv list gives us the command line arguments to the
# script. To use it, we also need to import the "sys" module.
import sys
# Here's where we import the load_numbers function from above.
from load import load_numbers

# And here, we pass the first command line argument (which should be
# the path to a file) to load_numbers, and store the returned list of
# numbers in a variable.
numbers = load_numbers(sys.argv[1])

# Bogosort just randomly rearranges the list of values over and over,
# so the first thing it's going to need is a function to detect when
# the list is sorted. We'll write an is_sorted function that takes a
# list of values as a parameter. It will return True if the list
# passed in is sorted, or False if it isn't.
def is_sorted(values):
  # We'll loop through the numeric index of each value in the list,
  # from 0 to one less than the length of the list. Like many
  # languages, Python list indexes begin at 0, so a list with a
  # length of 5 has indexes going from 0 through 4.
  for index in range(len(values) - 1):
    # If the list is sorted, then every value in it will be less than
    # the one that comes after it. So we test to see whether the
    # current item is GREATER than the one that follows it.
    if values[index] > values[index + 1]:
      # If it is, it means the whole list is not sorted, so we return
      # False.
      return False
  # If we get down here, it means the loop completed without finding
  # any unsorted values. (Python uses whitespace to mark code blocks,
  # so un-indenting the code like this marks the end of the loop.)
  # Since all the values are sorted, we can return True.
  return True

# Now we need to write the function that will actually do the
# so-called sorting.  The bogo_sort function will also take the list
# of values it's working with as a parameter.
def bogo_sort(values):
  # We'll call our is_sorted function to test whether the list is
  # sorted. We'll keep looping until is_sorted returns True.
  while not is_sorted(values):
    # Python has a ready-made function that randomizes the order of
    # elements in a list. Since the list isn't sorted, we'll call
    # that function here. And since this is inside the loop, it will
    # be randomized over and over until our is_sorted function
    # returns True.
    random.shuffle(values)
  # If the loop exits, it means is_sorted returned True, and the list
  # is sorted.  So we can now return the sorted list.
  return values

# Finally, we need to call our bogo_sort function, pass it the list
# we loaded from the file, and print the sorted list it returns.
print(bogo_sort(numbers))

To run this, save the above code to two files in the same directory, and ensure a file named 5.txt is saved in a subdirectory named numbers. Then open a terminal/console, change to the directory where bogosort.py is saved, and run this command:

python bogosort.py numbers/5.txt

JavaScript

// Randomly shuffle the elements of the array that's passed in.
function shuffle(array) {
    var swapIndex = array.length;
    var temp, randomIndex;

    while (swapIndex !== 0) {

        randomIndex = Math.floor(Math.random() * swapIndex);

        swapIndex -= 1;

        temp = array[swapIndex];
        array[swapIndex] = array[randomIndex];
        array[randomIndex] = temp;
    }

    return array;
}

// Returns true if array is sorted, false if not.
function isSorted(array){
    for(var i = 1; i < array.length; i++) {
        if (array[i-1] > array[i]) {
            return false;
        }
    }
    return true;
}

// Shuffles array until it's sorted.
function bogoSort(array){
    while(isSorted(array) == false) {
        array = shuffle(array);
    }
    return array;
}

const testValues = [29, 100, 1, 2, 57];

var sorted = bogoSort(testValues);
console.log(sorted);

Java

import java.util.*;

public class BogoSort {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(29, 100, 1, 2, 57));
        bogoSort(list);
        System.out.println(list);
    }

    static void bogoSort(ArrayList<Integer> list) {
        while(!isSorted(list)) {
            Collections.shuffle(list);
        }
    }

    static boolean isSorted(ArrayList<Integer> list) {
        for(int i=1; i < list.size(); i++) {
            if(list.get(i) < list.get(i-1)) {
                return false;
            }
        }
        return true;
    }
}

C-Sharp

using System;
using System.Collections.Generic;

namespace Bogosort
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var list = new List<int>() { 29, 100, 1, 2, 57 };
            BogoSort(list);
            Console.WriteLine(String.Join(",", list));
        }

        public static void BogoSort(IList<int> list)
        {
            var attempt = 1;
            while (!IsSorted(list))
            {
                Console.WriteLine($"Attempt {attempt}");
                list.Shuffle();
                attempt++;
            }            
        }

        static bool IsSorted(IList<int> list)
        {
            for (int i = 1; i < list.Count; i++)
            {
                if (list[i] < list[i - 1])
                {
                    return false;
                }
            }
            return true;
        }
    }

    /// <summary>
    /// IList extension methods.
    /// </summary>
    static class IListExtensions
    {
        static Random rng = new Random();

        /// <summary>
        /// Shuffle the items in the specified list.
        /// </summary>
        /// <param name="list">The list to shuffle.</param>
        /// <typeparam name="T">The item type.</typeparam>
        public static void Shuffle<T>(this IList<T> list)
        {
            int n = list.Count;
            while (n > 1)
            {
                n--;
                int k = rng.Next(n + 1);
                T value = list[k];
                list[k] = list[n];
                list[n] = value;
            }
        }
    }
}