Find median of an array using Quick Select Algorithm in Java

In this module, we are going to discuss find the median of an array using the quick-select algorithm in Java. The main aim of the quick-select algorithm is to find the kth smallest element on the unsorted array elements list. One of the basic ideas in finding the median of an array is to implement a quick-select algorithm. We take a single array arr which is unsorted and returns the median of an array as an output.

Test Criteria :

array arr={32,22,55,36,50,9}
After sorting arr={9,22,32,36,50,55} median=34
array arr={32,22,9,35,50}
After sorting arr={9,22,32,35,50} median=32

Implementing Quick Select Algorithm to Find Median in Java

The following code gives a complete understanding of the implementation of a quick-select algorithm.

import java.io.*;
import java.util.*;
public class Quick_Select
{ 
    static int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];          //taken pivot element as last element
        int z = (low-1);
        for (int j=low; j<high; j++) 
        { 
            if (arr[j] < pivot) 
            {                                  //arranging all elements that are less than pivot
                z++; 
                int temp = arr[z]; 
                arr[z] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
        int temp = arr[z+1]; 
        arr[z+1] = arr[high];     //finalizing th position of piviot element in array which is sorted position
        arr[high] = temp; 
  
        return z+1; 
    } 
    public static int kselection(int[] arr, int low,  
                                  int high, int k) 
    { 
        int partition_sorting_value = partition(arr,low,high); 
        if(partition_sorting_value == k)           //comparing the position returned with the desired position k
            return arr[partition_sorting_value];     
        else if(partition_sorting_value < k )      //partition value is less than k search left half array
            return kselection(arr, partition_sorting_value + 1, high, k ); 
        else                //partition value is greater than k search right half array         
            return kselection(arr, low, partition_sorting_value-1, k );          
    }
    static void find_median(int arr[])
    {
        int len=arr.length;
        if(len%2==1)
        {
            System.out.println(kselection(arr,0,len-1,len/2));  //median is at n/2 position if length is odd
        }
        else
        {
            int a=kselection(arr,0,len-1,len/2);      
            int b=kselection(arr,0,len-1,len/2-1);
            System.out.println((a+b)/2);       //median by performing average between n/2 and n/2-1
        }
    }
    public static void main(String[] args)throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s[]=br.readLine().trim().split("\\s+");
        int arr[]=new int[s.length];
        for(int i=0;i<s.length;i++)
        {
            arr[i]=Integer.parseInt(s[i]);
        }
        find_median(arr);
        
    }
}

Output :

Test Case 1:

32 22 9 35 50
32

Test Case 2:

32 22 55 36 50 9
34

Explanation:

Here, what we have done first is sending array to find_median() if the length is even we have taken two variables for finding the n/2 and n/2-1 elements as ‘a’ and ‘b’ which get the result from function call to the kselection(). The partition() is used to sort the elements of given array indexing from range low to high passed to the function which returns the taken pivot location after placing it in actual sorted position. After receiving the location we can compare that with the required position of the kth smallest element which is median in the current program.