Problem of the Day -- Bogosort

Bogosort

Given an array in random order try to sort the array by just shuffling the values. Once the array is sorted print out how many iterations ran. This is also known as bogosort. I'd recommend keeping your array length to 10 or less as the average number of runs for 10 is over 36 million.

Permalink: http://problemotd.com/problem/bogosort/

Comments:

Lasharn - 12 years ago

Maybe a bit longer than it needs to be but here is my Java solution. I also had it timed because why not? :)

Gotta love bogosort.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class BogoSort {
    private static final int SIZE = 10; //set list size here
    private static List<Integer> list = new ArrayList<>(SIZE);
    public static void main(String[] args) {
        //create list
        for (int i = 0; i < SIZE; i++) {
            list.add((int)(100*Math.random())); //list is random numbers between 0-99
        }
        double start = System.nanoTime(); //start timing
        int iterations = 0;
        boolean inOrder = false;
        while(true) {
            Collections.shuffle(list);
            for (int i = 0; i < SIZE-1; i++) {
                if(list.get(i) > list.get(i+1)) {
                    inOrder = false; //detect out of order
                }
            }
            if(inOrder == true) {
                double stop = System.nanoTime(); //stop timing
                double time = (stop - start)/1000000; //running time in ms
                //print results and terminate
                System.out.println("It took " + iterations + " iterations"
                        + " in " + time + "ms using bogo sort to sort a list of size " + SIZE);
                return;
            }
            inOrder = true;
            iterations++;
        }
    }
}

reply permalink

Max Burstein - 12 years ago

lol nice. What kind of times were you seeing?

reply permalink
Lasharn - 12 years ago
It varied quite a bit (no surprises there since it's bogosort). Times were between 1-3 seconds.

When I add just 1 extra integer to the list (to make it size 11) this increased significantly to around 25-30 seconds. I wouldn't have the patience to add more.

reply permalink

Aaron Frase - 12 years ago

Here's my python solution.

from random import shuffle, randint

def inorder(a):
    for i, n in enumerate(a):
        if i < len(a)-1 and n > a[i+1]:
            return False
    return True

if __name__ == '__main__':
    nums = [randint(1,99) for x in range(10)]
    count = 0
    print('Sorting:', nums)
    while not inorder(nums):
        shuffle(nums)
        count += 1
    print('Sorted:', nums)
    print('Iterations:', count)

reply permalink

Nick Krichevsky - 12 years ago

Did it with recursion in C++

#include <iostream>
#include <ctime>
bool checkSorted(int list[], int length);
int sort(int list[], int length, int count);
int main(){
    srand(time(NULL));
    int list[] = {6,3,8,4,9,7,6};
    std::cout<<sort(list,7,0)<<std::endl;
    return 0;
}
bool checkSorted(int list[],int length){
    if (length>0){
        int last = list[0];
        for (int i=0; i<length; i++){
            if (list[i]>=last){
                last = list[i];
                continue;
            }
            else{
                return false;
            }
        }
    }
    return true;
}

int sort(int list[], int length, int count){
    if (!checkSorted(list,length)){
        for (int i=0; i<length; i++){
            int pos1 = rand()%length;
            int pos2 = rand()%length;
            int temp = list[pos1];
            list[pos1] = list[pos2];
            list[pos2] = temp;          
        }
        for (int j=0; j<length; j++){
            std::cout<<list[j]<<",";

        }
        std::cout<<std::endl;   
        return sort(list,length,count+1);
    }
    return count;
}

reply permalink

Dustin S - 12 years ago

Here is my solution in go. The main function runs a 1000 trials of bogosort on lists of sizes 2-10.

If you are interested, I put the data from my experiments in a spreadsheet, and create some graphs. LINK

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func is_sorted(list []int) bool {
    len_list := len(list)
    result := true
    if len_list > 1 {
        for i := 0; i < len_list - 1; i++ {
            if list[i] > list[i+1] {
                result = false
                break
            }
        }
    }
    return result
}

func bogosort(elements int) (int, time.Duration){
    rand.Seed(time.Now().UTC().UnixNano())
    list := make([]int, elements)
    for i := 0; i < elements; i++ {
        list[i] = rand.Int()
    }

    iterations := 0
    start := time.Now()
    for {
        if !is_sorted(list) {
            first := rand.Intn(elements)
            second := rand.Intn(elements)
            list[first], list[second] = list[second], list[first]
            iterations += 1
        } else {
            break
        }
    }
    diff := time.Now().Sub(start)
    return iterations, diff
}

func main() {
    for t := 2; t <= 10; t++ {
        var min_time time.Duration
        var max_time time.Duration
        var total_time time.Duration
        var total_iterations int
        trials := 1000

        fmt.Println("=========", t, "Elements", "========")
        for i := 0; i < trials; i++ {
            iterations, time := bogosort(t)
            total_time += time
            total_iterations += iterations
            if time < min_time || min_time == 0 {
                min_time = time
            } else if time > max_time || max_time == 0{
                max_time = time
            }
        }

        fmt.Println("min. time:", min_time)
        fmt.Println("max. time:", max_time)
        fmt.Println("avg. time:", total_time / 1000)
        fmt.Println("avg. iteration:", total_iterations / trials)
    }


}

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Bogosort

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri