Using C++ to create a circular dynamic arra
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 ...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 Runtime 0(1) CDA(); CDA(int s); 0(1) -CDA(); elmtype& operator[](int i); O(1) 0(1) Description Default Constructor. The array should be of capacity 1 and ordered is false. For this constructor the array should be of capacity and sizes with ordered = false. Destructor for the class Traditional [] operator. Should print a message if i is 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. increases the size of the array by 1 and stores v at the end of the array. Should double the capacity when the new element doesn't fit. If ordered is true, check to be sure that the array is still in order. increases the size of the array by 1 and stores v at the beginning of the array. Should double the capacity 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. reduces the size of the array by 1 at the end. Should shrink the capacity when only 25% of the array is in use void AddEnd(elmtype v); 0(1) amortized void AddFront(elmtype v); O(1) amortized void DelEnd(); 0(1) amortized void Del Front(); 0(1) amortized int Length(); int Capacity(); int Clear(); reduces the size of the array by 1 at the beginning of the array. Should shrink the capacity when only 25% of the array is in use after the delete. returns the size of the array. returns the capacity of the array. Frees any space currently used and starts over with an array of capacity 1 and size 0. Returns the status of the ordered flag. O(1) 0(1) 0(1) bool Ordered(); (1) int SetOrdered(); Elmtype Select(int k); 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. 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. Performs insertion sort on the array. Sets ordered to O(size*size) true. worst case 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 InsertionSort() void QuickSort(); void CountingSort(int m); O(size * m) int Search(elmtype e) Sorts the values in the array using counting sort, where the values in the array are in the range 0...m. Set ordered to true. If ordered is true, perform a binary search of the array looking for the item e. Otherwise perform linear search. Returns the index of the item if found or -1 otherwise. O(lg size) or O(size) Your class should include proper memory management, including a destructor, a copy constructor, and a copy assignment operator. 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 ...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 Runtime 0(1) CDA(); CDA(int s); 0(1) -CDA(); elmtype& operator[](int i); O(1) 0(1) Description Default Constructor. The array should be of capacity 1 and ordered is false. For this constructor the array should be of capacity and sizes with ordered = false. Destructor for the class Traditional [] operator. Should print a message if i is 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. increases the size of the array by 1 and stores v at the end of the array. Should double the capacity when the new element doesn't fit. If ordered is true, check to be sure that the array is still in order. increases the size of the array by 1 and stores v at the beginning of the array. Should double the capacity 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. reduces the size of the array by 1 at the end. Should shrink the capacity when only 25% of the array is in use void AddEnd(elmtype v); 0(1) amortized void AddFront(elmtype v); O(1) amortized void DelEnd(); 0(1) amortized void Del Front(); 0(1) amortized int Length(); int Capacity(); int Clear(); reduces the size of the array by 1 at the beginning of the array. Should shrink the capacity when only 25% of the array is in use after the delete. returns the size of the array. returns the capacity of the array. Frees any space currently used and starts over with an array of capacity 1 and size 0. Returns the status of the ordered flag. O(1) 0(1) 0(1) bool Ordered(); (1) int SetOrdered(); Elmtype Select(int k); 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. 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. Performs insertion sort on the array. Sets ordered to O(size*size) true. worst case 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 InsertionSort() void QuickSort(); void CountingSort(int m); O(size * m) int Search(elmtype e) Sorts the values in the array using counting sort, where the values in the array are in the range 0...m. Set ordered to true. If ordered is true, perform a binary search of the array looking for the item e. Otherwise perform linear search. Returns the index of the item if found or -1 otherwise. O(lg size) or O(size) Your class should include proper memory management, including a destructor, a copy constructor, and a copy assignment operator
