The Quick Select algorithm is an efficient algorithm used to find the k-th smallest element in an unsorted array or list. It is based on the QuickSort algorithm and has an average time complexity of O(n), where n is the number of elements in the array.

How it Works

The Quick Select algorithm works by partitioning the array based on a pivot element. It selects a pivot element and rearranges the array such that all elements smaller than the pivot are on the left side, and all elements greater than the pivot are on the right side. If the pivot element is at the k-th position, then it is the k-th smallest element. If the pivot element is on a position greater than k, then we recursively apply the Quick Select algorithm on the left subarray. Otherwise, if the pivot element is on a position less than k, we recursively apply the Quick Select algorithm on the right subarray.

Example Code

Here’s an example implementation of the Quick Select algorithm in Python:

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

    for j in range(low, high):
        if arr[j] <= pivot:
            i = 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):
    if low < high:
        pivot_index = partition(arr, low, high)

        if pivot_index == k - 1:
            return arr[pivot_index]
        elif pivot_index > k - 1:
            return quick_select(arr, low, pivot_index - 1, k)
        else:
            return quick_select(arr, pivot_index + 1, high, k)

    return arr[low]


# Example usage
array = [6, 8, 2, 10, 5]
k = 3
element = quick_select(array, 0, len(array) - 1, k)
print(f"The k-th smallest element is {element}")

In this example, we have an array [6, 8, 2, 10, 5] and we want to find the 3rd smallest element. The Quick Select algorithm is used to find the element, and in this case, the output will be 5.

Conclusion

The Quick Select algorithm is a powerful algorithm for finding the k-th smallest element in an unsorted array. It has an average time complexity of O(n) and is often used in various applications such as finding the median or finding the k smallest elements. By partitioning the array based on a pivot element, the algorithm reduces the search space and quickly identifies the desired element.