/Java/Quick select method for kth smallest element in java

Quick select method for kth smallest element in java

// Java code for kth smallest element in an array
import java.util.Arrays;
import java.util.Collections;
  
class GFG {
    // Standard partition process of QuickSort.
    // It considers the last element as pivot
    // and moves all smaller element to left of
    // it and greater elements to right
    public static int partition(Integer[] arr, int l,
                                int r)
    {
        int x = arr[r], i = l;
        for (int j = l; j <= r - 1; j++) {
            if (arr[j] <= x) {
                // Swapping arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
  
                i++;
            }
        }
  
        // Swapping arr[i] and arr[r]
        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
  
        return i;
    }
  
    // This function returns k'th smallest element
    // in arr[l..r] using QuickSort based method.
    // ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
    public static int kthSmallest(Integer[] arr, int l,
                                  int r, int k)
    {
        // If k is smaller than number of elements
        // in array
        if (k > 0 && k <= r - l + 1) {
            // Partition the array around last
            // element and get position of pivot
            // element in sorted array
            int pos = partition(arr, l, r);
  
            // If position is same as k
            if (pos - l == k - 1)
                return arr[pos];
  
            // If position is more, recur for
            // left subarray
            if (pos - l > k - 1)
                return kthSmallest(arr, l, pos - 1, k);
  
            // Else recur for right subarray
            return kthSmallest(arr, pos + 1, r, k - pos + l - 1);
        }
  
        // If k is more than number of elements
        // in array
        return Integer.MAX_VALUE;
    }
  
    // Driver program to test above methods
    public static void main(String[] args)
    {
        Integer arr[] = new Integer[] { 12, 3, 5, 7, 4, 19, 26 };
        int k = 3;
        System.out.print("K'th smallest element is " + kthSmallest(arr, 0, arr.length - 1, k));
    }
}
  
// This code is contributed by Chhavi

Source: geeksforgeeks.org

Similar codes

0 vote287 views3 answers
D/NetworkSecurityConfig: No Network Security Config specified, using platform default
Java
1 vote282 views3 answers
Recursion java
Java
6 votes272 views5 answers
SharedPreferences
Java
0 vote273 views1 answer
Java create date object from yesterday
Java
0 vote265 views1 answer
How to convert Javascript return value to String in Android
Java
0 vote277 views1 answer
Get char out of string java
Java
3 votes283 views1 answer
Java stream and filter
Java
0 vote312 views1 answer
Test excel file java multipart
Java
0 vote266 views1 answer
How to get string input line in java
Java
-2 votes293 views1 answer
Java create new empty list
Java