Problem overview
The method sort(_ nums: inout [Int]) must sort an array of integers in ascending order, in place, with Selection Sort. It returns nothing: the caller's array is changed. For [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5]. Duplicates stay, and each value appears as often as before.
The statement sets O(n^2) time and O(1) extra space. Selection Sort meets both: it uses two nested loops and needs no second array.
Approach: fill the positions from left to right
Selection Sort builds the sorted array one position at a time. The outer loop visits the positions in order. For position i, the goal is to put the smallest value from i onward there. When position i is done, everything before position i + 1 is in its final place, so later passes never touch it.
The inner loop looks at every position j after i. Whenever it finds a value smaller than the one at i, it swaps them. By the end of the inner loop, nums[i] holds the minimum of the whole tail.
Here is the first pass on [3, 1, 3, 2, 5, 4] with i = 0. At j = 1 the 1 is smaller than the 3, so they swap and the array becomes [1, 3, 3, 2, 5, 4]. No later value is smaller than 1, so position 0 is finished. The pass for i = 1 swaps the 3 with the 2 (at j = 3) and gives [1, 2, 3, 3, 5, 4]. Positions 2 and 3 need no change, and the pass for i = 4 swaps 5 and 4 to give [1, 2, 3, 3, 4, 5].
This version swaps every time it sees a smaller value. The textbook form instead remembers the index of the smallest value and makes a single swap per pass. Both give the same sorted array. The remembering form does fewer swaps: on [5, 4, 3, 2, 1] the lesson's version swaps 10 times, while the other makes at most one swap per pass. The lesson's version is simpler to write.
In everyday Swift you would call the standard library's nums.sort(), which sorts in place and runs in O(n log n) time. Writing Selection Sort by hand is practice with loops, swaps and in-place updates, and it is the simplest sorting algorithm to reason about.
The single-swap form looks like this in Swift:
func classic(_ nums: inout [Int]) {
for i in 0..<nums.count {
var m = i
for j in (i + 1)..<nums.count {
if nums[j] < nums[m] { m = j }
}
if m != i { nums.swapAt(i, m) }
}
}
On [3, 1, 3, 2, 5, 4] it also produces [1, 2, 3, 3, 4, 5]. The rest of this article follows the lesson's version.
Step by step
- Outer loop.
for i in 0..<nums.countvisits each position that needs its final value. - Inner loop.
for j in (i + 1)..<nums.countcompares positionionly with the positions after it. Positions beforeiare already final. - Compare.
if nums[i] > nums[j]detects a smaller value to the right. With>instead of>=, equal values are never swapped, which avoids pointless work. - Write the swap helper. It takes the array as
inoutand two indices. It savesnums[i]intemp, copiesnums[j]intonums[i], and putstempinnums[j]. Without the temporary, the first assignment would overwritenums[i]and lose its old value. - Call it. Inside the
if, callswap(&nums, i, j). The&marks an argument passed to aninoutparameter.
The solution in Swift
class Solution {
func swap(_ nums: inout [Int], _ i: Int, _ j: Int) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
func sort(_ nums: inout [Int]) {
for i in 0..<nums.count {
for j in (i + 1)..<nums.count {
if nums[i] > nums[j] {
swap(&nums, i, j)
}
}
}
}
}
The Swift details worth knowing:
- Arrays are values. A normal parameter is a constant copy. Assigning to
nums[0]in a method with a plainnums: [Int]parameter is a compile error:'nums' is a 'let' constant. Marking itinoutmakes the method work on the caller's array instead. - The call site needs
&. Callingswap(nums, i, j)without it fails withpassing value of type '[Int]' to an inout parameter requires explicit '&'. The caller must also pass avar, since aletarray cannot be changed. - The underscores.
_ nums,_ iand_ jdrop the argument labels, so calls readswap(&nums, i, j). - A built-in swap. Swift arrays have
swapAt(_:_:), sonums.swapAt(i, j)does the same job. The lesson writes the swap out to show how it works. - Empty ranges. When
iis the last index,(i + 1)..<nums.countis empty, so the inner loop does nothing. An empty array gives0..<0, and the method leaves it unchanged.
Complexity
Time: O(n^2). The inner loop runs n - 1 times for i = 0, n - 2 times for i = 1, and so on, so the comparisons total n(n - 1)/2 whatever the input order. The number of swaps depends on the input, but it never exceeds the number of comparisons.
Space: O(1). The array is sorted in place. The method uses a few integers: the loop variables and temp.
Edge cases and common mistakes
- Empty and single-element arrays.
[]stays[]and[9]stays[9]. - Already sorted input. No comparison finds a smaller value, so no swap happens, but the loops still run, so the time stays
O(n^2). - Reverse order.
[5, 4, 3, 2, 1]becomes[1, 2, 3, 4, 5]. - All equal values.
[2, 2, 2]is unchanged, since>never fires. - Negative numbers.
[-1, 5, -10, 0]becomes[-10, -1, 0, 5]. - Starting the inner loop at
i. It compares an element with itself, which never swaps but wastes a step. Starting ati + 1avoids it. - Swapping without a temporary. Writing
nums[i] = nums[j]and thennums[j] = nums[i]leaves both positions with the same value.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[]stays[].[9]stays[9].[5, 4, 3, 2, 1]becomes[1, 2, 3, 4, 5].[-1, 5, -10, 0]becomes[-10, -1, 0, 5].
