25

Imagine a case where comparison of two elements is hugely expensive.

Which sorting algorithm would you use?

Which sorting algorithm uses the fewest comparisons in the average case?

What if you can expect a lot of the compared elements to be identical, say in 80% of the comparisons. Does it make a difference?

Improve this question
3

7 Answers 7

Reset to default
17

Merge-insertion sort, a variant of insertion sort, was touted as the sorting algorithm with the fewest known comparisons for several decades, and is perhaps still the best freely-documented sorting algorithm for minimal comparisons:

Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for n items whenever n ≤ 15 or 20 ≤ n ≤ 22, and it has the fewest comparisons known for n ≤ 46.

Glenn K. Manacher's algorithm “and later record-breaking sorting algorithms” (none of which, unfortunately, seem to be freely documented at this time) are reported to adapt the merge-insertion sort algorithm to offer even fewer comparisons.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

12

The winner is Sleep Sort, which uses no comparisons.

Improve this answer

10 Comments

After going through the link I find the algorithm is sleepy in literal sense. Because the algo has to wait for at least the time=largest_value, while rest of the sort algoes would be complete with sorting way before. But when the question is solely around minimizing the no. of comparison then this algo rocks!! :)
Funny idea :) Although it assumes that converting the sort key to integer is easy.
I think the claim "no comparisons" is too strong and thus wrong - there must be at least n compares when iterating the elements (assuming the length of the array is unknown at compile time). Also: is sleep(time) a machine instruction? I believe the underlying OS will need some comparisons to implement it, though I am not certain of it (will be glad for clarification regarding it). (p.s. not the downvoter, still nice work around IMO)
@amit: when we talk about comparisons in a sorting algorithm we are generally talking about comparisons of element values, and by this criterion Sleep Sort uses no comparisons. (sleep() is just an implementation detail - it could easily be implemented as a hardware timer interrupt.) Sleep Sort is not meant to be taken too seriously though - it's just a novelty - an amusing and interesting example of "outside the box" thinking.
Interesting idea. However sorting only requires a comparison function between two elements: there is no requirement that you might be able to convert individual elements to a duration. For instance we can ask people to sort items by preference without asking them to give an explicit rating for each item. We don't even need to assume such a rating exists. In the event the comparison function is implemented is such a way that it converts two elements to integers and returns according to their natural order, then sleepsort would require n such conversions, which is equivalent to N/2 comparisons.
|
1

Quite Possibly Insertion Sort

Sorting is one of those subjects where, as they say, the devil is in the details. Typically, secondary considerations dominate the performance input parameters.

However, if comparisons are very expensive and if most keys are identical, it is possible that the input could be considered already sorted or already almost sorted.

In that case, what you want is a reasonable algorithm that has the fastest best case, and that would almost certainly be an insertion sort.

Improve this answer

2 Comments

Why would you want to find an algorithm with the fastest best case (instead of an algorithm with the fastest average case)?
-1 This is a reasonable intuition, but it doesn't pan out in practice. Even for nearly-sorted lists, merge sort is way better than insertion sort for number of comparisons (see e.g. these experimental results) just because of how quickly n^2 vs. n log n catches up with you.
1

It's depends what data do you have. You need stable algorithm or not?

Where your data are uniformly you can use bucket sort ( Θ(n), O(n^2))

counting sort (I think it's what you are looking for), it's also stable algorithm, but need more memory (less is you have a lot of identical records).

Of course you can use Sleep sort, but if you have a lot of data it won't works.

If your elements are in 80% identical maybe there is a simple way to said there are identical (just the same)?

Improve this answer

Comments

0

Shellsort uses less comparisons.

And you have lot of identical elements, Counting sort should do the job

Improve this answer

Comments

0

maybe a non-comparative algorithm like radix sort might be the answer, because it s also fast in general case(takes time O(n)). also makes no comparisons between the elements but on the other hand it requires a lot of memory

Improve this answer

Comments

-1

Distribution sort (using a hashing array) takes almost no comparisons.

m = max number  may appear in the input + 1
hash = array of size m
initialize hash by zeroes

for i = 0 to n - 1
    hash[input[i]] = hash[input[i]] + 1
j = 0
for i = 0 to m - 1
    while hash[i] > 0
        sorted[j] = i
        j = j + 1
        hash[i] = hash[i] - 1
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.