Monthly Archives: December 2012

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;
	}
}

C++ Bubble Sort

A simple implementation of Bubble Sort algorithm:

Also on Blogger

– Random Generator:

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

– Bubble Sort Algorithm:

template <typename Comparable>
void bubbleSort(vector<Comparable> &a)
{
	bool sorted = false;
	for(int pass = 1; pass < a.size() && !sorted; pass++)
	{
		sorted = true; // Optimize and stop if array is already sorted
		for(int index = 0; index < a.size() - pass; index++)
		{
			if(a[index] > a[index + 1])
			{
				swap(a[index], a[index + 1]);
				sorted = false;
			}
		}
	}
}

– Bubble Sort Algorithm, inverted version:

template <typename Comparable>
void bubbleSortInverted(vector<Comparable> &a)
{
	bool sorted = false;
	for(int pass = a.size() - 1; pass > 0 && !sorted; pass--)
	{
		sorted = true; // Optimize and stop if array is already sorted
		for(int index = a.size() - 1; index > 0; index--)
		{
			if(a[index] < a[index - 1])
			{
				swap(a[index], a[index - 1]);
				sorted = false;
			}
		}
	}
}

C++ Selection Sort

A brief implementation about Selection Sort:

– First we need a random generator:

void fillRandom(vector<int> &iArray)
{
	srand((unsigned)time(0));
	for(int i = 0; i < iArray.size(); i++)
	{
		iArray[i] = rand();
	}
}

– Selection Sort algorithm starting from biggest to smallest:

template <typename Comparable>
void selectionSort(vector<Comparable> &a, int last)
{
	if(last <= 0)
	{
		return;
	}

	vector<Comparable>::size_type largest = a[0];
	int index = 0;
	for(int i = 1; i <= last; i++)
	{
		if(a[i] > largest)
		{
			largest = a[i];
			index = i;
		}
	}

	vector<Comparable>::size_type buffer = a[index];
	a[index] = a[last];
	a[last] = buffer;
	selectionSort(a, last - 1);
}

– Selection Sort algorithm starting from smallest to biggest:

template <typename Comparable>
void selectionSortInvert(vector<Comparable> &a, int first)
{
	if(first >= a.size())
	{
		return;
	}

	Comparable smallest = a[first];
	int index = first;
	for(int i = first + 1; i < a.size(); i++)
	{
		if(a[i] < smallest)
		{
			smallest = a[i];
			index = i;
		}
	}

	vector<Comparable>::size_type buffer = a[index];
	a[index] = a[first];
	a[first] = buffer;
	selectionSortInvert(a, first + 1);
}

– Finally, libraries used:

#include <iostream>
#include <vector>
#include <ctime>