Find k'th smallest element in an array

Given an array of n elements and a value k, find out the k^th smallest value in the array.

Method 1: Use Sorting

1. Sort the array in non decreasing order.
2. return arr[k-1]

Time Complexity: O(n log n)

Method 2: Use QuickSelect

QuickSelect has a procedure similar to QuickSort algorithm. It uses the partition function of quicksort to find the index of the pivot element and repeats the following steps until the pivot index is not equal to k.

1. Find the index of last element of array as pivot.
2. If pivot index = k: return array[p_index]
3. If pivot index <  k: Search in the left half of the array[1...p_Index-1]
4. If pivot index > k: Search in the right half of the array[p_Index+1...n]

The algorithm calls the partition function but unlike quicksort which calls partition function for both the halves of the array, quickselect calls the partition function only for the half where the k^th smallest element could be found.

You may ask, Why searching only in one-half works?

The answer is simple, each time the partition function is called it brings all the elements larger than the pivot ahead of it and the elements smaller than the pivot before it.

Hence the kth element will always lie in the half we search with respect to our pivot index value found.

Code in Python:

# Find the Kth smallest element in a given array.
# taking smallest in arr as 1st smallest

"""
Approach used: QuickSelect
Time Complexity: O(n)
"""


def partition(arr, low, high):
    i = (low - 1)
    pivot = arr[high]  # pivot

    for j in range(low, high):

        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
            # increment index of smaller element
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_select(arr, low, high, k):
    # arr follows zero indexing hence kth smallest will be at index (k - 1)
    k -= 1
    while low < high:
        p_index = partition(arr, low, high)

        # found the kth smallest value
        if p_index == k:
            return arr[p_index]
        # pivot index is less than k hence kth smallest is in the right half
        elif p_index < k:
            low = p_index + 1
        # pivot index is greater than k hence kth smallest is in the left half
        else:
            high = p_index - 1
    # if k < 0 or k > len(arr) then simply return the smallest or largest value in arr
    return arr[low]


arr = [10, 7, 8, 9, 1, 5]
n = len(arr) - 1

# find 4th smallest element in the array
print(quick_select(arr, 0, n, 4))

"""
Outputs:
8
"""

Time Complexity:

The time complexity of QuickSelect is linear that is O(n). But it highly depends on the pivot index found and in what ratio is the array dividing in each iteration.
In the worst case, the performance of quickselect will be same as quicksort, that is, O(n2) when pivot always divides the array in only one-half.

Applications:

This question can be asked in various ways in interviews.

One popular question is to find the median of an array. A median is a middle element when the array is sorted. 

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal