changing pivot evaluation place causes QuickSort to fail

Question

In QuickSort, evaluating pivot before the sorting conditions makes the algorithm work, while using its index to get its value within the conditions makes it fail, although the pivot index is calculated in advance and should not be changing unlike the left and right ones.

I can't figure out what is the issue here, and how this change result into algorithm failure, as it seems no change in the logic, but rather code re-organization with the same functionality.

Kindly check the below implentation, the explained issue is in the method partition in the commented part:

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] numbers = { 120, 10, 3, 8, 15, 22, 6, 2, 17, 60, 4, 13};
        System.out.println(Arrays.toString(numbers));
        quickSort(numbers);
        System.out.println(Arrays.toString(numbers));
    }

    private static void quickSort(int[] numbers) {
        quickSort(numbers, 0, numbers.length - 1);
    }

    private static void quickSort(int[] numbers, int left, int right) {
        if(left >= right) return;
        int index = partition(numbers, left, right);
        quickSort(numbers, left, index-1);
        quickSort(numbers, index, right);
    }

    private static int partition(int[] arr, int left, int right) {
        int pivotIndex = (left + right) / 2;
        int pivot = arr[pivotIndex];
        while(left <= right){
            // This won't work
            //while(arr[left] < arr[pivotIndex]) left++;
            //while(arr[right]> arr[pivotIndex]) right--;

            //This will work
            while(arr[left] < pivot) left++;
            while(arr[right]> pivot) right--;
            
            if(left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
        //swap(numbers, pivot, left);
        return left;
    }

    private static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

starboy_jb starboy_jb · Accepted Answer · 2020-12-07T15:58:43

Because value at pivot index can be change,

Consider this very simple arr [7, 10, 4, 2].

After the first call of partition function the value of left,

In the working code, The value will be 3 and the array will be [7, 2, 4, 10].

In the non-working code, The value will be 2 and the array will [7, 2, 4, 10]. Which is obviously incorrect because the left values from index 2 should be lesser than the value at index 2. Which is not follow because 7 is less than 4 and it is on the left side.

changing pivot evaluation place causes QuickSort to fail

1 Answers