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:
Send an email using the SMTP protocol
Giới thiệu Design Patterns
Transactions with Spring and JPA
Spring Boot - Google OAuth2 Sign-In
Java 9 Stream API Improvements
Spring Security Registration – Resend Verification Email
Serialization và Deserialization trong java
Java Program to Implement Patricia Trie
Hashing a Password in Java
Convert a Map to an Array, List or Set in Java
Java equals() and hashCode() Contracts
Java Program to Generate All Pairs of Subsets Whose Union Make the Set
Comparing Strings in Java
Java Program to Check Whether a Given Point is in a Given Polygon
Spring Web Annotations
Introduction to Liquibase Rollback
Java Program to Implement Skip List
Kết hợp Java Reflection và Java Annotations
Java – Write to File
Count Occurrences of a Char in a String
Custom Thread Pools In Java 8 Parallel Streams
Java Program to Find Inverse of a Matrix
Check if there is mail waiting
Java Program to Perform Complex Number Multiplication
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Spring Data – CrudRepository save() Method
Multi Dimensional ArrayList in Java
Java Program to Generate Date Between Given Range
How to Add a Single Element to a Stream
Spring MVC Async vs Spring WebFlux
Hướng dẫn Java Design Pattern – Dependency Injection
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not