Question

9. Modify the quicksort and mergesort programs we learnt during the class to count the number of element comparisons for the two sorting methods. Use the following test drive to test them.

public class Sorts

{

   int numComparisions = 0;

   public void quicksort(int [] x, int l, int h)

   {

// your modifies codes go here

   }

   public void mergesort(int [] x, int l, int h)

   {

// your modifies codes go here

   }

   public static void main(String [] args)

   {

Sorts sorts = new Sorts();

int N = 10000;

int [] x = new int[N];

int [] y = new int[N];

for (int n=0; n < N; n++)

x[n]=y[n] = (int)(Math.random()*N*2);

sorts.quicksort(x,0,x.length-1);

System.out.println("Quicksort:#C="+ sorts.numComparisons);

sorts.numComparisons = 0;

sorts.quicksort(y,0,y.length-1);

System.out.println("Mergesort:#C="+ sorts.numComparisons);

   }

}

10. Modify your program above to count and print out how many times of recursive calls have

been made during the sorting.

Answer 1

Merge Sort program with count of comparisons and recursive calls:

class Main {
    public static int count_comparison = 0, count_calls = 0;
        // Merges two subarrays of arr[].
        // First subarray is arr[l..m]
        // Second subarray is arr[m+1..r]
        void merge(int arr[], int l, int m, int r)
        {
                // Find sizes of two subarrays to be merged
                int n1 = m - l + 1;
                int n2 = r - m;

                /* Create temp arrays */
                int L[] = new int[n1];
                int R[] = new int[n2];

                /*Copy data to temp arrays*/
                for (int i = 0; i < n1; ++i)
                        L[i] = arr[l + i];
                for (int j = 0; j < n2; ++j)
                        R[j] = arr[m + 1 + j];

                /* Merge the temp arrays */

                // Initial indexes of first and second subarrays
                int i = 0, j = 0;

                // Initial index of merged subarry array
                int k = l;
                while (i < n1 && j < n2) {
                        if (L[i] <= R[j]) {
                            count_comparison += 1;
                                arr[k] = L[i];
                                i++;
                        }
                        else {
                                arr[k] = R[j];
                                j++;
                        }
                        k++;
                }

                /* Copy remaining elements of L[] if any */
                while (i < n1) {
                        arr[k] = L[i];
                        i++;
                        k++;
                }

                /* Copy remaining elements of R[] if any */
                while (j < n2) {
                        arr[k] = R[j];
                        j++;
                        k++;
                }
        }

        // Main function that sorts arr[l..r] using
        // merge()
        void sort(int arr[], int l, int r)
        {
                if (l < r) {
                        // Find the middle point
                        int m = (l + r) / 2;

                        // Sort first and second halves
                        sort(arr, l, m);
                        count_calls += 1; 
                        sort(arr, m + 1, r);
                        count_calls += 1; 

                        // Merge the sorted halves
                        merge(arr, l, m, r);
                }
        }

        /* A utility function to print array of size n */
        static void printArray(int arr[])
        {
                int n = arr.length;
                for (int i = 0; i < n; ++i)
                        System.out.print(arr[i] + " ");
                System.out.println();
        }

        // Driver method
        public static void main(String args[])
        {
                int N = 10000;
                int [] x = new int[N];
                int [] y = new int[N];
                
                for (int n=0; n < N; n++)
                {
                    x[n]=y[n] = (int)(Math.random()*N*2);
                } 

                System.out.println("Given Array");
                printArray(x);

                Main ob = new Main();
                ob.sort(x, 0, x.length - 1);

                System.out.println("\nSorted array");
                printArray(x);
                System.out.println("\nNumber of comparison are:" + count_comparison);
                System.out.println("\nNumber of recursive calls are:" + count_calls);
                
        }
}

Quick Sort program with count of comparisons and recursive calls:

class Main 
{ 
    public static int count_comparisons = 0, count_calls = 0;   //  variables to capture counts
        /* This function takes last element as pivot, 
        places the pivot element at its correct 
        position in sorted array, and places all 
        smaller (smaller than pivot) to left of 
        pivot and all greater elements to right 
        of pivot */
        int partition(int arr[], int low, int high) 
        { 
                int pivot = arr[high]; 
                int i = (low-1); // index of smaller element 
                for (int j=low; j<high; j++) 
                { 
                    count_comparisons += 1;
                        // If current element is smaller than the pivot 
                        if (arr[j] < pivot) 
                        { 
                                i++; 

                                // swap arr[i] and arr[j] 
                                int temp = arr[i]; 
                                arr[i] = arr[j]; 
                                arr[j] = temp; 
                        } 
                } 

                // swap arr[i+1] and arr[high] (or pivot) 
                int temp = arr[i+1]; 
                arr[i+1] = arr[high]; 
                arr[high] = temp; 

                return i+1; 
        } 


        /* The main function that implements QuickSort() 
        arr[] --> Array to be sorted, 
        low --> Starting index, 
        high --> Ending index */
        void sort(int arr[], int low, int high) 
        { 
                if (low < high) 
                { 
                        /* pi is partitioning index, arr[pi] is 
                        now at right place */
                        int pi = partition(arr, low, high); 

                        // Recursively sort elements before 
                        // partition and after partition 
                        sort(arr, low, pi-1); 
                        count_calls += 1;
                        sort(arr, pi+1, high); 
                        count_calls += 1;
                } 
        } 

        /* A utility function to print array of size n */
        static void printArray(int arr[]) 
        { 
                int n = arr.length; 
                for (int i=0; i<n; ++i) 
                        System.out.print(arr[i]+" "); 
                System.out.println(); 
        } 

        // Driver program 
        public static void main(String args[]) 
        { 
            int N = 10000;
                int [] x = new int[N];
                for (int n=0; n < N; n++)
                {
                    x[n] = (int)(Math.random()*N*2);
                } 
                
                System.out.println("Given Array");
                printArray(x);

                Main ob = new Main();
                ob.sort(x, 0, x.length - 1); 
                count_calls += 1;

                System.out.println("sorted array"); 
                printArray(x); 
                
                System.out.println("Number of comparisons :" + count_comparisons); 
                System.out.println("Number of recursive calls :" + count_calls);        
        } 
}