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:
Recommended Package Structure of a Spring Boot Project
Tính trừu tượng (Abstraction) trong Java
Validations for Enum Types
Remove HTML tags from a file to extract only the TEXT
Concatenating Strings In Java
Java Program to Implement LinkedList API
Jackson Unmarshalling JSON with Unknown Properties
Java CyclicBarrier vs CountDownLatch
Quick Guide on Loading Initial Data with Spring Boot
Java Program to Implement ConcurrentSkipListMap API
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Remove the First Element from a List
Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm
Java Program to Represent Linear Equations in Matrix Form
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
Hướng dẫn Java Design Pattern – Bridge
Spring MVC Tutorial
Implementing a Runnable vs Extending a Thread
Programmatic Transaction Management in Spring
Jackson Ignore Properties on Marshalling
Life Cycle of a Thread in Java
Java Program to Implement Quick sort
Fixing 401s with CORS Preflights and Spring Security
Java Program to Implement AttributeList API
Apache Tiles Integration with Spring MVC
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Spring Boot - Sending Email
Filtering and Transforming Collections in Guava
Java Program to Implement Hash Tables Chaining with Binary Trees
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Java Program to Implement Binomial Heap
Guide to ThreadLocalRandom in Java