/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 vote195 views1 answer
Instance of keyword
Java
0 vote143 views1 answer
Pass a list of string as PathVariable to api spring boot
Java
1 vote145 views1 answer
Android highlight part of textview
Java
0 vote131 views1 answer
How to Register a Custom Auto-Configuration?
Java
0 vote139 views1 answer
Reponse entity as result spring controller
Java
0 vote138 views3 answers
Change replication factor hadoop cluster command
Java
2 votes654 views1 answer
Execution failed for task ':app:signReleaseBundle'. > A failure occurred while executing com.android.build.gradle.internal.tasks.Finalize Bundle Task$BundleTool Runnable
Java
-1 vote147 views1 answer
Directory size java
Java
0 vote155 views1 answer
Check authorities spring
Java Spring
0 vote92 views1 answer
Spring send parameter to url
Java