Sort Comparisons Counter

Question

I have this code that sorts an array that is filled with random numbers and counts the number comparisons that it takes to complete the sort. I'm using the sort methods selection bubble and merge sort. I have the counter for the selection and the bubble but not the merge I have no clue where to put it. It might be a simple answer but I just can't get it to work.

Code:

/***********************************************************************
     * 
     * Selection Sort:
     * Reads in the array and then searches for the largest number. 
     * After it finds the largest number, it then swaps that number with the
     * last number of the array
     * Precondition: takes in an array of "n" items, which in this particular
     * case is 2000, 4000, 6000, 8000, and 10000 random items in an array
     * Postcondition: all numbers are sorted in ascending order
     * 
     **********************************************************************/
    public static int SelectionSort (int[] intArray) {

        //Set initial count of comparisons at 0         
        comparisons= 0;        //Number of swaps made


        for(int last = intArray.length - 1; last > 0; last--) {

            int largestIndex = last;    //Int which places the largest number at the end of the array

            // Find largest number
            for(int i = 0; i < last; i++) {

                //if i > the last number
                if (intArray[i] > intArray[largestIndex]){
                    largestIndex = i;       //switch the last number and i
                } // end if

                //Comparison+1 
                comparisons++;

            } // end for

            // Swap last element with largest element
            int largest = intArray[last];
            intArray[last] = intArray[largestIndex];
            intArray[largestIndex] = largest;

        }
        //Return comparison counter
        return comparisons;
    }

    /***********************************************************************
     * 
     * Bubble Sort:
     * Takes an array of random integers and sorts them by comparing adjacent
     * numbers to one another. Whichever the larger adjacent number, Bubble
     * Sort switches it towards the back end of the adjacent numbers. It does
     * this until the list is fully sorted.
     * Precondition: takes in a random array of integers
     * Postcondition: array is sorted from smallest to largest
     * 
     **********************************************************************/
    public static int BubbleSort (int[] intArray) {

        //Instance Variables    
        int n = intArray.length;
        //boolean swap;   
        comparisons = 0;

        //swap = false;
        //for i starts at 0, when i is less than array length, i++ until reach array length
        for(int i=0; i < n; i++) {

            for(int j=1; j < (n-i); j++) {

                if(intArray[j-1] > intArray[j]) {

                    //Swap the elements
                    int temp = intArray[j];
                    intArray[j] = intArray[j+1];
                    intArray[j+1] = temp;
                    //swap = true;

                } 
            //comparisons get +1 until the for loop is done sorting
            comparisons++;
           }  //End for loop
        }
        //Return the comparison counter
         return comparisons;
    }

    /************************************************************************************
     * 
     * Merge Sort:
     * This method takes a random array and splits it in half. Once the array is
     * split in half, it creates a temp0rary array. This temporary array is built by
     * the method searching the two halves of the original array and puts the information
     * in order stored in the temporary array. Once all the numbers are in order, the 
     * temporary array is then copied back to the original array.
     * Precondition: take in an array of random integers
     * Postcondition: return the random array sorted in ascending order
     * 
     **********************************************************************************/
    public static int mergeSort(int[] intArray) {

        if(intArray.length >= 2) {

            int mid = intArray.length / 2;
            //Create 2 arrays to store half of the data in each
            int[] first = new int[mid];     //holds first half of array
            int[] second = new int[intArray.length - mid];  //holds second half of array

            for(int i = 0; i < first.length; i++) { 
                first[i] = intArray[i];     
            }

            for(int i = 0; i < second.length; i++) {
                second[i] = intArray[mid+i];
            }

            mergeSort(first);
            mergeSort(second);
            merge(first, second, intArray);     //Merge all together

        }

        return comparisons;
    }

    //merging first and second halves of mergeSort array
    public static int merge(int[] first, int[] second, int[] intArray) {

        int iFirst = 0;
        int iSecond = 0;
        int i = 0; 

        //moving the smaller element into intArray
        while(iFirst < first.length && iSecond < second.length) {

            comparisons++;

            if(first[iFirst] < second[iSecond]) {
                intArray[i] = first[iFirst];
                iFirst++;
            }

            else {
                intArray[i] = second[iSecond];
                iSecond++;
            }
            i++;
        }


        //copying the remaining of first array
        while(iFirst < first.length) {
            intArray[i] = first[iFirst];
            iFirst++; i++; 
        }

        //copying the remaining of second array
        while(iSecond < second.length)
        {
            intArray[i] = second[iSecond];
            iSecond++; i++; 
        } 

        return comparisons;
    }

    /**************************************************************************************
     * Instance methods:
     * These methods perform actions to the array.
     * 
     * copyArray()--makes a copy of the array to be used in the main class
     *              so that each method is able to create the same array
     * 
     * printArray()--prints out the array for display
     * 
     * randomArray()--creates a random integer array used by all three sorting methods
     * 
     **************************************************************************************/

    public static int[] copyArray(int[] intArray) {

        //Constructor that creates copyArray
        int[] copyArray = new int[intArray.length];     //siz equal to the length of the array

        for(int i = 0; i < intArray.length; i++){
            copyArray[i] = intArray[i];
        } // end for

        return copyArray;

    } // end copyArray

    //Prints out array
    public static void printArray(int[] intArray){
        //Preconditions
        //  Input: unsorted integer array   
        //  Assumptions: array is full
        //Postconditions
        //  Output: none
        //  Actions: array is displayed on screen

        System.out.print("Array==> ");
        for(int i = 0; i < intArray.length; i++){
            System.out.print(intArray[i] + " ");
        } // end for

        System.out.println(" ");

    } // end printArray

    //Creates a random array that is used for each sorting method
    public static int[] randomArray(int array, double range){
        //Preconditions
        //  Input: size of array(n), range of integers (0 to range)
        //  Assumptions: none
        //Postconditions
        //  Output: array of random integers 0 to floor(range) 
        //  Actions: none

        int[] intArray = new int[array];

        for(int i = 0; i < array; i++){
            intArray[i] = (int)(Math.random() * range);
        } // end for

        return intArray;

    } // end randomIntArray


}

