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 kth 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 kth 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 kth smallest element and it is returned.

3.  If the index is less than k (k > pivotIndex) then kthsmallest 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:

Recommended Articles for you:

• Quick Sort Algorithm with example code.
• Best programming laptop for programmers.
• How do you reverse an array in C?
• C program to find the Median of two sorted arrays of different sizes.
• Basics of the recursive function.
• Merge Sort algorithm with example code.
•  C program to rearrange array such that even positioned are greater than odd.
• How to rotate an array left and right by a given number K?
• Why is it faster to process sorted array than an unsorted array?
• How to access 2d array in C?
• How to remove duplicates from a given array in C?
• Array interview questions.
• How to create dynamic array in C?
• How to pass an array as a parameter in C?