• Michiel (3/3) Feb 05 2007 When I use array.sort, which sorting algorithm does D use? Can the progr...
• Jarrett Billingsley (7/11) Feb 05 2007 DMD at least uses quicksort. You can find the actual source for it in
• Bill Baxter (5/21) Feb 05 2007 I thought it used a quicksort with insertion sort for the smallest array...
• Jarrett Billingsley (9/12) Feb 05 2007 There's apparently some licensing issues with qsort.d? I'm not entirely...
• Bill Baxter (9/25) Feb 05 2007 Yeh, I can believe that. qsort2 calls the TypeInfo.compare method to do...
• Lionello Lunesu (4/6) Feb 07 2007 make -fwin32.mak
• Jarrett Billingsley (5/11) Feb 07 2007 I always get all kinds of errors.. unless it's changed since 0.170 or s...
• Lionello Lunesu (5/19) Feb 08 2007 It has changed, in fact. I've posted the issues a while back in bugzilla...
• Jarrett Billingsley (3/6) Feb 08 2007 Oh, well cool then :)
• Oskar Linde (26/28) Feb 06 2007 Just write a library replacement[1]. The only difference is that it will...
• Sean Kelly (8/23) Feb 06 2007 For what it's worth, Tango contains a sort routine in tango.core.Array.

Michiel <nomail hotmail.com> writes:

When I use array.sort, which sorting algorithm does D use? Can the programmer
overwrite the implementation of this function?

Thanks!

"Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:

"Michiel" <nomail hotmail.com> wrote in message 
news:eq8bim$2gou$1 digitaldaemon.com...
 When I use array.sort, which sorting algorithm does D use? Can the 
 programmer
 overwrite the implementation of this function?

 Thanks!

DMD at least uses quicksort.  You can find the actual source for it in 
/dmd/src/phobos/internal/qsort2.d.  You can see that it just calls the C 
stdlib qsort() function.

If you want to use a different algorithm, you'd have to change this file and 
recompile phobos.  A daunting task.. 

Bill Baxter <dnewsgroup billbaxter.com> writes:

Jarrett Billingsley wrote:
 "Michiel" <nomail hotmail.com> wrote in message 
 news:eq8bim$2gou$1 digitaldaemon.com...
 When I use array.sort, which sorting algorithm does D use? Can the 
 programmer
 overwrite the implementation of this function?

 Thanks!

 
 DMD at least uses quicksort.  You can find the actual source for it in 
 /dmd/src/phobos/internal/qsort2.d.  You can see that it just calls the C 
 stdlib qsort() function.
 
 If you want to use a different algorithm, you'd have to change this file and 
 recompile phobos.  A daunting task.. 
 
 

I thought it used a quicksort with insertion sort for the smallest arrays.
In fact such a beast seems to be in dmd/src/phobos/internal/qsort.d.
Are you sure arrays use the qsort2.d implementation?

--bb

"Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:

"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:eq8iau$2s4p$1 digitaldaemon.com...
 I thought it used a quicksort with insertion sort for the smallest arrays.
 In fact such a beast seems to be in dmd/src/phobos/internal/qsort.d.
 Are you sure arrays use the qsort2.d implementation?

There's apparently some licensing issues with qsort.d?  I'm not entirely 
sure, but.. well to be honest I'm not sure whether it uses qsort.d or 
qsort2.d.  I shouldn't have jumped to that conclusion.  Looking at the 
phobos makefile it seems to use qsort.d, but qsort2.d is also mentioned.

Either way, it's probably not the fastest, as I wrote a templated 
_recursive_ quicksort (not even using a stack like the one in qsort.d) that 
consistently outperforms the builtin one by 5~10% (on my computer at least). 

Bill Baxter <dnewsgroup billbaxter.com> writes:

Jarrett Billingsley wrote:
 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:eq8iau$2s4p$1 digitaldaemon.com...
 I thought it used a quicksort with insertion sort for the smallest arrays.
 In fact such a beast seems to be in dmd/src/phobos/internal/qsort.d.
 Are you sure arrays use the qsort2.d implementation?

 
 There's apparently some licensing issues with qsort.d?  I'm not entirely 
 sure, but.. well to be honest I'm not sure whether it uses qsort.d or 
 qsort2.d.  I shouldn't have jumped to that conclusion.  Looking at the 
 phobos makefile it seems to use qsort.d, but qsort2.d is also mentioned.
 
 Either way, it's probably not the fastest, as I wrote a templated 
 _recursive_ quicksort (not even using a stack like the one in qsort.d) that 
 consistently outperforms the builtin one by 5~10% (on my computer at least). 
 
 

