Difference between Comparison (QuickSort) and Non-Comparison (Counting Sort) based Sorting Algorithms?

For many of you, this might be a surprise that how you can sort or arrange items without comparing with each other, but it's possible. There are some sorting algorithms that perform sorting without comparing the elements rather by making certain assumption about the data they are going to sort. The process is known as non-comparison sorting and algorithms are known as the non-comparison based sorting algorithms. No comparison sorting includes Counting sort which sorts using key value, Radix sort, which examines individual bits of keys, and Bucket Sort which examines bits of keys. These are also known as Liner sorting algorithms because they sort in O(n) time. They make certain assumption about data hence they don't need to go through comparison decision tree.


So, based upon how they work, you can broadly classify the sorting algorithms into two categories, comparison based e.g. QuickSort or MergeSort, and non-comparison based e.g. Counting sort or Radix Sort. As the name suggest, the fundamental difference between a comparison based and a non-comparison based sorting algorithm is the comparison decision.

In the first type, a comparator is required to compare numbers or items. Basically, this comparator defines the ordering e.g. numerical order, lexicographical order, also known as dictionary order to arrange elements. On the other hand, non-comparison based sorting algorithms don't use comparison but rely on integer arithmetic on keys.



Why Non-Comparison based Algorithms?

Some of you might be thinking why do we need non-comparison based algorithms at all, isn't comparison based sorting algorithms is enough? Well, if you look at the performance of comparison based sorting algorithm, you will realize that Bubble sort, Selection Sort, and Insertion sort takes around O(n^2) time to sort n items.

While, heap sort, quick sort, and merge sort takes O(NlogN) time in the best case and around O(n^2) in the worst case. Can we do better than O(NlogN) using sorting algorithm? can we sort items in O(n) time using these sorting algorithms? Well, the answer is No.

It can be proven that any comparison-based sorting algorithm will take at least O(NlogN) operations to sort n elements, hence you need a non-comparison based sorting algorithm which allows you to sort elements in linear time.

The linear sorting algorithms are also one of the popular data structure and algorithm questions in recent times, so you better know about it.





Comparison based Sorting vs NonComparison based Sorting

Due to the working difference between these two types of algorithms, generally, the non-comparison based sorting algorithms like Radix Sort, Counting Sort, and Bucket Sort are faster than QuickSort, Merge Sort and Heap Sort. Let's see a couple of more differences between these sorting algorithms to understand better.

The latter type is also known as Integer sort because it relies on integer arithmetic for sorting rather than comparison.


Speed
One of the most critical differences between these two sorting algorithms is speed. Non-comparison sorting is usually faster than sorting because of not doing the comparison. The limit of speed for comparison-based sorting algorithm is O(NlogN) while for non-comparison based algorithms its O(n) i.e. linear time.


Comparator
Comparison based sorting algorithm e.g. QuickSort, Merge Sort. or Heap Sort requires a Comparator to sort elements e.g. while sorting an array of String, but non-comparison based sorting algorithms doesn't require any comparator.


Usage
Non-Comparison based sorting algorithm can use to sort any object provided it provides Comparator to define ordering, but a non-comparison based sorting algorithm can not be used to sort anything other than integers, that's why the are also known as integer sorting. You can also see Introduction of Algorithms to learn more about the O(n) sorting algorithms.

Difference between Comparison (QuickSort) and Non-Comparison (Counting Sort) based Sorting Algorithms?



Examples
The QuickSort, Merge Sort, Heap Sort, Selection Sort, Bubble Sort and Insertion Sort, while some popular example of non-comparison based sorting is Radix Sort, Counting Sort, Bucket Sort etc


Memory Complexity
The best case for memory complexity with the comparison based sorting is O(1) because it's possible to sort an array of numbers in place i.e. without using any additional memory. You can see the code for in place Quicksort algorithm here. On the other hand, memory complexity for non-comparison based sorting algorithm is always O(n).


CPU complexity
The lower bound of CPU complexity or how much time it take for the algorithm to sort N numbers in the worst case is O(NlogN), but in the case of non-comparison based sorting the CPU complexity lower bound is O(n) i.e. the worst case is even worse with non-comparison based sorting algorithms.

Here is a nice animation of some of the popular comparison-based sorting algorithms:

Difference between Comparison and Non-Comparisonbased Sorting Algorithms?



That's all about the difference between comparison and non-comparison based sorting algorithms. Most of the common sorting algorithms fall into the category of comparison based sorting algorithms e.g. quicksort, mergesort etc and those are the more likely you will use in the real world, but specialized non-comparison algorithms e.g. counting sort and bucket sort can be very useful if the set of input meet the pre-conditions required. You can further read, Introduction to Algorithms by Thomas H. Cormen to learn more about non-comparison based sorting algorithms e.g. bucket sort.



4 comments :

ManInBlue said...

Good read. Nicely articulated details. Thanks

thanumoorthy said...

Thank you for this Post :)

pawan patidar said...

Usage
Non-Comparison based sorting algorithm can use to sort any object provided it provides Comparator to define ordering.

Please Correct, it should be:
Comparison based sorting algorithm can use to sort any object provided it provides Comparator to define ordering.

pawan patidar said...





Non-Comparison based sorting algorithm can use to sort any object provided it provides Comparator to define ordering, but a non-comparison based sorting algorithm can not be used to sort anything other than integers, that's why the are also known as integer sorting

Under Usage: Both is non-Comparison, later should be Comparison only.

Post a Comment