Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #27527

Re: A riddle with QSORT

Show all headers | View raw

mhx@iae.nl writes:
>On Monday, December 30, 2013 12:48:14 PM UTC+1, Albert van der Horst wrote:
>> I'm sorting an array of 10 million and it takes 87 sec with qsort.
>> [..]
>> The running time goes down to 57 secs.
>[..]
>> How come?
>[..]
>> (I know the answer, hence riddle.)
>
>The logical thing is to suspect that your array contains many duplicates? 

It's a bad implementation of quicksort if duplicates slow it down; in
a decent implementation duplicates produce a speedup.

My first guess would be cache effects, and given that there is not
enough code shown to make any sense of it (including the claim that
the second N< makes the sort stable), I won't make a second guess.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

A riddle with QSORT albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-30 11:48 +0000
  Re: A riddle with QSORT mhx@iae.nl - 2013-12-30 06:00 -0800
    Re: A riddle with QSORT anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-30 15:55 +0000
  Re: A riddle with QSORT Pablo Hugo Reda <pabloreda@gmail.com> - 2013-12-30 12:24 -0800
  Re: A riddle with QSORT "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> - 2013-12-30 19:29 -0500

csiph-web