My thoughts on sort algorithms

I think it is a great idea for programmers of all levels to have a basic idea how sort algorithms work, just not for the reasons you might think.

Sorting data is a fairly common programming task, however higher level programming languages for the most part take care of sorting. I have yet to work with a higher level programming language where I could do a better job at sorting than the method implemented by the framework.

There is a reason for this, we’ve been using computers since 1835, and modern systems for over half a century, and we’ve become ridiculously proficient in the area of sorting algorithms.

What I like about sorting algorithms is that efficiency is easy to quantify. Without too much difficulty you can write methods than can determine how well your algorithm will perform on different datasets both in volume and type.

Modern high level programming languages take advantage of scientific achievement and implement (in theory) the best possible sorting algorithms we know to date.

To prove this point I coded up a bubble sort, a selection sort and an insertion sort. I will still get around to manually writing the quick sort.

I called these sort methods on an array of 100k (rnd*1000000) – Bubble sort natually the slowest could sort in 46 seconds. The selection performed much better at 16 seconds. The insertion better still at roughly 13 seconds. However the built in Array.Sort (which uses quick sort) pulled this off at a whopping 0.04 seconds!

How can you honestly hope to compete with that? If you have performance issues with such a sort then perhaps you shouldn’t be using a high level language in the first place?

Implementing built in sorting also to some degree always the sort to improve potentially as newer versions of the higher level language are released without making any code changes or monitoring scientific breakthroughs in sorting algorithms. Because like everything what we have now will be improved on as our datasets get larger and more varied.

So given all of this why would I still advocate learning sorting algorithms.

1. For ad hoc tasks where you absolutely cannot implement a built in sort.
2. To learn the methodologies and apply them to other problems that might not seem initially related.
3. To give you general knowledge on IO vs comparisons in loops.
4. To further improve your reductionism capabilities when dealing with performance issues.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s