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

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);
}
}
``````
Source (Stackoverflow)