Sorting algorithm when comparison is heavy
in [General Programming]
|
Prev: Wholesale ESQ-Terazza-Ladies-Watch-07100648 Cheapest
Next: Wholesale Replica Corum Watches - Fake Corum Watch
From: Juha Nieminen on 10 Apr 2008 00:35 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)? 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).
From: Richard Harter on 10 Apr 2008 01:41 On Thu, 10 Apr 2008 07:35:28 +0300, Juha Nieminen <nospam(a)thanks.invalid> 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)? > > 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). If you really want to dig into this sort of thing you should read Knuth's volume III on sorting. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: Juha Nieminen on 10 Apr 2008 03:30 Richard Harter wrote: > If you really want to dig into this sort of thing you should read > Knuth's volume III on sorting. If I had such a book I wouldn't be asking here, would I?
From: Ian Collins on 10 Apr 2008 04:06 Juha Nieminen wrote: > Richard Harter wrote: >> If you really want to dig into this sort of thing you should read >> Knuth's volume III on sorting. > > If I had such a book I wouldn't be asking here, would I? I think the point was the subject is non-trivial, too involved for a simple Usenet post! -- Ian Collins.
From: Bartc on 10 Apr 2008 04:31
"Juha Nieminen" <nospam(a)thanks.invalid> wrote in message news:47fd9992$0$8159$4f793bc4(a)news.tdc.fi... > 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. > > 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? -- Bart |