/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 vote499 views1 answer
Spring delete objest from database that are not in your object list
Java Spring
1 vote448 views1 answer
Android recyclerview show hide item with animation with default animation
Java
0 vote367 views1 answer
Advantages of Exception handling in java
Java
0 vote400 views1 answer
Java lb to kg
Java
0 vote368 views1 answer
Mp3 player Java
Java
6 votes382 views3 answers
Java get current year
Java
1 vote380 views1 answer
Set height of layout programmatically android
Java
1 vote342 views1 answer
Jersey test dependency
Java
6 votes397 views2 answers
RecyclerView OnClickListener
Java
0 vote388 views1 answer
Fail method java
Java