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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Implement Heap’s Algorithm for Generating Permutations

» Next - Java Program to Perform Searching based on Locality of Reference

Related Posts:

Recommended Articles: