Sorting algorithm

Xinok xinok at live.com
Sat Oct 8 08:36:29 PDT 2011


On 10/8/2011 11:04 AM, Andrei Alexandrescu wrote:
> On 10/08/11 10:01, Xinok wrote:
>> On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
>>> On 10/07/11 23:00, Xinok wrote:
>>>> Thanks, I'll look into it when I have a little more time.
>>>
>>> Looking forward to it.
>>>
>>>> If my algorithm were to be implemented in Phobos, the template
>>>> arguments
>>>> for std.algorithm.sort would need to be modified. For my algorithm
>>>> to be
>>>> stable, it requires defining two conditions, both a 'less' and
>>>> 'greater'.
>>>
>>> Wouldn't swapping the argument to less work?
>>>
>>>
>>> Andrei
>>
>> The merge step in my algorithm is similar to Timsort, in that it can
>> merge left to right as well as right to left. This needs two conditions
>> to do a stable sort, 'less or equal' and 'greater or equal'.
>>
>> By swapping the arguments, you can only get 'greater or equal'. You're
>> still missing 'less or equal', which is required for my algorithm to be
>> stable.
>
> I don't understand. Say all you have is "<". Then you can do everything:
>
> a <= b is !(b < a)
> a > b is b < a
>
> This is an absolute classic. Probably it's negation that is missing from
> your assumptions? You can always negate a predicate.
>
>
> Andrei

I actually wasn't aware you could do that O.o, although you got the 
operators wrong in your example.

It does add overhead though. It requires two comparisons, and possibly 
twice the number of lookups, such as in this statement:
lef[c] > rig[off - c]

How about, if the greater argument is empty, then it fills it 
automatically with this. But also give the programmer the option to 
define both conditions for more efficient code.


More information about the Digitalmars-d mailing list