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:
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:
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.
- if a ≤ b and b ≤ c then a ≤ c (transitivity)
- for all a and b, either a ≤ b or b ≤ a (totalness or trichotomy).
- Quick sort
- Heap sort
- Merge sort
- Intro sort
- Insertion sort
- Selection sort
- Bubble sort
- Odd-even sort
- Cocktail sort
- Cycle sort
- Merge insertion (Ford-Johnson) sort
- Smoothsort
- Timsort
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