Wednesday, August 4, 2010

Comparison sort and Integer sorts

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey two of the properties of a total order:
  1. if ab and bc then ac (transitivity)
  2. for all a and b, either ab or ba (totalness or trichotomy).
Some of the most well-known comparison sorts include:

Note that comparison based sorting algorithm don't take assumptions on data types, but only on the comparison operator.

Note - But the non-comparison sort algorithms, take dependency on type of data.

Non comparison sort or Integer Sort

Integer sorting is the algorithmic problem of sorting a collection of data values by numeric keys, each of which is an integer. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are. There are many integer sorting algorithms that are not comparison sorts; they include:
  • Radix sort (works on data which is integer, and it works at the binary level) 
  • Counting sort (works on data when it is integer and integer are small) 
  • Bucket sort (works on distributional assumption on data) 


Time complexity : 
Comparison based sorting has worst case running time of Ω (n log n).

But, if you make assumption on data i.e. use integer sorting technique, then you can use integer sort or non-comparison sort, as it reduces the time complexity to O(n) time.

0 comments:

Post a Comment