Category Archives: Uncategorized

C++ Insertion Sort

A simple implementation of insertion sort algorithm in C++

– Fill array with random numbers

template <typename Comparable>
void fillRandom(vector<Comparable> &iArray, Comparable range)
{
	srand((unsigned)time(0));
	for(Comparable i = 0; i < iArray.size(); i++)
	{
		iArray[i] = rand() % range;
	}
}

– Insertion Sort forwards

template <typename Comparable>
void insertionSort(vector<Comparable> &a)
{
	for(int unsorted = 1; unsorted < a.size(); unsorted++)
	{
		int loc;
		Comparable nextItem = a[unsorted];
		for(loc = unsorted; loc > 0 && nextItem < a[loc - 1]; loc--)
		{
			a[loc] = a[loc - 1];
		}

		a[loc] = nextItem;
	}
}

– Insertion Sort backwards

template <typename Comparable>
void insertionSortInverted(vector<Comparable> &a)
{
	for(int unsorted = a.size() - 2; unsorted >= 0; unsorted--)
	{
		int loc;
		Comparable nextItem = a[unsorted];
		for(loc = unsorted; loc < a.size() - 1 && nextItem > a[loc + 1]; loc++)
		{
			a[loc] = a[loc + 1];
		}

		a[loc] = nextItem;
	}
}
Advertisements

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!