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

Tagged: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: