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.
package com.sanfoundry.combinatorial; import java.util.Scanner; public class KthLargestOrderStatistics { public static int partition(int[] array, int first, int last) { int pivot = array[first]; int pivotPosition = first++; while (first <= last) { // scan for values less than the pivot while ((first <= last) && (array[first] < pivot)) { first++; } // scan for values greater than the pivot while ((last >= first) && (array[last] >= pivot)) { last--; } if (first > last) { // swap the last uncoformed // element with the pivot swap(array, pivotPosition, last); } else { // swap unconformed elements: // first that was not lesser than the pivot // and last that was not larger than the pivot swap(array, first, last); } } return last; } private static void swap(int[] array, int first, int last) { int temp; temp = array[first]; array[first] = array[last]; array[last] = temp; } public static int orderStatistic(int[] array, int k, int first, int last) { int pivotPosition = partition(array, first, last); if (pivotPosition == k - 1) { return array[k - 1]; } if (k - 1 < pivotPosition) { return orderStatistics(array, k, first, pivotPosition - 1); } else { return orderStatistics(array, k, pivotPosition + 1, last); } } // iterative version private static int orderStatistics(int[] array, int k, int first, int last) { int pivotPosition = partition(array, first, last); while (pivotPosition != k - 1) { if (k - 1 < pivotPosition) { last = pivotPosition - 1; } else { first = pivotPosition + 1; } pivotPosition = partition(array, first, last); } return array[k - 1]; } public static int kthSmallest(int[] array, int k) { return orderStatistic(array, k, 0, array.length - 1); } public static int kthLargest(int[] array, int k) { return orderStatistic(array, array.length - k + 1, 0, array.length - 1); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the number of elements in the sequence: "); int n = sc.nextInt(); int[] sequence = new int[n]; System.out.println("Enter the elements of the sequence: "); for (int i = 0; i < sequence.length; i++) { sequence[i] = sc.nextInt(); } System.out .println("Enter the kth index to be returned as kth largest element of the sequence:"); int k = sc.nextInt(); System.out.println("Kth largest:" + kthLargest(sequence, k)); sc.close(); } }
Output:
$ 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
Related posts:
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Concurrent Test Execution in Spring 5
Java Program to Find the Mode in a Data Set
Spring WebClient Filters
Spring Boot Configuration with Jasypt
Introduction to Java 8 Streams
Java Program to Implement Brent Cycle Algorithm
Convert Hex to ASCII in Java
StringBuilder vs StringBuffer in Java
Java Program to Implement Unrolled Linked List
Arrays.asList vs new ArrayList(Arrays.asList())
Java Program to Perform Searching Using Self-Organizing Lists
Java Program to Implement WeakHashMap API
Java Program to Implement HashTable API
Java Program to Implement Repeated Squaring Algorithm
Java Program to Check whether Directed Graph is Connected using DFS
Java – Convert File to InputStream
Reading an HTTP Response Body as a String in Java
Autoboxing và Unboxing trong Java
Java Program to Perform the Sorting Using Counting Sort
Spring Boot - Tracing Micro Service Logs
Lập trình đa luồng với CompletableFuture trong Java 8
Guide To CompletableFuture
How to Find an Element in a List with Java
Java Program to Find kth Smallest Element by the Method of Partitioning the Array
Logout in an OAuth Secured Application
Java Program to Perform the Unique Factorization of a Given Number
Spring Boot - Creating Docker Image
Java Program to implement Priority Queue
Java Program to Implement Trie
Dockerizing a Spring Boot Application
Easy Ways to Write a Java InputStream to an OutputStream