How does the sorted method work in reverse in Swift?

Question

let names = ["Chris", "Alex", "Ewa", "Barry", "Daniella"]


func backward(_ s1: String, _ s2: String) -> Bool {
     return s1 > s2
}
var reversedNames = names.sorted(by: backward)
// reversedNames is equal to ["Ewa", "Daniella", "Chris", "Barry", "Alex"]

Because arguments are passed to the backwards function, it is difficult to understand what is happening. How does this code work?

Answer 1

@matt's answer is excellent. Please keep it as the accepted answer. I'd like to expand on it a bit.

When you pass your function backward to sorted(), behind the scenes, in code that you don't see, it calls backward multiple times to compare two items. To expose this behavior, add a print statement to backward:

func backward(_ s1: String, _ s2: String) -> Bool {
     print("backward comparing \(s1) and \(s2)")
     return s1 > s2
}

Then when you run:

var reversedNames = names.sorted(by: backward)

you will see:

backward comparing Alex and Chris
backward comparing Ewa and Alex
backward comparing Ewa and Chris
backward comparing Barry and Alex
backward comparing Barry and Chris
backward comparing Daniella and Alex
backward comparing Daniella and Barry
backward comparing Daniella and Chris
backward comparing Daniella and Ewa

So even though we don't see the sorted() code, it is obviously calling backward multiple times to compare the items in order to sort them.

There are numerous sorting algorithms, but they all have one thing in common. It is necessary to compare the items two at a time in the process of sorting them.

---

Case Study: Insertion Sort

Let's look at a real sorting algorithm and how it uses the sorting function that you pass it.

Below is an implementation of an insertion sort which is a very simple algorithm. Imagine you are given five playing cards to sort.

1. Place the cards on a table, and then pick up the first one in your left hand. The cards in your left hand are the sorted cards. Since you only have one, the cards in your left hand are sorted by default.
2. Now pick up a second card with your right hand and insert it into the correct place in your left hand. In order to do this, you will have to compare the card in your right hand to the cards in your left hand to find the right insertion point. Since you have just two cards, you just have to compare them to decide if the new card goes before or after the first card.
3. Continue this process of picking up a card and inserting it into the right location for each card on the table until you are holding all of the cards in your left hand.
4. The cards in your left hand are now sorted.

Here is insertion sort:

// Sort array by building up the sorted result array, inserting the
// items one at a time into the result array which is always sorted
func insertionSort(array original: [String], by comesBefore: (String, String) -> Bool) -> [String] {
    // start the result array off with the first item from the
    // original
    var result = original.isEmpty ? [] : [original.first!]

    // For every other item in the original array, find out where
    // it goes and insert it there
    for item in original.dropFirst() {
        // Have we found the insertion point?
        var found = false

        // The current insertion point into the result array
        var newidx = 0

        // Loop while we haven't found the insertion point for the
        // current item and we haven't reached the end of the result
        // array
        while !found && newidx < result.count {
            // call the passed-in function to decide if the new item comes
            // before the current item of the result array
            if comesBefore(item, result[newidx]) {
                // Great!  The current item comes before result[newidx],
                // so we now know where to insert it
                found = true
            } else {
                // Item doesn't come before result[newidx], so let's move
                // on to the next index
                newidx += 1
            }
        }

        // Having found the insertion point, insert item into the result
        // array
        result.insert(item, at: newidx)
    }

    // Return the result array which now contains all of the items
    // which have been sorted by inserting them into the correct spots
    return result
}

Now, run it:

let reversedNames = insertionSort(array: names, by: backward)

backward comparing Alex and Chris
backward comparing Ewa and Chris
backward comparing Barry and Ewa
backward comparing Barry and Chris
backward comparing Barry and Alex
backward comparing Daniella and Ewa
backward comparing Daniella and Chris

print(reversedNames)

["Ewa", "Daniella", "Chris", "Barry", "Alex"]

So, you see that the function you pass to insertionSort() is used to decide the order of the items. As @matt said, by taking a function, the sort lets you decide what comes before means.

Answer 2

The sorted method, sent to an array, obtains elements of that array in pairs and decides which one comes first. By applying that to all the elements of the array, it ends up with a sorted array.

But what does "comes first" mean? It can mean anything! The fact is, you get to decide what it means. To tell the sorted method what "comes first" means, you hand it, as argument, a function that takes two elements and returns a Bool saying whether the first element "comes first".

Well, backward is such a function:

func backward(_ s1: String, _ s2: String) -> Bool {
    return s1 > s2
}

The backward function says: the first argument "comes first" in relation to the second argument only if it is larger.

Now we hand the backward function to the sorted method:

var reversedNames = names.sorted(by: backward)

Notice that backward there is not a call to the backward function; it is the name of the backward function. We hand the function itself to sorted so it knows what "comes first" means.

So sorted ends up returning an array where every larger element "comes first" in relation to every smaller element. For strings, "larger" means "later in the alphabet", so we get ["Ewa", "Daniella", "Chris", "Barry", "Alex"].