# Data Structure and Algorithm

### Searching

Searching involves deciding whether a search key is present in the data. For example, looking up a phone book or address book. The searching algorithm includes:

• Linear Search: See "Linear Search".
• Recursive Binary Search for sorted list
• Binary Tree Search

#### Linear Search

See "Linear Search".

##### Complexity

The worst-case and average-case time complexity is O(n). The best-case is O(1).

#### Binary Search

A binary search (or half-interval search) is applicable only to a sorted array. It compares the search key with the middle element. If there is a match, it returns the element's index. If the search key is less then the middle element, repeat searching on the left half; otherwise, search the right half. If the remaining element to be searched is zero, return "no found".

 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55``` ```/* Search an array for a key using Binary Search (BinarySearch.cpp) */ #include using namespace std; int binarySearch(const int a[], int size, int key); int binarySearch(const int a[], int iLeft, int iRight, int key); void print(const int a[], int iLeft, int iRight); int main() { const int SIZE = 10; int a1[SIZE] = {1, 4, 5, 8, 12, 19, 24, 31, 43, 55}; // sorted cout << binarySearch(a1, SIZE, 8) << endl; cout << binarySearch(a1, SIZE, 12) << endl; cout << binarySearch(a1, SIZE, 24) << endl; cout << binarySearch(a1, SIZE, 21) << endl; } // Search the array for the given key // If found, return array index; otherwise, return -1 int binarySearch(const int a[], int size, int key) { // Call recursive helper function return binarySearch(a, 0, size-1, key); } // Recursive helper function for binarySearch int binarySearch(const int a[], int iLeft, int iRight, int key) { // For tracing the algorithm print(a, iLeft, iRight); // Test for empty list if (iLeft > iRight) return -1; // Compare with middle element int mid = (iRight + iLeft) / 2; // truncate if (key == a[mid]) { return mid; } else if (key < a[mid]) { // Recursively search the lower half binarySearch(a, iLeft, mid - 1, key); } else { // Recursively search the upper half binarySearch(a, mid + 1, iRight, key); } } // Print the contents of the given array from iLeft to iRight (inclusive) void print(const int a[], int iLeft, int iRight) { cout << "{"; for (int i = iLeft; i <= iRight; ++i) { cout << a[i]; if (i < iRight) cout << ","; } cout << "}" << endl; }```
##### Complexity

The worst-case and average-case time complexity for binary search is O(log n). The best-case is O(1).

### Sorting

Sorting involves arranging data in ascending or descending order, according to a certain collating sequence (or sorting sequence). The sorting algorithm includes:

• Insertion Sort: See "Insertion Sort".
• Selection Sort: See "Selection Sort".
• Bubble Sort: See "Bubble Sort"
• Merge Sort (Recursive Top-Down or Interactive Bottom-up)
• Quick Sort (Recursive)
• Bucket Sort
• Heap Sort
• Binary Tree Sort

#### Bubble Sort

See "Bubble Sort"

##### Complexity

The average-case and worst-case time complexity is O(n2).

#### Insertion Sort

See "Insertion Sort".

##### Complexity

The average-case and worst-case time complexity is O(n2).

#### Selection Sort

See "Selection Sort".

##### Complexity

The average-case and worst-case time complexity is O(n2).

#### Merge Sort

##### Recursive Top-Down Merge Sort

The algorithm is as follows:

1. Recursively divide the list into 2 sublists.
2. When the sublists contain 1 element (a list of 1 element is sorted), merge two sublists in the right order. Unwind the merging recursively.
 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97``` ```/* Sorting an array using Merge Sort (MergeSort.cpp) */ #include using namespace std; void mergeSort(int a[], int size); void mergeSort(int a[], int iLeft, int iRight, int work[]); void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight, int iRightHalfLeft, int iRightHalfRight, int work[]); void print(const int a[], int iLeft, int iRight); int main() { // Test 1 const int SIZE_1 = 8; int a1[SIZE_1] = {8, 4, 5, 3, 2, 9, 4, 1}; print(a1, 0, SIZE_1 - 1); cout << endl; mergeSort(a1, SIZE_1); print(a1, 0, SIZE_1 - 1); cout << endl << endl; // Test 2 const int SIZE_2 = 13; int a2[SIZE_2] = {8, 4, 5, 3, 2, 9, 4, 1, 9, 1, 2, 4, 5}; print(a2, 0, SIZE_2 - 1); cout << endl; mergeSort(a2, SIZE_2); print(a2, 0, SIZE_2 - 1); cout << endl; } // Sort the given array of size void mergeSort(int a[], int size) { int work[size]; // work space mergeSort(a, 0, size - 1, work); } // Sort the given array in [iLeft, iRight] void mergeSort(int a[], int iLeft, int iRight, int work[]) { if ((iRight - iLeft) >= 1) { // more than 1 elements, divide and sort // Divide into left and right half int iLeftHalfLeft = iLeft; int iLeftHalfRight = (iRight + iLeft) / 2; // truncate int iRightHalfLeft = iLeftHalfRight + 1; int iRightHalfRight = iRight; // Recursively sort each half mergeSort(a, iLeftHalfLeft, iLeftHalfRight, work); mergeSort(a, iRightHalfLeft, iRightHalfRight, work); // Merge two halves merge(a, iLeftHalfLeft, iLeftHalfRight, iRightHalfLeft, iRightHalfRight, work); } } // Merge two halves in [iLeftHalfLeft, iLeftHalfRight] and [iRightHalfLeft, iRightHalfRight] // Assume that iLeftHalfRight + 1 = iRightHalfLeft void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight, int iRightHalfLeft, int iRightHalfRight, int work[]) { int size = iRightHalfRight - iLeftHalfLeft + 1; int iResult = 0; int iLeft = iLeftHalfLeft; int iRight = iRightHalfLeft; while (iLeft <= iLeftHalfRight && iRight <= iRightHalfRight) { if (a[iLeft] <= a[iRight]) { work[iResult++] = a[iLeft++]; } else { work[iResult++] = a[iRight++]; } } // Copy the remaining left or right into work while (iLeft <= iLeftHalfRight) work[iResult++] = a[iLeft++]; while (iRight <= iRightHalfRight) work[iResult++] = a[iRight++]; // for tracing print(a, iLeftHalfLeft, iLeftHalfRight); print(a, iRightHalfLeft, iRightHalfRight); cout << "=> "; print(work, 0, size - 1); cout << endl; // Copy the work back to the original array for (iResult = 0, iLeft = iLeftHalfLeft; iResult < size; ++iResult, ++iLeft) { a[iLeft] = work[iResult]; } } // Print the contents of the given array from iLeft to iRight (inclusive) void print(const int a[], int iLeft, int iRight) { cout << "{"; for (int i = iLeft; i <= iRight; ++i) { cout << a[i]; if (i < iRight) cout << ","; } cout << "} "; }```
```{8,4,5,3,2,9,4,1}
{8} {4} => {4,8}
{5} {3} => {3,5}
{4,8} {3,5} => {3,4,5,8}
{2} {9} => {2,9}
{4} {1} => {1,4}
{2,9} {1,4} => {1,2,4,9}
{3,4,5,8} {1,2,4,9} => {1,2,3,4,4,5,8,9}
{1,2,3,4,4,5,8,9}

{8,4,5,3,2,9,4,1,9,1,2,4,5}
{8} {4} => {4,8}
{5} {3} => {3,5}
{4,8} {3,5} => {3,4,5,8}
{2} {9} => {2,9}
{2,9} {4} => {2,4,9}
{3,4,5,8} {2,4,9} => {2,3,4,4,5,8,9}
{1} {9} => {1,9}
{1,9} {1} => {1,1,9}
{2} {4} => {2,4}
{2,4} {5} => {2,4,5}
{1,1,9} {2,4,5} => {1,1,2,4,5,9}
{2,3,4,4,5,8,9} {1,1,2,4,5,9} => {1,1,2,2,3,4,4,4,5,5,8,9,9}
{1,1,2,2,3,4,4,4,5,5,8,9,9}```
##### Interactive Bottom-up Merge Sort

Treat the list as sublists of length 1, and interactively merge a pair of sublists bottom-up, until there is only one sublist.

 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95``` ```/* Sorting an array using Merge Sort with bottom-up interactive algorithm (MergeSortInteractive.cpp) */ #include using namespace std; void mergeSort(int a[], int size); void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight, int iRightHalfLeft, int iRightHalfRight, int work[]); void print(const int a[], int iLeft, int iRight); int main() { // Test 1 const int SIZE_1 = 8; int a1[SIZE_1] = {8, 4, 5, 3, 2, 9, 4, 1}; print(a1, 0, SIZE_1 - 1); cout << endl; mergeSort(a1, SIZE_1); print(a1, 0, SIZE_1 - 1); cout << endl << endl; // Test 2 const int SIZE_2 = 13; int a2[SIZE_2] = {8, 4, 5, 3, 2, 9, 4, 1, 9, 1, 2, 4, 5}; print(a2, 0, SIZE_2 - 1); cout << endl; mergeSort(a2, SIZE_2); print(a2, 0, SIZE_2 - 1); cout << endl; } // Sort the given array of size void mergeSort(int a[], int size) { int work[size]; // work space int width = 1; // width of sublists to merge while (width < size) { // Merge 2 sublists of width for (int i = 0; i < size - width; i += 2*width) { // Get the bounds of left and right sublists int iLeftHalfLeft = i; int iLeftHalfRight = i + width - 1; int iRightHalfLeft = i + width; int iRightHalfRight = i + 2*width - 1; if (iRightHalfRight >= size - 1) iRightHalfRight = size - 1; // Merge left and right sublists merge(a, iLeftHalfLeft, iLeftHalfRight, iRightHalfLeft, iRightHalfRight, work); } width *= 2; } } // Merge two halves in [iLeftHalfLeft, iLeftHalfRight] and [iRightHalfLeft, iRightHalfRight] // Assume that iLeftHalfRight + 1 = iRightHalfLeft void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight, int iRightHalfLeft, int iRightHalfRight, int work[]) { int size = iRightHalfRight - iLeftHalfLeft + 1; int iResult = 0; int iLeft = iLeftHalfLeft; int iRight = iRightHalfLeft; while (iLeft <= iLeftHalfRight && iRight <= iRightHalfRight) { if (a[iLeft] <= a[iRight]) { work[iResult++] = a[iLeft++]; } else { work[iResult++] = a[iRight++]; } } // Copy the remaining left or right into work while (iLeft <= iLeftHalfRight) work[iResult++] = a[iLeft++]; while (iRight <= iRightHalfRight) work[iResult++] = a[iRight++]; // for tracing print(a, iLeftHalfLeft, iLeftHalfRight); print(a, iRightHalfLeft, iRightHalfRight); cout << "=> "; print(work, 0, size - 1); cout << endl; // Copy the work back to the original array for (iResult = 0, iLeft = iLeftHalfLeft; iResult < size; ++iResult, ++iLeft) { a[iLeft] = work[iResult]; } } // Print the contents of the given array from iLeft to iRight (inclusive) void print(const int a[], int iLeft, int iRight) { cout << "{"; for (int i = iLeft; i <= iRight; ++i) { cout << a[i]; if (i < iRight) cout << ","; } cout << "} "; }```
```{8,4,5,3,2,9,4,1}
{8} {4} => {4,8}
{5} {3} => {3,5}
{2} {9} => {2,9}
{4} {1} => {1,4}
{4,8} {3,5} => {3,4,5,8}
{2,9} {1,4} => {1,2,4,9}
{3,4,5,8} {1,2,4,9} => {1,2,3,4,4,5,8,9}
{1,2,3,4,4,5,8,9}

{8,4,5,3,2,9,4,1,9,1,2,4,5}
{8} {4} => {4,8}
{5} {3} => {3,5}
{2} {9} => {2,9}
{4} {1} => {1,4}
{9} {1} => {1,9}
{2} {4} => {2,4}
{4,8} {3,5} => {3,4,5,8}
{2,9} {1,4} => {1,2,4,9}
{1,9} {2,4} => {1,2,4,9}
{3,4,5,8} {1,2,4,9} => {1,2,3,4,4,5,8,9}
{1,2,4,9} {5} => {1,2,4,5,9}
{1,2,3,4,4,5,8,9} {1,2,4,5,9} => {1,1,2,2,3,4,4,4,5,5,8,9,9}
{1,1,2,2,3,4,4,4,5,5,8,9,9}```
##### Complexity

The worst-case and average-case time complexity is O(n log n). The best-case is typically O(n log n). However, merge sort requires a space complexity of O(n) for carrying out the merge-sorting.

#### Quick Sort

Quick sort is a divide and conquer algorithm. It picks a pivot and divides the list into two sub-lists: the low elements and the high elements, and recursively sorts the sub-lists.

1. Pick a element, called pivot, from the list.
2. Partition the list so that the smaller elements are before the pivot, and the larger elements after the pivot.
3. Recursively sort the sub-lists.

Partition: The partition procedure are:

```// Assume that the pivot element is already on the right
partition(array, left, right)
storeIndex := left
for i from left to right - 1  // left <= i < right
if array[i] <= pivotValue
if i != storeIndex
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right]  // Move pivot to its final place
return storeIndex```

Choosing the pivot: If the list is already sorted, choosing the first or last element as pivot results in worst performance of O(n2). We choose the middle element, and swap the the element at the right end, so as not to interfere with the partition process.

##### QuickSort.cpp
 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107``` ```/* Sorting an array using Quick Sort (QuickSort.cpp) */ #include using namespace std; void quickSort(int a[], int size); void quickSort(int a[], int left, int right); void choosePivot(int a[], int left, int right); int partition(int a[], int left, int right); void print(const int a[], int left, int right); int main() { // Test 1 const int SIZE_1 = 8; int a1[SIZE_1] = {8, 4, 5, 3, 2, 9, 4, 1}; print(a1, 0, SIZE_1 - 1); cout << endl; quickSort(a1, SIZE_1); print(a1, 0, SIZE_1 - 1); cout << endl << endl; // Test 2 const int SIZE_2 = 13; int a2[SIZE_2] = {8, 4, 5, 3, 2, 9, 4, 1, 9, 1, 2, 4, 5}; print(a2, 0, SIZE_2 - 1); cout << endl; quickSort(a2, SIZE_2); print(a2, 0, SIZE_2 - 1); cout << endl; } // Sort the given array of size void quickSort(int a[], int size) { quickSort(a, 0, size - 1); } // Sort the given array in [left, right] void quickSort(int a[], int left, int right) { if ((right - left) >= 1) { // more than 1 elements, need to sort choosePivot(a, left, right); int pivotIndex = partition(a, left, right); quickSort(a, left, pivotIndex - 1); quickSort(a, pivotIndex + 1, right); } } // Choose a pivot element and swap with the right void choosePivot(int a[], int left, int right) { int pivotIndex = (right + left) / 2; int temp; temp = a[pivotIndex]; a[pivotIndex] = a[right]; a[right] = temp; } // Partition the array [left, right] with pivot initially on the right. // Return the index of the pivot after partition, all elements to the // left of pivot are smaller; while to the right are larger. int partition(int a[], int left, int right) { int pivot = a[right]; int temp; // for swapping int storeIndex = left; // Start the storeIndex from left, swap elements smaller than // pivot into storeIndex and increase the storeIndex. // At the end of the pass, all elements up to storeIndex are // smaller than pivot. for (int i = left; i < right; ++i) { // exclude pivot if (a[i] < pivot) { // for tracing print(a, left, right); if (i != storeIndex) { temp = a[i]; a[i] = a[storeIndex]; a[storeIndex] = temp; } ++storeIndex; // for tracing cout << "=> "; print(a, left, right); cout << endl; } } // Swap pivot and storeIndex a[right] = a[storeIndex]; a[storeIndex] = pivot; // for tracing print(a, left, storeIndex - 1); cout << "{" << a[storeIndex] << "} "; print(a, storeIndex + 1, right); cout << endl; return storeIndex; } // Print the contents of the given array from left to right (inclusive) void print(const int a[], int left, int right) { cout << "{"; for (int i = left; i <= right; ++i) { cout << a[i]; if (i < right) cout << ","; } cout << "} "; }```
```{8,4,5,3,2,9,4,1}
{8,4,5,1,2,9,4,3} => {1,4,5,8,2,9,4,3}
{1,4,5,8,2,9,4,3} => {1,2,5,8,4,9,4,3}
{1,2} {3} {8,4,9,4,5}
{} {1} {2}
{8,4,5,4,9} => {8,4,5,4,9}
{8,4,5,4,9} => {8,4,5,4,9}
{8,4,5,4,9} => {8,4,5,4,9}
{8,4,5,4,9} => {8,4,5,4,9}
{8,4,5,4} {9} {}
{} {4} {4,5,8}
{4,8,5} => {4,8,5}
{4} {5} {8}
{1,2,3,4,4,5,8,9}

{8,4,5,3,2,9,4,1,9,1,2,4,5}
{8,4,5,3,2,9,5,1,9,1,2,4,4} => {3,4,5,8,2,9,5,1,9,1,2,4,4}
{3,4,5,8,2,9,5,1,9,1,2,4,4} => {3,2,5,8,4,9,5,1,9,1,2,4,4}
{3,2,5,8,4,9,5,1,9,1,2,4,4} => {3,2,1,8,4,9,5,5,9,1,2,4,4}
{3,2,1,8,4,9,5,5,9,1,2,4,4} => {3,2,1,1,4,9,5,5,9,8,2,4,4}
{3,2,1,1,4,9,5,5,9,8,2,4,4} => {3,2,1,1,2,9,5,5,9,8,4,4,4}
{3,2,1,1,2} {4} {5,5,9,8,4,4,9}
{} {1} {2,2,1,3}
{2,3,1,2} => {1,3,2,2}
{1} {2} {2,3}
{} {2} {3}
{5,5,9,9,4,4,8} => {5,5,9,9,4,4,8}
{5,5,9,9,4,4,8} => {5,5,9,9,4,4,8}
{5,5,9,9,4,4,8} => {5,5,4,9,9,4,8}
{5,5,4,9,9,4,8} => {5,5,4,4,9,9,8}
{5,5,4,4} {8} {9,9}
{5,4,4,5} => {4,5,4,5}
{4,5,4,5} => {4,4,5,5}
{4,4} {5} {5}
{} {4} {4}
{} {9} {9}
{1,1,2,2,3,4,4,4,5,5,8,9,9}```
##### Complexity

The worst-case time complexity is O(n2). The average-case (typical) and best-case is O(n log n). In-place sorting can be achieved without additional space requirement.

#### Bucket Sort

Bucket sort (or bin sort) works by distributing the elements into a number of buckets, and each bucket is then sorted individually. Bucket sort is a distribution sort, and is a cousin of radix sort, in which the sorting begins at the most significant digit and goes down to the less significant ones. Bucket sort is not a comparison sort like bubble sort, insertion sort or selection sort.

The algorithm is as follows:

1. Set up buckets, initially empty.
2. Scatter: place each element into an appropriate bucket.
3. Sort each non-empty bucket.
4. Gather: Gather elements from buckets and put back to the original array.
##### Radix Sort (Recursive)

Use 10 buckets to sort from the most-significant down to the least-significant digit.

 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105``` ```/* Bucket Sort (Radix Sort) (BucketSort.cpp) */ #include #include using namespace std; void bucketSort(int a[], int size); void bucketSort(vector & list, int radix); void printBuckets(const vector buckets[], int size); void print(const vector list); const int NUM_BUCKETS = 10; int main() { const int SIZE = 13; int a[] = {28, 104, 25, 593, 22, 129, 4, 11, 129, 4, 111, 20, 9}; bucketSort(a, SIZE); } void bucketSort(int a[], int size) { // find maximum to decide on the number of significant digits int max = a[0]; for (int i = 1; i < size; ++i) { if (a[i] > max) max = a[i]; } // Decide on the max radix (1000, 100, 10, 1, etc) int radix = 1; while (max > 10) { radix *= 10; max /= 10; } // copy the array into a vector vector list(size); for (int i = 0; i < size; ++i) { list[i] = a[i]; } bucketSort(list, radix); } // Sort the given array of size on the particular radix (1, 10, 100, etc) // Assume elements are non-negative integers // radix shall be more than 0 void bucketSort(vector & list, int radix) { if (list.size() > 1 && radix > 0) { // Sort if more than 1 elements // For tracing cout << "To sort: "; print(list); vector buckets[NUM_BUCKETS]; // 10 buckets // Distribute elements into buckets for (int i = 0; i < list.size(); ++i) { int bucketIndex = list[i] / radix % 10; buckets[bucketIndex].push_back(list[i]); } // For tracing cout << "radix=" << radix << ": "; printBuckets(buckets, NUM_BUCKETS); // Recursively sort the non-empty bucket for (int bi = 0; bi < NUM_BUCKETS; ++bi) { if (buckets[bi].size() > 0) { bucketSort(buckets[bi], radix / 10); } } // Gather all the buckets into list and return list.resize(0); // remove all elements for (int bi = 0; bi < NUM_BUCKETS; ++bi) { for (int j = 0; j < buckets[bi].size(); ++j) { list.push_back((buckets[bi])[j]); } } // For tracing cout << "Sorted: "; print(list); } } // Print the contents of all buckets void printBuckets(const vector buckets[], int size) { for (int i = 0; i < size; ++i) { // print each bucket cout << "{"; for (int bi = 0; bi < buckets[i].size(); ++bi) { cout << (buckets[i])[bi]; if (bi < buckets[i].size() - 1) cout << ","; } cout << "} "; } cout << endl; } // Print the contents of vector void print(const vector list) { cout << "{"; for (int i = 0; i < list.size(); ++i) { cout << list[i]; if (i < list.size() - 1) cout << ","; } cout << "}" << endl; }```
```To sort: {28,104,25,593,22,129,4,11,129,4,111,20,9}
radix=100: {28,25,22,4,11,4,20,9} {104,129,129,111} {} {} {} {593} {} {} {} {}
To sort: {28,25,22,4,11,4,20,9}
radix=10: {4,4,9} {11} {28,25,22,20} {} {} {} {} {} {} {}
To sort: {4,4,9}
radix=1: {} {} {} {} {4,4} {} {} {} {} {9}
Sorted: {4,4,9}
To sort: {28,25,22,20}
radix=1: {20} {} {22} {} {} {25} {} {} {28} {}
Sorted: {20,22,25,28}
Sorted: {4,4,9,11,20,22,25,28}
To sort: {104,129,129,111}
radix=10: {104} {111} {129,129} {} {} {} {} {} {} {}
To sort: {129,129}
radix=1: {} {} {} {} {} {} {} {} {} {129,129}
Sorted: {129,129}
Sorted: {104,111,129,129}
Sorted: {4,4,9,11,20,22,25,28,104,111,129,129,593}```

Program Notes:

• Need to implement the buckets using dynamic array (such as `vector`) as their sizes are unknown; and to expensive to set to the maximum.

### Data Structures

The built-in array has many limitations. It is fixed in size and cannot grow and shrink during execution. The size has to be decided during the declaration.

Many applications require dynamic data structures, that can grow and shrink during execution. The commonly used data structures include:

• List: Single linked list, double linked list, etc.
• Queue: FIFO queue, priority queue, etc.
• Stack: LIFO queue
• Tree:
• Map or Associative Array:

#### Single Linked List

##### Node.h
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19``` ```#ifndef NODE_H #define NODE_H template class List; // Forward reference template class Node { private: T data; Node * nextPtr; public: Node (T d) : data(d), nextPtr(0) { }; // Constructor T getData() const { return data; }; // Public getter for data Node * getNextPtr() const { return nextPtr; } // Public getter for nextPtr friend class List; // Make List class a friend to access private data }; #endif```

Program Notes:

• [TODO]
##### List.h
 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128``` ```#ifndef LIST_H #define LIST_H #include #include "Node.h" // Forward Reference template std::ostream & operator<<(std::ostream & os, const List & lst); template class List { private: Node * frontPtr; // First node Node * backPtr; // Last node public: List(); // Constructor ~List(); // Destructor void pushFront(const T & value); void pushBack(const T & value); bool popFront(T & value); bool popBack(T & value); bool isEmpty() const; friend std::ostream & operator<< <>(std::ostream & os, const List & lst); // Overload the stream insertion operator to print the list }; // Constructor - Create an empty list without any node template List::List() : frontPtr(0), backPtr(0) { } // Destructor - Remove all the dynamically allocated nodes template List::~List() { while (frontPtr) { Node * tempPtr = frontPtr; frontPtr = frontPtr->nextPtr; delete tempPtr; } // std::cout << "Destructor completed..." << std::endl; } // Is list empty? Check if frontPtr is null template bool List::isEmpty() const { return frontPtr == 0; } // Push the data in front by dynamically allocate a new node template void List::pushFront(const T & value) { Node * newNodePtr = new Node(value); if (isEmpty()) { frontPtr = backPtr = newNodePtr; } else { newNodePtr->nextPtr = frontPtr; frontPtr = newNodePtr; } } // Push the data at the end by dynamically allocate a new node template void List::pushBack(const T & value) { Node * newNodePtr = new Node(value); if (isEmpty()) { frontPtr = backPtr = newNodePtr; } else { backPtr->nextPtr = newNodePtr; backPtr = newNodePtr; } } // Pop and the data in front to value and remove the node template bool List::popFront(T & value) { if (isEmpty()) { return false; } else if (frontPtr == backPtr) { // only one node value = frontPtr->data; delete frontPtr; // remove node frontPtr = backPtr = 0; // empty } else { value = frontPtr->data; Node * tempPtr = frontPtr; frontPtr = frontPtr->nextPtr; delete tempPtr; } return true; } // Pop and the data at the end to value and remove the node template bool List::popBack(T & value) { if (isEmpty()) { return false; } else if (frontPtr == backPtr) { // only one node value = backPtr->data; delete backPtr; // remove node frontPtr = backPtr = 0; // empty } else { // Locate second to last node Node * currentPtr = frontPtr; while (currentPtr->nextPtr != backPtr) { currentPtr = currentPtr->nextPtr; } value = backPtr->data; delete backPtr; // remove last node backPtr = currentPtr; currentPtr->nextPtr = 0; } return true; } // Overload the stream insertion operator to print the list template std::ostream & operator<< (std::ostream & os, const List & lst) { os << '{'; if (!lst.isEmpty()) { Node * currentPtr = lst.frontPtr; while (currentPtr) { os << currentPtr->getData(); if (currentPtr != lst.backPtr) os << ','; currentPtr = currentPtr->getNextPtr(); } } os << '}'; } #endif```

Program Notes:

• [TODO]
##### TestList.cpp
 ```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``` ```/* Test Driver for List class (TestList.cpp) */ #include #include "List.h" using namespace std; int main() { List lst1; cout << lst1 << endl; lst1.pushFront(8); lst1.pushBack(88); lst1.pushFront(9); lst1.pushBack(99); cout << lst1 << endl; int result; lst1.popBack(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popBack(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popFront(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popFront(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popBack(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; }```
```{}
{9,8,88,99}
value is 99, list is {9,8,88}
value is 88, list is {9,8}
value is 9, list is {8}
value is 8, list is {}
empty list```

Program Notes:

• [TODO]

#### Double Linked List

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23``` ```/* DoubleLinkedNode template class for double linked list (DoubleLinkedNode.h) */ #ifndef DOUBLE_LINKED_NODE_H #define DOUBLE_LINKED_NODE_H template class DoubleLinkedList; // Forward reference template class DoubleLinkedNode { private: T data; DoubleLinkedNode * nextPtr; DoubleLinkedNode * prevPtr; public: DoubleLinkedNode (T d) : data(d), nextPtr(0), prevPtr(0) { }; T getData() const { return data; }; DoubleLinkedNode * getNextPtr() const { return nextPtr; } DoubleLinkedNode * getPrevPtr() const { return prevPtr; } friend class DoubleLinkedList; // Make DoubleLinkedList class a friend to access private data }; #endif```

Program Notes:

• [TODO]
 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131``` ```/* DoubleLinkedList template class for double linked list (DoubleLinkedList.h) */ #ifndef DOUBLE_LINKED_LIST_H #define DOUBLE_LINKED_LIST_H #include #include "DoubleLinkedNode.h" // Forward Reference template std::ostream & operator<<(std::ostream & os, const DoubleLinkedList & lst); template class DoubleLinkedList { private: DoubleLinkedNode * frontPtr; DoubleLinkedNode * backPtr; public: DoubleLinkedList(); // Constructor ~DoubleLinkedList(); // Destructor void pushFront(const T & value); void pushBack(const T & value); bool popFront(T & value); bool popBack(T & value); bool isEmpty() const; friend std::ostream & operator<< <>(std::ostream & os, const DoubleLinkedList & lst); // Overload the stream insertion operator to print the list }; // Constructor - Create an empty list with no node template DoubleLinkedList::DoubleLinkedList() : frontPtr(0), backPtr(0) { } // Destructor - Remove all the dynamically allocated nodes template DoubleLinkedList::~DoubleLinkedList() { while (frontPtr) { DoubleLinkedNode * tempPtr = frontPtr; frontPtr = frontPtr->nextPtr; delete tempPtr; } // std::cout << "Destructor completed..." << std::endl; } // Is list empty? Check if frontPtr is null template bool DoubleLinkedList::isEmpty() const { return frontPtr == 0; } // Push the data in front by dynamically allocate a new node template void DoubleLinkedList::pushFront(const T & value) { DoubleLinkedNode * newPtr = new DoubleLinkedNode(value); if (isEmpty()) { frontPtr = backPtr = newPtr; } else { frontPtr->prevPtr = newPtr; newPtr->nextPtr = frontPtr; frontPtr = newPtr; } } // Push the data at the end by dynamically allocate a new node template void DoubleLinkedList::pushBack(const T & value) { DoubleLinkedNode * newPtr = new DoubleLinkedNode(value); if (isEmpty()) { frontPtr = backPtr = newPtr; } else { backPtr->nextPtr = newPtr; newPtr->prevPtr = backPtr; backPtr = newPtr; } } // Pop and the data in front to value and remove the node template bool DoubleLinkedList::popFront(T & value) { if (isEmpty()) { return false; } else if (frontPtr == backPtr) { // only one node value = frontPtr->data; delete frontPtr; // remove node frontPtr = backPtr = 0; // empty } else { value = frontPtr->data; DoubleLinkedNode * tempPtr = frontPtr; frontPtr = frontPtr->nextPtr; frontPtr->prevPtr = 0; delete tempPtr; } return true; } // Pop and the data at the end to value and remove the node template bool DoubleLinkedList::popBack(T & value) { if (isEmpty()) { return false; } else if (frontPtr == backPtr) { // only one node value = backPtr->data; delete backPtr; // remove node frontPtr = backPtr = 0; // empty } else { value = backPtr->data; DoubleLinkedNode * tempPtr = backPtr; backPtr = backPtr->prevPtr; // 2nd last node backPtr->nextPtr = 0; delete tempPtr; } return true; } // Overload the stream insertion operator to print the list template std::ostream & operator<< (std::ostream & os, const DoubleLinkedList & lst) { os << '{'; if (!lst.isEmpty()) { DoubleLinkedNode * currentPtr = lst.frontPtr; while (currentPtr) { os << currentPtr->getData(); if (currentPtr != lst.backPtr) os << ','; currentPtr = currentPtr->getNextPtr(); } } os << '}'; } #endif```

Program Notes:

• [TODO]
 ```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``` ```/* Test Driver for List class (TestList.cpp) */ #include #include "DoubleLinkedList.h" using namespace std; int main() { DoubleLinkedList lst1; cout << lst1 << endl; lst1.pushFront(8); lst1.pushBack(88); lst1.pushFront(9); lst1.pushBack(99); cout << lst1 << endl; int result; lst1.popBack(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popBack(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popFront(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popFront(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; lst1.popBack(result) ? cout << "value is " << result << ", list is " << lst1 << endl : cout << "empty list" << endl; }```
```{}
{9,8,88,99}
value is 99, list is {9,8,88}
value is 88, list is {9,8}
value is 9, list is {8}
value is 8, list is {}
empty list```

Program Notes:

• [TODO]

#### Stack (LIFO Queue)

##### Stack.h
 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87``` ```#ifndef STACK_H #define STACK_H #include // Forward Reference template class Stack; template std::ostream & operator<<(std::ostream & os, const Stack & s); template class Stack { private: T * data; // Array int tos; // Top of stack, start at index -1 int capacity; // capacity of the array int increment; // each subsequent increment size public: explicit Stack(int capacity = 10, int increment = 10); ~Stack(); // Destructor void push(const T & value); bool pop(T & value); bool isEmpty() const; friend std::ostream & operator<< <>(std::ostream & os, const Stack & s); // Overload the stream insertion operator to print the list }; // Constructor - Create an empty list without any node template Stack::Stack(int cap, int inc) : capacity(cap), increment(inc) { data = new T[capacity]; tos = -1; } // Destructor - Remove all the dynamically allocated nodes template Stack::~Stack() { delete[] data; // remove the dynamically allocate storage // std::cout << "Destructor completed..." << std::endl; } // Is list empty? Check if frontPtr is null template bool Stack::isEmpty() const { return tos < 0; } // Push the data on top of the stack template void Stack::push(const T & value) { if (tos < capacity - 1) { // Have space, simply add in the value data[++tos] = value; } else { // No more space. Allocate a bigger array T * newDataPtr = new T[capacity + increment]; for (int i = 0; i <= tos; ++i) { newDataPtr[i] = data[i]; // copy over } delete[] data; data = newDataPtr; } } // Pop the data from the TOS template bool Stack::pop(T & value) { if (isEmpty()) { return false; } else { value = data[tos--]; } return true; } // Overload the stream insertion operator to print the list template std::ostream & operator<< (std::ostream & os, const Stack & stack) { os << '{'; for (int i = stack.tos; i >= 0; --i) { os << stack.data[i]; if (i > 0) os << ','; } os << '}'; } #endif```

Program Notes:

• [TODO]
##### TestStack.cpp
 ```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``` ```/* Test Driver for Stack class (TestStack.cpp) */ #include #include "Stack.h" using namespace std; int main() { Stack s1; cout << s1 << endl; s1.push(8); s1.push(88); cout << s1 << endl; int result; s1.pop(result) ? cout << "value is " << result << ", stack is " << s1 << endl : cout << "empty stack" << endl; s1.push(9); s1.push(99); cout << s1 << endl; s1.pop(result) ? cout << "value is " << result << ", stack is " << s1 << endl : cout << "empty stack" << endl; s1.pop(result) ? cout << "value is " << result << ", stack is " << s1 << endl : cout << "empty stack" << endl; s1.pop(result) ? cout << "value is " << result << ", stack is " << s1 << endl : cout << "empty stack" << endl; s1.pop(result) ? cout << "value is " << result << ", stack is " << s1 << endl : cout << "empty stack" << endl; }```
```{}
{88,8}
value is 88, stack is {8}
{99,9,8}
value is 99, stack is {9,8}
value is 9, stack is {8}
value is 8, stack is {}
empty stack```

#### Tree

A tree has a root node. Each parent node could have child nodes. A node without child is called a leaf node. A tree with only the root node is called a null tree. The depth of a tree is the length of the path from the root to the deepest node in the tree. A null tree has depth of zero.

In a binary tree, a parent node could have up to two child nodes: left child and right child (called siblings with the same parent). They are root of the left subtree and right subtree respectively.

##### Depth-First Search (DFS)

Start at the root and explore as far as possible along each branch before backtracking. They are 3 types of depth-first search:

1. Pre-order: visit the root, traverse the left subtree, then the right subtree. E.g., 6 -> 5 -> 4 -> 10 -> 7 -> 9 ->15.
2. In-order: traverse the left subtree, visit the root, then the right subtree. E.g., 4 -> 5 -> 6 -> 7 -> 9 ->10 -> 15.
3. Post-order: traverse the left subtree, the right subtree, then visit the root. E.g, 4 -> 5 -> 9 -> 7 -> 15 -> 10 -> 6.

Pre-, in- and post- refer to the order of visiting the root.

##### Breadth-First Search (BFS)

Begin at the root, visit all its child nodes. Then for each of the child nodes visited, visit their child nodes in turn. E.g., 6 -> 5 -> 10 -> 4 -> 7 -> 15 -> 9.

##### Binary Search Tree

A binary search tree, without duplicate elements, has these properties:

1. All values in the left subtree are smaller than the parent node.
2. All values in the right subtree are larger than the parent node.

The above diagram illustrates a binary search tree. You can retrieve the sorted list or perform searching via in-order depth-first traversal. Take note that the actual shape of the tree depends on the order of insertion.

##### Node.h
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23``` ```/* Node template class for binary tree (Node.h) */ #ifndef NODE_H #define NODE_H template class BinaryTree; // Forward reference template class Node { private: T data; Node * rightPtr; Node * leftPtr; public: Node (T d) : data(d), rightPtr(0), leftPtr(0) { }; T getData() const { return data; }; Node * getRightPtr() const { return rightPtr; } Node * getLeftPtr() const { return leftPtr; } friend class BinaryTree; // Make BinaryTree class a friend to access private data }; #endif```

Program Notes:

• [TODO]
##### BinaryTree.h
 ```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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155``` ```/* BinaryTree template class for binary tree (BinaryTree.h) */ #ifndef BINARY_TREE_H #define BINARY_TREE_H #include #include #include "Node.h" // Forward Reference template std::ostream & operator<<(std::ostream & os, const BinaryTree & lst); template class BinaryTree { private: Node * rootPtr; // private helper functions void insertNode(Node * & ptr, const T & value); void preOrderSubTree(const Node * ptr, std::ostream & os = std::cout) const; void inOrderSubTree(const Node * ptr, std::ostream & os = std::cout) const; void postOrderSubTree(const Node * ptr, std::ostream & os = std::cout) const; void removeSubTree(Node * & ptr); public: BinaryTree(); // Constructor ~BinaryTree(); // Destructor void insert(const T & value); bool isEmpty() const; void preOrderTraversal(std::ostream & os = std::cout) const; void inOrderTraversal(std::ostream & os = std::cout) const; void postOrderTraversal(std::ostream & os = std::cout) const; void breadthFirstTraversal(std::ostream & os = std::cout) const; friend std::ostream & operator<< <>(std::ostream & os, const BinaryTree & lst); // Overload the stream insertion operator to print the list }; // Constructor - Create an empty list with no node template BinaryTree::BinaryTree() : rootPtr(0) { } // Destructor - Remove all the dynamically allocated nodes template BinaryTree::~BinaryTree() { removeSubTree(rootPtr); // std::cout << "Destructor completed..." << std::endl; } template void BinaryTree::removeSubTree(Node * & ptr) { if (ptr) { removeSubTree(ptr->leftPtr); // remove left subtree removeSubTree(ptr->rightPtr); // remove right subtree delete ptr; } } // Is list empty? Check if rootPtr is null template bool BinaryTree::isEmpty() const { return rootPtr == 0; } // Push the data in front by dynamically allocate a new node template void BinaryTree::insert(const T & value) { insertNode(rootPtr, value); } // Need to pass the pointer by reference so as to modify the caller's copy template void BinaryTree::insertNode(Node * & ptr, const T & value) { if (ptr == 0) { ptr = new Node(value); } else { if (value < ptr->data) insertNode(ptr->leftPtr, value); else if (value > ptr->data) insertNode(ptr->rightPtr, value); else std::cout << "duplicate value" << std::endl; } } template void BinaryTree::preOrderTraversal(std::ostream & os) const { os << "{ "; preOrderSubTree(rootPtr); os << '}' << std::endl; } template void BinaryTree::preOrderSubTree(const Node * ptr, std::ostream & os) const { if (ptr) { os << ptr->data << ' '; preOrderSubTree(ptr->leftPtr); preOrderSubTree(ptr->rightPtr); } } template void BinaryTree::inOrderTraversal(std::ostream & os) const { os << "{ "; inOrderSubTree(rootPtr); os << '}' << std::endl; } template void BinaryTree::inOrderSubTree(const Node * ptr, std::ostream & os) const { if (ptr) { inOrderSubTree(ptr->leftPtr); os << ptr->data << ' '; inOrderSubTree(ptr->rightPtr); } } template void BinaryTree::postOrderTraversal(std::ostream & os) const { os << "{ "; postOrderSubTree(rootPtr); os << '}' << std::endl; } template void BinaryTree::postOrderSubTree(const Node * ptr, std::ostream & os) const { if (ptr) { postOrderSubTree(ptr->leftPtr); postOrderSubTree(ptr->rightPtr); os << ptr->data << ' '; } } // Breadth First Search (BFS) template void BinaryTree::breadthFirstTraversal(std::ostream & os) const { std::queue * > q; if (!isEmpty()) q.push(rootPtr); os << "{ "; Node * currentPtr; while (currentPtr = q.front()) { std::cout << currentPtr->data << ' '; if (currentPtr->leftPtr) q.push(currentPtr->leftPtr); if (currentPtr->rightPtr) q.push(currentPtr->rightPtr); q.pop(); // remove this node } os << '}' << std::endl; } // Overload the stream insertion operator to print the list in in-order traversal template std::ostream & operator<< (std::ostream & os, const BinaryTree & lst) { lst.inOrderTraversal(os); return os; } #endif```

Program Notes:

• [TODO]
##### TestBinaryTree.cpp
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21``` ```/* Test Driver for BinaryTree class (TestBinaryTree.cpp) */ #include #include "BinaryTree.h" using namespace std; int main() { BinaryTree t1; t1.insert(6); t1.insert(10); t1.insert(5); t1.insert(15); t1.insert(7); t1.insert(4); t1.insert(9); t1.preOrderTraversal(); t1.inOrderTraversal(); t1.postOrderTraversal(); cout << t1; t1.breadthFirstTraversal(); }```
```{ 6 5 4 10 7 9 15 }  // pre-order depth-first search
{ 4 5 6 7 9 10 15 }  // in-order depth-first search (ascending order)
{ 4 5 9 7 15 10 6 }  // post-order depth-first search
{ 4 5 6 7 9 10 15 }  // in-order depth-first search
{ 6 5 10 4 7 15 9 }  // breadth-first search```

Program Notes:

• [TODO]

[TODO] Breadth-First Search: need a FIFO queue to keep the child nodes.

REFERENCES & RESOURCES

REFERENCES & RESOURCES