Could you explain the principle of operation of the Quickselect algorithm?

The Quickselect algorithm is used to find the k-th largest element in an unsorted array. It is based on the idea of Quicksort but instead of fully sorting the array, it recursively selects only the part where the desired element may be.

Working principle:

1. Choose a pivot element.
2. Partition the array into elements less than and greater than the pivot.
3. Determine the position of the pivot after partitioning.
4. If the position matches k, return the pivot.
5. Otherwise, recursively search in the left or right part of the array.

This allows finding the k-th element in average time O(n).

Example in Java:

public int quickselect(int[] arr, int k) {
    return quickselectHelper(arr, 0, arr.length - 1, k);
}

private int quickselectHelper(int[] arr, int left, int right, int k) {
    if (left == right) return arr[left];
    int pivotIndex = partition(arr, left, right);
    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickselectHelper(arr, left, pivotIndex - 1, k);
    } else {
        return quickselectHelper(arr, pivotIndex + 1, right, k);
    }
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    int temp = arr[i];
    arr[i] = arr[right];
    arr[right] = temp;
    return i;
}