Как работает Quickselect Algorithm?

# Как работает Quickselect Algorithm

Quickselect — это алгоритм для поиска k-го наименьшего элемента в неотсортированном массиве. Похож на QuickSort, но работает быстрее.

1. Суть алгоритма

Quickselect основан на идее QuickSort, но только рекурсивно обрабатывает одну часть массива:

1. Выбрать pivot элемент
2. Partition массив относительно pivot
3. Если pivot находится на позиции k — найдено!
4. Если k < позиция pivot — искать в левой части
5. Если k > позиция pivot — искать в правой части

2. Пример вручную

Массив: [3, 1, 5, 2, 4], найти 3-й наименьший элемент (k=3)

Шаг 1: Выбираем pivot = 3 (первый элемент)
[3, 1, 5, 2, 4]
 
Шаг 2: Partition относительно 3
[1, 2, 3, 5, 4]  <- 3 на позиции 2 (индекс 2)
     ↑
     pivot position = 2

Шаг 3: Ищем 3-й элемент (k=3, но индекс k-1=2)
У нас pivot на позиции 2, нам нужна позиция 2 → найдено!
Ответ: 3

3. Реализация на Java

public class QuickSelect {
    
    // Найти k-й наименьший элемент (k от 1 до n)
    public static int findKthSmallest(int[] nums, int k) {
        int n = nums.length;
        // Преобразуем k (от 1) в индекс (от 0)
        return quickSelect(nums, 0, n - 1, k - 1);
    }
    
    private static int quickSelect(int[] nums, int left, int right, int kIndex) {
        // Базовый случай: один элемент
        if (left == right) {
            return nums[left];
        }
        
        // Выбираем случайный pivot и partition
        Random rand = new Random();
        int pivotIndex = left + rand.nextInt(right - left + 1);
        
        // Partition и получаем финальную позицию pivot
        pivotIndex = partition(nums, left, right, pivotIndex);
        
        // Если pivot находится на нужной позиции — нашли!
        if (kIndex == pivotIndex) {
            return nums[kIndex];
        }
        // Если нужная позиция в левой части
        else if (kIndex < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, kIndex);
        }
        // Если нужная позиция в правой части
        else {
            return quickSelect(nums, pivotIndex + 1, right, kIndex);
        }
    }
    
    private static int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivot = nums[pivotIndex];
        
        // Swap pivot в конец
        swap(nums, pivotIndex, right);
        int storeIndex = left;
        
        // Двигаем все меньшие элементы в левую часть
        for (int i = left; i < right; i++) {
            if (nums[i] < pivot) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        
        // Вставляем pivot на правильное место
        swap(nums, right, storeIndex);
        return storeIndex;
    }
    
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

4. Пример использования

public static void main(String[] args) {
    int[] nums = {3, 1, 5, 2, 4};
    
    System.out.println("1-й наименьший: " + QuickSelect.findKthSmallest(nums, 1));  // 1
    System.out.println("2-й наименьший: " + QuickSelect.findKthSmallest(nums, 2));  // 2
    System.out.println("3-й наименьший: " + QuickSelect.findKthSmallest(nums, 3));  // 3
    System.out.println("4-й наименьший: " + QuickSelect.findKthSmallest(nums, 4));  // 4
    System.out.println("5-й наименьший: " + QuickSelect.findKthSmallest(nums, 5));  // 5
}

5. Сложность

Временная сложность

• Лучший случай: O(n) — случайное разбиение быстро находит k
• Средний случай: O(n) — в среднем нужно проверить половину элементов
• Худший случай: O(n²) — если pivot всегда на краю (очень редко)

Сравнение:

Сортировка (QuickSort): O(n log n)
QuickSelect: O(n) в среднем

Значит QuickSelect быстрее!

Пространственная сложность

O(1) или O(log n) на рекурсию (в зависимости от реализации)

6. Модификация: Median of Medians (гарантированный O(n))

Если нужна гарантированная O(n) сложность без случайности:

public class MedianOfMedians {
    
