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

Comments:

• Lasharn - 10 years, 5 months 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 - 10 years, 5 months ago

  lol nice. What kind of times were you seeing?

  reply permalink

• Lasharn - 10 years, 5 months 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 - 10 years, 5 months 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 - 10 years, 5 months 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 - 10 years, 4 months 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