How to Implement the QuickSelect Algorithm

Introduction

The QuickSelect algorithm is a highly efficient method for finding the nth smallest (or largest) element in an unordered list. It closely relates to the QuickSort algorithm but focuses on partial sorting to improve efficiency. In this article, we will show how to implement it in Java.

How QuickSelect Works

QuickSelect works similarly to QuickSort by selecting a pivot element and partitioning the array around it. However, instead of sorting both halves, it only recurses into the part that contains the nth smallest element. This reduces the average time complexity to O(n), making it much faster than fully sorting the array.

QuickSelect Steps

1. Select a pivot element.
2. Partition the array into two sets: one set will contain elements less than the pivot, and the other one will contain elements greater than the pivot.
3. After partitioning, select a pivot again.
4. If the pivot is at n-1, return it.
5. Otherwise, recur into the left partition if n is there or right otherwise.

QuickSelect Implementation

We can implement the QuickSelect algorithm with the following Java code:

	@Test
	public void quickSelectTest() throws Exception {
		int[] array = { 8, 9, 4, 3, 23, 15 };
		int n = 3;
		System.out.println(quickSel(array, 0, array.length - 1, n - 1));
	}

    private static int quickSel(int[] array, int l, int r, int n) {
        if (l == r) {
            return array[l];
        }

        int pivot = part(array, l, r);
        
        if (pivot == n) {
            return array[pivot];
        } else if (pivot > n) {
            return quickSel(array, l, pivot - 1, n);
        } else {
            return quickSel(array, pivot + 1, r, n);
        }
    }

    private static int part(int[] array, int l, int r) {
        int pivot = array[r];
        int i = l;
        for (int j = l; j < r; j++) {
            if (array[j] <= pivot) {
                swapElements(array, i, j);
                i++;
            }
        }
        swapElements(array, i, r);
        return i;
    }

    private static void swapElements(int[] array, int i, int j) {
        int tempelem = array[i];
        array[i] = array[j];
        array[j] = tempelem;
    }

Complexity Analysis

• O(n) in the best case
• O(n²) if the pivot is always the smallest or largest element.
• Space Complexity is O(1)

Use Cases of QuickSelect

It can be used to find the median of an array, to solve the Nth largest/smallest element problem, and in stream processing in scenarios in which full sorting is not needed.

Conclusion

The QuickSelect algorithm provides a highly efficient way to find the k-th smallest element in an array without fully sorting it. With an average time complexity of O(n), it is widely used in applications requiring fast selection operations.

You can find the example code on Github.