I've been playing with sorting algorithms a lot in recent months,
so I want to implement a *working* stable sort for Phobos which
is broken at the moment. I have a working library and I'm still
adding to it. It's much more complex than a simple merge sort,
being over 300 lines of code at the mo
On 03/13/2012 02:31 AM, Xinok wrote:
I've been playing with sorting algorithms a lot in recent months, so I
want to implement a *working* stable sort for Phobos which is broken at
the moment. I have a working library and I'm still adding to it. It's
much more complex than a simple merge sort, bei
Le 13/03/2012 07:53, Chad J a écrit :
On 03/13/2012 02:31 AM, Xinok wrote:
I've been playing with sorting algorithms a lot in recent months, so I
want to implement a *working* stable sort for Phobos which is broken at
the moment. I have a working library and I'm still adding to it. It's
much mor
On Tuesday, 13 March 2012 at 06:53:30 UTC, Chad J wrote:
Hey, I'd love to see more sorting algorithms in phobos. Being
stuck with one seems kind of... wrong.
Things like this are better left to 3rd party libs. Phobos
already has two, a stable and unstable sort, which fulfill 99% of
cases.
On Tuesday, 13 March 2012 at 08:37:06 UTC, deadalnix wrote:
I have a radix sort (that need some rework to be phobos
quality) and a smoothsort (that could be included in phobos).
Would you mind sharing your smoothsort? I haven't implemented one
myself and I'd love to test it out.
Radix sort, on
Le 13/03/2012 10:19, Xinok a écrit :
On Tuesday, 13 March 2012 at 08:37:06 UTC, deadalnix wrote:
I have a radix sort (that need some rework to be phobos quality) and a
smoothsort (that could be included in phobos).
Would you mind sharing your smoothsort? I haven't implemented one myself
and I'
On 3/13/12 4:02 AM, Xinok wrote:
On Tuesday, 13 March 2012 at 06:53:30 UTC, Chad J wrote:
Hey, I'd love to see more sorting algorithms in phobos. Being stuck
with one seems kind of... wrong.
Things like this are better left to 3rd party libs. Phobos already has
two, a stable and unstable sort,
On 3/13/12 1:31 AM, Xinok wrote:
I've been playing with sorting algorithms a lot in recent months, so I
want to implement a *working* stable sort for Phobos which is broken at
the moment. I have a working library and I'm still adding to it. It's
much more complex than a simple merge sort, being o
On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote:
Le 13/03/2012 10:19, Xinok a écrit :
Would you mind sharing your smoothsort? I haven't implemented
one myself
and I'd love to test it out.
It is on github :
https://github.com/deadalnix/Dsort/blob/master/sort/smooth.d
Thanks. I fo
On Tuesday, 13 March 2012 at 14:31:59 UTC, Andrei Alexandrescu
wrote:
On 3/13/12 1:31 AM, Xinok wrote:
- It's a natural merge sort, which is faster on partially
sorted lists,
and adds little overhead for mostly random lists.
- It uses O(log n log n) additional space for merging.
That's 1024 w
How does the built-in sort do? I ask because the sort routine I wrote works
the same way, which is optimized for ranges with a lot of common elements.
On Mar 13, 2012, at 7:33 AM, Andrei Alexandrescu
wrote:
> On 3/13/12 4:02 AM, Xinok wrote:
>> On Tuesday, 13 March 2012 at 06:53:30 UTC, Chad
I forgot to mention that my routine uses the same basic algorithm as the
built-in sort.
On Mar 13, 2012, at 8:54 AM, Sean Kelly wrote:
> How does the built-in sort do? I ask because the sort routine I wrote works
> the same way, which is optimized for ranges with a lot of common elements.
>
Le 13/03/2012 16:08, Xinok a écrit :
On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote:
Le 13/03/2012 10:19, Xinok a écrit :
Would you mind sharing your smoothsort? I haven't implemented one myself
and I'd love to test it out.
It is on github :
https://github.com/deadalnix/Dsort/blob
On 3/13/12 10:54 AM, Sean Kelly wrote:
How does the built-in sort do? I ask because the sort routine I
wrote works the same way, which is optimized for ranges with a lot of
common elements.
It's not about common (equal) elements, it's about elements for which
comparisons do a lot of work beca
On Tuesday, 13 March 2012 at 16:04:55 UTC, deadalnix wrote:
Le 13/03/2012 16:08, Xinok a écrit :
On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote:
Le 13/03/2012 10:19, Xinok a écrit :
Would you mind sharing your smoothsort? I haven't
implemented one myself
and I'd love to test it ou
On Tuesday, 13 March 2012 at 16:11:05 UTC, Andrei Alexandrescu
wrote:
On 3/13/12 10:54 AM, Sean Kelly wrote:
How does the built-in sort do? I ask because the sort routine
I
wrote works the same way, which is optimized for ranges with a
lot of
common elements.
It's not about common (equal) e
Le 13/03/2012 17:38, Xinok a écrit :
On Tuesday, 13 March 2012 at 16:04:55 UTC, deadalnix wrote:
Le 13/03/2012 16:08, Xinok a écrit :
On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote:
Le 13/03/2012 10:19, Xinok a écrit :
Would you mind sharing your smoothsort? I haven't implemented
Andrei Alexandrescu:
> it's about elements for which
> comparisons do a lot of work because they have common prefixes. Consider:
>
> auto arr = [ "aaa", "aab", "aac", "aad" ];
> sort!((a, b) => a > b)(arr);
>
> There will be a lot of redundant prefix comparisons because the sorting
> method do
On Tuesday, 13 March 2012 at 06:32:01 UTC, Xinok wrote:
I've been playing with sorting algorithms a lot in recent
months, so I want to implement a *working* stable sort for
Phobos which is broken at the moment. I have a working library
and I'm still adding to it. It's much more complex than a
On Tuesday, 13 March 2012 at 14:31:59 UTC, Andrei Alexandrescu
wrote:
On 3/13/12 1:31 AM, Xinok wrote:
- I wrote it to sort random-access ranges *without* slicing,
but I think
the exclusion of slicing makes it slower. I'm writing a
separate
implementation which uses slicing and I'll keep it if
On Tuesday, 13 March 2012 at 18:32:27 UTC, Xinok wrote:
On Tuesday, 13 March 2012 at 06:32:01 UTC, Xinok wrote:
I've been playing with sorting algorithms a lot in recent
months, so I want to implement a *working* stable sort for
Phobos which is broken at the moment. I have a working library
an
On Wednesday, 14 March 2012 at 03:55:31 UTC, Xinok wrote:
I removed the code without slicing from the lib, though I still
retain a copy.
I added 3 unittests: A basic sort test, a stability test, and a
CTFE test.
I added a few asserts which have helped me discover bugs in the
past.
I only added
On Thursday, 15 March 2012 at 20:20:59 UTC, Xinok wrote:
Third update:
http://www.mediafire.com/?9jx07estd58wh2p
+ Added in-place sorting; Set template argument inPlace to true
+ Fixed CTFE compatibility issues
+ Vastly improved unittest
+ CTFE unittest will no longer stop compilation upon failu
23 matches
Mail list logo