    public static int findKthSmallest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k - 1);
    }
    
    private static int quickSelect(int[] nums, int left, int right, int kIndex) {
        if (left == right) {
            return nums[left];
        }
        
        // Вместо случайного pivot используем медиану медиан
        int pivotIndex = medianOfMedians(nums, left, right);
        
        pivotIndex = partition(nums, left, right, pivotIndex);
        
        if (kIndex == pivotIndex) {
            return nums[kIndex];
        } else if (kIndex < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, kIndex);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, kIndex);
        }
    }
    
    private static int medianOfMedians(int[] nums, int left, int right) {
        if (right - left + 1 <= 5) {
            // Для маленьких подмассивов — просто отсортируем
            return left + (right - left) / 2;
        }
        
        // Разбиваем на группы по 5 элементов
        int[] medians = new int[(right - left) / 5 + 1];
        for (int i = 0; i < medians.length; i++) {
            int subLeft = left + i * 5;
            int subRight = Math.min(subLeft + 4, right);
            int medianIndex = medianOfMedians(nums, subLeft, subRight);
            medians[i] = nums[medianIndex];
        }
        
        // Рекурсивно найти медиану медиан
        return medianOfMedians(nums, 0, medians.length - 1);
    }
    
    private static int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivot = nums[pivotIndex];
        swap(nums, pivotIndex, right);
        int storeIndex = left;
        
        for (int i = left; i < right; i++) {
            if (nums[i] < pivot) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        
        swap(nums, right, storeIndex);
        return storeIndex;
    }
    
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

7. Практические применения

1. Поиск медианы

public static double findMedian(int[] nums) {
    int n = nums.length;
    if (n % 2 == 1) {
        // Нечётное количество — средний элемент
        return QuickSelect.findKthSmallest(nums, n / 2 + 1);
    } else {
        // Чётное — средняя между двумя элементами
        int mid1 = QuickSelect.findKthSmallest(nums, n / 2);
        int mid2 = QuickSelect.findKthSmallest(nums, n / 2 + 1);
        return (mid1 + mid2) / 2.0;
    }
}

2. Поиск k-го наибольшего

// Найти k-й наибольший — это n-k+1 наименьший
public static int findKthLargest(int[] nums, int k) {
    return QuickSelect.findKthSmallest(nums, nums.length - k + 1);
}

3. Поиск k наименьших элементов

public static List<Integer> findKSmallest(int[] nums, int k) {
    int kthSmallest = QuickSelect.findKthSmallest(nums, k);
    
    List<Integer> result = new ArrayList<>();
    for (int num : nums) {
        if (num <= kthSmallest) {
            result.add(num);
            if (result.size() == k) break;
        }
    }
    
    return result;
}

8. Сравнение с сортировкой

// Задача: найти 5-й наименьший элемент из 1 млн элементов

// Способ 1: Сортировка (QuickSort)
Arrays.sort(nums);  // O(n log n) = 1,000,000 * 20 = 20 млн операций
int result = nums[4];  // O(1)

// Способ 2: QuickSelect
int result = QuickSelect.findKthSmallest(nums, 5);  // O(n) = 1,000,000 операций

// QuickSelect на 20x быстрее!

9. Альтернативы (когда использовать что)

10. Интервью tip

// На интервью часто спрашивают найти k-й наименьший в BST

public class TreeNode {
    int val;
    TreeNode left, right;
}

public int kthSmallest(TreeNode root, int k) {
    // In-order обход BST даёт отсортированный список
    List<Integer> sorted = new ArrayList<>();
    inorder(root, sorted);
    return sorted.get(k - 1);
}

private void inorder(TreeNode node, List<Integer> list) {
    if (node == null) return;
    inorder(node.left, list);
    list.add(node.val);
    inorder(node.right, list);
}

// Или с ранней остановкой (более эффективно)
class Counter {
    int count = 0;
}

public int kthSmallest(TreeNode root, int k) {
    Counter counter = new Counter();
    return inorderKth(root, k, counter).val;
}

private TreeNode inorderKth(TreeNode node, int k, Counter counter) {
    if (node == null) return null;
    
    TreeNode left = inorderKth(node.left, k, counter);
    if (left != null) return left;
    
    counter.count++;
    if (counter.count == k) return node;
    
    return inorderKth(node.right, k, counter);
}

Вывод

QuickSelect — это эффективный алгоритм для поиска k-го элемента:

• Средняя сложность: O(n) — быстрее, чем сортировка
• Лучше чем: сортировка для конкретного элемента
• Случайный pivot: обычно достаточно, Median of Medians гарантирует O(n)
• Применения: медиана, top-k, order statistics