Archive for the ‘Programming’ Category

McGaijin Software interview – Learn Hiragana Now!

Thursday, September 30th, 2010

McGaijin Software have just released their first iOS app “Learn Hiragana Now!” to help you learn the Japanese hiragana alphabet. Here is my interview with them.

1. Tell us about your new iOS app.

‘Learn Hiragana Now!’ is my little app to help people to read and write hiragana (one of the Japanese syllabaries) in as fast a time as possible.

learn hiragana now

2. How did you get the idea for Learn Hiragana Now?

My husband and I love Japan, and while we both spoke enough Japanese to get around, on our first trip we soon realised that being able to read would be a massive benefit. When we got back home we made an effort to learn hiragana, but if you don’t use what you learn regularly it quickly disappears from your memory. We made up some mnemonics (memory aids) to assist learning, and found that the learning became more permanent. When we both bought iPod Touches we got the idea for the app. It is the perfect platform – it’s portable so you can learn anywhere, and the touch interface makes it very easy to use.

3. What challenges did you face with creating it?

Everything! I bought a second-hand Mac laptop to develop it on, and I’d never used a Mac before so it was a steep learning curve. I’d also never done any programming!

4. What tools did you use?

  • PhoneGap to compile the application (a package to allow you to use HTML & JavaScript within iPhone apps).
  • PaintShop Pro for the images.
  • CoffeeCup HTML editor to create the bones of the app.

5. What testing did you do for the app?

Everything was tested by hand. As the app was mainly HTML it was easy to test in a normal web browser. Once it was compiled on an actual iPod Touch I just made sure that every link went to the correct place – it was more time consuming than I thought, so hopefully there are no bugs!

6. How did you become interested in programming?

Creating this app was my first programming experience.

7. Will you be porting this app to other platforms?

PhoneGap allows compilation to Android, and Blackberry if I remember correctly. I’ve got an Android phone but to be honest I’ve not had chance to sit down and look at this properly – real life tends to get in the way of things!

8. What would you like to see changed or added to the iPhone SDK?

As a complete beginner when it comes to programming (and Macs!) I would love to see a beyond-simple set of video tutorials that you can use to get up and running, and teach programming basics.

9. What next for McGaijin Software?

I’m working on ‘Learn Katakana Now!’ – a similar app with a new set of mnemonics to learn katakana. Again, this is taking longer than I originally thought, but it will get there eventually.

10. Are there any other iOS apps you’d recommend for learning Japanese?

Kana LS – it’s a perfect companion for Learn Hiragana Now. It allows you to practise actually writing the kana on the screen with your finger, great for revision!
Human Japanese – a great introduction to the Japanese language, filled with tons of interesting facts.

Learn Hiragana Now! is available on the App Store now.

Learn

You can get the latest information about them McGaijin Software on the McGaijin Software website.

DOS: Get the directory name from a file path

Monday, June 28th, 2010

If you need to write a DOS batch file that takes a file path as an input parameter and needs to do something to other files in the same directory as the input file then you’ll find there is no easy way to get the file’s directory name into a variable.

dos path from file

You could pass in the directory name as a separate parameter but that seems like cheating. I sometimes find answers to problems like these on Rob van der Woude’s scripting site or Google, but no luck this time.

I had to figure this one out from scratch. Here’s what I do. Let me know if you have a better (shorter) way of doing this.

  • Output the result of running ‘dir’ on the file path into a temporary file.
  • Loop through the lines in the temporary file, skipping the first three, and then taking the third token.
  • Assign that token to a variable.

If all has worked the variable which I’ve called ‘thedirectory’ should now contain the file path.

I’ve tested this on Windows 7 and I’m guessing it will work on other versions of Windows, but I’ll make no promises.

Here is the code:

goto :skip_functions

:setDir
if not %thedirectory% == "" goto :EOF
set thedirectory=%1
goto :EOF

:getDirectory
del %TEMP%\getdir.tmp
dir %1 > %TEMP%\getdir.tmp
for /f "skip=3 tokens=3" %%i in (%temp%\getdir.tmp) do call :setDir %%i
goto :EOF

:skip_functions

set thedirectory=""
call :getDirectory %1

@echo off
echo thefile =%1
echo thedirectory=%thedirectory%

