Odtnhj

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