Question

Create a program called DualPivotQuickSort.java that implements the QuickSort algorithm using Yaroslavskiy’s algorithm. The program should be able to do the following: accepts one command line parameter. The parameter specifies the path to a text file containing the integers to be sorted. The structure of the file is as follows: There will be multiple lines in the file (number of lines unknown). Each line will contain multiple integers, separated by a single whitespace. reads the integers from the text file in part a into an array of integers. sort the integers in descending order using DualPivotQuickSort, and then prints out a sorted version of these integers on a single line, separated by white spaces. The implementation should follow the given the pseudo code/algorithm description. DUALPIVOTQUICKSORTYAROSLAVSKIY(A, left, right) // Sort the array A in index range left, ... , right 1 if right left 1 p= A[le Show transcribed image text

Answer 1

Program:

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution{
  
   //RECURSIVE FUNCTION WHICH USES TWO PIVOTS P1 AND P2
   //UNLIKE THE TRADITIONAL QUICKSORT WHICH USES A SINGLE PIVOT
   //AND WHENEVER IT CALLS PARTITION IT ARRANGES THE ARRAY SUCH THAT
   //ALL THOSE NUMBERS BEFORE P1 ARE GREATER THAN OR EQUAL TO P1
   //AND ALL THOSE NUMBERS N BETWEEN P1 AND P2 FOLLOW P1>=N>=P2
   //AND ALL NUMBERS AFTER P2 ARE LESS THAN OR EQUAL TO P2
   //(THIS ORDER IS BECAUSE THE QUESTION ACCEPTED DESCENDING SORTING)  
   void DualPivotQuickSort(int arr[], int low, int high)
        {
       //ONLY WHEN THE SUB-PROBLEM HAS VALID START AND END
       if (low < high) {

            //LP USED FOR LEFT PIVOT AND RP USED FOR RIGHT PIVOT.
            //FOR LP WE USE THE ARRAY REPRESENTATION SO THAT IT CAN BE
            //PASSED AS REFERENCE AND CHANGES TO IT CAN BE APPLIED EVEN LOCALLY.
            int[] lp = {0};
            int rp;

            rp = partition(arr, low, high, lp);
            //AFTER THE ABOVE STEP WE HAVE BOTH LEFT AND RIGHT PIVOTS SET TO THE APPROPRIATE VALUES.  

            //RECURSIVELY SOLVE FOR THE SUBPROBLEMS :
            //LOW TO LP-1
            //LP+1 TO RP-1
            //RP+1 TO HIGH
            DualPivotQuickSort(arr, low, lp[0] - 1);
            DualPivotQuickSort(arr, lp[0] + 1, rp - 1);
            DualPivotQuickSort(arr, rp + 1, high);
       }
        }
  
        //SWAP FUNCTION TO SWAP TWO ARRAY ELEMENTS
        void swap(int arr[],int i1,int i2){
       int temp = arr[i1];
       arr[i1] = arr[i2];
       arr[i2] = temp;
        }

        //PARTITION FUNCTION THAT PROVIDES TWO PIVOTS THE LEFT PIVOT AND THE RIGHT PIVOT
        int partition(int arr[], int low, int high, int[] lp)
        {
       //BECAUSE WE WANT THE ARRAY TO BE IN DESCENDING ORDER , THEREFORE ARR[LOW] SHOULD BE GREATER THAN ARR[HIGH]
       if (arr[low] < arr[high])
            swap(arr, low, high);

      
       // P IS THE LEFT PIVOT AND Q IS THE RIGHT PIVOT.
       int j = low + 1;
       int g = high - 1, k = low + 1, p = arr[low], q = arr[high];

       while (k <= g) {
      
            // IF ELEMENTS ARE GREATER THAN OR EQUAL TO LEFT PIVOT
            if (arr[k] >= p) {
                swap(arr,k,j);
                j++;
            }
      
            //IF ELEMENTS ARE LESS THAN RIGHT PIVOT
            else if (arr[k] < q) {
                while (arr[g] <= q && k < g)
                    g--;
                swap(arr,k,g);
                g--;
                if (arr[k] >= p) {
                    swap(arr,k, j);
                    j++;
                }
            }
            k++;
       }
       j--;
       g++;
      
       // BRING PIVOTS TO THEIR APPROPRIATE POSITIONS
       swap(arr,low, j);
       swap(arr,high, g);
      
       //SETTING THE RIGHT AND LEFT PIVOTS.
       lp[0] = j;
      
       return g;
        }

       public static void main (String[] args) throws java.lang.Exception
       {

       String fileName;
       System.out.println("Please enter file name: ");      
       Scanner sc = new Scanner(System.in);
       fileName = sc.nextLine();
           //USED TO READ THE FILE
           BufferedReader reader;
      
           //VECTOR TO STORE THE INTEGERS READ FROM THE FILE
           Vector V = new Vector();
           try{
           reader = new BufferedReader (new FileReader(fileName));
           String line = reader.readLine();
           while(line!=null){
               String[] tokens = line.split(" ");
               for(String token:tokens){
                   if(token.length()>0)
                       V.add(Integer.parseInt(token));
               }
                
               line = reader.readLine();
                  }
           }catch(IOException e){
           e.printStackTrace();
           }
  
        
           int[] arr = new int[V.size()];    
           Iterator value = V.iterator();
           int i = 0;

           //COPYING THE VECTOR VALUES INTO THE ARRAY
           while(value.hasNext()){
           arr[i] = Integer.parseInt(String.valueOf(value.next()));
           i++;
           }

      
           Solution s=new Solution();
           s.DualPivotQuickSort(arr,0,V.size()-1);
       System.out.println("Array sorted in descending order: ");
           for(int j=0;j<V.size();j++)
            System.out.print(String.valueOf(arr[j])+" ");
       System.out.println("");
       }
}

input.txt:

input.txt:

output:

Screenshots(for better understanding):