So implementieren Sie Duplikate in QuickSelect

Ich habe den Schnellauswahlalgorithmus erstellt, der darin besteht, die k-te kleinste Zahl in einem Array zu finden. Mein Problem ist, dass es nur mit einem Array ohne Duplikate funktioniert. Wenn ich ein Array habe

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

Es wird gesagt, dass die drittkleinste Zahl 2 ist, aber es ist tatsächlich 3.

Ich weiß nicht, was ich tun soll. Hier sind meine beiden Methoden quickSelect und 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;
}