Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 146 ยท Collections

Sorting and Searching Arrays

Sort and search Swift arrays with sort, sorted, sorted(by:), keypath and multi-key ordering, firstIndex, binary search, partition and reversed - with costs and common mistakes.

Putting things in order and finding things again are the two oldest jobs in programming. Swift's standard library does both well: sort and sorted are fast, firstIndex and contains handle linear searches, and with a few lines you can add binary search for sorted data. Knowing which tool to pick, and what each one costs, is what separates code that is merely correct from code that stays fast when the data grows.

This lesson walks through in-place and copying sorts, custom orderings (descending, by a property, by several keys), the Comparable protocol, searching linearly and by halving, partition, and the lazy reversed(). It builds on Arrays and uses closures from Closures.

sort versus sorted

There are two spellings of every sorting method, and the difference is the same as with other mutating pairs in Swift. sort() reorders the array in place and needs var. sorted() leaves the original alone and returns a new array, so it works on let constants and on any sequence, not just arrays.

Swift sort() and sorted()

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Both default to ascending order using <, so the element type must be Comparable. Strings compare by Unicode scalar values by default, so every uppercase letter sorts before every lowercase one: "Zebra" comes before "apple", as the "Apple" in the output above is first only because it is the only capitalized word. For human-friendly alphabetical order, compare with localizedStandardCompare from Foundation, or lowercase the keys.

Sorting a type that is not Comparable

If the elements have no default ordering, sort() does not exist for them, and the compiler tells you so:

Swift No default ordering (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The diagnostic says that sorted() on a Sequence requires Player to conform to Comparable, and a note shows the extension it came from (where Self.Element : Comparable). You have two fixes. Either supply the ordering at the call site with a closure, or teach the type to compare itself once with Comparable so sorted(), min(), max() and < all work.

Custom orderings with sorted(by:)

sorted(by:) takes a closure (Element, Element) -> Bool that answers "should the first argument come before the second?". It must be a strict weak ordering: false when the two elements are equal (use <, never <=), and consistent. Violating that does not crash, but results become unpredictable.

Swift Ordering by a property

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Notice that Ada and Cy both have 90. The documentation does not promise that equal elements keep their original order (the sort is not guaranteed stable), although in current releases sort happens to be stable. Do not depend on it; if ties must resolve in a particular way, say so explicitly with a second key.

Sorting by several keys

Compare tuples. Swift compares tuples element by element from the left and stops at the first difference, which is exactly "sort by score, then by name":

Swift Multi-key ordering with tuples

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The trick is the swapped $1.score, $0.name: the first element is reversed to get descending scores, the second is not, so names ascend. If that looks too clever, write it with explicit if:

Swift
// read-only example
players.sorted {
    if $0.score != $1.score { return $0.score > $1.score }
    return $0.name < $1.name
}

Making a type Comparable

When one ordering is the obvious one for a type, adopt Comparable. You only write <; Equatable can be synthesized, and >, <=, >= come for free.

Swift Conforming to Comparable

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Searching linearly

For an unsorted array, searching means looking at the elements one by one, which is O(n). The standard tools are contains, first(where:), firstIndex(of:), firstIndex(where:), lastIndex(where:) and allSatisfy.

Swift Linear search tools

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

All of these return optionals when they look for a position or element, since the answer may be "not found". Unwrap them with if let or guard let. Counting matches with filter { ... }.count allocates a temporary array; count(where:) (available in Swift 6) does the same job without it.

Binary search on sorted data

If the array is already sorted, you can find a value in O(log n) steps by repeatedly halving the range: look at the middle element and throw away the half that cannot contain the target. A million elements need about twenty comparisons instead of a million.

The standard library does not ship a general binary search for arrays, but the algorithm is short. This version returns the lower bound: the first index whose element is not less than the target. That is more useful than a plain yes/no, because it also tells you where a missing value would be inserted.

Swift Binary search and lower bound

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Two cautions. First, binary search on an unsorted array returns nonsense, not an error: always sort first, or keep the array sorted as you insert. Second, the mid-point is computed from distance rather than (low + high) / 2, which avoids integer overflow for huge ranges and also works for slices whose indices do not start at zero.

If you search the same data many times, a Set or Dictionary (Sets, Dictionaries) answers "is it there?" in constant time with no sorting required. Keep a sorted array when you need ordered traversal, ranges ("everything between 10 and 20") or the lower-bound position.

partition

partition(by:) rearranges the array in place so that all elements failing the predicate come first and all elements satisfying it come last. It returns the index where the second group starts. It does not preserve order inside either group, and it is O(n), which makes it the building block of quicksort and of "move all the negatives to the end" tasks.

Swift Partitioning in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

If you need the groups as separate arrays and want to keep their order, two filter calls (or reduce(into:)) are clearer, at the cost of two passes and two allocations.

reversed

reversed() on an array does not build a new array. It returns a ReversedCollection, a lightweight view that walks backward, so it is O(1) to create. Wrap it in Array(...) when you need real storage.

Swift reversed() is a view

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Costs and good habits

  • sort is O(n log n) in the worst case (an introsort/timsort-style hybrid); sorting an already almost-sorted array is fast.
  • Do not sort inside a loop when you can sort once outside it.
  • If you only need the largest few items, sorted().prefix(3) still sorts everything. For huge inputs consider keeping a small heap or using max(by:) repeatedly.
  • Calling sorted(by:) with an expensive key (like $0.name.lowercased()) recomputes the key on every comparison. Precompute keys with map first when it matters.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the difference between sort() and sorted()?

    By Swift's naming convention, the verb form mutates and the participle form returns a new value.
  2. 2. Why does [Player(...)].sorted() fail to compile?

    The no-argument sort relies on <, so the elements must be Comparable. Otherwise pass sorted(by:).
  3. 3. What must be true before you use binary search?

    Binary search discards half the range at each step based on the order. On unsorted data it returns wrong answers without any error.
  4. 4. What does reversed() return for an Array?

    The non-mutating reversed() is O(1); reverse() is the in-place version.
  5. 5. In sorted { ($1.score, $0.name) < ($0.score, $1.name) }, what order results?

    Swapping $0 and $1 for the score reverses that key. The name stays $0 < $1, so names ascend within equal scores.

Summary

  • sort() mutates a var array; sorted() returns a new one and works on any sequence. Both are O(n log n).
  • The default order needs Comparable; otherwise use sorted(by:) with a strict weak ordering (<, not <=).
  • Compare tuples to sort by several keys; swap $0 and $1 to reverse one key.
  • Linear search tools (contains, firstIndex, first(where:)) are O(n) and return optionals.
  • Binary search needs sorted input and finds a position in O(log n); a lower-bound function is the most useful form.
  • partition(by:) splits in place without keeping order; reversed() is a cheap lazy view.

Next: Sets