Feedback very appreciated.
Add stableSort() to the standard library.
Thank you for the proposal! It is much appreciated!
####
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.
####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).
#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().
@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.
Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).
Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.
Constraints
Self.Generator.Element : Comparable
We should also add an overload that takes a comparator closure.
#####
Impact on existing code
#####
None.
####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).
I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do. What other parameters could sort()
conceivably get in future? Should the parameter be a boolean flag or
a resilient option set? Foundation has NSSortOptions, which has just
"Stable" and "Concurrent". The "concurrent" part, in my opinion,
needs to be handled somehow for all algorithms in a consistent manner,
rather than adding flags for each API separately.
####
Open questions
####
Should we also provide a stableSortInPlace() implementation?
Absolutely!
Dmitri
···
On Sun, Jan 10, 2016 at 3:11 PM, Davide Italiano <dccitaliano@gmail.com> wrote:
--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
