Find Kth min elem by randomized pivot method. Some weird bug

Question

I try to use "randomized pivot" method to find the Kth min elem among given array.
[The code]

public class FindKthMin {

// Find the Kth min elem by randomized pivot.
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
    int tempElem = givenArray[firstIndex];
    givenArray[firstIndex] = givenArray[secondIndex];
    givenArray[secondIndex] = tempElem;
}
private static int partition (int[] givenArray, int start, int end, int pivotIndex) {

    // Debug:
    //System.out.println("debug: start = " + start);
    //System.out.println(">> end = " + end);
    //System.out.println(">> pivotIndex = " + pivotIndex);


    int pivot = givenArray[pivotIndex];
    int left = start - 1;
    int right = end;
    boolean hasDone = false;
    while (!hasDone) {
        while (!hasDone) {
            left ++;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[left] >= pivot) {
                // Exchange givenArray[left] and the givenArray[right].
                exchange(givenArray, left, right);
                break;
            }
        }
        while (!hasDone) {
            right --;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[right] < pivot) {
                // Exchange the givenArray[right] and the givenArray[left].
                exchange(givenArray, right, left);
                break;
            }
        }
    }
    givenArray[right] = pivot;
    // Debug:
    //System.out.println(">> split = " + right);
    //System.out.println();
    return right;
}
private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = (int)(start +  Math.random() * (end - start + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition(givenArray, start, end, rand);
    if (k == split + 1) return givenArray[split];
    else if (k < split + 1) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split + 1, end, k);
}
public static int findKthMin_RanP (int[] givenArray, int k) {
    int size = givenArray.length;
    if (k < 1 || k > size) return -1;
    return findKthMin_RanP_Helper(givenArray, 0, size - 1, k);
}


// Main method to test.
public static void main (String[] args) {
    // Test data: {8, 9, 5, 2, 8, 4}.
    int[] givenArray = {8, 9, 5, 2, 8, 4};

    // Test finding the Kth min elem by randomized pivot method.
    System.out.println("Test finding the Kth min elem by randomized pivot method, rest = " + findKthMin_RanP(givenArray, 1));
}
}

But the result is unstable, sometimes right and sometimes wrong.
Please have a look at the 5th row of findKthMin_RanP_Helper method:
If I change this int split = partition(givenArray, start, end, rand); to int split = partition(givenArray, start, end, end);, the result is always correct.
I really can not find what's wrong with this.

---

EDIT:
The problem comes from the "partition", the new partition should like this:

    private static int partition_second_version (int[] givenArray, int start, int end, int pivotIndex) {
    int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left <= right) {
        while (givenArray[left] < pivot) left ++;
        while (givenArray[right] > pivot) right --;
        if (left <= right) {
            // Exchange givenArray[left] and givenArray[right].
            exchange(givenArray, left, right);
            left ++;
            right --;
        }
    }
    return left;
}

And the findKthMin_RanP_Helper should be changed like this:

    private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = start +  (int)(Math.random() * ((end - start) + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition_second_version (givenArray, start, end, rand);
    if (k == split) return givenArray[split - 1];
    else if (k < split) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split, end, k);
}

Answer 1

Your partition routine could be simplified...

  private static int partition(int[] givenArray, int start, int end, int pivotIndex) {
    final int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left < right) {
        while (left < givenArray.length && givenArray[left] <= pivot) {
            left++;
        }

        while (right > -1 && givenArray[right] > pivot) {
            right--;
        }

        if (left >= right) {
            break;
        }
        exchange(givenArray, right, left);
    }
    return right;
}

The one bug I see in your code is your partition routine. In the first exchange call, it is not guaranteed that the right index will always point to a value which is < pivot.