James PK's Technical Journal

[ Home | Journal ]


Mon, 16 Dec 2013

C++ - Basic Sorting

"Understanding Algorithms and Data Structures" by Brunskill and Turner was on the reading list of one the units on my CS course. It has some interesting chapters on searching. Although fairly basic in the scheme of things I found these basic sorting type fun to play around with.

Brunskill & Turner, pose some interesting questions along the way, such as how many comparisons are there?, how many swaps occur? , etc. They add a couple of interesting tweaks to get some performance lift. This is my rough take of the functions for those three search types.

Selection
void selection_sort(int numbers [],int size)
{
	int comparisions=0;
	int swap=0;
	for (int i=1;i < size;i++)
	{
		int i_min=i;
		for (int j=i+1; j < size;j++)
		{	
			++comparisions;
   			if (numbers[j] < numbers[i_min])
    				i_min =j;
		}
		if (i_min != i)
		{
			int temp=numbers[i_min];
			numbers[i_min]=numbers[i];
			numbers[i]=temp;	
			++swap;
		}
	}
	#cout comparisions & swaps
}
Bubble
void bubble_sort(int numbers [],int size)
{
	int comparisions=0;
	int swap=0;
	for (int i=0;i < size;i++)
		for (int j=0; j< size; j++)
		{
			++comparisions;
			if (numbers[j] > numbers[j+1])
			{	int tmp=numbers[j];
				numbers[j]=numbers[j+1];
				numbers[j+1] = tmp;
				++swap;
			}
		}
	#cout comparisions & swaps
}
Insertion
void insertion_sort(int numbers [],int size)
{
	int comparisons=0;
	int swap=0;
	for (int i=1;i < size;i++)
	{
		int pos=i;
		int val=numbers[i];
		while ( pos >0 && val < numbers[pos-1])
		{	numbers[pos]= numbers[pos-1];
			pos=pos-1;
			comparisons++;
		}
		numbers[pos]=val;
		swap++;
	}
	#cout comparisions & swaps
}

Results - Running the above, on a various sizes of arrays with random numbers, with the `time` command, unsurprising shows the insertion sort (it does *far* less comparisons than the other two approaches) as the winner.

Comments
1. I used an array to store the numbers, using a vector might have been an alternative.
2. Using the time command gives a *very* rough indication of performance - could do alot better by putting a timer around the function call and not the programme itself.
3. The arrays all used different sets random numbers - obliviously they would need to be the same across all three tests to have strong validity.

posted at: 00:00 | path: /cpp | permanent link to this entry


Made with Pyblosxom