[swift-evolution] Add stableSort() to the standard library.

Fri Jan 22 10:11:46 CST 2016

This seems interesting, simple and clean. Also, this kinda reminds me of the Strategy Pattern <https://en.wikipedia.org/wiki/Strategy_pattern>:

protocol SortingStrategy { /* declare `sort()` */ }

class StableSort: SortingStrategy { /* implement a stable `sort()` */ }

class UnstableSort: SortingStrategy { /* implement a unstable `sort()` */ }

class Sorter {

    let strategy: SortingStrategy

    init(using strategy: SortingStrategy) { self.strategy = strategy }

    func sort( /* ... */ ) { return self.strategy.sort( /* ... */ ) }
}

let stableSort = Sorter(using: StableSort())
stableSort.sort( /* ... */ )

let unstableSort = Sorter(using: UnstableSort())
unstableSort.sort( /* ... */ )

One could go further and, instead of `StableSort` and `UnstableSort`, provide different options of sorting algorithms:

class IntroSort: SortingStrategy { /* intro sort implementation */ }
class QuickSort: SortingStrategy { /* quick sort implementation */ }
class MergeSort: SortingStrategy { /* merge sort implementation */ }
// ...

Not sure, however, if having those in the language itself would be make sense. Perhaps a separate library would be a better place.

Wonder if using protocol with default implementations above, rather than classes, would’ve been better...

Best,

— A

> On Jan 22, 2016, at 8:03 AM, ankit goel via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Hey,
> 
> A single sort function with an enum parameter that let's you choose among sort(), sortInPlace() and stableSort() would be nice.
> 
> enum SortOptions {
>   case none
>   case InPlace
>   case Stable
> }
> 
> func sort(items, type: SortOptions = .none)
> 
> // call to sort function
> sort([1,2,3,4], type: .Stable)
> 
> This way a single sort function handles all three cases and enums provide autocompletion while calling the function.
> 
> 
> On Fri, Jan 22, 2016 at 3:22 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> 
> on Thu Jan 21 2016, Charles Kissinger <crk-AT-akkyra.com> wrote:
> 
> >> On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org <mailto: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.
> >
> > Stable sorting as the default would follow the Principle of Least
> > Astonishment, I think (especially for programmers coming from Python
> > and Java, where stable is the default). And the more widely useful
> > algorithm, even if it is at the expense of performance, seems like the
> > right choice for a standard library.
> >
> >>
> >> 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.
> >
> > I suppose one complication for Swift is that any particular algorithm
> > might perform well with reference types but less so with value types
> > if they happen to be large and the algorithm does a relatively large
> > amount of copying.
> 
> That's true, but if that's the case we could (and should) select the
> algorithm accordingly.  It's all statically-knowable, so shouldn't even
> cost a branch in practice.
> 
> >> 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 wonder if anyone actually would be clamoring for an unstable sort
> > option, per se, given how well timsort seems to perform.
> 
> Maybe not.  If you look around, you'll find timsort has a handful of
> competitors we also ought to examine.
> 
> > An algorithm, stable or unstable, with lower memory requirements or
> > different edge case behavior might be the most useful alternative. For
> > instance, an algorithm that sorts in-place without any significant
> > memory overhead (“in-place" not in the mutating sense, but in not
> > requiring temporary storage during the sort) could be handy when
> > dealing with large sequences on more memory-constrained
> > devices.
> 
> True; that's what the current algorithm does.
> 
> > Still, I wonder if it will really be a pain point for anyone
> > if the only option is a state-of-the-art stable sort.
> 
> A real question.  There's a lot of research to do, here.  If someone
> wanted to take on this investigation and do a thorough job of it, I'm
> sure it would have a big impact.
> 
> Cheers,
> 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>
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160122/e43cee06/attachment.html>