My BogoSort program may have a logic error

Question

For an assignment, I have to write some Bogosort code, and empirically determine the program's Big O notation.

However, I am unsure of whether the code works, because even though it sorts it for 3 and 4 element arrays of type int, I don't think it should be doing it in 0 ms.

Conversely, it's taking really long for 5 elements (still haven't gotten a successful case within 15 minutes yet), which indicates to me that there may be something wrong with the program. Since there are no errors being thrown, I believe any problem found would be a logic error.

I've tried running the IDE debugger on the program. Each of the methods used for the bogosort seemed to be working as intended, although I was not able to reach the case where it sorted an array properly while using the debugger.

However, by changing the values of the array to have it already sorted, I was able to test the case where the array was sorted, and the code was executed successfully.

This seems to indicate that the problem if there is any, would have to do with a logic error in sorting, where the sort method is somehow never getting to the correct solution.

The file is as shown below, and is commented.

Any suggestions for the program will have to pertain to the current structure (no adding methods, no using ArrayLists) since this is a homework assignment.

public class BogoSort {

    public static void main(String[] args) {
        int[] myArray = {20, 142, 115, 120, 140};
        //sets start time
        long start = System.currentTimeMillis();
        bogoSort(myArray);
        //sets end time
        long end = System.currentTimeMillis();
        printArray(myArray);
        //print time (end time - start time)
        System.out.println((end - start) + "ms");
    }

    // Places the elements of a into sorted order.
    public static void bogoSort(int[] a) {
        while(!isSorted(a)){
            //calls the shuffle method if it's not sorted
            shuffle(a);
        }
    }
    // Returns true if a's elements are in sorted order.
    public static boolean isSorted(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i+1]) {
                //returns false if the number in this index is greater than 
                //the number in the next index aka not sorted 
                return false;
            }
        }       
        //else return true
        return true;
    }
    // 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){
        Random r = new Random();
        for(int i = a.length - 1;i > 0;i--){
            //random number between 0 and i
            int j = r.nextInt(i);
            //calls swap method  
            swap(a, i, j);
        }
    }
    // Swaps a[i] with a[j].
    public static void swap(int[] a, int i, int j) {
        //temp variable to hold value of a[i] for swap
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void printArray(int[] a)
    {
        for(int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);

        }
    }

}//end of BogoSort class

Results should be as follows:

20
115
120
140
142
???ms

??? is a value for how long the program runs for, maybe about 720 ms, if I understand bogosort's Big O notation correctly.

Currently, I have not gotten a result for an array above a size of 4.

The time it takes for an array of 3 or 4 elements to sort is 0 ms, which is a bit odd to me, I feel like it should be about 24 ms for 3 elements, and 120 ms for 4 elements.

The result of the sorting of a 3 or 4 element array is that the numbers are sorted correctly, as per the expected result.

Answer 1

Your shuffle algorithm is broken due to an off-by-1 error. If you try it with int[] myArray = {2,1,3};, you'll see that it fails to complete for 3 elements as well.

When dealing with randomness, it's better to use statistics than eyeballing, because it's hard to notice this at a glance:

$ java BogoSort | head -n 100000 > file
$ sort file | uniq -c
33325 [1, 3, 2]
33315 [2, 1, 3]
33360 [3, 2, 1]

As you can see, you only ever generate 3 out of 6 possible permutations.

When you shuffle, like your comment indicates, you swap each element with one earlier in the array. You need to additionally allow the element to stay in place. You can do this by adding 1 to the index you choose:

// Shuffles an array of ints by randomly swapping each
// element with an element ahead of it in the array **or leave it in place**.
public static void shuffle(int[] a){
    Random r = new Random();
    for(int i = a.length - 1;i > 0;i--){
        //random number between 0 and i
        int j = r.nextInt(i+1);   // <-- +1 here to select the current element
        //calls swap method
        swap(a, i, j);
    }
}

The result now looks better (I rigged the program to keep printing even when it's sorted):

$ sort file | uniq -c
16807 [1, 2, 3]
16579 [1, 3, 2]
16745 [2, 1, 3]
16697 [2, 3, 1]
16361 [3, 1, 2]
16811 [3, 2, 1]

and indeed, it now finishes in 0-1ms. Running it on 8 numbers takes ~10ms, and 10 numbers take ~150ms, in line with the expected factorial curve.

Answer 2

The accepted answer correctly identified the fault and a straight forward solution.

I attempted to dig a bit deeper into why there were missing permutations. From that answers suggested starting point, [2,1,3], the incorrect shuffle would result can only produce two outcomes: [1,3,2] and [3,2,1]. This is already a mistake, since you expect a shuffle to be able to produce any of the 6 permutations. However, in addition, under the incorrect shuffle, those outcomes can only produce each other on another iteration of the bad shuffle.

So, to think about it differently, the only way for [2,1,3] to shuffle into [1,2,3] would be if the third element was allowed to stay in place. The only way for [1,3,2] to shuffle into [1,2,3] would be if the first element was allowed to stay in place. Finally, the only way for [3,2,1] to shuffle into [1,2,3] would be if the second element was allowed to stay in place. But the algorithm does not allow elements to stay, and any moved element during the shuffle iteration is not moved again.

The bad shuffle only produces the permutations that cause all the elements to be in a different position. In other words, it can only produce rotations!_{Only for the 3 element case}

So, if the starting point is not a rotation of the sorted array, the algorithm will never terminate.

In comments, I had suggested an alternative shuffle implementation:

public static void shuffle(int[] a){
    Random r = new Random();
    int x = r.nextInt(a.length);
    for(int i = a.length-1;i > 0;i--){
        int j = r.nextInt(i);
        if (j < x) break;
        swap(a, i, j);
    }
}

However, the weakness of this shuffle is that itself still lacks the ability to generate any possible permutation. The ability of the bogosort to eventually see all possible permutations using this implementation depends on each successive call to shuffle producing slightly different inputs for the next call.