Data Structures and Algorithm Analysis Java Write a program to verify your solut

Question

Data Structures and Algorithm Analysis Java

Write a program to verify your solution to Exercises 7.17. Your program should randomly generate three integer arrays of N=103, 105, and 107 elements and run either merge sort or insertion sort to sort the arrays in increasing and decreasing orders. Then run both insertion sort and merge sort on the three ordered and three reverse-ordered arrays and output the numbers of comparisons and assignments performed between elements of the input arrays during the executions of the two sorting algorithms on each of the arrays.

Explanation / Answer

Answer: See the analysis for insertion sort in ascending and decending order both:

--------------------------------------------

package sortinganalysis;

/**
* SortingAnalysis class
*
*/
public class SortingAnalysis {
   static int size1=103;
   static int size2=105;
   static int size3=107;

//function of insertion sort in ascending order
    static void insertionSortAscending(int array[])
    {
        int numComparisons=0;
        int numAssignments=0;
        for (int i=1; i<array.length; ++i)
        {
            int val = array[i];
            int j = i-1;               
            while (j>=0 && array[j] >= val)
            {
                numComparisons++;
               array[j+1] = array[j];
                j = j-1;
            }
            array[j+1] = val;
            numAssignments++;
        }
      
        System.out.println("Number of comparisons in Insertion sort in ascending order:"+numComparisons);
        System.out.println("Number of assignments in Insertion sort in ascending order:"+numAssignments);
    }
  
//function of insertion sort in descending order
static void insertionSortDecending(int array[])
   {
        int numComparisons=0;
        int numAssignments=0;
        for (int i=1; i<array.length; ++i)
        {
            int val = array[i];
            int j = i-1;               
            while (j>=0 && array[j] <= val)
            {
                numComparisons++;
               array[j+1] = array[j];
                j = j-1;
            }
            array[j+1] = val;
            numAssignments++;
        }
      
        System.out.println("Number of comparisons in Insertion sort in descending order:"+numComparisons);
        System.out.println("Number of assignments in Insertion sort in descending order:"+numAssignments);
    }

//function to display an array
    static void showArray(int array[])
    {
        for (int i=0; i<array.length; ++i)
            System.out.print(array[i] + " ");
        System.out.println();
    }

/**
   * main() function
   * @param args
   */
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       //create three random arrays
       int[] arr1=new int[size1];
       int[] arr2=new int[size2];
       int[] arr3=new int[size3];
      
       //initialize arrays with random numbers
       for(int i=0;i<arr1.length;i++)
       {
           arr1[i]=(int)(Math.random()*9+1);
       }
       for(int i=0;i<arr2.length;i++)
       {
           arr2[i]=(int)(Math.random()*9+1);
       }
       for(int i=0;i<arr3.length;i++)
       {
           arr3[i]=(int)(Math.random()*9+1);
       }
      
       //perform insertion sort in ascending order
       System.out.println("Sorting first array of size "+size1+" in ascending order...");
       SortingAnalysis.insertionSortAscending(arr1);
       SortingAnalysis.showArray(arr1);
       System.out.println("Sorting second array of size "+size2+" in ascending order...");
       SortingAnalysis.insertionSortAscending(arr2);
       SortingAnalysis.showArray(arr2);
       System.out.println("Sorting third array of size "+size3+" in ascending order...");
       SortingAnalysis.insertionSortAscending(arr3);
       SortingAnalysis.showArray(arr3);
      
       //perform insertion sort in descending order
       System.out.println("Sorting first array of size "+size1+" in descending order...");
       SortingAnalysis.insertionSortDecending(arr1);
       SortingAnalysis.showArray(arr1);
       System.out.println("Sorting second array of size "+size2+" in descending order...");
       SortingAnalysis.insertionSortDecending(arr2);
       SortingAnalysis.showArray(arr2);
       System.out.println("Sorting third array of size "+size3+" in descending order...");
       SortingAnalysis.insertionSortDecending(arr3);
       SortingAnalysis.showArray(arr3);
   }

}

--------------------------------------------

Output:

--------------------------------------------------

Sorting first array of size 103 in ascending order...
Number of comparisons in Insertion sort in ascending order:3188
Number of assignments in Insertion sort in ascending order:102
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9
Sorting second array of size 105 in ascending order...
Number of comparisons in Insertion sort in ascending order:3220
Number of assignments in Insertion sort in ascending order:104
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9
Sorting third array of size 107 in ascending order...
Number of comparisons in Insertion sort in ascending order:3217
Number of assignments in Insertion sort in ascending order:106
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9
Sorting first array of size 103 in descending order...
Number of comparisons in Insertion sort in descending order:5253
Number of assignments in Insertion sort in descending order:102
9 9 9 9 9 9 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sorting second array of size 105 in descending order...
Number of comparisons in Insertion sort in descending order:5460
Number of assignments in Insertion sort in descending order:104
9 9 9 9 9 9 9 9 9 9 9 9 9 8 8 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
Sorting third array of size 107 in descending order...
Number of comparisons in Insertion sort in descending order:5671
Number of assignments in Insertion sort in descending order:106
9 9 9 9 9 9 9 9 9 9 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1

----------------------------------------------------------------

Note: Analysis for merge sort can also be done in same way

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.