Re: Sorting algorithm when comparison is heavy

Ben Bacarisse wrote:

.... snip ...

What has that got to do with sorting expensive to compare items?
Yes, this method can be used to sort things like numbers, but
these are not the kind of items under discussion. The OP is
asking about sorting things with very expensive compare operations.
If the objects can be cheaply mapped to buckets in any way that
preserves the required ordering, then the object have a cheap
compare operation (just map to bucket number first).

I have five items A, B, C, D and E. I will, if needed, answer
any ordering question about them by email (i.e. if you ask me if
A <= C I will reply yes or no). Obviously this takes some time,
so speed things up by using your method to sort them in, as you
say, O(N) time using no compare operations (i.e. without mailing
me).

FYI here is the original query.

Juha Nieminen wrote:
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)?

Your sorting problem can be solved as long as you have access to
the items. One, that I mentioned earlier, is of handling just a
single digit of the (possibly) long value. We can start with the
least significant digit, (lets say the digits are 0 through 9) and
dump everything into 10 piles, based on that digit. Now we collect
all the results in order of digits, and repeat, using the next
(more significant) digit. This is not dependent on the length of
the value (although the sorting time is) and results in a fully
sorted pile after handling the most significant digit. Changing
the count of digits just changes the count of piles.

It is not really practical today, with effectively endless memory
available. But it handled cards quite efficiently. Going back to
the original problem, someone proposed mergesort, which doesn't
really reduce the comparisons, but is especially efficient because
it can easily handle singly linked lists.

The more significant methods deal with things that are just too
large to fit in memory. Wirth has a very instructive system in
"Data Structures + Algorithms = Programs".

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

** Posted from http://www.teranews.com **
.

Relevant Pages

  • Re: Sorting algorithm when comparison is heavy
    ... asking about sorting things with very expensive compare operations. ... so speed things up by using your method to sort them in, ... single digit of the long value. ...
    (comp.programming)
  • Re: Well Ordering the Reals
    ... > But if one has infinitely many digit positions between two ... If the string between them is defined, either with a bit pattern or as ... With one point you can define a finite neighborhood. ... The only places he CAN compare bit patterns are at ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... >>> points and into the neighbor hood of another. ... > If TO is to have only finitely many digit positions between two of his ... If the string between them is defined, either with a bit pattern or as equal to ... The only places he CAN compare bit patterns are at ...
    (sci.math)
  • Re: Sorting algorithm when comparison is heavy
    ... optimal way of sorting such elements (in other words, ... What has that got to do with sorting expensive to compare items? ... cheaply mapped to buckets in any way that preserves the required ... using no compare operations. ...
    (comp.programming)
  • Re: Relative Cardinality
    ... There are other ways to compare apart from comparing ... >> digit by digit. ... > taken all particles in the universe to construct our big number so ... 3-dimensional, physical universe, it _can_ look at the number. ...
    (sci.math)