Yeh, I can believe that.  qsort2 calls the TypeInfo.compare method to do 
its dirty work.  It probably does not ever get inlined.  Whereas a 
templated version can usually inline the compare away.


about for years.  It's the first thing he pulls out whenever someone 
says C++ is slow.  No no! He says, look at std::sort!  Faster than C's 
qsort() could ever even hope to be!

--bb

Lionello Lunesu <lio lunesu.remove.com> writes:

Jarrett Billingsley wrote:
 If you want to use a different algorithm, you'd have to change this file and 
 recompile phobos.  A daunting task.. 

make -fwin32.mak

Really. I do it all the time :)

L.

"Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:

"Lionello Lunesu" <lio lunesu.remove.com> wrote in message 
news:eqcv8j$8gs$1 digitaldaemon.com...
 Jarrett Billingsley wrote:
 If you want to use a different algorithm, you'd have to change this file 
 and recompile phobos.  A daunting task..

 make -fwin32.mak

 Really. I do it all the time :)

 L.

I always get all kinds of errors..  unless it's changed since 0.170 or so. 
I end up having to manually change a bunch of stuff in the makefiles and in 
the directory tree to get it to work right. 

Lionello Lunesu <lio lunesu.remove.com> writes:

Jarrett Billingsley wrote:
 "Lionello Lunesu" <lio lunesu.remove.com> wrote in message 
 news:eqcv8j$8gs$1 digitaldaemon.com...
 Jarrett Billingsley wrote:
 If you want to use a different algorithm, you'd have to change this file 
 and recompile phobos.  A daunting task..

 make -fwin32.mak

 Really. I do it all the time :)

 L.

 
 I always get all kinds of errors..  unless it's changed since 0.170 or so. 
 I end up having to manually change a bunch of stuff in the makefiles and in 
 the directory tree to get it to work right. 

It has changed, in fact. I've posted the issues a while back in bugzilla 
and Walter has addressed them all. I'm not sure about linux though, but 
building phobos for windows has never been easier.

L.

"Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:

"Lionello Lunesu" <lio lunesu.remove.com> wrote in message 
news:eqelo7$2a5u$1 digitaldaemon.com...

 It has changed, in fact. I've posted the issues a while back in bugzilla 
 and Walter has addressed them all. I'm not sure about linux though, but 
 building phobos for windows has never been easier.

Oh, well cool then :) 

Oskar Linde <oskar.lindeREM OVEgmail.com> writes:

Michiel wrote:
 When I use array.sort, which sorting algorithm does D use? Can the programmer
 overwrite the implementation of this function?

Just write a library replacement[1]. The only difference is that it will 
have to be called as:

array.sort() instead of array.sort

The advantages are several. It will be faster than the built in sort and 
you will have the possibility of making it support custom ordering 
predicates and more. IMHO, the built in .sort and .reverse properties(?) 
should be removed as identical in syntax and infinitely more flexible 
library implementations are possible.

For a sample implementation, see my old and dusty std.array proposal:
http://www.csc.kth.se/~ol/array.d
Ugly DDoc:
http://www.csc.kth.se/~ol/array.html

it includes:
array.sort()
array.sort(predicate wrongOrder)
array.stableSort()
array.stableSort(predicate wrongOrder)

And in-place versions:
array.doSort()
array.doSort(predicate wrongOrder)
array.doStableSort()
array.doStableSort(predicate wrongOrder)

I believe it still compiles, but no guarantees as it was written for DMD 
0.149 or thereabouts.

/Oskar

Sean Kelly <sean f4.ca> writes:

Oskar Linde wrote:
 Michiel wrote:
 When I use array.sort, which sorting algorithm does D use? Can the 
 programmer
 overwrite the implementation of this function?

 
 Just write a library replacement[1]. The only difference is that it will 
 have to be called as:
 
 array.sort() instead of array.sort
 
 The advantages are several. It will be faster than the built in sort and 
 you will have the possibility of making it support custom ordering 
 predicates and more. IMHO, the built in .sort and .reverse properties(?) 
 should be removed as identical in syntax and infinitely more flexible 
 library implementations are possible.

For what it's worth, Tango contains a sort routine in tango.core.Array. 
  In the brief testing I've done performs roughly the same as the 
built-in sort routine.  It's a modified version of quicksort, and I 
found that using insertion sort for small ranges (as the built-in sort 
does) had no measurable effect on performance so I didn't bother with 
the additional complexity.


Sean