Assignment 1Assignment 1: Recursion COMP 2140, Fall 2021 Due: Tuesday 5 October 2021 at 5:00 p.m...

Question

Assignment 1Assignment 1: Recursion COMP 2140, Fall 2021 Due: Tuesday 5 October 2021 at 5:00 p.m Instructions: • You must complete the “Honesty Declaration” checklist on the course website before you can submit any assignment. • Assignments must follow the programming standards document published on UM Learn. • After the due date and time, assignments may be submitted, but will be subject to a late penalty. Please see the course outline document published on UM Learn for the course policy for late submissions. • If you make multiple submissions, only the most recent version (the last submission) will be marked. We strongly encourage you to submit early! • These assignments are your chance to learn the material for the exams. Code your assignments indepen- dently. We use software to compare all submitted assignments to each other, and pursue academic dishonesty vigorously. • You can get help from the T.A. during your lab section and from the instructors and from the course Assignment 1 discussion forum on UM Learn. You can discuss general topics related to the assignment with fellow students or other people, but you cannot discuss the solution to the assignment with them. You cannot copy code from anywhere except COMP 2140 class notes, unless we tell you otherwise. For a full discussion of our expectations for individual work on this assignment, see the Department of Computer Science’s expectations webpage. • Your Java programs must compile and run upon download, without requiring any modi- fications. The marker will not fix your program’s problems. See also the “Hand in” instructions at the end of this assignment. Review: Insertion Sort with Sifting Up Insertion sort sorts an array of items by maintaining a sorted part at one end of the array — the sorted part starts out containing just one item. Then insertion sort “sifts” the unsorted items (one at a time) into their correct positions in the sorted part. Here, sifting means moving over items in the sorted part to make a space in the correct position for the new item. Each time insertion sort sifts one of the unsorted items into the sorted part, the sorted part of the array grows in size by one item. For this assignment, sifting is going to go up (moving sorted items smaller than the new item down one position) and the sorted part is going to be at the end of the array. For example, if an array contains 65, 72, 18, 7, 48, 16, 42, 50 (in that order), then insertion sort starts by saying that 50 is the initial sorted part (of size 1) and 65, 72, 18, 7, 48, 16, 42 is the unsorted part: 65 73 18 7 48 16 42 50 unsorted sorted 1 https://sci.umanitoba.ca/cs/expectations/ Then insertion sifts up 42, then 16, then 48, and so on — that is, it repeatedly sifts up the item that is immediately beside the current sorted part. To sift up an item, insertion sort first takes a copy of the item to be sifted (the sift item). Then it looks at the items in the sorted part, starting from the smallest and moving each sorted item less than the sift item one position to the left. For example, suppose insertion sort is about to sift up 48: 65 73 18 7 48 16 42 50 unsorted sorted Then insertion sort takes a copy of 48, creating a “hole” in the array: 65 73 18 7 16 42 50 siftItem 48 Then it loops through the sorted items (starting with 16, the smallest), comparing them to the sift item and moving items left until either: • It comes to the end of the array — the sift item is bigger than all the sorted items and belongs at the end; or • It comes to a sorted item that is ≥ the sift item — the sift item belongs just before that sorted item. In the example, it moves 16 and then 42 because they are less than 48, but stops when it sees that 48 ≤ 50: 65 73 18 7 16 42 50 siftItem 48 Moving the items leaves a hole where the sift item, 48, belongs: 65 73 18 7 16 42 50 siftItem 48 To finish the sifting of 48, it is placed into the hole — the sorted part has grown by one item: 65 73 18 7 16 42 48 50 unsorted sorted Here is code for an iterative version of insertion sort that implements the above process: public static void iterativeInsertionSort( int[] a ) { for ( int i = a.length-2; i >= 0; i-- ) { // The sorted part is in positions i+1 to a.length-1. siftUp( a, i ); // sift up the item at position i } // end for } // end iterativeInsertionSort 2 and its helper method that does the sift-up process: private static void siftUp( int[] a, int pos ) { int siftItem = a[pos]; // remember the item we’re sifting up int i; // loop index is needed after the loop // Move one position to the left all items that are .java (e.g., A1CameronHelen.java) to contain your code. (Make sure the class it contains matches the file name.) Then write the following methods: 1. A method fillArray, which is passed an int array and a maximum value (an int). It should fill the given int array with random positive integers no larger than the given maximum value. Hint: (int)(Math.random() * maxValue) produces a random integer in the range 0, . . ., maxValue-1. 2. A method arrayToString that is passed an int array and returns a String containing the first 10, followed by “. . . ”, followed by the last 10 items in the array (or just all the items in the array if the array’s length is 20 or less). The items should be separated by blanks. 3 3. A method isSorted that verifies that an array is in ascending order. It should be passed an int array. It should return true if the array is in ascending sorted order and false if it is not. It must check that each item in the array is no bigger than the item immediately after it. 4. A recursive insertion sort method and the public driver method described in the previous section (using siftUp and having the sorted part at the end of the array, not the beginning). Both the driver method and the recursive helper method should be named recursiveInsertionSort. Then add to your file the iterative insertion sort and the siftUp method provided above. Finally, write a main method (and whatever helper methods it needs) to do all of the following for each of the iterative and the recursive insertion sorts: • Create an array of 1000 random positive integers no greater than 5000. • Print the the first 10 and the last 10 items in the array (before sorting). • Sort the array and time the sorting. (Copy the code that times a method from the Lab1.java file.) • Check if the array is correctly sorted, and print either “Array is correctly sorted” or “ERROR: Array is NOT correctly sorted” (as appropriate). • Print the the first 10 and the last 10 items in the array (after sorting). Finally, the main method should report the two timings and also which of the two methods was faster. Sample Output: Assignment 1 Solution Testing the iterative insertion sort: Array before sorting: 3225 3214 2149 2234 560 3 4813 4262 3689 2808 ... 3851 558 3775 4380 3449 4663 1942 4622 2354 1766 Array is correctly sorted Array after sorting: 3 13 17 18 24 27 27 31 31 37 ... 4923 4923 4924 4926 4942 4951 4960 4967 4972 4980 Testing the recursive insertion sort: Array before sorting: 3683 750 4746 1979 311 3164 587 1814 2964 155 ... 1201 2597 1107 357 653 2881 502 1227 1682 4310 Array is correctly sorted Array after sorting: 7 7 9 14 19 22 40 46 48 49 ... 4954 4959 4962 4964 4973 4979 4982 4984 4991 4995 Timing: Time to insertion sort (iteratively): 1321266 nanoseconds 4 Time to insertion sort (recursively): 1197017 nanoseconds The recursive insertion sort was at least as fast as the iterative one! Processing ends Note: Timing Java methods is hard to do accurately, since Java does things in the background (one example: garbage collection) that can affect the timing of your methods. Furthermore, the “random” array passed to one method might be closer to sorted than the “random” array passed to the other method — and insertion sort is faster on nearly-sorted arrays! Thus, you may get different timing results than the sample. The two methods are essentially doing the same work, however, so they ought to have similar running times on truly random arrays. Hand In • To submit the assignment, upload the specified file to the Assignment 1 folder on the course website. Verify that the submission worked. (See the detailed hand-in instructions in the “COMP2140-HandIn- Instructions” document under “General Information” in the content browser of the course website on UM Learn.) • Submit ONE .java file, which must be named A1.java (e.g., A1CameronHelen.java). •

Kshitij · Accepted Answer

/*   Created by IntelliJ IDEA.
 *   Author: Kshitij Varshney (kshitijvarshne1)
 *   Date: 27-Sep-21
 *   Time: 4:26 PM
 *   File: InsertionSort.java
 */
package September.sep_27_21;
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = new int[1000];
        fillArray(arr);
        System.out.println("Testing the iterative insertion sort:");
        System.out.println("Array before sorting:");
        arrayToString(arr);
        long beginTime = System.nanoTime();
        int[] copy = arr;
        iterativeInsertionSort(copy);
        long endTime = System.nanoTime();
        if (isSorted(copy)) {
            System.out.println("Array is correctly sorted");
        } else {
            System.out.

Assignment 1: Recursion COMP 2140, Fall 2021 Due: Tuesday 5 October 2021 at 5:00 p.m Instructions: • You must complete the “Honesty Declaration” checklist on the course website before you can submit...

Answer To: Assignment 1: Recursion COMP 2140, Fall 2021 Due: Tuesday 5 October 2021 at 5:00 p.m Instructions: •...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment