Vfrdtyky

I have made the quick select algorithm, which is to find the kth smallest number in an array. My problem is, it only works with an array without duplicates.
If I have an array

arr = {1,2,2,3,5,5,8,2,4,8,8}

It will say that the third smallest number is 2, but it is actually 3.

I am stuck on what to do, here are my two methods quickSelect and Partition:

private int quickselect(int array, int leftIndex, int rightIndex, int kthSmallest) {



    if(kthSmallest > array.length - 1){

        System.out.print("Number does not exist. Please enter a number less than: ");

        return array.length - 1;

    }



    if (leftIndex == rightIndex) {

        return array[leftIndex];

    }



    int indexOfPivot = generatePivot(leftIndex, rightIndex);



    indexOfPivot = quickSelectPartition(array, leftIndex, rightIndex, indexOfPivot);



    if (kthSmallest == indexOfPivot) {



        return array[kthSmallest];



    } else if (kthSmallest < indexOfPivot) {



        return quickselect(array, leftIndex, indexOfPivot - 1, kthSmallest);



    } else {



        return quickselect(array, indexOfPivot + 1, rightIndex, kthSmallest);

    }

}





private int quickSelectPartition(int array, int left, int right, int pivotIndex) {



    int pivotValue = array[pivotIndex];



    swapIndexes(array, pivotIndex, right);



    int firstPointer = left;



    for(int secondPointer = left; secondPointer < right; secondPointer++) {



        if(array[secondPointer] < pivotValue) {



            swapIndexes(array, firstPointer, secondPointer);



            firstPointer++;

        }

    }



    swapIndexes(array, right, firstPointer);



    return firstPointer;

}

If adding to the running time is acceptable, you could start by copying distinct elements into a new array:

private int getDistinct(int array) {

    Set<Integer> distinct = new HashSet<>();

    int endIdx = 0;



    for (int element : array) {



        if (distinct.add(element)) {

            array[endIdx++] = element;

        }

    }



    return Arrays.copyOfRange(array, 0, endIdx);

}

and then do quickselect on that:

int arr = new int {1, 2, 2, 3, 5, 5, 8, 2, 4, 8, 8};

int kthSmallest = 6;



int distinctArray = getDistinct(arr);

int kthSmallestElement = quickselect(distinctArray, 0, distinctArray.length - 1, kthSmallest - 1);



System.out.println(kthSmallestElement);

Output:

8