And if you want to know what I needed it for have a look at my post about stitching together photos using ImageMagick.

Triangle Identification – C++ solution and test code

Tuesday, September 23rd, 2008

Here is another interview coding question that I have heard of.

You have to write a function to identify the triangle type. You have to return a number between 1 or 4 to identify either a valid triangle type or an error.

The solution is very simple requiring only one condensed line of code to identify each triangle type. Two lines of code identify error cases. One of the error cases identifies input with 0 or negative lengths. The other error case identifies line lengths that don’t make a triangle or which make a segment (thanks to Yabba for pointing out these error cases).

As an exercise you could try to extend the solution to identify right-angled triangles as well.

const int SCALENE = 1;
const int ISOSCELES = 2;
const int EQUILATERAL = 3;
const int ERROR = 4;
int TriangleType(int x, int y, int z)
{
	if ((x + y <= z) || (x + z <= y) || (z + y <= x)) return ERROR;
	if (x<=0 || y<=0 || z<=0) return ERROR;
	if (x == y && y == z) return EQUILATERAL;
	if (x == y || y == z || z == x) return ISOSCELES;
	return SCALENE;
}

The more interesting code comes from testing the function. To test the function I pass in a series of triangle side lengths. I also pass in the expected result. If the actual result matches the expected result then the test passes.

The test data is written in a way that allows each test to be defined in a single line of code which makes it very easy to extend.

This easy extendibility was fortunate as my original version of this solution missed out the cases where the line lengths don’t make a triangle (e.g. 1, 1, 5), and where the line lengths make a segment (e.g. 2, 2, 4).

void TriangleTest()
{
const int testDataSize = 14;
int testData[testDataSize][4] = {
	{9, 9, 9, EQUILATERAL},
	{4, 5, 5, ISOSCELES},
	{5, 4, 5, ISOSCELES},
	{5, 3, 3, ISOSCELES},
	{0, 0, 0, ERROR}, // 0 number checks
	{0, 1, 2, ERROR},
	{1, 0, 2, ERROR},
	{1, 2, 0, ERROR},
	{-1, -1, -1, ERROR}, // negative number checks
	{-1, 1, 2, ERROR},
	{1, -1, 2, ERROR},
	{1, 2, -1, ERROR},
	{2, 2, 4, ERROR}, // line segment not a triangle
	{1, 1, 5, ERROR} // not a triangle
};
for (int i=0; i<testDataSize; ++i)
{
	int result = TriangleType(
		testData[i][0], testData[i][1], testData[i][2]);
	if (result == testData[i][3])
	{
		cout << " Pass: triangleType("
			<< testData[i][0] << ", "
			<< testData[i][1] << ", "
			<< testData[i][2] << ")==" << result << endl;
	}
	else
	{
		cout << "!Fail: triangleType("
			<< testData[i][0] << ", "
			<< testData[i][1] << ", "
			<< testData[i][2] << ")==" << result
			<< " Expected: " << testData[i][3] << endl;
	}
}
}


Reverse the words in a sentence – C++ solution and test code

Tuesday, September 16th, 2008

Here is a solution to the standard interview questions of reversing the letters in the words of a sentence. It is a more complex version of the even more common “reverse a string” question. I also include my test code.

There are two main parts to this. The first identifies where the word boundaries are. The second reverses the letters between two positions in the array.

The wordStart and wordEnd variables keep track of the word boundaries. We first look for the start of the word and then the end and store the positions. These values are then passed to ReverseWord along with the character array. ReverseWord does some simple character swapping to reverse the word.

void ReverseWords(char string[])
{
	int length = StringLength(string);
	int wordStart = -1;
	int wordEnd = -1;
	for (int i=0; i<length; ++i)
	{
		if (string[i] == ' ' && wordStart == -1)
		{
			continue;
		}
		else if (wordStart == -1)
		{
			wordStart = i;
		}
		if (wordStart != -1 && string[i] == ' ')
		{
			wordEnd = i-1;
			ReverseWord(string, wordStart, wordEnd);
			wordStart = -1;
			wordEnd = -1;
		}
	}
	if (wordStart != -1)
	{
		wordEnd = length-1;
		ReverseWord(string, wordStart, wordEnd);
	}
}
void ReverseWord(char string[], int wordStart, int wordEnd)
{
	int midPoint = (wordStart+wordEnd)/2;
	for (int l=wordStart, r=wordEnd; l<=midPoint; ++l, --r)
	{
		char tmp = string[l];
		string[l] = string[r];
		string[r] = tmp;
	}
}