Answer 1

When (or just prior to) the following lines are executed:

• if (intArray[i] > intArray[largestIndex]){
• if(intArray[j-1] > intArray[j]) {
• if(first[iFirst] < second[iSecond]) {

Your mergeSort method uses recursion. As such, it needs to take a comparisons parameter, and pass that down to each subsequent method call and receive the resulting value back again.

public static int mergeSort(int[] intArray, int comparisons) {

    if(intArray.length >= 2) {

        int mid = intArray.length / 2;
        //Create 2 arrays to store half of the data in each
        int[] first = new int[mid];     //holds first half of array
        int[] second = new int[intArray.length - mid];  //holds second half of array

        for(int i = 0; i < first.length; i++) { 
            first[i] = intArray[i];     
        }

        for(int i = 0; i < second.length; i++) {
            second[i] = intArray[mid+i];
        }

        comparisons = mergeSort(first, comparisons);
        comparisons = mergeSort(second, comparisons);
        comparisons = merge(first, second, intArray, comparisons);     //Merge all together

    }

    return comparisons;
}

//merging first and second halves of mergeSort array
public static int merge(int[] first, int[] second, int[] intArray, int comparisons) {

    int iFirst = 0;
    int iSecond = 0;
    int i = 0; 

    //moving the smaller element into intArray
    while(iFirst < first.length && iSecond < second.length) {

        comparisons++;

        if(first[iFirst] < second[iSecond]) {
            intArray[i] = first[iFirst];
            iFirst++;
        }

        else {
            intArray[i] = second[iSecond];
            iSecond++;
        }
        i++;
    }


    //copying the remaining of first array
    while(iFirst < first.length) {
        intArray[i] = first[iFirst];
        iFirst++; i++; 
    }

    //copying the remaining of second array
    while(iSecond < second.length)
    {
        intArray[i] = second[iSecond];
        iSecond++; i++; 
    } 

    return comparisons;
}