Description
Part 1: Extend your implementation from lab07 to include functions for Bubble Sort and Binary Search.
| #ifndef ARRAY_H #define ARRAY_H
template <class T> class Array { private: /* You fill out the private contents. */ public: /* Do a deep copy of the array into the list. * Note: This one uses a pointer! */ Array(const T *array, const int size); /* Do a deep copy of the array into the list * Note: This one uses a reference to a List! */ Array(const Array<T> &list); /* Return the current length of the array */ int getLength() const; /* Returns the index in the array where value is found. * Return -1 if value is not present in the array. */ int search(const T &value); /* Removes an item at position index by shifting later elements left. * Returns true iff 0 <= index < size. */ bool remove(const int index); /* Retrieves the element at position pos */ T& operator[](const int pos); /* Returns if the two lists contain the same elements in the * same order. */ bool operator==(Array<T> &list) const; |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /* Runs a bubble sort algorithm on the array.
* The array shall be ordered from least to greatest */ void bubbleSort(); /* Searches for an element with value value and returns the index of that * data. * NOTE: We assume the array is sorted! * Return -1 if the value is not found. */ int binarySearch(const T &value); /* Free any memory used! */ ~Array(); }; /* Since Array is templated, we include the .cpp. * Templated classes are not implemented until utilized (or explicitly declared). */ #include “array.cpp” #endif |
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.
Memory Management:
Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code! Please run Valgrind on your tests to ensure no memory leaks!
STL:
You may not use anything from the STL.
