/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

1 vote237 views1 answer
Context error in android studio
Java
0 vote234 views1 answer
Exception in thread "main" java.util.zip.ZipException: error
Java
2 votes310 views3 answers
List in java
Java
0 vote240 views1 answer
Java platform runlater keeps running
Java
1 vote226 views1 answer
Textarea user select disable java swing
Java
10 votes222 views3 answers
Float java
Java
0 vote250 views2 answers
Andriod button wont change color
Java
1 vote240 views2 answers
Java importing
Java
1 vote238 views1 answer
Turn off focus border java
Java
0 vote229 views1 answer
Delete one item from list recycleview
Java