# Mystery: StringProtocol.compare\<T\>(...) -\> ComparisonResult: sort works as expect, map give incorrect result

**URL:** <https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971>\
**Category:** Using Swift\
**Created:** [February 22, 2021, 3:35am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971 "2021-02-22T03:35:55Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![young](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/young/32/7878_2.png) [@young](https://forums.swift.org/u/young)\
**Post date:** [February 22, 2021, 3:35am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/1 "2021-02-22T03:35:55Z")

</div>

```swift
import Foundation

let original = ["Kofi", "Abena", "Peter", "Kweku", "Akosua", "abena", "bee", "ábenā"]
// the compare closure works for sorting
let sorted = original.sorted { $0.compare($1, options: [.diacriticInsensitive, .caseInsensitive]) == .orderedAscending }
// but here doesn't work:
// find the accending order true/false value of the array compare to string "ábenā"
// using the exact same closure as above
// but this is not returning the expected result comparing to the sorted array
let orderTrueFalse = sorted.map { $0.compare("ábenā", options: [.diacriticInsensitive, .caseInsensitive]) == .orderedAscending }

print("original", original)
print("sorted", sorted)
print("orderTrueFalse", orderTrueFalse)
// print:
// original ["Kofi", "Abena", "Peter", "Kweku", "Akosua", "abena", "bee", "ábenā"]
// sorted ["Abena", "abena", "ábenā", "Akosua", "bee", "Kofi", "Kweku", "Peter"]
// orderTrueFalse [false, false, false, false, false, false, false, false]
// why it's not [true, true, false, false, false, false, false, false]

```

---

<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:** [February 22, 2021, 3:54am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/2 "2021-02-22T03:54:44Z")

</div>

Try this:

```swift
let order = sorted.map { $0.compare("ábenā", options: [.diacriticInsensitive, .caseInsensitive]) }
let orderIsAscending = order.map { $0 == .orderedAscending }
let orderIsSame = order.map { $0 == .orderedSame }
let orderIsDescending = order.map { $0 == .orderedDescending }
print("orderIsAscending", orderIsAscending)
print("orderIsSame", orderIsSame)
print("orderIsDescending", orderIsDescending)

```

They're ignoring diacritics and cases, so they compare equal instead of ascending.

---

<div class="post-metadata">

**Author:** ![QuinceyMorris](https://avatars.discourse-cdn.com/v4/letter/q/d26b3c/32.png) [@QuinceyMorris](https://forums.swift.org/u/QuinceyMorris)\
**Post date:** [February 22, 2021, 3:58am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/3 "2021-02-22T03:58:56Z")

</div>

Couldn't we just give the explanation here, which is that (with those options) "ábenā" is _ **not** _ bigger than (`.orderedAscending` relative to) anything in the list?

(Edit: OK, I see you added the explanation. 🙂 )

---

<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:** [February 22, 2021, 4:05am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/4 "2021-02-22T04:05:15Z")

</div>

TBH, I wasn't even sure that's where the confusion is in the beginning. Could be that @young forget that comparison has three results. I do that a few times, hehe (I mean, what even is [trichonomy](https://en.wikipedia.org/wiki/Trichotomy_(mathematics))?). Could also be that they forgot that diacritic & case insensitivity is set, or how they work.

At least the code compiles, and I can see what they got vs expect. So that's better than a majority of questions already.

---

<div class="post-metadata">

**Author:** ![young](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/young/32/7878_2.png) [@young](https://forums.swift.org/u/young)\
**Post date:** [February 22, 2021, 4:22am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/5 "2021-02-22T04:22:06Z")

</div>

> [@Lantua](#):
>
> They're ignoring diacritics and cases, so they compare equal instead of ascending.

I see. So how did the sorted() with the same `compare(...) == orderedAscending` compute the ordering? So the comparison is always false, then the order should not change:

```swift
let hm = original.sorted {_, _ in false }
print(hm)
// print ["Kofi", "Abena", "Peter", "Kweku", "Akosua", "abena", "bee", "ábenā"]

```

I wasn't even thinking and was not aware of what this does:

```swift
$0.compare($1, options: [.diacriticInsensitive, .caseInsensitive]) == .orderedAscending

```

I got this from some example of how to sort string with diacritics because I need to sort things this way. I simply plug the compare expression into my search function and didn't get the result I expected.

Anyway, the sorted() did come to some new order, how did it find the order, if the compare expression is always `false`?

---

<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:** [February 22, 2021, 4:40am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/6 "2021-02-22T04:40:25Z")

</div>

> [@young](#):
>
> So the comparison is always false, then the order should not change:

There're a few steps here. Firstly, [`sort`](https://developer.apple.com/documentation/swift/array/2296801-sort) requires you to adhere to a few assumptions:

> `areInIncreasingOrder` must be a _strict weak ordering_ over the elements. That is, for any elements `a` , `b` , and `c` , the following conditions must hold:
> 
> - `areInIncreasingOrder(a, a)` is always `false` . (Irreflexivity)
> - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true` , then `areInIncreasingOrder(a, c)` is also `true` . (Transitive comparability)
> - Two elements are _incomparable_ if neither is ordered before the other according to the predicate. If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable. (Transitive incomparability)

Just like `hash(into:)`, violating these requirements is generally a bug, and the result is undefined behaviour. Luckily _always return false_ adhere to these rules, so the result is (relatively) defined. `sort` ensures that if `areInIncreasingOrder(a, b)` returns true, then `a` will precede `b` in the sorted list.

Now, what does it mean when `areInIncreasingOrder` always returns false? If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, a)` are both false, then it means that in a sorted list, `a` can be placed before or after `b`.

Is it required that the sorted list is in the exact same order? Not generally. If you sort `[(1, "a"), (1, "b")]` by the first member, then `[(1, "b"), (1, "a")]` is a perfectly valid result, `1` and `1` are next to each other in the sorted list, after all.

What you need is called "stable" sorts, where equal elements appear in the same order that it appears in the original list. Unfortunately, `Array.sorted` is apparently not stable.

> The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements for which `areInIncreasingOrder` does not establish an order.

So what exactly is that order that the result returns? Well, that's an implementation detail. If it uses quicksort, it would be in one particular order and another order in merge sort. You see, many algorithms just assume that you can swap equal elements without problem (which is a pretty good optimization).

So if you want to make sure that "equal" elements appear in the same order that they appear, you need to encode it into the array somehow. One way is to add `offset` into the array before sorting, and strip it off afterward:

```swift
let ok = original.enumerated().sorted { false || $0.offset < $1.offset }.map { $0.element }
print(ok) // ["Kofi", "Abena", "Peter", "Kweku", "Akosua", "abena", "bee", "ábenā"]

```

---

<div class="post-metadata">

**Author:** ![QuinceyMorris](https://avatars.discourse-cdn.com/v4/letter/q/d26b3c/32.png) [@QuinceyMorris](https://forums.swift.org/u/QuinceyMorris)\
**Post date:** [February 22, 2021, 4:57am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/7 "2021-02-22T04:57:07Z")

</div>

> [@young](#):
>
> Anyway, the sorted() did come to some new order, how did it find the order, if the compare expression is always `false` ?

Specifically, your problem is here in your question.

In `orderTrueFalse`, you didn't compare array elements _ **with each other** _. You compared array elements _ **with `"ábenā"`** _.

"ábenā" is less than or equal to everything in the array. So, it isn't greater than ( `.orderedAscending` relative to) anything in the array. So you always get `false`.

---

<div class="post-metadata">

**Author:** ![young](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/young/32/7878_2.png) [@young](https://forums.swift.org/u/young)\
**Post date:** [February 22, 2021, 5:50am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/8 "2021-02-22T05:50:11Z")

</div>

Ok. I think I cannot sort the way I did and do binary search on that. I need to keep two separate "sorted" arrays: one sorted the way I did for UI presentation and another sorted with "`<`" comparison for search.

Is this right?

---

<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:** [February 22, 2021, 5:58am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/9 "2021-02-22T05:58:45Z")

</div>

That's one way to do it. TBH, it's quite a hassle to synchronize the two objects, so I don't usually use that approach.

You can also use one array that sort with diacritic & case insensitive options, _then_ break a tie with the order of the original list. If I understand your UI requirements correctly, that would work with your UI (it definitely works with binary search, given you appropriately handle duplicates). This is similar to what I showed earlier:

```swift
let sorted = original.enumerated().sorted {
    switch $0.element.compare($1.element, options: [.diacriticInsensitive, .caseInsensitive]) {
    case .orderedAscending: return true
    case .orderedSame: return $0.offset < $1.offset
    case .orderedDescending: return false
    }
} .map { $0.element }
print(sorted)
// ["Abena", "abena", "ábenā", "Akosua", "bee", "Kofi", "Kweku", "Peter"]

```

Here, `"Abena"`, `"abena"`, `"ábenā"` are grouped together, ordered by their appearance in `original`.

> [@young](#):
>
> I think I cannot sort the way I did and do binary search on that.

Binary search can handle duplicates. If you want the search to return `"Abena"`, `"abena"`, `"ábenā"` when you look for `AbEnA`, you can search twice, once to find the first element, and again to find the last.

```swift
let searchTerm = ...
let firstIndex = sorted.binarySearch {
  $0.element.compare(searchTerm.element, options: [.diacriticInsensitive, .caseInsensitive]) != .orderAscending
}
let endIndex = sorted.binarySearch {
  $0.element.compare(searchTerm.element, options: [.diacriticInsensitive, .caseInsensitive]) == .orderDescending
}

return sorted[firstIndex..<lastIndex]

```

Depending on how `binarySearch` is defined, you may want to tweak the condition, but that's the idea.

* * *

Edit:

One thing I forgot to mention is that, having separate arrays as you said _always works_ simply because you're maintaining separate structure for UIs and searches. Though if your search criteria is stricter than the UI criteria (text that are the _same_ from the UI perspective is _different_ from search perspective), or the converse is true (text that are the _same_ from the search perspective is _different_ from UI perspective), then you can use one array, as I mentioned above.

---

<div class="post-metadata">

**Author:** ![young](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/young/32/7878_2.png) [@young](https://forums.swift.org/u/young)\
**Post date:** [February 22, 2021, 5:28pm UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/11 "2021-02-22T17:28:29Z")

</div>

> [@Lantua](#):
>
> given you appropriately handle duplicates

There is no duplicate, entries are unique. So `"Abena", "abena", "ábenā"` are different entries, just need to present to user in sorted order of "`[.diacriticInsensitive, .caseInsensitive]`" . My binary search would work if I can come up with a compare predicate that tell the ordering given a target like "ábenā".

For my example after sorted:

> ["Abena", "abena", "ábenā", "Akosua", "bee", "Kofi", "Kweku", "Peter"]

Search for `"ábenā"`

I need a compare predicate the give me the `isInAccendingOrder`:

> [true, true, false, false, false, false, false, false]

---

<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:** [February 22, 2021, 5:54pm UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/12 "2021-02-22T17:54:06Z")

</div>

I'd like to first warn that it's very fishy that the UI treats `"Abena"` and `"abena"` as the same string, but the search treats them differently. It doesn't sound like the best design if the list screams _I'm aware of the diacritics and handled it for you_, then the search bar screams _actually not_.

However, if you insist, I can see two ways that you can deal with that.

1. Use separate arrays as you suggested, one sorted with `StringProtocol.compare` for UI appearance\* and another with `String.<` for searching.

2. Break the `StringProtocol.compare` ties with `String.<` so that you can use the same array,

\* Even then, you want to make sure to break the ties as `sorted` is unstable. If you sort it again the entire UI may need to be updated if the sort algorithm puts _incomparable_ things in a different order, which could happen even if you just add/remove unrelated strings.

---

<div class="post-metadata">

**Author:** ![young](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/young/32/7878_2.png) [@young](https://forums.swift.org/u/young)\
**Post date:** [February 23, 2021, 1:02am UTC](https://forums.swift.org/t/mystery-stringprotocol-compare-t-comparisonresult-sort-works-as-expect-map-give-incorrect-result/44971/13 "2021-02-23T01:02:23Z")

</div>

👍 Now I understand why

> `.sorted { $0.compare($1, options: [.diacriticInsensitive, .caseInsensitive]) == .orderedAscending }`

is enough to sort the sample elements. But for search it doesn't work and needs the more "able" predicate.

Thanks!
