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;
}
}
}
}