Sometimes Quicksort doesn't end?
I've done a bunch of attempts at the quicksort algorithm that I just can't seem to get it to work. This code is the closest I got, except that it doesn't completely sort about once every five times - it outputs something like 266, 186, 219, 276, 357, 405, 686, 767, 834, 862
. I tried to find commonality between all sets of numbers that do this, but I can't find anything. I've spent many hours wading through it with the debugger, but I 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);
}
source to share
I did two things to your code to make it work:
at the beginning of the method set j = right +1
and move v = arr.get(right)
to the expression after the first statement.
It 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 it was really unreadable code, you should read the CleanCode book.
source to share