Binary Insertion Sort

[eb1993]

I'm feeling very stuck with what to do, very new at this. I'm supposed 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, I will use a binary search. The number of comparisons will be tracked in the SortTester to see if my comparisons are in the range that indicates I have adjusted the search.

//main.cpp

#include <fstream>
#include <iostream>
#include <time.h>

#include "SortTester.h"

using namespace std;

typedef unsigned int uint;

uint findInsertionLocation(SortTester &tester, uint start, uint end, uint index) {
   
//insert code to find the location to insert the next element into


return 0;

}

void insertionSort(SortTester &tester, uint size) {

//insert 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 implmenting the binary search for the insertion location
}

int main() {
	uint size = 10;
	SortTester tester = SortTester(size);
	cout<<"Unsorted"<<endl;
	tester.print();
	insertionSort(tester, size);
	if (tester.isSorted()) {
		cout<<"PASSED List Sorted (10 pts)"<<endl;
	}
	else {
		tester.print();
		cout<<"FAILED List not Sorted"<<endl;
	}

	if (tester.areComparesBinary()) {
	   cout<<"PASSED Binary Insertion Sort (15 pts)"<<endl;
	}
	else {
	   cout<<"FAILED Binary Insertion Sort"<<endl;
	}

	if (tester.isSortStable()) {
	   cout<<"PASSED Extra Credit - sort is stable (5pts)"<<endl;
	}
	else {
	   cout<<"Sort is not stable - swap occured among entries with same value"<<endl;
	}
}



//SortTester.h

#include <fstream>
#include <vector>


class SortTester {
    private:
		std::vector<int> 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 <iostream>
#include <time.h>
#include <cmath>

#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<<it<<" ";
	}
	cout<<"\n";
}

int SortTester::compare(unsigned int a, unsigned int b) {
	numCompares++;
	return testList[a] - testList[b];
}

void SortTester::swap(unsigned int a, unsigned int b) {
	if ((testList[a] == testList[b]) and (a != b)) {
		stableSort= false;
	}
	if ( (a > testList.size()) or (b > testList.size()) or (a<0) or (b<0) ) {
		cout<<"Invalid swap request of "<<a<<" and "<<b<<" no swap performed"<<endl;
		return;
	}
	int temp = testList[a];
	testList[a] = testList[b];
	testList[b] = temp;
	return;
}

bool SortTester::isSorted() {
	bool sorted = true;
	for (unsigned int i=0; i < testList.size() - 1; i++) {
		if (testList[i] > 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;
}

[jonnin]

where is the insertion sort?
if you have not done that, did you have a question on it? Do what they said, write it the normal way first, but make the search loop part a function so you can swap it out with the binary search after.
https://en.wikipedia.org/wiki/Insertion_sort

insertion sort leads to shell sort which is much, much more interesting IMHO.