Java Program to Find ith Largest Number from a Given 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.

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