1. Introduction

Finding the k’th smallest element in an array is a classic problem with various solutions. One of the most efficient approaches involves using the QuickSelect algorithm, which is a variation of the QuickSort sorting algorithm. In this post, we’ll be diving into how to implement this approach in Java.

2. Program Steps

1. Select a ‘pivot’ element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

2. The pivot, after partitioning, ends up in its sorted position in the array, with all smaller elements to its left and all greater elements to its right.

3. If the pivot’s position matches k, return the pivot. If k is smaller than the pivot’s position, recur for the left sub-array, otherwise recur for the right sub-array.

3. Code Program

public class KthSmallestElement {

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }

        int temp = arr[i];
        arr[i] = arr[high];
        arr[high] = temp;

        return i;
    }

    public static int kthSmallest(int[] arr, int low, int high, int k) {
        if (k > 0 && k <= high - low + 1) {
            int pos = partition(arr, low, high);

            if (pos - low == k - 1) {
                return arr[pos];
            }

            if (pos - low > k - 1) {
                return kthSmallest(arr, low, pos - 1, k);
            }

            return kthSmallest(arr, pos + 1, high, k - pos + low - 1);
        }

        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;
        System.out.println("K&apos;th smallest element is " + kthSmallest(arr, 0, arr.length - 1, k));
    }
}

Output:

K'th smallest element is 7

4. Step By Step Explanation

1. The partition function works by placing an element (pivot) in its correct sorted position in the array. All lesser elements are placed to the left of the pivot and all greater elements to the right.

2. The kthSmallest function uses this partitioning method. If the pivot's position matches k, the pivot is our answer.

3. If k is smaller than the pivot's position, the function recursively searches the left sub-array. Otherwise, it searches the right sub-array.

4. For the provided array and k=3, the third smallest element is 7.