Here is the test code. For each test a character array is passed to the word reversing function. The result is then compared against the expected result. If they match the test passes. If they don’t match then the test fails. I’ve tried to test the obvious cases. You could easily find flaws in the word reversal function but it is probably good enough to get you onto the next question.

void ReverseWordsTest()
{
	char test1[] = "cat and dog";
	char expected1[] = "tac dna god";
	ReverseAndCheck(test1, expected1);
	char test2[] = "cat and dog ";
	char expected2[] = "tac dna god ";
	ReverseAndCheck(test2, expected2);
	char test3[] = " cat and dog";
	char expected3[] = " tac dna god";
	ReverseAndCheck(test3, expected3);
	char test4[] = " cat and dog ";
	char expected4[] = " tac dna god ";
	ReverseAndCheck(test4, expected4);
	char test5[] = "cat  and dog";
	char expected5[] = "tac  dna god";
	ReverseAndCheck(test5, expected5);
	char test6[] = "catanddog";
	char expected6[] = "goddnatac";
	ReverseAndCheck(test6, expected6);
	char test7[] = "";
	char expected7[] = "";
	ReverseAndCheck(test7, expected7);
}
void ReverseAndCheck(char string[], char expected[])
{
	ReverseWords(string);
	if (MatchingStrings(string, expected))
	{
	cout << " Pass: " << string << endl;
	}
	else
	{
	cout << "!Fail: " << string << " != " << expected << endl;
	}
}
bool MatchingStrings(char string1[], char string2[])
{
	int length = StringLength(string1);
	if (length != StringLength(string2))
	{
		return false;
	}
	for (int i=0; i<length; ++i)
	{
		if (string1[i] != string2[i])
		{
			return false;
		}
	}
	return true;
}
int StringLength(char string[])
{
	int index = 0;
	char s = string[index];
	while (s)
	{
		++index;
		s = string[index];
	}
	return index;
}


Picking the 5th from last element in a singly linked list

Monday, August 18th, 2008

Here’s another of those fun coding interview puzzles. The kind that companies like Microsoft or Google might ask you. Given a singly linked list, select the 5th from last element. I’m writing the solution in C++ but the solution in Java would be almost identical. I’m also putting up my test code.

The restrictions are – you can only make one pass of the list, and you don’t know the length of the list.

First we need to define our linked list element. All it needs is to store a value, and a pointer to the next element in the list.

class Element
{
public:
	Element(int valueArg) : value(valueArg), next(NULL) {}
public:
	int value;
	Element* next;
};

Here is the actual solution. As we are only allowed one pass of the list we use two pointers. The second pointer trails 5 places behind the first pointer. When the first pointer reaches the end of the list we simply return whichever element the second pointer is pointing to.

We need to take care of the special case where the list has less than 5 elements – including the case where the list has 0 elements!

Element* FifthFromLast(Element* root)
{
	Element* current = root;
	int fromLast = 5;
	while (fromLast > 0 && current)
	{
		current = current->next;
		--fromLast;
	}
	if (fromLast != 0)
	{
		return NULL; // less than 5 items in list
	}
	Element* fifthFromLast = root;
	while (current)
	{
		current = current->next;
		fifthFromLast = fifthFromLast->next;
	}
	return fifthFromLast;
}

Here is the test code which tests the most common cases for this problem. As the parameter to FifthFromLast is the root element we can simulate a shorter list by passing in one of the middle elements.

