A4: Using Arrays

On This Page Overview Specifications Test Cases Extra Credit Grading Criteria (20) What to Turn In Overview During this assignment, you will: Generate random numbers Use static methods and variables with arrays Pass array references to methods Return arrays from methods Use an array with loops Develop an improved version of bubble sort Compare the use linear search and binary search Implement a recursive method Background Information Arrays are an important data structure in programming. With this assignment, you can become familiar with how arrays are used in Java. One of the algorithms you will examine is bubble sort. The bubble sort algorithm cycles through the array from left to right (or top to bottom if you want to picture it that way) interchanging adjacent elements when the first is larger than the second. After each pass through the array the numbers will be getting closer to being in order. The sorting is finished when a cycle is completed where no two elements are out of order. The name of this sorting algorithm comes from the way smaller elements "bubble up" toward the left end (or top) of the array. Below is a demonstration applet that shows how smaller pieces will gradually work their way to the top. Each time the button is pressed one cycle or pass is made through the array, comparing all the elements one at a time versus their neighbor. You can use this visual aid to examine how bubble sort behaves. ^ top Specifications Create a class called ArrayUtil using the starter code available here. Within this class, implement all the following methods: public static int[] makeArray(int size): Creates an array of size and initializes the array with random values between low and high - 1. Calling this method must not cause any user input or output operations. public static int[] copyArray(int[] array): Creates an copy of an array and returns the copy. Calling this method must not cause any user input or output operations. public static void bubbleSort(int[] array): Sorts an array using bubble sort, similar to the method shown in figure 7.10 of the textbook. However, modify the method to count the number of comparisons made during sorting. Calling this method must not cause any user input or output operations. public static void bubbleSortPlus(int array[]): Sorts an array using an enhanced bubble sort. The bubble sort shown in the text can be made more efficient. Make the following improvements in the bubble sort algorithm: After the first pass, the largest number is guaranteed to be in the correct location at the end of the array. After the second pass, the two highest numbers are in the correct locations. This behavior continues until the end of the sorting process. Instead of making these extra passes, modify the algorithm to not make the unnecessary passes. The data in the array may be in the correct order before the current algorithm is finished. Modify the sort to check at the end of each pass if any swaps have been made. If none have been made, the data is already in sorted order and the method should end. However, if any swaps have been made, then at least one more pass is needed. public static int linearSearch(int[] array, int key): Searches an array for specified key value using linear search, similar to the method shown in figure 7.11 of the textbook. However, modify the method to count the number of comparisons made during searching. public static int binarySearch(int[] array, int key): Searches an array for specified key value using binary search, similar to the method shown in figure 7.12 of the textbook. However, modify the method to count the number of comparisons made during searching. Calling this method must not cause any user input or output operations. public static void showArray(int[] array): Iteratively prints an array from start to the end. public static void showArray(int[] array, int start): Recursively prints an array from start to the end. Hint: convert your iterative version to a recursive version. public static void main(String[] args): Begins execution of the Java application, requesting the size of the array to test from the user, calling makeArray to create the array, and then passing the array to the runTests method. The runTests method is supplied with the starter code and may not be changed in any way. Use the command line for input. Do not change the name of the class or any method from those specified. Sample Output This program requests an array size from the user, creates an array of that size filled with random numbers, and tests the array. Enter the array size to test (0 to exit): -5 Size cannot be a negative number! Enter the array size to test (0 to exit): 10 Original array elements are: 79, 38, 13, 59, 73, 6, 33, 1, 57, 41 Bubble Sort comparisons needed: 90 Sorted array elements are: 1, 6, 13, 33, 38, 41, 57, 59, 73, 79 Enhanced Bubble Sort comparisons needed: 44 1, 6, 13, 33, 38, 41, 57, 59, 73, 79 Linear search Comparisons needed: 10 Binary search Comparisons needed: 5 ^ top Test Cases Testing is an important part of software development. Usually, programmers develop tests for each unit of code they produce. This is know as "unit testing" and allows the programmer to verify that the code they develop works correctly. To assist you in developing your code, I provide tests for this assignment. These tests, known collectively as "test cases", help to make sure that your assignment meets its requirements. I will use these test cases (and perhaps others) to test your assignment, and you should too. If the test cases do not pass, then you will lose points for the assignment. Install the tests by copying the following file into the same directory as your .java source code files: ArrayUtilTest.java Run the tests as you would any other Java program. You may need to compile your source code before compiling and running the test code. ^ top Extra Credit The following are worth extra credit points: Implement another sorting algorithm and show the number of comparisons needed for that algorithm. Add methods to main to display the results. (2 points) Implement methods to find the minimum, maximum and average of the array values. Add methods to main to display the results. (2 points) Make certain that your README.txt file lists any extra credit attempted. ^ top Grading Criteria The instructor will evaluate your assignment using the following criteria. Each criteria represents a specific achievement of your assignment and has a scoring guide. The scoring guide explains the possible scores you can receive. Some scoring guides have a list of indicators. These indicators are a sign of meeting, or a symptom of not meeting, the specific criterion. Note that a single indicator may not always be reliable or appropriate in a given context. However, as a group, they show the condition of meeting the criterion. For information on grading policies, including interpretation of scores, see the course Syllabus. Program Compilation 4: Source code compiles with no errors or warnings 0: Does not compile Functionality 10: Demonstrates mastery of the assignment Has extra features or demonstrates techniques beyond the assignment Applies concepts from the lessons appropriately Meets all specifications (see above) with particularly elegant solutions No errors encountered during operation All test cases pass 8: Has all the functionality expected of the assignment Demonstrates many techniques from the lesson Meets all specifications (see above) Implementation seems more complicated than necessary. May have one minor error All test cases pass 6: Has most of the functionality expected of the assignment Demonstrates some techniques from the lesson Meets all but one of the specifications (see above) Implementation seems excessively complicated. May have 2-3 minor errors All but one test case passes 4: Has some of the functionality expected of the assignment Demonstrates some techniques from the lesson Meets at least 1/2 of the specifications (see above) Implementation seems excessively complicated. May have more than 3 minor errors At least 1/2 of all test cases pass 2: Serious functional problems but shows some effort and understanding Meets less than 1/2 of the of the specifications (see above) Has a major error or many minor errors Implementation seems very convoluted Demonstrates few techniques from the lesson Less than 1/2 of all test cases pass 0: Does not execute Code Documentation 4: Code is well-documented Name, date, and page description in opening comment block Comment block at start of every function Proper use of whitespace and indenting Descriptive variable names README.txt file included 3: Code has minor documentation errors Has 1 documentation error 2: Code has some documentation errors Has 2-3 documentation errors 1: Code has many documentation errors Has more than 3 documentation errors 0: No apparent attempt to document code README.txt File 2: README.txt file submitted with specified information included 1: README.txt submitted but some information was not included 0: No README.txt submitted Maximum Score: 20, plus extra credit ^ top What to Turn In Submit your assignment following the instructions for homework. Include the following items for grading: README.txt file ArrayUtil.java Any other source code needed to make your program function You must submit all the files needed to make your assignment function properly. Do not assume that the instructors has any files unless explicitly stated by the instructor. Your assignment must work as submitted. ^ top Home | WebCT | Announcements | Schedule | Expectations | Syllabus Help | FAQ's | HowTo's | Links Last Updated: September 25 2003 @15:51:11