Start using very small arrays, maybe [3] to [5] int's. And use simple arrays, not an array collection. If you manage to sort an array of over 100 integers, in less than an hour, then try again, you did something wrong. Slow computers can seldom sort [10] and even the fastest struggle to reach [15]. This sort algorithm is VERY inefficient. You must sort integers with multiple digits (e.g. 42, 13, 19, 83, 23), else duplicates cause apparent success that is not real.

Use the attached BogoSort.java and write your code where specified.

OK, got that done, not a tough program once you discover it can be as simple as while(!sorted(array)){shuffle(array))} with appropriate methods for boolean sorted and void shuffle.

Now the tough question: What's Big-O for Bogo sort?

Use the System clock (milliseconds) or equivalent way to count operations and assess the run-time complexity, O(N), O(N^3), O(N^N) or worse? Create an Excel workbook of your results, and clearly indicate your answer for Big-O. Your chart should have sufficient labels and data to support your Big-O answer. Attach your one final working code file (.java) again for this assignment submission, and be certain to provide sufficient code comments on what you did, and the conclusion you reached. I should be able to run this one .java file and see your program work. Also attach an Excel workbook (.xls or .xlsx) with your timing data and a chart (graph). Since Bogo is based on a random number generator, it is important to show multiple time points for each N on your chart.

What might this Excel spreadsheet look like? I attach Timing.xlsx a rough set of testing for Collections.sort() of the Java API, claimed to be N*log(N) complexity, so I run a bunch of times, plot time versus N*log(N) and yes, it appears to fit well. For your BOGO Sort, life is tough, seems to be running at random times, but YES, there is a trend. Record data many times at each N, some N might be very consistent, others are not, maybe something like this: bogo.jpg But yes, there is an overall trend and real answer to this problem.

//BogoSort.java

public class BogoSort {

public static void main(String[] args) {

int[] myArray = { /****put your test numbers here ******/};

bogoSort(myArray);

printArray(myArray);

}

// Places the elements of a into sorted order.

public static void bogoSort(int[] a) {

//**********Write code here******************

}

// Returns true if a's elements are in sorted order.

public static boolean isSorted(int[] a) {

//**********Write code here******************

}

// Shuffles an array of ints by randomly swapping each

// element with an element ahead of it in the array.

public static void shuffle(int[] a) {

//**********Write code here******************

}

// Swaps a[i] with a[j].

public static void swap(int[] a, int i, int j) {

//**********Write code here******************

}

public static void printArray(int[] a)

{

for(int i=0; i

{

System.out.println(a[i]);

}

}

}//end of BogoSort class