See the template and attached files here: https://app.mediafire.com/myfiles
CIS 350
Sorted Array
Assignment
In this assignment, you will be required to implement a generic SortedArray Container class. Elements in the SortedArray should be always in the non-decreasing order. Unlike basic arrays that burden the programmer with the task of keeping track of its capacity and utilization, the SortedArray must also provide an interface to the programmer to allow for retrieval of information about the number of elements inside it as well as the maximum number of elements it can store.
Requirements
• SortedArray MUST store elements internally in an array. Please refer to the vector implementation example in the lecture slides 2-1.
• SortedArray MUST be able to store elements of any comparable type that provides operator < and operator =.
• All the elements in the SortedArray should always be in non-decreasing order.
• SortedArray MUST have a no-argument constructor that initializes its internal array to some size. This size MUST NOT be so large as to prevent a calling program to initialize several instances of SortedArray in a single execution. Suggested length values are 16 or 64.
• Every SortedArray instance holding n elements MUST accept insertions as long as the system has enough free memory to dynamically allocate an array of 2n+1 elements at insertion request time, regardless of the initial capacity of its internal array.
• SortedArray MUST implement the full interface specified in the file SortedArray.h
• You MUST NOT change the file SortedArray.h
• You class implementation must be in the file SortedArray.cpp
• You must submit a memo (a single word or pdf file) with the time complexity analysis of each member function.
• I will provide a program to test your class. Compile and run the program with the class. You should probably write other test program(s) to make sure everything works.
Interface
The interface of SortedArray is provided in the attached SortedArray.h file.
It provides for the following public functionality, all of which can be achieved using an internal array representation for the data.
• SortedArray(): no-argument constructor. Initializes the internal array to some pre-specified size.
• ~SortedArray(): destructor.
• SortedArray(const SortedArray<Object>&): copy constructor.
• SortedArray<Object>& operator= invoked by the copy constructor.
• const Object& operator [](int)const: returns the ith element stored in this SortedArray, where the 1st element is the element in the front.
• bool equals (const SortedArray <Object> & rhs): returns true if this array and the rhs array have the same elements, in the same order. (The capacity of the containers may be different, only the actual number of elements in each must be the same for the call to return true.)
• void clear(): removes all the elements of the container. This SortedArray should still be useful after a call to this function. Note, should not delete the array, just set the size properly.
• bool empty(): returns true if the SortedArray contains no elements, and false otherwise.
• void print(ostream& os, char delimiter=”,”) const: print all elements of SortedArray to ostream os. Each element is followed by a delimiter except the last element.
• int size(): returns the number of elements stored in this SortedArray, which may be less than its capacity.
• int capacity(): returns the current capacity of this SortedArray.
• void reserve(int newCapacity): sets the new capacity. MUST report an error current size is already larger than the requested capacity. MAY do nothing if the existing capacity (but not the size) is larger than the requested capacity.
• void insert(const Object &): insert new elements into the correct position in the array, sliding elements over the position to right, as needed.
• void deleteMin( ): remove the element in position 0, and slide over all the other item.
• void deleteMax( ): remove the last element.
• const Object & findMin( ) const: find the minimum element.
• const Object & findMax( ) const: find the maximum element.
• int binarySearch (const Object & x): Performs the standard binary search using two comparisons per level, see the lecture slides 3. Returns index where item is found or -1 if not found.
Note 1, three additional files are provided. SortedArray.h is the header file. You should not modify it. SortedArray.cpp is simply a skeleton. You will need to complete it and implement each member function inside it. program1Test.cpp is a simple test program. When you create a project, you should only add SortedArray.h and program1Test.cpp, but not SortedArray.cpp (which is already included in SortedArray.h file).
Note 2, if you implement this project in Java or Python, you will need to make some necessary adjustments. For example, there are no destructor and no operator overloading in Java. You need to replace the operator[] with a get(int) method.
What to turn in:
Upload all your files as a single ZIP file to the Canvas under the “P1” assignment folder. You should include two files, your source code (SortedArray.cpp) and your memo (a single WORD of PDF file).
How the program will be graded.
What
Points
Analysis
20
Time Analysis Worst case O() of each member function with explanation.
Program Style
5
Your Name
Description of the problem in your own words
Overall program style and comments
Functionality
75