void LinkedListTest()
{
	Element* one = new Element(1);
	Element* two = new Element(2);
	Element* three = new Element(3);
	Element* four = new Element(4);
	Element* five = new Element(5);
	Element* six = new Element(6);
	Element* seven = new Element(7);
	Element* eight = new Element(8);
	Element* nine = new Element(9);
	Element* ten = new Element(10);
	one->next = two;
	two->next = three;
	three->next = four;
	four->next = five;
	five->next = six;
	six->next = seven;
	seven->next = eight;
	eight->next = nine;
	nine->next = ten;
	cout << "Test: find 5th from last in 10 item list" << endl;
	Element* fifthFromLast = FifthFromLast(one);
	if (fifthFromLast == six)
	{
		cout << " Pass" << endl;
	}
	else
	{
		cout << "!Fail" << endl;
	}
	cout << "Test: with 4 item list - expect NULL" << endl;
	Element* nullReturnCheck = FifthFromLast(seven);
	if (nullReturnCheck == NULL)
	{
		cout << " Pass" << endl;
	}
	else
	{
		cout << "!Fail" << endl;
	}
	cout << "Test: FifthFromLast(NULL) - expect NULL" << endl;
	nullReturnCheck = FifthFromLast(NULL);
	if (nullReturnCheck == NULL)
	{
		cout << " Pass" << endl;
	}
	else
	{
		cout << "!Fail" << endl;
	}
	// clean up
	Element* current = one;
	while (current)
	{
		Element* next = current->next;
		delete current;
		current = next;
	}
}

This is the output from running the tests.

Test: find 5th from last in 10 item list
 Pass
Test: with 4 item list - expect NULL
 Pass
Test: FifthFromLast(NULL) - expect NULL
 Pass


Reverse a linked list – C++ source code

Monday, July 21st, 2008

Reversing a linked list is a simple programming problem, which is often an interview question. In this case I’m referring to a singly linked list. I’ll provide the C++ solution and the C++ test code.

One of the easiest ways to reverse the linked list is to create a new head pointer, iterate through the list removing each item in turn and then inserting them at the beginning of the new list.

Here is the definition of my linked list node and the code to reverse the list.

class Node
{
public:
	Node(int value) : value(value), next(NULL) {}
public:
	int value;
	Node* next;
};
Node* reverseList(Node* head)
{
	Node* newList = NULL;
	Node* current = head;
	while (current)
	{
		Node* next = current->next;
		current->next = newList;
		newList = current;
		current = next;
	}
	return newList;
}

Below is the code I used to test this. This is what it does:

  1. It creates a simple linked list.
  2. Prints it out – output should be ‘12345’.
  3. Reverses it.
  4. Prints it out – output should be ‘54321’.
  5. Reverses it again.
  6. Prints it – output should be ‘12345’.
  7. Deletes the list.
void listTests()
{
	Node* one = new Node(1);
	Node* two = new Node(2);
	Node* three = new Node(3);
	Node* four = new Node(4);
	Node* five = new Node(5);
	one->next = two;
	two->next = three;
	three->next = four;
	four->next = five;
	Node* head = one;
	printList(head);
	head = reverseList(head);
	printList(head);
	head = reverseList(head);
	printList(head);
	// cleanup memory
	Node* current = head;
	while (current)
	{
		Node* next = current->next;
		delete current;
		current = next;
	}
}
void printList(Node* head)
{
	Node* current = head;
	while (current)
	{
		cout << current->value;
		current = current->next;
	}
	cout << endl;
}

This should be the output:

12345
54321
12345

If you are interested in other linked list related code I have a post about picking the 5th from last element from a singly linked list, and one on selecting random numbers from a stream or linked list. Both of these are based on programming interview questions.

Dijkstra’s Algorithm code in C++

Tuesday, July 15th, 2008

Dijkstra’s algorithm is a famous algorithm that calculates the routes and distances from a start node to all other nodes in a connected graph where all the distances are positive.

Here is a version which I wrote in C++. My aim here was to try to create a version that was easy to read, rather than the most efficient version. I used the excellent Introduction to Algorithms book as a reference for my version of Dijkstra’s. This version is implemented using STL vectors to store the edges and nodes. I might later modify it to use adjacency lists and priority queues to produce a more efficient implementation.

First off is my Node and Edge class. You’ll note that the objects add themselves to the nodes and edges vectors as they are constructed.

vector<Node*> nodes;
vector<Edge*> edges;
class Node
{
public:
	Node(char id)
		: id(id), previous(NULL),
		distanceFromStart(INT_MAX)
	{
		nodes.push_back(this);
	}
public:
	char id;
	Node* previous;
	int distanceFromStart;
};
class Edge
{
public:
	Edge(Node* node1, Node* node2, int distance)
		: node1(node1), node2(node2), distance(distance)
	{
		edges.push_back(this);
	}
	bool Connects(Node* node1, Node* node2)
	{
		return (
			(node1 == this->node1 &&
			node2 == this->node2) ||
			(node1 == this->node2 &&
			node2 == this->node1));
	}
public:
	Node* node1;
	Node* node2;
	int distance;
};

