CODEWITHSUNDEEP
javaalgorithmsortingquicksort
IHazABone
IHazABone

Reputation: 525

Quicksort occasionally not completing?

I've made a bunch of attempts at a quicksort algorithm, which I just can't seem to make work. This code is the closest I've gotten, except that it about one in five times it doesn't fully sort - it outputs something like 266, 186, 219, 276, 357, 405, 686, 767, 834, 862. I've tried to find a commonality between all the sets of numbers that do this, but I can't find anything. I've spent many hours stepping through it with a debugger but can't see anything (although I feel like I'm missing something obvious). What am I doing wrong?

public static void sort(ArrayList<Integer> arr, int left, int right) {
    int i = left - 1, j = right, v = arr.get(right);
    if(right - i == 0 || right - i == 1)return;

    for(;;) {
        while(arr.get(++i) < v);
        while(v < arr.get(--j) && j != 0)
            if(j == 1)break;
        if(i >= j)break;

        Collections.swap(arr, i, j);
    }
    Collections.swap(arr, i, right);

    sort(arr, left, i - 1);
    sort(arr, i, right);
}

Upvotes: 3

Views: 77

Answers (1)

osundblad
osundblad

Reputation: 2681

I did two things to your code to get it to work:

at beginning of method set j = right +1 and move v = arr.get(right) to after first if statement.

Should look something like this:

public static void sort(ArrayList<Integer> arr, int left, int right) {
        int i = left - 1;
        int j = right + 1;
        if (right - i == 0 || right - i == 1) return;
        int v = arr.get(right);

        for (;;) {
            while (arr.get(++i) < v);
            while (v < arr.get(--j) && j != 0)
                if (j == 1) break;
            if (i >= j) break;

            Collections.swap(arr, i, j);
        }
        Collections.swap(arr, i, right);

        sort(arr, left, i - 1);
        sort(arr, i, right);
    }

But this was really unreadable code, you should read the book CleanCode.

Upvotes: 2

Related Questions