[swift-evolution] Add stableSort() to the standard library.
Tyler Cloutier
cloutiertyler at aol.com
Wed Jan 20 14:19:14 CST 2016
> On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>
>
> on Sun Jan 10 2016, Davide Italiano via swift-evolution <swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.org <http://swift-evolution-m3fhrko0vlzytjvyw6ydsg-at-public.gmane.org/>> wrote:
>
>> Feedback very appreciated.
>>
>> Add stableSort() to the standard library.
>>
>> ####
>> Introduction
>> ####
>> At the time of writing the Swift standard library provides two way two
>> different versions of sort.
>> The first one is sort(), which provides a regular unstable[1] sorting algorithm.
>> The second one, sortInPlace(), which also provides unstable sorting with the
>> additional guarantee that the algorithm will operate in-place, i.e., it will
>> use only a constant amount of extra space (independent from the input size).
>> The aim of this proposal is to implement a third variant, stableSort(), in order
>> to provide a stable version of sorting.
>
> A few thoughts:
>
> 1. The C++ stable sort algorithm draws on just nearly every other
> algorithm in the entire standard library, many of which we don't
> currently have in Swift. Doing something similar would expand the
> algorithms we support, which IMO would be a good thing.
>
> 2. I am very intrigued with Python's argument that, for a
> general-purpose audience, stable sorting should be the default. It's
> certainly more widely-useful than unstable sorting.
>
> 3. There are several interesting and fast stable sorting algorithms out
> there, including Python's timsort; it would take some experimentation
> to discover which one(s) to use for Swift.
>
> 4. I'm not a fan of adding a parameter to sort to select stability,
> because of the added API complexity. People who want a
> faster-but-unstable sort can call unstableSort, right?
I think the potential here is that people might not even be aware there is such an option. unstableSort() not terribly autocomplete friendly which I think adds to complexity. It seems like a parameter would be in line with API’s like print(_:separator:terminator:), even though the print arguments are not constants. I think the print API is very intuitive, but perhaps I’m misunderstanding what you mean by complexity?
Tyler
>
> -Dave
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160120/be41ac64/attachment.html>
More information about the swift-evolution
mailing list