CODEWITHSUNDEEP
algorithmdata-structuresdefinition
user3785745
user3785745

Reputation:

Definition of non comparison sort?

I'm going through sorting algorithms. Radix sort is stated as an non comparison sort but it compares digits in a number and sorts them. Can some one Please let me know what does non comparison sort actually mean?

Upvotes: 6

Views: 12560

Answers (2)

Landys
Landys

Reputation: 7757

To my understanding, the differences between comparison and non-comparison sort algorithm are not whether there are comparisons in the algorithm, but whether they use the internal character of the items to be sorted.

A comparison sort algorithm sorts items by comparing values between each other. It can be applied to any sorting cases. And the best complexity is O(n*log(n)) which can be proved mathematically.

A non-comparison sort algorithm uses the internal character of the values to be sorted. It can only be applied to some particular cases, and requires particular values. And the best complexity is probably better depending on cases, such as O(n).

All sorting problem that can be sorted with non-comparison sort algorithm can be sorted with comparison sort algorithm, but not vice versa.

For Radix sort, it benefits from that the sorted items are numbers that can be reduced to digits. It cares about what the sorted items are. While the comparison sort algorithm only needs an order of items.

Upvotes: 9

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

A comparison sort algorithm compares pairs of the items being sorted and the output of each comparison is binary(i.e. smaller than or not smaller than). Radix sort considers the digits of the numbers in sequence and instead of comparing them, groups numbers in buckets with respect to the value of the digit(in a stable manner). Note that the digit is not compared to anything - it is simply put in a bucket corresponding to its value.

It is important to know why we care about comparison/non-comparison sort algorithms. If we use a comparison sort algorithm then on each comparison we will split the set of possible outcomes roughly in half(because the output is binary) thus the best complexity we can possibly have is O(log(n!)) = O(n*log(n)). This restriction does not hold for non-comparison sorts.

Upvotes: 6

Related Questions