Sorted and custom comparators in Swift - Time & Space Complexity

Time Complexity: Sorted and custom comparators

O(n log n)

Understanding Time Complexity

When we sort items using Swift's sorted method with a custom comparator, we want to know how the time it takes changes as the list grows.

We ask: How does sorting time grow when we have more items to sort?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let numbers = [5, 3, 8, 1, 2]
let sortedNumbers = numbers.sorted { a, b in
    return a < b
}
print(sortedNumbers)
    

This code sorts an array of numbers in ascending order using a custom comparison closure.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting algorithm repeatedly compares pairs of elements using the custom comparator.
• How many times: The number of comparisons grows as the sorting algorithm processes the list, depending on the sorting method used internally.

How Execution Grows With Input

As the list gets bigger, the number of comparisons needed to sort grows faster than the list size itself.

Input Size (n)	Approx. Operations
10	About 30 comparisons
100	About 700 comparisons
1000	About 10,000 comparisons

Pattern observation: The number of operations grows roughly like n log n, meaning doubling the list size makes the work about twice as much (plus a bit more).

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as the list grows, but not as fast as checking every pair; it grows a bit faster than just the list size.

Common Mistake

[X] Wrong: "Sorting with a custom comparator always takes longer than sorting with default methods."

[OK] Correct: The custom comparator only changes how two items are compared, not the overall sorting method. The time mainly depends on the number of items, not the comparator itself.

Interview Connect

Understanding how sorting time grows helps you explain your code choices clearly and shows you know how to handle data efficiently in real projects.

Self-Check

What if we changed the custom comparator to sort in descending order? How would the time complexity change?

Practice

1. What does the sorted(by:) method do in Swift?

easy

A. It sorts an array using a custom rule you provide.

B. It removes duplicate elements from an array.

C. It reverses the order of elements in an array.

D. It filters elements based on a condition.

Solution

1. Step 1: Understand the purpose of sorted(by:)

   This method sorts elements of an array based on a closure that defines the order.

2. Step 2: Compare with other array methods

   Unlike filtering or reversing, sorted(by:) changes order based on a custom rule.

3. Final Answer:

   It sorts an array using a custom rule you provide. -> Option A

4. Quick Check:

   sorted(by:) = custom sorting [OK]

Hint: Remember: sorted(by:) arranges items your way [OK]

Common Mistakes:

• Confusing sorting with filtering
• Thinking it removes duplicates
• Assuming it reverses the array

2. Which of the following is the correct syntax to sort an array of integers in descending order using sorted(by:)?

easy

A. let sortedArray = numbers.sorted(by: { $1 > $0 })

B. let sortedArray = numbers.sorted(by: { $0 < $1 })

C. let sortedArray = numbers.sorted()

D. let sortedArray = numbers.sorted(by: { $0 > $1 })

Solution

1. Step 1: Understand sorting order

   To sort descending, the comparator must return true when the first element is greater than the second.

2. Step 2: Check each option

   let sortedArray = numbers.sorted(by: { $0 > $1 }) uses { $0 > $1 } which sorts descending. let sortedArray = numbers.sorted(by: { $0 < $1 }) sorts ascending. let sortedArray = numbers.sorted() sorts ascending by default. let sortedArray = numbers.sorted(by: { $1 > $0 }) reverses the comparison incorrectly.

3. Final Answer:

   let sortedArray = numbers.sorted(by: { $0 > $1 }) -> Option D

4. Quick Check:

   Descending sort uses $0 > $1 [OK]

Hint: Use $0 > $1 for descending sort [OK]

Common Mistakes:

• Using $0 < $1 for descending
• Forgetting to provide closure for custom order
• Confusing parameter order in closure

3. What is the output of the following Swift code?

let names = ["Anna", "Bob", "Charlie"]
let sortedNames = names.sorted(by: { $0.count < $1.count })
print(sortedNames)

medium

