/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

5 votes336 views4 answers
Cors spring boot
Java Spring
0 vote264 views1 answer
Start with <> and end with <> in Java
Java
4 votes307 views10 answers
Array
Java
-1 vote272 views10 answers
Loop array
Java
1 vote263 views1 answer
Remove spaces at beginning and end of string java
Java
0 vote308 views1 answer
Java scan a file
Java
0 vote279 views1 answer
Matrix program
Java
0 vote293 views1 answer
Java random number generator 4
Java
0 vote363 views1 answer
Customized cache key java
Java
0 vote303 views1 answer
How to convert character into operator
Java