# Partial sorting?

**URL:** <https://forums.swift.org/t/partial-sorting/28941>\
**Category:** Discussion\
**Tags:** collection, sorting\
**Created:** [September 18, 2019, 8:47pm UTC](https://forums.swift.org/t/partial-sorting/28941 "2019-09-18T20:47:24Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\
**Post date:** [September 18, 2019, 8:47pm UTC](https://forums.swift.org/t/partial-sorting/28941/1 "2019-09-18T20:47:24Z")

</div>

Just cruising the [C++ algorithm list](https://en.cppreference.com/w/cpp/algorithm) and wondered about [`std::partial_sort`](https://en.cppreference.com/w/cpp/algorithm/partial_sort) and [`std::nth_element`](https://en.cppreference.com/w/cpp/algorithm/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?

---

<div class="post-metadata">

**Author:** ![GetSwifty](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/getswifty/32/39108_2.png) [@GetSwifty](https://forums.swift.org/u/GetSwifty)\
**Post date:** [September 18, 2019, 9:38pm UTC](https://forums.swift.org/t/partial-sorting/28941/2 "2019-09-18T21:38:22Z")

</div>

There may be performance implications I'm not taking into account, but this is pretty easily accomplished via:

```swift
let thing = [3, 2, 4, -1, -4]
let partiallySorted = thing[..<3].sorted() + thing[3...]
print(partialSort) // prints [2, 3, 4, -1, -4]

```

This doesn't do the transform in place, but it's possible there's a way to do that as well.

Is there a use case you have in mind where in-place modification is important for this kind of thing?

---

<div class="post-metadata">

**Author:** ![Dante-Broggi](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dante-broggi/32/7955_2.png) [@Dante-Broggi](https://forums.swift.org/u/Dante-Broggi)\
**Post date:** [September 18, 2019, 9:45pm UTC](https://forums.swift.org/t/partial-sorting/28941/3 "2019-09-18T21:45:42Z")

</div>

You actually can do that transform in place:

```swift
var thing = [3, 2, 4, -1, -4]
thing[..<3].sort()
print(thing) // prints [2, 3, 4, -1, -4]

```

---

<div class="post-metadata">

**Author:** ![Josh\_Osborne](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/josh_osborne/32/833_2.png) [@Josh\_Osborne](https://forums.swift.org/u/Josh_Osborne)\
**Post date:** [September 18, 2019, 10:14pm UTC](https://forums.swift.org/t/partial-sorting/28941/4 "2019-09-18T22:14:52Z")

</div>

> [@GetSwifty](#):
>
> There may be performance implications I'm not taking into account

The only time I have ever used nth\_element it was because it is an O(n) algorithm, so a much faster way to find the 90th percentile of a data set then sorting it. It was also a fair while ago and 200Mhz was a monster fast machine, so maybe I wouldn’t need it now 🙂

(Ok, yeah, I’m sure people need it _right now_, just not me at the moment)

---

<div class="post-metadata">

**Author:** ![GetSwifty](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/getswifty/32/39108_2.png) [@GetSwifty](https://forums.swift.org/u/GetSwifty)\
**Post date:** [September 18, 2019, 10:23pm UTC](https://forums.swift.org/t/partial-sorting/28941/5 "2019-09-18T22:23:43Z")

</div>

Nice! I was thinking that's how ArraySlice worked, but didn't have time to test it.

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [September 18, 2019, 10:29pm UTC](https://forums.swift.org/t/partial-sorting/28941/6 "2019-09-18T22:29:25Z")

</div>

That's not partial sort, `partialSort`ing would result in

```swift
[-4, -1, 2, 4 , 3]
  - sorted - - n/a -

```

The first `n` elements also need to be smallest among the whole list.

AFAICT, there's no way to do it in-just-a-few-lines in swift.

---

<div class="post-metadata">

**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\
**Post date:** [September 18, 2019, 11:02pm UTC](https://forums.swift.org/t/partial-sorting/28941/7 "2019-09-18T23:02:48Z")

</div>

Thanks for bringing these up, @CTMacUser — we probably will eventually want both of the C++ algorithms in the standard library. Partial sorting is more efficient than sorting a whole collection if you only need the smallest _n_ of your elements.

I'm not sure I understand what your `leastOrderedIndex` and `mostOrderedIndex` do — are they examining the "skipped" elements at all?

> [@CTMacUser](#):
>
> Can any of these be implemented stably?

There are two kinds of stability for `partial_sort`, right? Stability of the sorted section at the front and the stability of the unsorted section at the end. The C++ versions aren't stable for either. This would be a question we'd definitely need to discuss when designing this feature in the stdlib.

> [@Dante-Broggi](#):
>
> You actually can do the transform in place:
> 
> ```swift
> var thing = [3, 2, 4, -1, -4]
> thing[..<3].sort()
> print(thing) // prints [2, 3, 4, -1, -4]
> 
> ```

Note that a partial sort isn't the same as sorting part of a collection — the result would be more like:

```swift
var thing = [3, 2, 4, -1, -4]
thing.partialSort(upTo: 3)
// [-4, -1, 2, 3, 4]

```

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [September 18, 2019, 11:05pm UTC](https://forums.swift.org/t/partial-sorting/28941/8 "2019-09-18T23:05:07Z")

</div>

> [@nnnnnnnn](#):
>
> I'm not sure I understand what your `leastOrderedIndex` and `mostOrderedIndex` do — are they examining the "skipped" elements at all?

I’m pretty sure it’s nth element, from the front and from the back.

---

<div class="post-metadata">

**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\
**Post date:** [September 19, 2019, 1:53am UTC](https://forums.swift.org/t/partial-sorting/28941/9 "2019-09-19T01:53:22Z")

</div>

Yes, I said:

```
    - Postcondition: `self[..<middle]` is sorted according to `areInIncreasingOrder` considering all the elements in `self`.

```

That " **considering all**" is important there. Elements too large to be in the prefix get bumped out (to an unspecified order) while too-small elements on the outside get bumped in.

> [@nnnnnnnn](#):
>
> I'm not sure I understand what your `leastOrderedIndex` and `mostOrderedIndex` do — are they examining the "skipped" elements at all?

`leastOrderedIndex(afterSkipping: 0, by: MyPredicate())` finds the index of the element `min(by:)` would target. `leastOrderedIndex(afterSkipping: 1, by: MyPredicate())` ignores the smallest element and returns the index of the second-smallest element. I think I just accidentally made it up; I'm not sure there's a way to do it better than wasting O(n) space then calling `partitionToSort(at: by:)`.

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [September 19, 2019, 2:02am UTC](https://forums.swift.org/t/partial-sorting/28941/10 "2019-09-19T02:02:06Z")

</div>

There's a [Quickselect](https://en.wikipedia.org/wiki/Quickselect) algorithm. To which all the technique of `Quicksort` applies. This can be done in-place, if you allow mutation of the original collection. This is likely what happened in `nth_element` in C++.

---

<div class="post-metadata">

**Author:** ![Josh\_Osborne](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/josh_osborne/32/833_2.png) [@Josh\_Osborne](https://forums.swift.org/u/Josh_Osborne)\
**Post date:** [September 19, 2019, 8:36pm UTC](https://forums.swift.org/t/partial-sorting/28941/11 "2019-09-19T20:36:24Z")

</div>

> [@Lantua](#):
>
> There's a [Quickselect](https://en.wikipedia.org/wiki/Quickselect) algorithm. [...]. This is likely what happened in `nth_element` in C++.

The one C++ nth\_element I looked at uses [Introselect](https://en.wikipedia.org/wiki/Introselect), which has better worst case performance then Quickselect (`O(n log n)` v. `O(n²)`).

I haven't benchmarked them, so I can't really say how the "not worst case" compares. Wikipedia says Introselect is "comparable", so I guess "slower but not by too much for some values of too much"?

**Added** :

> Both algorithms were introduced by [David Musser](https://en.wikipedia.org/wiki/David_Musser) in ([Musser 1997](https://en.wikipedia.org/wiki/Introselect#CITEREFMusser1997)), with the purpose of providing [generic algorithms](https://en.wikipedia.org/wiki/Generic_algorithm) for the [C++ Standard Library](https://en.wikipedia.org/wiki/C%2B%2B_Standard_Library) that have both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.[[1]](https://en.wikipedia.org/wiki/Introselect#cite_note-1) However, in most C++ Standard Library implementations that use introselect, another "introselect" algorithm is used, which combines quickselect and heapselect, and has a worst-case running time of _O_ ( _n_ log _n_ )[[2]](https://en.wikipedia.org/wiki/Introselect#cite_note-2).

I guess I should have actually read my references, not skimmed ;-)