QuickSort

The next algorithm the course required us to implement is QuickSort. QuickSort is quite a well known algorithm and, theoretically speaking, it performs as good as Merge Sort ( O(n log n) time ). In practice however, it usually comes out faster. Choosing the pivot well is essential to a good running time.
Here is my implementation, with the pivot choosing subroutine left out:

	template<typename T>
	void quickSort(std::vector<T>& nums)
	{
	_qSort(nums, 0, nums.size());
	}
	template<typename T>
	void _qSort(std::vector<T>& nums, int begin, int end)
	{
	if(end - begin < 2)
	return;
	int pivot = choosePivot(nums, begin, end);
	swap(nums[begin], nums[pivot]);
	pivot = begin;
	int i = begin + 1;
	for(int j = begin + 1; j < end; j++)
	{
	if(nums[j] < nums[pivot])
	{
	swap(nums[i], nums[j]);
	i++;
	}
	}
	swap(nums[pivot], nums[i-1]);
	_qSort(nums, begin, i-1);
	_qSort(nums, i, end);
	}

view raw quicksort.cpp hosted with ❤ by GitHub

In my next post I will show how we can choose a good pivot and how much it matters.

Selection Sort

I decided to throw another sorting algorithm into the mix: Selection Sort.
In theory, this one should be the worst of all.
In practice, it turned out a little bit different:


Create a graph
This was my implementation:

	template<typename T>
	void selectionSort(std::vector<T>& nums)
	{
	for(int i = 0; i < nums.size(); i++)
	{
	int smallest = i;
	for(int j = i+1; j < nums.size(); j++)
	{
	if(nums[j] < nums[smallest])
	smallest = j;
	}
	swap(nums[i], nums[smallest]);
	}
	}

view raw selectionsort.cpp hosted with ❤ by GitHub

When we analyze these algorithms mathematically, we can conclude that:

• Merge Sort runs in O(n log n) time.
• Both selection and insertion sort run in O(n²) time.

As you can see, this makes a huge difference when amount of data increases.

Insertion Sort

In order to understand just how important a good sorting algorithm is, I quickly whipped up an Insertion Sort:

	template<typename T>
	void insertionSort(std::vector<T>& nums)
	{
	for(int i = 0; i < nums.size(); i++)
	{
	int pos = i;
	for(int j = i-1; j >= 0; j--)
	{
	if(nums[j] > nums[pos])
	{
	swap(nums[j], nums[pos]);
	pos = j;
	}
	else
	break;
	}
	}
	}

view raw insertionsort.cpp hosted with ❤ by GitHub

I applied both of them on a list of 100,000 numbers. This was the result, in seconds:
Graphing

Merge Sort

The first programming challenge the course over at Coursera provided us with was to implement an algortihm for counting the inverions in an array. As it turns out, this can be achieved by applying a minor modification in the Merge Sort algorithm. I implemented it both in C++ and Python.
Python version

	def mergeSort(nums):
	if len(nums) < 2:
	return nums[:]
	a = nums[ 0 : len(nums)/2 ]
	b = nums[ len(nums)/2 : ]
	a = mergeSort(a)
	b = mergeSort(b)
	result = []
	i = 0
	j = 0
	for k in range(len(nums)):
	if i >= len(a):
	result.append(b[j])
	j += 1
	elif j >= len(b):
	result.append(a[i])
	i += 1
	else:
	if a[i] <= b[j]:
	result.append(a[i])
	i += 1
	else:
	result.append(b[j])
	j += 1
	return result

view raw mergesort.py hosted with ❤ by GitHub

C++ version

	template<typename T>
	std::vector<T> mergeSort(const std::vector<T>& nums)
	{
	if(nums.size() < 2)
	return nums;
	std::vector<T> a, b;
	a.assign(nums.begin(), nums.end() - nums.size()/2);
	b.assign(nums.end() - nums.size()/2, nums.end());
	a = mergeSort(a);
	b = mergeSort(b);
	std::vector<T> result;
	result.reserve(nums.size());
	for(int k = 0, j = 0, i = 0; k < nums.size(); k++)
	{
	if(i >= a.size())
	result.push_back(b[j++]);
	else if(j >= b.size())
	result.push_back(a[i++]);
	else
	{
	if(b[j] < a[i])
	result.push_back(b[j++]);
	else
	result.push_back(a[i++]);
	}
	}
	return result;
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

I'll leave the method to calculate the inversions as an exercise for the reader, it's really not that difficult.

Coursera

The finals are finally over! I'm so happy I can get back to work on my projects. As I mentioned in my last post I'll be revealing my latest project soon, on this blog. I'm also taking up a free course offered by Stanford University on Coursera. the "Design and Analysis of Algorithms" course will undoubtedly sharpen my skills regarding algorithms and will make me a better programmer in general. You can still sign up now!