www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - XSort - Sorting algorithms (including Timsort!)

reply "Xinok" <xinok live.com> writes:
I just wanted to share this. I started a project a few weeks ago 
on Github to implement several sorting algorithms in D. In total, 
there are 8 modules at the moment, each implementing a sorting 
algorithm or combination thereof.

https://github.com/Xinok/XSort

I just finished Timsort today. It's working, it's stable, but I 
need to spend a little more time better optimizing it.
Apr 11 2012
next sibling parent reply "Nathan M. Swan" <nathanmswan gmail.com> writes:
On Thursday, 12 April 2012 at 03:04:49 UTC, Xinok wrote:
 I just wanted to share this. I started a project a few weeks 
 ago on Github to implement several sorting algorithms in D. In 
 total, there are 8 modules at the moment, each implementing a 
 sorting algorithm or combination thereof.

 https://github.com/Xinok/XSort

 I just finished Timsort today. It's working, it's stable, but I 
 need to spend a little more time better optimizing it.

Cool! To make it a bit more generic, may I suggest making all the inputs only have to be "isInputRange", and have it converted to an array. NMS
Apr 11 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 12.04.2012 18:50, Xinok wrote:
 On Thursday, 12 April 2012 at 05:25:52 UTC, Nathan M. Swan wrote:
 On Thursday, 12 April 2012 at 03:04:49 UTC, Xinok wrote:
 I just wanted to share this. I started a project a few weeks ago on
 Github to implement several sorting algorithms in D. In total, there
 are 8 modules at the moment, each implementing a sorting algorithm or
 combination thereof.

 https://github.com/Xinok/XSort

 I just finished Timsort today. It's working, it's stable, but I need
 to spend a little more time better optimizing it.

Cool! To make it a bit more generic, may I suggest making all the inputs only have to be "isInputRange", and have it converted to an array. NMS

This incurs different behavior as random-access ranges would be sorted in place and input ranges wouldn't be. I could add separate functions to make this behavior explicit, but I see little point in doing so. It's quite easy to convert an input range to an array yourself: import std.array, std.range; auto inputRangeToArray(R)(R range) if(isInputRange!R && !isInfinite!R) { auto app = Appender!(ElementType!(R)[])(); static if(hasLength!R) app.reserve(range.length); app.put(range); return app.data; }

Indeed and there is a standard function array(...) that does this very thing. -- Dmitry Olshansky
Apr 12 2012
prev sibling parent "Xinok" <xinok live.com> writes:
On Thursday, 12 April 2012 at 05:25:52 UTC, Nathan M. Swan wrote:
 On Thursday, 12 April 2012 at 03:04:49 UTC, Xinok wrote:
 I just wanted to share this. I started a project a few weeks 
 ago on Github to implement several sorting algorithms in D. In 
 total, there are 8 modules at the moment, each implementing a 
 sorting algorithm or combination thereof.

 https://github.com/Xinok/XSort

 I just finished Timsort today. It's working, it's stable, but 
 I need to spend a little more time better optimizing it.

Cool! To make it a bit more generic, may I suggest making all the inputs only have to be "isInputRange", and have it converted to an array. NMS

This incurs different behavior as random-access ranges would be sorted in place and input ranges wouldn't be. I could add separate functions to make this behavior explicit, but I see little point in doing so. It's quite easy to convert an input range to an array yourself: import std.array, std.range; auto inputRangeToArray(R)(R range) if(isInputRange!R && !isInfinite!R) { auto app = Appender!(ElementType!(R)[])(); static if(hasLength!R) app.reserve(range.length); app.put(range); return app.data; }
Apr 12 2012