Next up is my code to construct a simple test graph. The starting node is initialised with a distance of 0. Dijkstra’s algorithm is then called before the results are printed out. Underneath the code is a diagram of what this graph looks like.

void DijkstrasTest()
{
	Node* a = new Node('a');
	Node* b = new Node('b');
	Node* c = new Node('c');
	Node* d = new Node('d');
	Node* e = new Node('e');
	Node* f = new Node('f');
	Node* g = new Node('g');
	Edge* e1 = new Edge(a, c, 1);
	Edge* e2 = new Edge(a, d, 2);
	Edge* e3 = new Edge(b, c, 2);
	Edge* e4 = new Edge(c, d, 1);
	Edge* e5 = new Edge(b, f, 3);
	Edge* e6 = new Edge(c, e, 3);
	Edge* e7 = new Edge(e, f, 2);
	Edge* e8 = new Edge(d, g, 1);
	Edge* e9 = new Edge(g, f, 1);
	a->distanceFromStart = 0; // set start node
	Dijkstras();
	PrintShortestRouteTo(f);
	// Node / Edge memory cleanup snipped
}

Dijkstra's algorithm

Here is the actual algorithm implementation. We remove the node with the smallest distance from the list of nodes, and then calculate all the minimum distances. We repeat until there are no more nodes left.

void Dijkstras()
{
	while (nodes.size() > 0)
	{
		Node* smallest = ExtractSmallest(nodes);
		vector<Node*>* adjacentNodes =
			AdjacentRemainingNodes(smallest);
		const int size = adjacentNodes->size();
		for (int i=0; i<size; ++i)
		{
			Node* adjacent = adjacentNodes->at(i);
			int distance = Distance(smallest, adjacent) +
				smallest->distanceFromStart;
			if (distance < adjacent->distanceFromStart)
			{
				adjacent->distanceFromStart = distance;
				adjacent->previous = smallest;
			}
		}
		delete adjacentNodes;
	}
}

Here are the supporting functions. The first function removes and returns the node with the smallest distance from the list.

The next returns a new vector containing all the nodes which are adjacent to the node that we pass in.

The third returns the distance value of an edge which directly connects the two nodes.

The final one checks if a node is in the list of nodes.

// Find the node with the smallest distance,
// remove it, and return it.
Node* ExtractSmallest(vector<Node*>& nodes)
{
	int size = nodes.size();
	if (size == 0) return NULL;
	int smallestPosition = 0;
	Node* smallest = nodes.at(0);
	for (int i=1; i<size; ++i)
	{
		Node* current = nodes.at(i);
		if (current->distanceFromStart <
			smallest->distanceFromStart)
		{
			smallest = current;
			smallestPosition = i;
		}
	}
	nodes.erase(nodes.begin() + smallestPosition);
	return smallest;
}
// Return all nodes adjacent to 'node' which are still
// in the 'nodes' collection.
vector<Node*>* AdjacentRemainingNodes(Node* node)
{
	vector<Node*>* adjacentNodes = new vector<Node*>();
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		Node* adjacent = NULL;
		if (edge->node1 == node)
		{
			adjacent = edge->node2;
		}
		else if (edge->node2 == node)
		{
			adjacent = edge->node1;
		}
		if (adjacent && Contains(nodes, adjacent))
		{
			adjacentNodes->push_back(adjacent);
		}
	}
	return adjacentNodes;
}
// Return distance between two connected nodes
int Distance(Node* node1, Node* node2)
{
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		if (edge->Connects(node1, node2))
		{
			return edge->distance;
		}
	}
	return -1; // should never happen
}
// Does the 'nodes' vector contain 'node'
bool Contains(vector<Node*>& nodes, Node* node)
{
	const int size = nodes.size();
	for(int i=0; i<size; ++i)
	{
		if (node == nodes.at(i))
		{
			return true;
		}
	}
	return false;
}

And finally here is the code which prints out the route between our start node ‘a’ and the destination node ‘f’. It starts at the destination node and then works backwards using the previous pointer in each node.

