Re: Sorting algorithm when comparison is heavy

thomas.mertes@xxxxxx writes:

On 10 Apr., 06:35, Juha Nieminen <nos...@xxxxxxxxxxxxxx> 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)?

The first idea that I have:
I would consider some good sort algorithm like quicksort together
with some caching for comparisons. If the elements are referred
with a pointer I would use a hash map with two pointers as key.
<snip>
What remains open is: Does a sorting algorithm like quicksort
really profit from such a caching.

It would surprise me if it did in general. The are O(n^2) possible
pairs, so even an algorithm that is O(n^2) in comparisons might never
compare the same pair twice. The exact number of pairs is n(n-1)/2
and this is the maximum done by insertion sort (I think). Bubble sort
does more, but who'd use that in the situation?

I suspect that all "good" sorts (those that are O(n.log(n)) will not
duplicate comparisons. I can't see how they could be O(n.log(n))
unless they avoided doing so.

You suggest using pointers, so I think the above applies. Of course,
you could have suggested using the values themselves. In that case,
if there are lots duplicate values, then you could win by caching the
results.

[In the OP's example (players in a tournament) all the values --
people -- are distinct, so there would be no gain there.]

--
Ben.
.

Relevant Pages

  • Re: attempt at qsort implementation
    ... qsortis not required to implement any particular sort algorithm. ... It's just supposed to sort. ... out of order by sorting them and returning the first one. ... A recursive bogosort uses bogosort to sort the possible orders by ...
    (comp.lang.c)
  • Re: sort on more than one key?
    ... I can sort on one key no problem.But what ... > sorting on more than one key, for example by last name then by first name. ... unstable) and in the compare function code the following for any pair ... key using a stable algorithm such as a nice "bubble" sort ...
    (comp.programming)
  • Re: lottery number thing problem
    ... Chris Theis wrote: ... (look for random_shuffle and sort). ... If you want to do the actual sorting yourself you will need a sorting ... algorithm. ...
    (comp.lang.cpp)
  • Re: lottery number thing problem
    ... Chris Theis wrote: ... (look for random_shuffle and sort). ... If you want to do the actual sorting yourself you will need a sorting ... algorithm. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Whats the position of pointers
    ... people to write a program to sort some data, where the intent is for them ... understand the *importance* of pointers (remember it is the importance ... he will come up with an algorithm which probably can be any of the ... algorithm with complexity Osuch as merge sort, ...
    (comp.lang.c)