Part 1: Implement Selection and Insertion sort for your Array List class. Then implement any of the basic sorts (Bubble, Selection, or Insertion) for a singly Linked List.
Note: Keep your old implementation and append the following functions:
template <class T class Array { private:
/* You fill out the private contents. */
public:
/* Runs a bubble sort algorithm on the array.
* The array shall be ordered from least to greatest
*/ void bubbleSort();
/* Runs a selection sort algorithm on the array.
* The array shall be ordered from least to greatest
*/ void selectionSort();
/* Runs a insertion sort algorithm on the array.
* The array shall be ordered from least to greatest
*/ void insertionSort();
/* Runs the sort routing you believe is the best. */ void sort();
};
/* SLL = Singly Linked List */ template<class T class SLList { public:
/* Sort the linked list. You may use any sort algorithm you wish */ void sort();
};
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
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.
Part 2: Performance
Generate a graph to compare the performance of bubble sort, selection sort, insertion sort, and the sort you chose for a Singly Linked List. Your graph should have data size on the x axis and time on the y axis. Make sure to label each graph line! Please turn in as a .pdf!
Auto Grader:
The auto grader is only grading part 1, I will have to assess part 2. In other words, if the auto grade issues a 100, that is only for part 1!
Memory Management:
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 the STL.
How to turn in:
Turn in via GitHub. Ensure the file(s) are in your directory and then:
• $ git add <files
• $ git commit
• $ git push
