How to transform quicksort to quickselect?

85 Views Asked by At

I've the following implementation for quicksort, but trying to transfer it to quickselect fails.

class Solution {
    public static void main(String[] args) {
        for (int i = 1; i < 5; i++) {
            int[] arr = new int[]{9,8,7,1,2,3,6,5,4};
            System.out.println(quicksort(arr, i));
        }
    }

    private static int quicksort(int[] arr, int k) {
        return quicksort(arr, 0, arr.length - 1, k);
    }

    private static int quicksort(int[] arr, int low, int high, int k) {
        int p = partition(arr, low, high);
        /* Doesnt work:
        if (p == k) {
            return arr[k];
        } else if (p < k) {
            return quicksort(arr, p+1, high, k);
        } else {
            return quicksort(arr, low, p-1, k);
        }
        */
    }

    private static int partition(int[] arr, int low, int high) {
        int i = low;
        int j = high;
        int pivot = arr[low + (high - low) / 2];

        while (true) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }

            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            } else {
                return j;
            }
        }
    }
}

It feels like the information that everything from 0..p is smaller or equal to arr[p] and vice-versa does not help at all.

Example: 9,8,7,1,2,3,6,5,4, after partition: 2, 1, 7, 8, 9, 3, 6, 5, 4 with p = 1 (choosen pivot was 2). So I know the first and second lowest value is in 0..1 range. But it isn't sorted, so I cannot simply say if (p == k-1) return arr[p], because it isn't guaranteed that arr[p] is the max of that half, just that everything in that half is less than the choosen pivot.

Any idea how I can make it work?

0

There are 0 best solutions below