Noob Noob - 20 days ago 7
Java Question

Descending Quicksort only half works

I'm writing a quicksort method to sort an array of integers in descending order. It works somewhat, but there are a few numbers that end up out of place. I cannot figure it out as I am new to sorting, so any help would be appreciated a lot!

public static void quikSort(int[] nums, int left, int right) {
int pivotIndex = (left + right) / 2;
int l = left;
int r = right;
int temp;
while (l <= r) {
while (nums[l] > nums[pivotIndex]) {
l++;
}
while (nums[r] < nums[pivotIndex]) {
r--;
}

if (l <= r) {
temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
}
if (left < r) {
quikSort(nums, left, r);
}
if (l < right) {
quikSort(nums, l, right);
}
}


Here is also some sample output (sometimes the output ends up perfectly sorted, but not always):

0: 9676

1: 5065

2: 3204

3: -2164

4: -6511

5: 8782

6: 1748

7: -3130

8: -8420

9: -9233

And from another run of the program:

0: 5360

1: 2221

2: 426

3: 2180

4: 818

5: -1828

6: -2452

7: -3953

8: -4919

9: -5442

Answer

During sorting swaps the value of 'nums[pivotIndex]' can change. Use fixed pivot instead:

public static void quickSort(Integer[] nums, int left, int right) {
    final int pivot = nums[(left + right) / 2]; // <== Fix pivot value.
    int l = left;
    int r = right;
    while (l <= r) {
        while (nums[l] > pivot) {
            l++;
        }
        while (nums[r] < pivot) {
            r--;
        }
        if (l <= r) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
            l++;
            r--;
        }
    }
    if (left < r) {
        quickSort(nums, left, r);
    }
    if (l < right) {
        quickSort(nums, l, right);
    }
}
Comments