Kth Largest element in an array using QuickSort in JAVA

You have always tried to find the largest element in an array. Today its time to take it to the next step, now we will try to find the kth largest element in an array in Java using quicksort where the value of k is given by the user.

Kth largest element in an array using quicksort in JAVA

You must have thought by now that it is as same as finding the largest element in an array, but let me tell you that that is a very basic method and if you have studied the concept of time complexity you will know that this basic method takes a lot of time to find the result because in this method it will process all the elements of array and then try to sort it and then find the kth largest element.

As a good programmer, it is our duty to find the best possible solution that has minimum time complexity. hence we solve this problem using quicksort because its time complexity is O(n) in an average case.it will break the array into two part and will only sort the required array instead of sorting the whole array thereby reducing its time complexity.
let’s take an array of size =7:
5  6  3  7  9  2  4

if the value of k=2 (2nd largest element )

Steps to sort only half portion of the array:

  1. Perform the quick sort at first, you will get a middle element (after sorting middle index=2, value=4)

  2. Compare your required position with middle element position ( required =size – k i.e 7-2=5, middle index=2)

  3. If it is equal voila! you got the answer, if not equal check for smaller or greater. (not equal)

  4. If your required position is greater than middle element position than quick sort right subarray
    ( yes 5>2 , sort right subarray)

  5. If found smaller quick sort left subarray

  6. After performing several recursion you will get your answer ( middle index =5, required value=7)

Here below is the code provided for the same:

import java.util.Scanner;

public class Largest_kth {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter size of array");
    int size = sc.nextInt();

    int[] arra = new int[size];
 
    System.out.println("Enter the array");

    for (int i = 0; i < size; i++) {
      arra[i] = sc.nextInt();
    }

    System.out.println("enter value of k for finding kth largest");

    int k = sc.nextInt();

    System.out.println("kth largest element= " + arra[find_largest(arra, size, k)]);

    sc.close();
  }

  static int quickSort(int array[], int start, int end)
 {
     int i = start;                            //for swapping with starting index 
 
       for (int t = start; t < end; t++) {

          if (array[t] < array[end]) {   //pivot is right most element 

             swap(array, t, i);  //swap if elemnt is smaller than pivot

             i++;
            }

       }
  
    if (array[i] > array[end])      //if pivot is smaller than all right most element
    
     swap(array, i, end);   //bring the pivot element in middle

    return i;                      //return the pivot position
  }

  static int find_largest(int a[], int size, int k)
  {
    
    int i = quickSort(a, 0, size - 1);   //storing the mediator index 

    while (i != size - k)     //   checking if mediator index is equal to required index 
    {
      if (i < size - k)    //if mediator index smaller than required then sort right sub array
   
     i = quickSort(a, i + 1, size - 1);

      else

        i = quickSort(a, 0, i - 1);   // else sort left sub array
    }
    return i;
  }

  static void swap(int arr[], int s, int l) {    //for swapping of elements

    int temp = arr[s];

    arr[s] = arr[l];

    arr[l] = temp;

  }
}

There are several methods to solve this problem. some are very much better than this one, time complexity wise. One can use any method according to their requirement. Similarly, you can find the smallest element also.

Hope you understand this code.

Also learn:

2 responses to “Kth Largest element in an array using QuickSort in JAVA”

  1. Lustymonk says:

    Most precise and best content.

  2. Anubhav Srivastava says:

    nicely explained

Leave a Reply

Your email address will not be published. Required fields are marked *