A. ["Bob", "Charlie", "Anna"]

B. ["Bob", "Anna", "Charlie"]

C. ["Charlie", "Anna", "Bob"]

D. ["Anna", "Bob", "Charlie"]

Solution

1. Step 1: Understand the sorting rule

   The closure sorts by string length ascending: shorter names come first.

2. Step 2: Apply sorting to the array

   "Bob" has 3 letters, "Anna" 4, "Charlie" 7. So order is ["Bob", "Anna", "Charlie"].

3. Final Answer:

   ["Bob", "Anna", "Charlie"] -> Option B

4. Quick Check:

   Sort by length ascending = ["Bob", "Anna", "Charlie"] [OK]

Hint: Sort by $0.count < $1.count for shortest first [OK]

Common Mistakes:

• Sorting alphabetically instead of by length
• Confusing < with > in closure
• Expecting original order

4. Identify the error in this Swift code that tries to sort an array of tuples by the second value:

let items = [("a", 3), ("b", 1), ("c", 2)]
let sortedItems = items.sorted(by: { $0.1 > $1.1 })
print(sortedItems)

medium

A. There is no error; the code sorts descending by second value.

B. The tuple elements cannot be accessed by index like $0.1.

C. The closure parameters should be $1.1 > $0.1 for ascending order.

D. The sorting closure must return an Int, not Bool.

Solution

1. Step 1: Check tuple access syntax

   Accessing tuple elements by $0.1 and $1.1 is correct in Swift closures.

2. Step 2: Verify sorting closure logic

   The closure returns true if first element's second value is greater, sorting descending by second value.

3. Final Answer:

   There is no error; the code sorts descending by second value. -> Option A

4. Quick Check:

   Tuple access and Bool return are correct [OK]

Hint: Tuple elements accessed as $0.1; closure returns Bool [OK]

Common Mistakes:

• Thinking tuple elements can't be accessed by index
• Expecting closure to return Int
• Confusing ascending and descending order

5. You have an array of dictionaries representing people: let people = [["name": "Alice", "age": 30], ["name": "Bob", "age": 25], ["name": "Charlie", "age": 30]]. How do you sort this array first by age ascending, then by name ascending if ages are equal?

hard

A. people.sorted { $0["age"] as! Int < $1["age"] as! Int && $0["name"] as! String < $1["name"] as! String }

B. people.sorted(by: { $0["age"] as! Int > $1["age"] as! Int || $0["name"] as! String > $1["name"] as! String })

C. people.sorted { ($0["age"] as! Int, $0["name"] as! String) < ($1["age"] as! Int, $1["name"] as! String) }

D. people.sorted(by: { $0["name"] as! String < $1["name"] as! String })

Solution

1. Step 1: Understand sorting by multiple keys

   Sorting by age ascending, then name ascending means comparing tuples of (age, name).

2. Step 2: Check each option's logic

   people.sorted { ($0["age"] as! Int, $0["name"] as! String) < ($1["age"] as! Int, $1["name"] as! String) } compares tuples directly, which sorts by age first, then name if ages equal. people.sorted { $0["age"] as! Int < $1["age"] as! Int && $0["name"] as! String < $1["name"] as! String } uses && which fails for correct ordering. people.sorted(by: { $0["age"] as! Int > $1["age"] as! Int || $0["name"] as! String > $1["name"] as! String }) sorts descending and mixes conditions incorrectly. people.sorted(by: { $0["name"] as! String < $1["name"] as! String }) sorts only by name.

3. Final Answer:

   people.sorted { ($0["age"] as! Int, $0["name"] as! String) < ($1["age"] as! Int, $1["name"] as! String) } -> Option C

4. Quick Check:

   Tuple comparison sorts by multiple keys [OK]

Hint: Compare tuples (age, name) for multi-level sorting [OK]

Common Mistakes:

• Using && instead of tuple comparison
• Sorting only by one key
• Mixing ascending and descending incorrectly