Quickselect Algorithm

Problem Description: The quickselect algorithm is an efficient algorithm for finding the kth smallest (or kth largest) element in an unsorted list. It is a variation of the quicksort algorithm but does not require fully sorting the entire array. Its average time complexity is O(n), and its worst-case time complexity is O(n²).

Solution Process:

1. Algorithm Concept
   Quickselect is based on the partitioning idea of quicksort. In quicksort, we select a pivot element to partition the array into two parts: all elements in the left part are less than or equal to the pivot, and all elements in the right part are greater than the pivot. Quickselect leverages this characteristic to continue searching only in the part containing the target element, thereby avoiding sorting the entire array.

2. Algorithm Steps

• Select a pivot element.
• Partition the array, placing elements less than the pivot on the left and elements greater than the pivot on the right.
• Compare the final position of the pivot with k:
  • If the pivot position is exactly k, return the pivot element.
  • If the pivot position is greater than k, recursively search for the kth smallest element in the left half.
  • If the pivot position is less than k, recursively search for the (k - pivot position - 1)th smallest element in the right half.

3. Detailed Implementation Process
   Let's understand through a specific example: Find the 3rd smallest element in the array [3, 2, 1, 5, 4].

Step 1: Select a pivot
Typically, the last element is chosen as the pivot. Here, we select 4 as the pivot.

Step 2: Partition operation
Set two pointers: i points to the end of the region less than the pivot, and j traverses the array.

• Initial state: [3, 2, 1, 5, 4], i = -1, j = 0
• j=0: 3<4, i++=0, swap arr[0] and arr[0] → array unchanged
• j=1: 2<4, i++=1, swap arr[1] and arr[1] → array unchanged
• j=2: 1<4, i++=2, swap arr[2] and arr[2] → array unchanged
• j=3: 5>4, no swap
• Finally, swap arr[i+1] and pivot → swap arr[3] and arr[4]
  Partition result: [3, 2, 1, 4, 5], pivot 4 is at position 3.

Step 3: Determine recursion direction
We want to find the 3rd smallest element (k=2, as counting usually starts from 0).
Pivot position 3 > 2, so continue searching for the 2nd smallest element in the left half [3, 2, 1].

Step 4: Recursively process the left half
Find the 2nd smallest element in [3, 2, 1], selecting 1 as the pivot.
Partition process:

• Initial: [3, 2, 1], i = -1, j = 0
• j=0: 3>1, no swap
• j=1: 2>1, no swap
• Swap arr[i+1] and pivot → swap arr[0] and arr[2]
  Partition result: [1, 2, 3], pivot 1 is at position 0.

Step 5: Continue judgment
Target position 2 > pivot position 0, so search for the (2-0-1)=1st smallest element in the right half [2, 3].

Step 6: Find the 1st smallest element in [2, 3]
Select 3 as the pivot. After partitioning, we get [2, 3], with the pivot at position 1.
Target position 1 = pivot position 1, result found: 3.

4. Time Complexity Analysis

• Best case: Each partition divides the array evenly, time complexity is O(n).
• Average case: O(n).
• Worst case: The worst pivot is chosen each time, time complexity is O(n²).

5. Optimization Strategies
   To avoid the worst-case scenario, strategies such as randomized pivot selection or median-of-three can be employed to improve algorithm performance.