<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">This seems interesting, simple and clean. Also, this kinda reminds me of the <a href="https://en.wikipedia.org/wiki/Strategy_pattern" class="">Strategy Pattern</a>:</div><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(192, 192, 192);" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><span style="color: rgb(222, 52, 140);" class="">protocol</span> SortingStrategy { <span style="color: rgb(192, 192, 192);" class="">/* declare `sort()` */</span> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">class</span> StableSort: <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">SortingStrategy</span> { <span style="color: rgb(192, 192, 192);" class="">/* implement a stable `sort()` */ </span>}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class=""><br class=""></span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">class</span> UnstableSort: <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">SortingStrategy</span> { <span style="color: rgb(192, 192, 192);" class="">/* implement a unstable `sort()` */ </span>}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">class</span> Sorter {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">let</span> strategy: <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">SortingStrategy</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">init</span>(using strategy: <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">SortingStrategy</span>) { <span style="color: rgb(222, 52, 140);" class="">self</span>.<span style="color: rgb(88, 126, 168);" class="">strategy</span> = strategy }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">func</span> sort( <span style="font-variant-ligatures: no-common-ligatures; color: #c0c0c0" class="">/* ... */ </span>) { <span style="color: rgb(222, 52, 140);" class="">return</span> <span style="color: rgb(222, 52, 140);" class="">self</span>.<span style="color: rgb(88, 126, 168);" class="">strategy</span>.<span style="color: rgb(88, 126, 168);" class="">sort</span>( <span style="color: rgb(192, 192, 192);" class="">/* ... */ </span>) }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(192, 192, 192);" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">let</span> stableSort = <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">Sorter</span>(using: <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">StableSort</span>())</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(88, 126, 168);" class="">stableSort<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">.</span>sort<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">( </span><span style="font-variant-ligatures: no-common-ligatures; color: #c0c0c0" class="">/* ... */</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> )</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">let</span> unstableSort = <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">Sorter</span>(using: <span style="font-variant-ligatures: no-common-ligatures; color: #587ea8" class="">UnstableSort</span>())</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(88, 126, 168);" class="">unstableSort<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">.</span>sort<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">( </span><span style="font-variant-ligatures: no-common-ligatures; color: #c0c0c0" class="">/* ... */</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> )</span></div></div><div class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><br class=""></span></div><div class="">One could go further and, instead of `StableSort` and `UnstableSort`, provide different options of sorting algorithms:</div><div class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><br class=""></span></div><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(192, 192, 192);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">class</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> IntroSort: </span><span style="color: rgb(88, 126, 168);" class="">SortingStrategy</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> { </span>/* intro sort implementation */<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(192, 192, 192);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">class</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> QuickSort: </span><span style="color: rgb(88, 126, 168);" class="">SortingStrategy</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> { </span>/* quick sort implementation */<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(192, 192, 192);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #de348c" class="">class</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> MergeSort: </span><span style="color: rgb(88, 126, 168);" class="">SortingStrategy</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> { </span>/* merge sort implementation */<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(192, 192, 192);" class="">// ...</div></div><div class=""><br class=""></div><div class="">Not sure, however, if having those in the language itself would be make sense. Perhaps a separate library would be a better place.<br class=""><br class=""></div><div class="">Wonder if using protocol with default implementations above, rather than classes, would’ve been better...</div><div class=""><br class=""></div><div class="">Best,</div><div class=""><br class=""></div><div class="">— A</div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 22, 2016, at 8:03 AM, ankit goel via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hey,<div class=""><br class=""></div><div class="">A single sort function with an enum parameter that let's you choose among sort(), sortInPlace() and stableSort() would be nice.</div><div class=""><br class=""></div><div class="">enum SortOptions {</div><div class=""> case none</div><div class=""> case InPlace</div><div class=""> case Stable</div><div class="">}</div><div class=""><br class=""></div><div class="">func sort(items, type: SortOptions = .none)</div><div class=""><br class=""></div><div class="">// call to sort function</div><div class="">sort([1,2,3,4], type: .Stable)</div><div class=""><br class=""></div><div class="">This way a single sort function handles all three cases and enums provide autocompletion while calling the function.</div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Fri, Jan 22, 2016 at 3:22 AM, Dave Abrahams via swift-evolution <span dir="ltr" class=""><<a href="mailto:swift-evolution@swift.org" target="_blank" class="">swift-evolution@swift.org</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5"><br class="">
on Thu Jan 21 2016, Charles Kissinger <<a href="http://crk-at-akkyra.com" class="">crk-AT-akkyra.com</a>> wrote:<br class="">
<br class="">
>> On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:<br class="">
>><br class="">
>><br class="">
>> on Sun Jan 10 2016, Davide Italiano via swift-evolution<br class="">
>> <<a href="http://swift-evolution-m3fhrko0vlzytjvyw6ydsg-at-public.gmane.org/" rel="noreferrer" target="_blank" class="">swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.org</a>> wrote:<br class="">
><br class="">
>><br class="">
>>> Feedback very appreciated.<br class="">
>>><br class="">
>>> Add stableSort() to the standard library.<br class="">
>>><br class="">
>>> ####<br class="">
>>> Introduction<br class="">
>>> ####<br class="">
>>> At the time of writing the Swift standard library provides two way two<br class="">
>>> different versions of sort.<br class="">
>>> The first one is sort(), which provides a regular unstable[1] sorting algorithm.<br class="">
>>> The second one, sortInPlace(), which also provides unstable sorting with the<br class="">
>>> additional guarantee that the algorithm will operate in-place, i.e., it will<br class="">
>>> use only a constant amount of extra space (independent from the input size).<br class="">
>>> The aim of this proposal is to implement a third variant, stableSort(), in order<br class="">
>>> to provide a stable version of sorting.<br class="">
>><br class="">
>> A few thoughts:<br class="">
>><br class="">
>> 1. The C++ stable sort algorithm draws on just nearly every other<br class="">
>> algorithm in the entire standard library, many of which we don't<br class="">
>> currently have in Swift. Doing something similar would expand the<br class="">
>> algorithms we support, which IMO would be a good thing.<br class="">
>><br class="">
>> 2. I am very intrigued with Python's argument that, for a<br class="">
>> general-purpose audience, stable sorting should be the default. It's<br class="">
>> certainly more widely-useful than unstable sorting.<br class="">
><br class="">
> Stable sorting as the default would follow the Principle of Least<br class="">
> Astonishment, I think (especially for programmers coming from Python<br class="">
> and Java, where stable is the default). And the more widely useful<br class="">
> algorithm, even if it is at the expense of performance, seems like the<br class="">
> right choice for a standard library.<br class="">
><br class="">
>><br class="">
>> 3. There are several interesting and fast stable sorting algorithms out<br class="">
>> there, including Python's timsort; it would take some experimentation<br class="">
>> to discover which one(s) to use for Swift.<br class="">
><br class="">
> I suppose one complication for Swift is that any particular algorithm<br class="">
> might perform well with reference types but less so with value types<br class="">
> if they happen to be large and the algorithm does a relatively large<br class="">
> amount of copying.<br class="">
<br class="">
</div></div>That's true, but if that's the case we could (and should) select the<br class="">
algorithm accordingly. It's all statically-knowable, so shouldn't even<br class="">
cost a branch in practice.<br class="">
<span class=""><br class="">
>> 4. I'm not a fan of adding a parameter to sort to select stability,<br class="">
>> because of the added API complexity. People who want a<br class="">
>> faster-but-unstable sort can call unstableSort, right?<br class="">
><br class="">
> I wonder if anyone actually would be clamoring for an unstable sort<br class="">
> option, per se, given how well timsort seems to perform.<br class="">
<br class="">
</span>Maybe not. If you look around, you'll find timsort has a handful of<br class="">
competitors we also ought to examine.<br class="">
<span class=""><br class="">
> An algorithm, stable or unstable, with lower memory requirements or<br class="">
> different edge case behavior might be the most useful alternative. For<br class="">
> instance, an algorithm that sorts in-place without any significant<br class="">
> memory overhead (“in-place" not in the mutating sense, but in not<br class="">
> requiring temporary storage during the sort) could be handy when<br class="">
> dealing with large sequences on more memory-constrained<br class="">
> devices.<br class="">
<br class="">
</span>True; that's what the current algorithm does.<br class="">
<span class=""><br class="">
> Still, I wonder if it will really be a pain point for anyone<br class="">
> if the only option is a state-of-the-art stable sort.<br class="">
<br class="">
</span>A real question. There's a lot of research to do, here. If someone<br class="">
wanted to take on this investigation and do a thorough job of it, I'm<br class="">
sure it would have a big impact.<br class="">
<br class="">
Cheers,<br class="">
<div class="HOEnZb"><div class="h5">Dave<br class="">
_______________________________________________<br class="">
swift-evolution mailing list<br class="">
<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class="">
</div></div></blockquote></div><br class=""></div>
_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></div></body></html>