void PrintShortestRouteTo(Node* destination)
{
	Node* previous = destination;
	cout << "Distance from start: "
		<< destination->distanceFromStart << endl;
	while (previous)
	{
		cout << previous->id << " ";
		previous = previous->previous;
	}
	cout << endl;
}

Update: 7th September 2008

I have now uploaded a zip file containing the Visual C++ Express Solution file and source code for this project – Dijkstra’s Source Code (8kb).

Select 100 random values from a stream / linked list

Friday, July 11th, 2008

Here’s an interesting puzzle / interview question that I heard recently.

Problem

You have a either a linked list or a stream containing int values. You don’t know how large the stream / linked list except that it contains 100 or more values. You need to write a method that selects 100 random values from the stream. You have to write the method so that there isn’t a bias towards values at the start, middle or end of the stream / list. In other words the chances of picking a value from anywhere in the stream / list should be roughly the same.

There are some restrictions.
You can’t cache the whole stream (if it is a stream).
Or if it is a linked list – you are only allowed a single pass of the list. You can’t iterate through it once to determine its length.

Solution

The solution is:

  1. Select the first 100 values and store them in an array.
  2. For each value after the first 100 we select them according to a decreasing probability. If we select a value then we replace a randomly selected value from our existing list.

So values 1-100 have a probability of 1 of being initially selected.
Value 101 has a 100/101 chance of being selected.
Value 102 has a 100/102 chance of being selected.
Value 1050 has a 100/1050 chance… etc.

100 is at the top of the division as this is our value for x – the number of values we are selecting.

You can see that value 101 has a very high chance of being selected. 100/101 in fact. As we are replacing one of our existing values, each of the existing values has a 100/101 chance of remaining after the replacement.

Using this simple logic we can get a random sample of the values even though we don’t know the length of the stream / list.

Code

Here is the C++ code showing how to do this. Also included is a simple test which sends the values 1-1 million to the function. 100 are randomly selected.

After the code is a graph which shows the distribution of the selected values. You can see that the distribution is fairly even showing that the code works. For random number selection code such as this, the easiest way to verify that the code works is to manually view the results in a graph and see if the output looks sensible.

const int size = 100;
int selected[size];
int count = 0;
void SelectRandomNumbers(int nextNum)
{
	if (count < size)
	{
		selected[count++] = nextNum;
		return;
	}
	double probability = (double)size / (double)(count+1);
	double select = (double)rand() / RAND_MAX;
	if (select < probability)
	{
		int randomIndex = RandomNumber(0, size);
		selected[randomIndex] = nextNum;
	}
	++count;
}
// min is inclusive
// max is non-inclusive
int RandomNumber(int min, int max)
{
	return (int)((double)rand()	/
		(RAND_MAX + 1) * (max - min) + min);
}
///////////////

const int iterations = 1000000;
void RandomSelectionTest()
{
	srand((unsigned)time(0));
	for (int i=0; i<iterations; ++i)
	{
		SelectRandomNumbers(i);
	}
	cout << size <<	" randomly selected ints:" << endl;
	PrintIntArray(selected, size);
}
void PrintIntArray(int thearray[], int size)
{
	for (int i=0; i<size; ++i)
	{
		cout << thearray[i] << endl;
	}
}

Graph

Here are the results. 1 million numbers were passed in. 100 were selected. You can see that the distribution is fairly even which means that the code is doing the correct thing.

Graph of randomly selected numbers

Friend Quotes – My first Facebook ‘app’

Wednesday, July 9th, 2008

A few weeks ago I finished my first Facebook ‘app’… Well, ‘app’ is too grand a word. All it does it display a random selection of your friend’s quotes on your Facebook profile page.

I wrote it just to see how easy it was to make a very simple Facebook extension. As it turns out it was very easy. Everything you need is on their official website – http://developers.facebook.com/. You’ll need to download their PHP library and put it on your web server.

My ‘app’ displays four randomly selected quotes from your friends (if you have any that is) on your profile.

One thing that I found important is to test the app using accounts other than your own. You are not allowed to create multiple standard accounts on Facebook. However you can create test accounts. To do this you create a standard account and then quickly convert into a test account. Full instruction for how to convert accounts into test accounts are here. Just be careful not to turn your main account into a test account!

To install the app to your profile go to the Facebook Friend Quotes page.

