Definition of sorting without comparison?

I am using sorting algorithms. The Radix sort is indicated as a sort without comparison, but it compares the digits in the number and sorts them. Could someone please let me know what comparison without comparison really means?


source to share

2 answers

As far as I understand, the differences between the compare and compare algorithm are not compared to whether comparisons exist in the algorithm , but whether they use the internal symbol of the sorted elements .. p>

The sorting sorting algorithm sorts the items by comparing the values ​​with each other. It can be applied to any sort of sort. And the best difficulty O(n*log(n))

that can be mathematically proven.

The no-comparison sorting algorithm uses the intrinsic nature of the values ​​being sorted. It can only be applied to some specific cases and requires specific values. And the best complexity is probably better depending on cases like O(n)


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

For Radix sort, this means that the sorted items are numbers, which can be reduced to numbers. It takes care of what the sorted items are. Although the comparison sorting algorithm only needs the order of the elements.



The comparison sorting algorithm compares pairs of sorted elements, and the result of each comparison is binary (i.e. smaller than

or not smaller than

). Radix sort takes the digits of the numbers in sequence into account and, instead of comparing them, groups the numbers in buckets in relation to the digit value (in a stable manner). Note that the digit is not compared to anything - it is simply placed in the bucket corresponding to its value.

It is important to know why we care about comparison / no-compare algorithms. If we use a comparison sorting algorithm, then with each comparison we will split the set of possible outcomes by about half (because the output is binary ), so the best complexity we can have is O(log(n!)) = O(n*log(n))

. This limitation is not met for non-comparison.



All Articles