Home > Overview, Sorting > Sorting Algorithms (Overview)

Sorting Algorithms (Overview)

“Bah! This is what you give to us as your first useful post?”, might be what is running through your mind right now. Well, the answer is, yes. Sorting algorithms are one of the most used class of algorithms in every sort of application that you use. While these might be taught well at the graduate level, their applications are not so well explained. Students don’t realize the different kinds of problems that can be solved utilizing such algorithms.

So let me first name the algorithms which are used for sorting and give a short overview for each. In the subsequent posts, I’ll go on to show the applications (the usual suspects, and some new ones) of the sorting algorithms. But you just have to know the following methods for any interviews/development process.

1. Bubble Sort – With a time complexity of O(n^2), this is the one of the worst algorithms you can use to sort your data. If you plan to use this ever, you aren’t fit to be on this website. The noobs can look up the algorithm and understand it here on this wiki link.

2. Exchange/Selection Sort – The complexity is O(n^2) once again and what is said for bubble sort is true for this as well. Once again, for noobs, the wiki link is here. Both this and Bubble sort can be fine tuned a bit, but not to much use.

3. Insertion Sort – This algorithm can fall in the same category as the previous two if implemented in the way explained at the start here. However, things can get interesting if this kind of sort is performed on a linked list while creating it. But again, such a method will also prove efficient only for small data sets.

4. Merge Sort – Hmm. O(n lg n) time complexity. Now we come to interesting things. Here, what we do is to separate the data set into smaller fragments till we are left with all segments of size one. Once this has been done, we start merging each of these fragments in a way such that each of the merged fragments is now sorted. This is known as the Divide-And-Conquer method. Since I expect readers to know how to implement all of these sorting algorithms, the ones not knowing the exact working of the algorithm can again refer to the wiki link here.

5. Heap Sort – Oh isn’t this just cool! It has a time complexity of O(n lg n) as well. So what we do in heap sort is that we form a heap of all the elements (max or min heap depending on what you want) and remove the root from the heap and re-heap it once again. So what you might be wondering is, what exactly is a heap?! Quite simply put, it is a binary tree with a certain property that every parent is the tree is either greater (in max heap) or lesser (in min heap) than both its children. Also, each new element is added in a balanced manner before the tree is re-heaped. You know what, I’ll give you a great powerpoint slide from my professor which explains Heap Sort very well. Here you go. Heap Sort (The great part is when you realize a heap can be easily implemented using an array itself. Remember doing that with binary trees?! 🙂 )

6. Quick Sort – With time complexity of O(n lg n), this type of sort is another example of the Divide-And-Conquer method that we talked about earlier. The reader might want to note that such a method (DAC) always uses recursion as its modus operandi. In this particular method, an element is selected as the pivot (generally, the last element. But variations exist) and this pivot is put in its right place. This ensures that the data-set is now divided into 2 parts (except in the worst case,i.e., data-set already sorted in some order). Now the same technique is applied to the two parts. And so on. Again, here is an awesome powerpoint slide to make you understand. Quicksort

7. Counting Sort – This is a sort based on the concept of counting how many times a number occurs. It can only be applied when you know the elements which can be present in your data-set. With a time complexity of O(n), this adds a space complexity of the order of the number of possible elements in the data-set. The sort is easily understandable and the concept of counting is better used at other places as will be explained soon in an applied post. 🙂 Noobs – refer the wiki link here for details.

Hah! So we come to the end of an overview of the sorting algorithms. As mentioned in the introductory post, I will dedicate more time on this blog on tackling application problems rather than explaining such simple algorithms in painful detail. That, you can find anywhere on the internet. So hopefully this will be a recap enough for you to understand the application questions of sorting algorithms in the next few posts.

PS: I skipped 2 ubercool algorithms : Bucket and Radix. I feel these will better be explained with an application and will follow up on these in later posts. 🙂

 

Advertisements
Categories: Overview, Sorting Tags: ,
  1. January 26, 2014 at 11:39 pm

    Here is complete description of Heap Sort Algorithm with example and screenshots
    http://geeksprogrammings.blogspot.in/2013/08/explain-heapsort-with-example.html

  1. No trackbacks yet.

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

%d bloggers like this: