We have now discussed quite a few sorts, and their performance metrics. For this assignment you are going to write an insertion sort in entirety  you will have available the same SortTester class that will provide the storage, comparison and swap functionality that you had on the last program. The assignment is to write an insertion sort and modify it such that instead of using a backwards linear search to find the location that the insertion elements belongs, you will use a binary search. The number of comparisons will be tracked in the SortTester to see if your comparisons are in the range that indicates you have adjusted the search. There is a bonus for this program if you can implement the algorithm in a way that maintains stability. Your swaps will be monitored and if your sort is stable, elements with the same value will not get swapped and you will receive the extra credit - you have to get full credit for all the other parts in order to be eligible for the extra credit.

main.cpp

#include #include #include #include "SortTester.h" using namespace std; typedef unsigned int uint; uint findInsertionLocation(SortTester &tester, uint start, uint end, uint index) { //insert your code to find the location to insert the next element into return 0; } void insertionSort(SortTester &tester, uint size) { //insert your code for insertion sort here //HINT// //First get your insertion sort working by just searching backward for location //Then once that is working - work on implemnting the binary search for the insertion location } int main() { uint size = 10; SortTester tester = SortTester(size); cout<<"Unsorted"<

SortTester.h

#include #include class SortTester { private: std::vector testList; unsigned int numCompares; bool stableSort; public: SortTester(unsigned int numEntries); void swap(unsigned int a, unsigned int b); //returns positive number if a > b, 0 if a==b, and negative number if a < b int compare(unsigned int a, unsigned int b); void print(); bool areComparesBinary(); bool isSorted(); bool isSortStable(); };

SortTester.cpp

#include #include #include #include "SortTester.h" using namespace std; SortTester::SortTester(unsigned int numEntries) { numCompares = 0; stableSort = true; srand(time(NULL)); for (unsigned int i=0; i < numEntries; i++ ) { testList.push_back( rand() % 100); } } void SortTester::print() { for (auto & it : testList) { cout< testList.size()) or (b > testList.size()) or (a<0) or (b<0) ) { cout<<"Invalid swap request of "< testList[i+1] ) { sorted = false; } } if ( sorted ) { return true; } //implied else print(); return false; } bool SortTester::areComparesBinary() { unsigned int n = testList.size(); return numCompares < 2*n*log2(n); } bool SortTester::isSortStable() { return stableSort; }