In the last lab you created an array and a linked implementation of a set. In this lab you are going to modify the array based implementation to store its elements in sorted order. It does not make sense to implement a sorted linked set because of the lack of element access. Storing the elements sorted adds complexity to the add operation, because the location of the new element must be found before it can be added. But the speed of methods that depend on search (add, remove, get) may increase because binary search is faster than linear search in the worst case. You will also try to determine what effect these changes have on the performance of a set.
The file Sets.tgz contains an implementation of the Array and Linked sets from the last lab. You can either use these files or your own from the last lab. Modify the arraySet class to be a sorted array set. Begin by modifying the add method to add elements to the proper location in sorted order (either ascending or descending). Note, all elements after the element that is added will have to be shifted to one index higher. Be sure to thoroughly test your code before proceeding. Next, modify the remove method to maintain the proper sort order. Note, all elements after the element removed will have to be shifted to one index lower. Be sure to thoroughly test your code before proceeding. Finally, modify the private getIndex method to implement binary search using recursion. The method will need two extra parameters that represent the range of the array to sort for the given element. Every recursive call of the method should specify a smaller range of the array to search. The recursion should terminate when it finds the element. Be sure to thoroughly test your code before proceeding.
Create a program that computes the steady state run-times of performing various operations on a large ArraySet and LinkedSet. Feel free to use your steady state code from previous labs or from the sorting time code on the course web site. Have your program print out a table comparing the steady state run-times of the sets when adding a random element, when removing a random element, and getting a random element. The remove and get methods should attempt to remove and get elements that are in the set.
Hand In: Tar your lab directory and e-mail it to your instructor with cpsc170 lab10 in the subject.