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.