Sorting in Swift: sort(), sorted() and Custom Closures

In order to sort an array we can use the .sort() method which sorts the elements of a given array in ascending order (default), descending order, or with a custom closure.

Similarly, .sorted() returns a new sorted array without modifying the original.

Important: .sort() changes the array it is called on, so the array must be declared with var. A let array can only be sorted with .sorted(), which returns a new array.

Syntax:

Let's see some examples below. Sorting an array of integers in ascending order

var numbers = [11, 3, 7, 5, 2]

numbers.sort() // numbers becomes [2, 3, 5, 7, 11]

Sorting an array of integers in ascending order using .sorted()

var arr = [11, 3, 7, 5, 2]

let sorted = arr.sorted() // sorted becomes [2, 3, 5, 7, 11]

Sorting an array of integers in descending order

var numbers = [11, 3, 7, 5, 2]

numbers.sort(by: >) // numbers becomes [11, 7, 5, 3, 2]

In Swift, sorting in reverse is simple: just pass by: >. The operator > is itself a function that takes two values and returns a Bool, so it works for any element type that can be compared with it.

Sorting an array of Strings in descending order

var names = ["Mircea", "Andy", "Xavier", "Michael", "Christina"]

names.sort(by: >) // --> ["Xavier", "Mircea", "Michael", "Christina", "Andy"]

Sort with custom closure (comparator):

The .sort() method supports a closure that we can use to specify how we want to sort. The closure takes two elements and returns Bool: return true if the first element should come before the second.

func compare(_ a: Int, _ b: Int) -> Bool {
    return a < b
}

The same function can be written as a closure expression (a nameless function we can easily pass to sort()) as follows:

{ (a: Int, b: Int) -> Bool in
    return a < b
}

If the closure just returns one thing, we can write it as follows:

{ a, b in a < b }

When the sort() method compares two values, it sends the values to the closure, and sorts the values according to the returned Bool:

• If the result is true, a is sorted before b.
• If the result is false, b is sorted before a.

All we need to do is pass the closure to the sort() method, either in parentheses or, as below, as a trailing closure written after the method name:

var numbers = [3, 23, 12]

// using the short version of the closure
numbers.sort { a, b in a < b } // --> [3, 12, 23]

To demonstrate a basic example, let's assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the count property of each string to compare them.

var words = ["banana", "pie", "Washington", "book"]

words.sort { a, b in a.count < b.count } // --> ["pie", "book", "banana", "Washington"]

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array consisting of two numbers.

We will be using [[Int]] — an array of Int arrays — which can be sorted with a custom closure.

var pairs = [[1, 5], [12, 5], [10, 1], [1, 3]]

pairs.sort { a, b in
    // in case the first values of each pair are equal,
    // compare them using their second values
    if a[0] == b[0] {
        return a[1] < b[1]
    }
    return a[0] < b[0]
}
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]

Time Complexity:

Sorting an array via .sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.

It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort() method sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so no second array is created for the result. Internally the sort may use some temporary memory, so the extra space is O(1) to O(n) depending on the implementation; .sorted() needs O(n) for the new array.

Assignment
Follow the Coding Tutorial and let's sort some arrays.

Hint
Look at the examples above if you get stuck.