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:
Java Program to Implement Pagoda
The HttpMediaTypeNotAcceptableException in Spring MVC
Spring Boot - Batch Service
Luồng Daemon (Daemon Thread) trong Java
Removing all duplicates from a List in Java
Java Program to Solve TSP Using Minimum Spanning Trees
Java 8 Collectors toMap
Java Program to implement Associate Array
Spring WebClient and OAuth2 Support
Hướng dẫn tạo và sử dụng ThreadPool trong Java
Registration – Password Strength and Rules
Redirect to Different Pages after Login with Spring Security
Spring Data JPA @Modifying Annotation
Java Program to Implement the Bin Packing Algorithm
Java Program to Represent Graph Using Adjacency Matrix
Java Program to Print only Odd Numbered Levels of a Tree
Java Program to Implement Hash Tree
Intro to Inversion of Control and Dependency Injection with Spring
Spring JDBC
Java Program to Permute All Letters of an Input String
Guide to the Volatile Keyword in Java
XML-Based Injection in Spring
Filtering a Stream of Optionals in Java
Tìm hiểu về xác thực và phân quyền trong ứng dụng
Java Program to Implement the One Time Pad Algorithm
Cachable Static Assets with Spring MVC
Spring Security 5 for Reactive Applications
Hashtable trong java
Java Program to Check Whether Topological Sorting can be Performed in a Graph
Hướng dẫn Java Design Pattern – Mediator
Ways to Iterate Over a List in Java
Java Program to Implement Hash Tables with Quadratic Probing