Data Structures Library Phase 1 Solution

DRAFT




For phase 1 of the CS201 programming project, we will start with a circular dynamic array class and extend it to implement some of the algorithms discussed in class.




Your dynamic array class should be called CDA for circular dynamic array. The CDA class should manage the storage of an array that can grow and shrink. The class should be implemented using C++ templates. As items are added and removed from both the front and the end of the array, the items will always be referenced using indices 0…size-1. Your CDA class should include a flag indicating whether the array is in sorted order, or it is unordered.




The public methods of your class should include the following (elmtype indicates the type from the template):




Function
Description
Runtime
CDA();
Default Constructor. The array should be of capacity 1
O(1)


and ordered is false.


CDA(int s);
For this constructor the array should be of capacity
O(1)


and size s with ordered = false.


~CDA();
Destructor for the class.
O(1)
elmtype& operator[](int i);
Traditional [] operator. Should print a message if i is
O(1)


out of bounds and return a reference to value of type




elmtype stored in the class for this purpose. If the




ordered flag is true, verify that any change in the array




leaves it still ordered. If necessary set the ordered flag




to false.


void AddEnd(elmtype v);
increases the size of the array by 1 and stores v at the
O(1)


end of the array. Should double the capacity when the
amortized


new element doesn't fit. If ordered is true, check to be




sure that the array is still in order.


void AddFront(elmtype v);
increases the size of the array by 1 and stores v at the
O(1)


beginning of the array. Should double the capacity
amortized


when the new element doesn't fit. The new element




should be the item returned at index 0. If ordered is




true, check to be sure that the array is still in order.


void DelEnd();
reduces the size of the array by 1 at the end. Should
O(1)


shrink the capacity when only 25% of the array is in use
amortized


after the delete.


void DelFront();
reduces the size of the array by 1 at the beginning of
O(1)


the array. Should shrink the capacity when only 25% of
amortized


the array is in use after the delete.


int Length();
returns the size of the array.
O(1)
int Capacity();
returns the capacity of the array.
O(1)
int Clear();
Frees any space currently used and starts over with an
O(1)


array of capacity 1 and size 0.


bool Ordered();
Returns the status of the ordered flag.
O(1)
int SetOrdered();
Check to see if the array is in order. Set the order flag
O(size)


appropriately. Return 1 if the array was ordered and -1




otherwise.


Elmtype Select(int k);
returns the kth smallest element in the array. If
O(1) or


ordered is true then return the item at index k-1.
O(size)


Otherwise use the quickselect algorithm. Quickselect
expected


should choose a random partition element.


Void InsertionSort()
Performs insertion sort on the array. Sets ordered to
O(size*size)


true.
worst case
void QuickSort();
Sorts the values in the array using the quick sort
O(size * size)


algorithm. This should pick the partition value using
worst case


the median of three technique. Set ordered to true.
O(size lg size)


Should also make use of insertion sort to improve
expected


performance.


void CountingSort(int m);
Sorts the values in the array using counting sort, where
O(size * m)


the values in the array are in the range 0…m. Set




ordered to true.


int Search(elmtype e)
If ordered is true, perform a binary search of the array
O(lg size) or


looking for the item e. Otherwise perform linear
O(size)


search. Returns the index of the item if found or -1




otherwise.








Your class should include proper memory management, including a destructor, a copy constructor, and a copy assignment operator.