Quickselect Algorithm: Quick Select Algorithm With Example Code

This blog post explains Quickselect Algorithm and its implementation using the C programming language. So before writing the C code for the Quickselect Algorithm let’s first understand the Quick select Algorithm.

What is Quickselect Algorithm:

We can find the smallest element using the Quicksort algorithm by sorting the unsorted list. But it is not a good way to sort the list just only to find the smallest element. So here we will use the Quickselect algorithm to find the smallest element.

Example:

Input: arr[] = {1, 10, 4, 3, 18, 15}
           k = 3
Output: 4 (3rd smallest number)




Input: arr[] = {1, 20, 14, 3, 22, 11}
           k = 4
Output: 14 (4th smallest number)

Quickselect is a selection algorithm to find the kth smallest element in an unsorted list. It is related to the quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm.

The main difference between Quickselect and QuickSort algorithms is, instead of recurring for both sides (after finding pivot), Quickselect recurs only for the part that contains the k^th smallest element.

Note: Every element on the left is less than the pivot and every element on the right is more than the pivot.

In this algorithm, we follow some simple steps which reduce the expected complexity from O(n log n) to O(n), with a worst-case of O(n^2).

1. If the index of the partitioned element (pivot) is more than k (k < pivotIndex), then k^th smallest is on the left side of the pivot. The algorithm recurs for the left part.

2. If the index (pivot) is the same as k (k == pivotIndex), then we have found the k^th smallest element and it is returned.

3. If the index is less than k (k > pivotIndex) then k^thsmallest is on the right side of the pivot. The algorithm recurs for the right part.

Selection Algorithm Pseudocode:

List ==> input list or array.

left ==> is first position of list.

right ==> is last position of list.

k ==> is k-th smallest element.


function quickSelect(list, left, right, k)

   if left = right
      return list[left]

   Select a pivotIndex between left and right

   pivotIndex := partition(list, left, right)
   if k = pivotIndex
      return list[k]
   else if k < pivotIndex
      right := pivotIndex - 1
   else
      left := pivotIndex + 1

Now let’s see the example code for the Quickselect Algorithm using the C programming language.

#include <stdio.h>

//function to swap variable
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}


/* partition function takes last element as pivot and places
   the pivot element at its correct position. It means all
   smaller element will be placed to left all greater elements
   to right of pivot
 */
int partition (int arr[], const int left, const int right)
{
    int pivot = arr[right]; // pivot
    int i = (left - 1);
    int j = left;
    for (j = left; j <= (right - 1); j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return (i + 1);
}


// Function returns the k'th smallest
//element in the arr within `left…right`
// (i.e., `left <= k <= right`).
int quickselect(int arr[], const int left, const int right, const int k)
{
    // If k is smaller than number of
    // elements in array
    if (k > 0 && k <= (right - left + 1))
    {
        // Partition the array around last
        // element and get position of pivot
        // element in sorted array
        int index = partition(arr, left, right);

        // If position is same as k
        if (index - left == k - 1)
            return arr[index];

        // If position is more, recur
        // for left subarray
        if (index - left > k - 1)
            return quickselect(arr, left, index - 1, k);

        // Else recur for right subarray
        return quickselect(arr, index + 1, right,
                           k - index + left - 1);
    }
}


int main()
{
    int arr[] = {1, 0, 10, 4, 3, 18, 15};

    const  int arr_size = sizeof(arr) / sizeof(arr[0]);

    const int k = 2;

    const int smallestElement = quickselect(arr, 0, arr_size - 1, k);

    printf("k'th smallest element is %d\n",smallestElement);

    return 0;
}

Output:

QuickSelect Complexity:

Time Complexity
Best	O(n)
Worst	O(n²)
Average	O(n*log n)

Quickselect Algorithm: Quick Select Algorithm With Example Code

What is Quickselect Algorithm:

Selection Algorithm Pseudocode:

QuickSelect Complexity:

Recommended Articles for you: