Noob - 10 months ago 71

Java Question

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 Source

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