Java Program to Find ith Largest Element from a List using Order-Statistic Algorithm

«
»
This is a java program to find the ith largest element from a list using order-statistic algorithm. This version of the code uses quick sort partitioning technique.

Here is the source code of the Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.combinatorial;
  3.  
  4. import java.util.Scanner;
  5.  
  6. public class KthLargestOrderStatistics
  7. {
  8.     public static int partition(int[] array, int first, int last)
  9.     {
  10.         int pivot = array[first];
  11.         int pivotPosition = first++;
  12.         while (first <= last)
  13.         {
  14.             // scan for values less than the pivot
  15.             while ((first <= last) && (array[first] < pivot))
  16.             {
  17.                 first++;
  18.             }
  19.             // scan for values greater than the pivot
  20.             while ((last >= first) && (array[last] >= pivot))
  21.             {
  22.                 last--;
  23.             }
  24.             if (first > last)
  25.             {
  26.                 // swap the last uncoformed
  27.                 // element with the pivot
  28.                 swap(array, pivotPosition, last);
  29.             }
  30.             else
  31.             {
  32.                 // swap unconformed elements:
  33.                 // first that was not lesser than the pivot
  34.                 // and last that was not larger than the pivot
  35.                 swap(array, first, last);
  36.             }
  37.         }
  38.         return last;
  39.     }
  40.  
  41.     private static void swap(int[] array, int first, int last)
  42.     {
  43.         int temp;
  44.         temp = array[first];
  45.         array[first] = array[last];
  46.         array[last] = temp;
  47.     }
  48.  
  49.     public static int orderStatistic(int[] array, int k, int first, int last)
  50.     {
  51.         int pivotPosition = partition(array, first, last);
  52.         if (pivotPosition == k - 1)
  53.         {
  54.             return array[k - 1];
  55.         }
  56.         if (k - 1 < pivotPosition)
  57.         {
  58.             return orderStatistics(array, k, first, pivotPosition - 1);
  59.         }
  60.         else
  61.         {
  62.             return orderStatistics(array, k, pivotPosition + 1, last);
  63.         }
  64.     }
  65.  
  66.     // iterative version
  67.     private static int orderStatistics(int[] array, int k, int first, int last)
  68.     {
  69.         int pivotPosition = partition(array, first, last);
  70.         while (pivotPosition != k - 1)
  71.         {
  72.             if (k - 1 < pivotPosition)
  73.             {
  74.                 last = pivotPosition - 1;
  75.             }
  76.             else
  77.             {
  78.                 first = pivotPosition + 1;
  79.             }
  80.             pivotPosition = partition(array, first, last);
  81.         }
  82.         return array[k - 1];
  83.     }
  84.  
  85.     public static int kthSmallest(int[] array, int k)
  86.     {
  87.         return orderStatistic(array, k, 0, array.length - 1);
  88.     }
  89.  
  90.     public static int kthLargest(int[] array, int k)
  91.     {
  92.         return orderStatistic(array, array.length - k + 1, 0, array.length - 1);
  93.     }
  94.  
  95.     public static void main(String[] args)
  96.     {
  97.         Scanner sc = new Scanner(System.in);
  98.         System.out.println("Enter the number of elements in the sequence: ");
  99.         int n = sc.nextInt();
  100.         int[] sequence = new int[n];
  101.         System.out.println("Enter the elements of the sequence: ");
  102.         for (int i = 0; i < sequence.length; i++)
  103.         {
  104.             sequence[i] = sc.nextInt();
  105.         }
  106.         System.out
  107.                 .println("Enter the kth index to be returned as kth largest element of the sequence:");
  108.         int k = sc.nextInt();
  109.         System.out.println("Kth largest:" + kthLargest(sequence, k));
  110.         sc.close();
  111.     }
  112. }

Output:

advertisement
$ javac KthLargestOrderStatistics.java
$ java KthLargestOrderStatistics
 
Enter the number of elements in the sequence: 
10
Enter the elements of the sequence: 
2 5 6 7 4 7 9 5 8 1
Enter the kth index to be returned as kth largest element of the sequence:
4
Kth largest:7

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.