CODEWITHSUNDEEP
javasortingquicksort
Noob
Noob

Reputation: 125

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

Upvotes: 0

Views: 117

Answers (1)

ursa
ursa

Reputation: 4591

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

Upvotes: 1

Related Questions