Introduction In this assignment, you\'ll implement two sorting algorithms that w

Question

Introduction

In this assignment, you'll implement two sorting algorithms that we've studied in class, and measure the performance of the algorithms:

Insertion Sort

Merge Sort

You'll write code to implement these two algorithms (don't use library routines for sorting). You'll measure the performance of these two algorithms on various size arrays, and compare the execution times of the two algorithms as the input size increases.

For smaller inputs, you'll find that Insertion Sort is faster. You should determine the smallest of the specified input sizes at which Merge Sort becomes faster than Insertion Sort. This size will vary depending on your individual implementation.

Measuring Execution Time

Measuring the timing of a single execution of an algorithm is usually imprecise, since the run time (especially for small inputs) may be on the order of the precision of the system timer. For performance measurement, we'll normally run an algorithm many times and then compute the average time for each execution.

Sorting algorithms reorder the original data, which may change the run time on subsequent executions (as we've seen with insertion sort).

For this assignment, your sort routines should copy a sub-range of the input array into an output array before sorting. The input array should not be modified. It will be reused for multiple calls to the sorting routine.

Copying an Array

Java

In Java, use the ArrayList type to store your arrays. You can create a copy of a portion of an ArrayList simply by passing a sub-list of it to the constructor of a new ArrayList. For example:

Program Components

You'll need the following pieces to implement this assignment. An overall description of the task to perform is in the next section. You may also define any additional functions that you need (for example, Merge for MergeSort).

AlphaSorted: implement a function that takes as an argument an ArrayList (Java) or vector (C++) of strings. The function should verify that the array is sorted by checking that each element precedes or is equal to the following element. Return true if the array is correctly sorted, false otherwise. The array must not be modified by this function.

InsertionSort: implement a function that takes as arguments an input array to be sorted and a length n. The function should copy the first nelements of the input array to a new output array containing only those n elements, and then use the Insertion Sort algorithm as described in class to sort the output array. The input array must not be modified. The function should return the new output array.

MergeSort: implement a function as above for InsertionSort, but using the Merge Sort algorithm instead. You'll need an outer, non-recursive MergeSortSetup function that copies the array sub-range and then calls a recursive function, MergeSort, to sort the output array. The recursive function should not make another copy of the entire array.
In your Merge routine, there is no such thing as infinity for strings, so you'll need to modify Merge to check for the end of the L and R arrays in some other way. You may not assume that you can choose a string which will be greater than all the strings in the input.

Code to measure CPU time.

Your Task

Create the input array by reading strings from the file specified by the first program command line argument into an ArrayList (Java).

For each value of n:

Calculate number of timing iterations iter = max(4, 8192/n) for Java. While debugging, you may wish to just set iter to 1; once everything is working correctly, use the full calculation to get more accurate timing.

For each value of n, call InsertionSort iter times to sort the first n items in the input array, using CpuTimer to calculate the total time for all the iterations. Divide this time by iter to get the average time for each call to InsertionSort.After computing the timing, check all of the following:

AlphaSorted is false for the input array.

AlphaSorted is true for the final output array.

Abort the program with a message if any of the above conditions are not met.

Repeat the same procedure you used for InsertionSort (using a separate timer) for MergeSortSetup.

Output

For each iteration of the loop, print to standard output the sub-array size n, and the average times for InsertionSort and MergeSort. Compute the average times in double precision, but convert to single precision (float) for output to avoid extraneous digits. Your output must follow the sample output format below.

Sample Output

My results using Java on a 2.2 GHz Intel Core i7 processor are shown below; your times will differ. My total run time was 77 sec. If your run time in Java is significantly lower, make sure that you have specified the -Xint parameter to the JVM (see comments in CpuTIme.java). If you don't specify this parameter, your run time will be faster, but the results may be invalid due to "Just In Time" (JIT) compilation.

Explanation / Answer

//Java Program for Solution

import java.text.SimpleDateFormat;

import java.util.*;

class Solution

{

    //Driver Program to run the application

    public static void main(String arg[]) throws Exception

    {   

//Test array element size from 8 to 8192

for(int element=8;element<=8192;element *=2)

{

int A[] = new int[element]; //This is for Insertion sort

int B[] = new int[element]; //This is for merge Sort

//First fill the elements of array using random value (from -10 to 8000)

ArrayList<Integer> list = new ArrayList<Integer>();

for(int ii=0;ii<element;ii++)   

list.add(-10 + (int)(Math.random()*8000));

//Now copy all the element into two array

for(int i=0;i<element;i++) B[i] = A[i]=list.get(i);

Date today = new Date();

String time1 = new java.sql.Time(today.getTime()).toString();

InsertionSort(A);

String time2 = new java.sql.Time(today.getTime()).toString();

SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");

Date date1 = format.parse(time1);

Date date2 = format.parse(time2);

long difference1 = date2.getTime() - date1.getTime();

difference1 /=1000.0;

//Data for insertion sort

time1 = new java.sql.Time(today.getTime()).toString();

MergeSort(A,0,element-1);

time2 = new java.sql.Time(today.getTime()).toString();

format = new SimpleDateFormat("HH:mm:ss");

date1 = format.parse(time1);

date2 = format.parse(time2);

long difference2 = date2.getTime() - date1.getTime();

System.out.println("Avg. times for n = "+ element +" : Insertion Sort "+ difference1 +" sec., Merge Sort "+difference2 +" sec.");

}

}

//AlphaSorted to check array is sorted or not

static boolean AlphaSorted(int arr[])

{

for(int i=1;i<arr.length;i++)

if(arr[i]<arr[i-1])

return false;

//if each second element is smaller than the first element, array is not sorted

return true;

}

// Insertion Sort

static void InsertionSort(int arr[])

{

int n = arr.length;

for (int i=1; i<n; ++i)

{

int key = arr[i];

int j = i-1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j>=0 && arr[j] > key)

{

arr[j+1] = arr[j];

j = j-1;

}

arr[j+1] = key;

}

}

//Method to print Array element

    static void PrintArray(int A[])

    {

        for(int i:A)

            System.out.print(i+" ");

        System.out.println();

    }

    //Sort method, which include conquer and divide, and merge finally

    static void MergeSort(int A[],int l,int r)

    {

        if(l<r)

        {

            int m = (l+r)/2;

            MergeSort(A,l,m);

            MergeSort(A,m+1,r);

            merge(A,l,m,r);

        }

    }

    //Merge method of all distinct array element after divide and conquer

    static void merge(int A[],int l,int m,int r)

    {       

        int n1 = m+1-l;

        int n2 = r - m;

        int L[] = new int[n1];

        int R[] = new int [n2];

        for(int i=0;i<n1;i++) L[i] = A[l+i];

        for(int j=0;j<n2;j++) R[j] = A[m+1+j];

        int i=0,j=0,k=l;

        while(i<n1 && j<n2)

            A[k++]= L[i]<=R[j] ? L[i++]: R[j++];

        while(i<n1) A[k++]=L[i++];

        while(j<n2) A[k++]=R[j++];

    }

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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