Quickselect Algorithm

The quickselect algorithm seeks to find the kth smallest value or the kth largest value in an input array in linear time on average and a constant space complexity if the algorithm operates in place without using another data structure.
 

Quickselect Conceptual Overview

The quickselect algorithm efficiently finds the kth smallest or largest element in an unsorted array. Here's a conceptual overview of how the algorithm works:

Selecting a Pivot

The algorithm starts by choosing a pivot element from the array. The choice of pivot can affect the efficiency of the algorithm. Common strategies include selecting the first element, the last element, the middle element, or a randomly chosen element.

Partitioning the Array

Once the pivot is chosen, the array is partitioned into two sections: elements smaller than the pivot and elements greater than the pivot. This partitioning step rearranges the elements so that all elements smaller than the pivot are placed to the left, and all elements greater than the pivot are put to the right.

Determining the Rank of the Pivot

After partitioning, the pivot element finds itself in its final sorted position if the array were sorted. The algorithm then determines the rank of the pivot element in the sorted array. If the rank of the pivot matches the desired rank (k), then the pivot is the kth smallest element, and the algorithm terminates.

Recursive Call or Iteration

If the rank of the pivot doesn't match the desired rank (k), the algorithm recursively or iteratively focuses on the partition containing the desired rank. This process continues until the pivot reaches the desired rank (k).

Returning the Result

Once the pivot's rank matches the desired rank (k), the algorithm returns the pivot element as the kth smallest element.

Code Walkthrough

# O(n) time | O(1) space
def quick_select(array, k):
    """
    Selects the kth smallest element from the given array.
    
    Parameters:
        array (list): The input list of integers.
        k (int): The desired rank of the element to select (1-indexed).
        
    Returns:
        int: The kth smallest element in the array.
    """
    position = k - 1
    return quick_select_helper(array, 0, len(array) - 1, position)

def quick_select_helper(array, startIdx, endIdx, position):
    """
    Helper function for the quickselect algorithm.
    
    Parameters:
        array (list): The input list of integers.
        startIdx (int): The starting index of the subarray.
        endIdx (int): The ending index of the subarray.
        position (int): The desired rank of the element to select (0-indexed).
        
    Returns:
        int: The kth smallest element in the array.
    """
    while True:
        if startIdx > endIdx:
            return None
        pivotIdx = startIdx
        leftIdx = startIdx + 1
        rightIdx = endIdx
        # Partition the array based on the pivot element
        while leftIdx <= rightIdx:
            # Move the left index until encountering an element greater than the pivot
            # and simultaneously move the right index until encountering an element smaller than the pivot.
            # Once both indices have found elements violating the partition rule,
            # swap them to correct the partition.
            if array[leftIdx] > array[pivotIdx] and array[rightIdx] < array[pivotIdx]:
                swap(leftIdx, rightIdx, array)
            # Move left index if the element is less than or equal to the pivot
            if array[leftIdx] <= array[pivotIdx]:
                leftIdx += 1
            # Move right index if the element is greater than or equal to the pivot
            if array[rightIdx] >= array[pivotIdx]:
                rightIdx -= 1
        # Swap the pivot with the right index (partitioning step)
        swap(pivotIdx, rightIdx, array)
        # Check if the right index is the desired position
        if rightIdx == position:
            return array[rightIdx]
        # Update the indices for the next iteration based on the position of the right index
        elif rightIdx < position:
            startIdx = rightIdx + 1
        else:
            endIdx = rightIdx - 1


def swap(one, two, array):
    """
    Swaps two elements in the given array.
    
    Args:
        one (int): Index of the first element to swap.
        two (int): Index of the second element to swap.
        array (list): The input list of integers.
    """
    array[one], array[two] = array[two], array[one]

# Unit tests
import unittest

class TestQuickSelect(unittest.TestCase):
    def test_quickselect(self):
        self.assertEqual(quick_select_helper([8, 5, 2, 9, 7, 6, 3], 3), 5)  # expected output: 5
        self.assertEqual(quick_select_helper([], 3), None)  # expected output: 0
        
        # Add more test cases for edge cases, empty array, etc.

if __name__ == "__main__":
    unittest.main()

Time & Space Complexity

Quickselect is a derivative of the quicksort algorithm. It is tailored to efficiently find the kth smallest or the kth largest element in an unsorted array. Here's the analysis of its time and space complexity.

Time Complexity

•     Best Case: O(n)
•     Average Case: O(n)
•     Worst Case: O(n^2)

In the best and average cases, the algorithm effectively reduces the search space by approximately half with each partitioning step, resulting in a linear time complexity of O(n). However, in the worst case, the partition process may not evenly divide the array, leading to unbalanced partitions and potentially degenerating into a worst-case time complexity of O(n^2).

It occurs when the pivot is consistently chosen poorly, such as when the array is already sorted or nearly sorted.

Space Complexity

 In the iterative implementation of the quickselect algorithm provided here, the space complexity is indeed O(1) because it doesn't utilize additional space proportional to the input size.

 Instead, it operates directly on the input array without requiring additional data structures or recursion.

Key Points

• Quickselect relies on the partitioning step to reduce the search space efficiently.
• It's similar to quicksort but only focuses on one partition instead of sorting both.
• The average time complexity is O(n), making it efficient for finding the kth smallest element.
• The worst-case time complexity is O(n^2) if the pivot selection consistently creates unbalanced partitions.
• The space complexity is O(1) because the algorithm operates in place without additional data structures.