Могли бы вы объяснить принцип функционирования алгоритма Quickselect?

Алгоритм Quickselect используется для поиска k-го по величине элемента в неотсортированном массиве. Он основан на идее быстрой сортировки (Quicksort), но вместо полной сортировки массива рекурсивно выбирает только ту часть, где может находиться искомый элемент.

Принцип работы:

1. Выбирается опорный элемент (pivot).
2. Массив разделяется на элементы меньше и больше pivot.
3. Определяется позиция pivot после разделения.
4. Если позиция совпадает с k, возвращаем pivot.
5. Иначе рекурсивно ищем в левой или правой части массива.

Это позволяет найти k-й элемент за среднее время O(n).

Пример на 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;
}