Thread overview | ||||||
---|---|---|---|---|---|---|
|
April 12, 2012 XSort - Sorting algorithms (including Timsort!) | ||||
---|---|---|---|---|
| ||||
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. |
April 12, 2012 Re: XSort - Sorting algorithms (including Timsort!) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Xinok | 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
|
April 12, 2012 Re: XSort - Sorting algorithms (including Timsort!) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nathan M. Swan | 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; } |
April 12, 2012 Re: XSort - Sorting algorithms (including Timsort!) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Xinok | 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 |
Copyright © 1999-2021 by the D Language Foundation