What is Quickselect Algorithm? (with code)

In computer science, there are numerous algorithms designed to solve different types of problems efficiently. We will learn in this article one such algorithm, known as Quick Select Algorithm, which efficiently finds the kth smallest element in an unsorted array or list. This algorithm builds upon the partitioning technique of the well-known QuickSort algorithm and offers a fast and elegant solution to the problem.

What is the QuickSelect Algorithm?

The QuickSelect algorithm follows the principle of divide and conquer to efficiently find the kth smallest element in an unsorted array. It uses a partitioning technique that is similar to QuickSort but with a modified approach.

In QuickSelect, the algorithm divides the array into two partitions based on a chosen pivot element. It then selects one partition to continue the search, based on the position of the pivot relative to the desired kth element. This process of dividing the problem into smaller subproblems is repeated until the kth element is found or the array is fully sorted.

It is an in-place algorithm, which means it does not require additional memory allocation and modifies the original array during the process. 

QuickSelect can be used to find both the kth smallest and kth largest elements in an array. By modifying the algorithm slightly, it can be adapted to find the kth largest element.

Step-by-Step Algorithm

Here is the step-by-step algorithm for QuickSelect:

1. Choose a pivot element from the array. This pivot element will help in dividing the array into two partitions.
2. Partition the array in such a way that all elements smaller than the pivot are on the left side, and all elements larger than the pivot are on the right side.
3. If the pivot element is at the kth position, return it as the kth smallest element.
4. If the pivot element is smaller than the kth position, recursively apply the QuickSelect algorithm to the right partition of the array.
5. If the pivot element is larger than the kth position, recursively apply the QuickSelect algorithm to the left partition of the array.

The algorithm repeats steps 1 to 5 until the kth smallest element is found or until the array is fully sorted.

Time Complexity

The average time complexity of the QuickSelect algorithm is O(n), where n is the number of elements in the array. However, in the worst-case scenario, the time complexity can be O(n^2), which occurs when the pivot is consistently chosen as the smallest or largest element.

Implementation of QuickSelect

Here's an implementation of the Quick Select algorithm in C++:

#include 
#include 

using namespace std;

// Function to swap two elements in the array
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Partitioning function to rearrange the elements
// based on the pivot
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // Choosing the last element as the pivot
    int i = low - 1; // Index of the smaller element

    for (int j = low; j < high; j++) {
        // If current element is smaller than or equal to the pivot
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // Place the pivot element in its correct position
    return i + 1; // Return the index of the pivot element
}

// QuickSelect algorithm to find the kth smallest element
int quickSelect(vector<int>& arr, int low, int high, int k) {
    if (low <= high) {
        int pivotIndex = partition(arr, low, high);

        // If the pivot element is the kth smallest element
        if (pivotIndex == k - 1)
            return arr[pivotIndex];

        // If the pivot element is greater than the kth smallest element
        else if (pivotIndex > k - 1)
            return quickSelect(arr, low, pivotIndex - 1, k);

        // If the pivot element is smaller than the kth smallest element
        else
            return quickSelect(arr, pivotIndex + 1, high, k);
    }
    return -1; // Return -1 if k is out of bounds or the array is empty
}

int main() {
    vector<int> arr = { 10, 7, 8, 3, 1, 2, 9, 5, 6, 4 };
    int k = 4; // Find the 4th smallest element

    int result = quickSelect(arr, 0, arr.size() - 1, k);

    if (result != -1)
        cout << "The " << k << "th smallest element is: " << result << endl;
    else
        cout << "Invalid input or array is empty!" << endl;

    return 0;
}

Output:

The 4th smallest element is: 4