Quickselect Algorithm

Problem Description
The Quickselect algorithm is an efficient method for finding the k-th smallest (or largest) element in an unsorted array, with an average time complexity of O(n) and a worst-case of O(n²). It is based on the partitioning idea of Quicksort but only recursively processes the part of the array that contains the target element, thereby reducing computational overhead.

Solution Process

1. Core Idea:

   • Select a pivot value and partition the array into three parts: elements less than the pivot, equal to the pivot, and greater than the pivot.
   • Depending on the position of the k-th smallest element relative to the pivot, decide whether to recursively process the left part, the right part, or directly return the pivot value.

2. Detailed Steps:
   Step 1: Select a Pivot

   • Common methods: randomly select an element, use the median-of-medians, or simply take the first element (simple but potentially inefficient).
   • Optimization: Use the "median-of-three" method (take the median of the first, middle, and last elements) to reduce the probability of worst-case scenarios.

   Step 2: Partition

   • Rearrange the array so that all elements less than the pivot are moved to the left, those equal to the pivot are in the middle, and those greater than the pivot are on the right.
   • After partitioning, the final position of the pivot is its correct sorted position.
   • Example:

     Array: [3, 2, 1, 5, 4], pivot=3
     After partitioning: [1, 2, 3, 5, 4]
                          ^ Pivot index=2
     

   Step 3: Determine Recursion Direction

   • Let the pivot index after partitioning be pivot_index, and the number of elements in the left part be left_count = pivot_index.
   • Compare k with left_count:
     • If k <= left_count: The k-th smallest element is in the left part. Recursively process the left subarray (the < pivot part).
     • If k > left_count + number of elements equal to the pivot: The k-th smallest element is in the right part. Recursively process the right subarray (the > pivot part), while updating k = k - (left_count + number of elements equal to the pivot).
     • Otherwise, the k-th smallest element is the pivot value, so return it directly.

3. Example
   Array: [3, 2, 1, 5, 4], find the 3rd smallest element (k=3).

   • Choose pivot=3, after partitioning: [1, 2, 3, 5, 4], pivot_index=2.
   • left_count=2 (elements 1 and 2), number of elements equal to the pivot=1 (element 3).
   • Decision: Is k=3 ≤ left_count+1=3? Yes, but k=3 > left_count=2, meaning the target is in the part equal to the pivot, so directly return 3.

4. Time Complexity Analysis

   • Average case: Each partition recursively processes half of the array, T(n) = T(n/2) + O(n) → O(n).
   • Worst case: Each partition is highly unbalanced (e.g., the array is already sorted and the pivot is an extreme value), T(n) = T(n-1) + O(n) → O(n²).
   • Optimization: Randomizing pivot selection can avoid worst-case scenarios, with an expected complexity of O(n).

5. Comparison with Heap Sort

   • Heap sort requires O(n log k) to find the k-th smallest element (maintaining a heap of size k), while Quickselect is more memory-efficient (operates in-place).

Key Points Summary

• Quickselect is a variation of Quicksort that avoids full sorting through "partitioning + targeted recursion."
• Pay attention to duplicate elements: during partitioning, elements equal to the pivot should be grouped together.
• In practice, it is often combined with insertion sort (directly sorting small arrays) to further improve efficiency.