Just cruising the C++ algorithm list and wondered about std::partial_sort and std::nth_element. I guess this could be Swift-ified like:
extension MutableCollection {
/// Reorders the elements of the collection so the value at the given index
/// is what it would be if the entire collection was sorted according to the
/// given predicate.
///
/// - Note: Put something about stability here, both for elements with the
/// same value as the one that will go in `pivot`, and for ones outside of
/// that.
///
/// - Precondition: `pivot != endIndex`
///
/// - Parameter pivot: The element location to receive its sorted value.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
///
/// - Postcondition: The value at `pivot` is what it should have if the
/// whole collection was sorted under `areInIncreasingOrder`. All
/// elements before `pivot` have values ordered before or equivalent to
/// the one at `pivot`. (Which means the later elements have values
/// ordered equivalently or after one at `pivot`.)
///
/// - Complexity:???
public mutating func partitionToSort(at pivot: Index, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
// std::nth_element
}
/// Sorts the collection in place up to (but not including) the given index,
/// using the given predicate as the comparison between elements.
///
/// The sort is not guaranteed to be stable. The order of elements outside
/// the target range is unspecified.
///
/// - Parameter middle: The past-the-end point for the sorting to take
/// effect.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
///
/// - Postcondition: `self[..<middle]` is sorted according to
/// `areInIncreasingOrder` considering all the elements in `self`.
///
/// - Complexity: ???
public mutating func sort(upTo middle: Index, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
// std::partial_sort
}
}
with Comparable versions skipping the predicate for <. But I'm still wondering why would these be needed, outside of implementing other sorting things? Stopping at a point much smaller then the whole collection doesn't help too much because you still have to scan the whole thing.
I think I misinterpreted one of those methods, because one of my first tries was:
extension Collection {
/// Finds the index of the element whose value is the least ranked, after
/// ignoring a given number of even lesser-ranked elements, using the given
/// predicate for comparisons.
///
/// - Note: Put something here about stability, like which element is chosen
/// if there are multiple elements that match the given place.
///
/// - Precondition: `count >= 0`
///
/// - Parameter count: The number of elements with an ever lesser rank to
/// skip past. If not given, defaults to zero.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: The index for the element with the lowest order rank after
/// skipping the `count` elements with even lower rank. Returns `nil` if
/// the collection is empty or does not have enough elements to skip over.
///
/// - Complexity: ???
public func leastOrderedIndex(afterSkipping count: Int = 0, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Index? {
// ???
}
/// Finds the index of the element whose value is the most ranked, after
/// ignoring a given number of even greater-ranked elements, using the given
/// predicate for comparisons.
public func mostOrderedIndex(afterSkipping count: Int = 0, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Index? {
// ???
}
}
(with Comparable variants) but I don't think leastOrderedIndex(afterSkipping: by:) has an analog in the C++ Standard library. I'm not sure it can be implemented in a refined way, besides copying indices to a mutable Array then calling partitionToSort(at: by:) on it. This would cost O(n) space and at least O(n) time.
Can any of these be implemented stably?