Update February 2011: Friend Quotes will no longer work as the profile.setFBML way of adding content to a Facebook profile has been deprecated.

QuickSort Implementation Code in C++

Wednesday, June 25th, 2008

I was having a look at the QuickSort algorithm (as you do for fun) and was trying to find a tidy looking implementation in C++. I found a lot of implementations out there but most of them looked far more complicated than I thought they should have been.

The QuickSort algorithm as printed in the Introduction to Algorithms book looks relatively simple. I wanted a C++ version that has a QuickSort function and a partition function. Many of the implementations that I’ve seen on the internet have both functions merged into one.

The neatest looking QuickSort code that I found was one this Java version written by a Prof. Dr. H. W. Lang. Compare how short and easy to read this piece of code is to other QuickSort implementations. This is close to what I want but the partition part is rolled into the main QuickSort code.

It also had quite a few differences to the Introduction to Algorithms QuickSort. I used the Prof. Dr. H. W. Lang code as a base, split the partition part out, and then made a few other changes to make the implementation closer to the Introduction to Algorithms version. This is what I ended up with.

int partition(int a[], int left, int right, int pivotIndex)
{
    int pivot = a[pivotIndex];
    do
    {
        while (a[left] < pivot) left++;
        while (a[right] > pivot) right--;
        if (left < right && a[left] != a[right])
        {
            swap(a[left], a[right]);
        }
        else
        {
            return right;
        }
    }
    while (left < right);
    return right;
}
void quicksort(int a[], int left, int right)
{
    if (left < right)
    {
        int pivot = (left + right) / 2; // middle
        int pivotNew = partition(a, left, right, pivot);
        quicksort(a, left, pivotNew - 1);
        quicksort(a, pivotNew + 1, right);
    }
}

I tested this in the free Microsoft Visual C++ Express Edition. Here is what I used to test the QuickSort code.

#include "stdafx.h"
#include <iostream>
using namespace std;
void printArray(int thearray[], int count)
{
    for (int i=0; i<count; ++i)
    {
        cout << thearray[i] << " ";
    }
    cout << endl;
}
void arraySortingTests()
{
// unique unsorted
int numbers1[] = {14, 17, 11, 13, 19, 16, 12, 15, 18, 10};
int numbers2[] = {19, 16, 10, 12, 14, 17, 13, 18, 15, 11};
// already sorted
int numbers3[] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
// reverse sorted
int numbers4[] = {19, 18, 17, 16, 15, 14, 13, 12, 11, 10};
// all duplicates
int numbers5[] = {7, 7, 7, 7, 7};
// 1 pair
int numbers6[] = {14, 17, 11, 13, 19, 16, 12, 15, 18, 14};
// 1 pair at start
int numbers7[] = {14, 14, 17, 11, 13, 19, 16, 12, 15, 18};
// multiple duplicates
int numbers8[] = {14, 14, 14, 13, 13, 13, 13, 12, 12, 12};
int numbers9[] = {12};
int numbers10[] = {12,10};
quicksort(numbers1, 0, 9);
printArray(numbers1, 10);
quicksort(numbers2, 0, 9);
printArray(numbers2, 10);
quicksort(numbers3, 0, 9);
printArray(numbers3, 10);
quicksort(numbers4, 0, 9);
printArray(numbers4, 10);
quicksort(numbers5, 0, 4);
printArray(numbers5, 5);
quicksort(numbers6, 0, 9);
printArray(numbers6, 10);
quicksort(numbers7, 0, 9);
printArray(numbers7, 10);
quicksort(numbers8, 0, 9);
printArray(numbers8, 10);
quicksort(numbers9, 0, 0);
printArray(numbers9, 1);
quicksort(numbers10, 0, 1);
printArray(numbers10, 2);
}
int _tmain(int argc, _TCHAR* argv[])
{
    arraySortingTests();
    return 0;
}

Update: 25/09/2011 as people noticed my original version of the Quick Sort algorithm didn’t work with duplicates. This new version does, and has extra tests cases to verify this. I’ve had to delete the comments which refer to the old version of the code, as they don’t make sense any more! If you spot any problems with this new version of the code, please let me know.
Update: 30/09/2011 Sergiy in the comments below has found a test case that this doesn’t work with :( If anyone can spot the fix please leave a comment.