Re: Sorting algorithm when comparison is heavy

Bartc wrote:
"Juha Nieminen" <nospam@xxxxxxxxxxxxxx> wrote in message
news:47fd9992$0$8159$4f793bc4@xxxxxxxxxxxxxx
1) Assume that comparing elements is an extremely heavy operation,
while copying/swapping them is very light. What would be the most
optimal way of sorting such elements (in other words, a sorting
algorithms which uses the absolute minimum of comparisons)?

I have no idea about algorithms at all. Neither do I have Knuth's work!

So perhaps I would just try half-a-dozen sorts on typical data and measure
the number of comparisons on each. And choose the one with the smallest
number. Except there are likely to be overlaps depending on your data.

Why is comparing items heavy? Maybe that can be looked at.

My question was theoretical and asked out of curiosity. I do not have
currently an actual problem requiring this solution.

2) Like 1, but assume that we can divide the entire set of elements to
be sorted into pairs, and all these pairs can be compared in parallel
(all comparisons take the same amount of time, and thus performing all
the comparisons in parallel takes the same amount of time as making one
comparison).

This is not a real task, is it?

But it could be. Imagine, for example, a chess tournament where you
want to completely sort the players by their strength (we can assume
they always compare in the same way against each other). The comparison
between any two players is an extremely heavy operation (could take
hours), but all the other necessary operations are very light in
comparison. Also, if we divide the players into pairs, all of them can
be compared simultaneously (iow. we divide the tournament into rounds).

My guess is that log2(n) rounds are needed for a full sorting.
However, I can't prove this, nor can I think of a reliable algorithm to
minimize the number of rounds (and comparisons) required.
.

Relevant Pages

  • Re: Sorting algorithm when comparison is heavy
    ... want to completely sort the players by their strength (we can assume ... My guess is that log2rounds are needed for a full sorting. ... Check for big-O notation in any book on analysis of algorithms. ... round1 A defeats B C defeats D ...
    (comp.programming)
  • Re: Sorting algorithm when comparison is heavy
    ... optimal way of sorting such elements (in other words, ... algorithms which uses the absolute minimum of comparisons)? ... we divide the tournament into rounds). ... As you would find from Knuth's book, there is no sort method that will ...
    (comp.programming)
  • Re: Sorting algorithm when comparison is heavy
    ... optimal way of sorting such elements (in other words, ... I have no idea about algorithms at all. ... want to completely sort the players by their strength (we can assume ... As I understand sorting, if you have three things to sort, then you sort on ...
    (comp.programming)
  • Re: Sorting algorithm when comparison is heavy
    ... optimal way of sorting such elements (in other words, ... I have no idea about algorithms at all. ... want to completely sort the players by their strength (we can assume ... As I understand sorting, if you have three things to sort, then you sort on ...
    (comp.programming)
  • Re: Sorting algorithm when comparison is heavy
    ... optimal way of sorting such elements (in other words, ... algorithms which uses the absolute minimum of comparisons)? ... we divide the tournament into rounds). ... As you would find from Knuth's book, there is no sort method that will ...
    (comp.programming)