Poderia explicar o princípio de funcionamento do algoritmo Quickselect?

O algoritmo Quickselect é utilizado para encontrar o elemento k-ésimo em um array não ordenado. Baseia-se na ideia de ordenação rápida (Quicksort), mas, em vez de ordenar completamente o array, seleciona recursivamente apenas a parte onde o elemento procurado pode estar.

Princípio de funcionamento:

1. Escolhe-se um elemento pivô.
2. O array é dividido em elementos menores e maiores que o pivô.
3. Determina-se a posição do pivô após a partição.
4. Se a posição corresponder a k, retorna-se o pivô.
5. Caso contrário, procura-se recursivamente na parte esquerda ou direita do array.

Isso permite encontrar o elemento k em tempo médio O(n).

Exemplo em 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;
}