Question

Use quickselect algorithm to partition an array into 3 subsets: values less than pivot, values equal to pivot, and values greater than pivot. The pivot must be a random element of the array. Find S1(the number of elements less than the pivot), S2 (the number of elements equal to the pivot), and S3 (the number of elements greater than the pivot). Your code must use only one array and must be able to handle duplicate array elements. Use Java.

Answer 1

import java.util.Arrays;

class quickselect  

{

    public static int partition (int[] arr,int low, int high)

    {

        int pivot = arr[high], loc = low;

        for (int i = low; i <= high; i++)

        {

            if(arr[i] < pivot)

            {

                int a = arr[i];

                arr[i] = arr[loc];

                arr[loc] = a;

                loc++;

            }

        }

        int a = arr[high];

        arr[high] = arr[loc];

        arr[loc] = a;

        return loc;

    }

    public static int Smallest(int[] arr, int low,int high, int k)

    {

        int partition = partition(arr,low,high);

        if(partition == k)

            return arr[partition];    

        else if(partition < k )

            return Smallest(arr, partition + 1, high, k );

        else

            return Smallest(arr, low, partition-1, k );         

    }

    public static void main(String[] args)

    {

      int b,i;

        Scanner s = new Scanner(System.in);   
     System.out.print("Enter no. of elements you want in array:"); 
       b= s.nextInt();      
       int array[] = new int[b];       
       System.out.println("Enter all the elements:");    
       for(i = 0; i < b; i++)  
     {                
        array[i] = s.nextInt();

}   

        int kPosition = 3;

        int length = array.length;

         

        if(kPosition > length)

        {

            System.out.println("Exception Index out of bound");

        }

        else

        {

            System.out.println("smallest element in array : " +

                                kthSmallest(array, 0, length - 1,

                                                          kPosition - 1));

        }

    }

}