Problem overview
The function sort receives a vector of integers, nums, and returns it in ascending order. The lesson asks for Selection Sort, which runs in O(n^2) time and uses O(1) extra space: the sorting happens inside the vector, with no second vector.
For nums = [3, 1, 3, 2, 5, 4] the result is [1, 2, 3, 3, 4, 5]. Duplicates stay in the output, so the two 3s are both there.
Approach: fix one position per pass
Selection Sort builds the sorted order from the left. In the first pass it puts the smallest value at index 0. In the second pass it puts the smallest of the remaining values at index 1, and so on. After the pass for index i, the positions 0..=i hold their final values, so later passes never look at them again.
Each pass compares position i with every position j to its right. Whenever the value at j is smaller than the value at i, the two swap. By the end of the pass, position i holds the smallest value from i onward.
The textbook version remembers the index of the smallest value and does a single swap at the end of the pass. The version in this lesson swaps as soon as it sees a smaller value. The result is the same, and it needs fewer lines, at the cost of possibly more swaps.
Here is what the vector looks like after each pass for [3, 1, 3, 2, 5, 4]:
[1, 3, 3, 2, 5, 4]
[1, 2, 3, 3, 5, 4]
[1, 2, 3, 3, 5, 4]
[1, 2, 3, 3, 5, 4]
[1, 2, 3, 3, 4, 5]
[1, 2, 3, 3, 4, 5]
The first pass already puts the 1 at index 0. The second pass puts the 2 at index 1. The passes for indices 2 and 3 find nothing to change, and the pass for index 4 swaps the 5 and the 4.
Step by step
- Write the outer loop over
0..n, withnthe length the starting code already stored. Each iteration is responsible for one position,i. - Write the inner loop over
(i + 1)..n. Everything beforeiis already in its final place, so only the positions to the right ofineed to be compared. - Compare
nums[i] > nums[j]. If the value atjis smaller, it should come before the value ati, so it moves to positioni. Using>and not>=means equal values are never swapped, which saves work. - Swap the two elements with
nums.swap(i, j). - Return
numsas the last expression. It was declaredmutin the parameter list, so the function can change the vector it owns.
The solution in Rust
impl Solution {
fn sort(mut nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
for i in 0..n {
for j in (i + 1)..n {
if nums[i] > nums[j] {
nums.swap(i, j);
}
}
}
nums
}
}
The Rust details worth a closer look:
mut numsin the signature. The vector is passed by value, so the function owns it. Writingmutbefore the parameter name lets the function modify it, and the caller no longer has the original: it was moved in.- Ranges are half-open.
0..nincludes 0 and stops beforen.(i + 1)..nis empty wheni + 1isnor more, so on the last pass the inner loop simply does nothing. - Why
swap. Writing the swap by hand would need two mutable references into the same vector at once, which the borrow checker rejects.Vec::swaptakes both indices and does the exchange safely. It panics if either index is out of bounds, but here both are always belown. - Indexing with
usize.iandjcome from ranges overusizevalues, which is the type Rust requires for indexing a vector.
Complexity
Time: O(n^2). The pass for index i makes n - 1 - i comparisons. Summed over all passes this is (n - 1) + (n - 2) + ... + 1 + 0, which is n(n - 1) / 2. The number of comparisons does not depend on the input order, so an already sorted vector costs as much as a shuffled one.
Space: O(1). The function stores only n, i and j. The swaps happen inside the vector it already owns.
Edge cases and common mistakes
- Empty or one-element vectors. With an empty vector,
nis 0 and the outer loop never runs. With one element, the inner loop is empty. Both are returned unchanged. - Starting the inner loop at
i. Comparing an element with itself never triggers a swap, so the result is still correct, but it adds a useless comparison to every pass. Starting ati + 1is the clean choice. - Starting the inner loop at 0. Then positions already fixed on the left can be compared with
nums[i]and swapped back, which can put larger values in front and break the order. - Comparing the wrong direction.
nums[i] < nums[j]sorts in descending order. - Negative numbers and duplicates. Only comparisons are used, so
[-2, 5, -2, 0]becomes[-2, -2, 0, 5]without any special handling.
Testing
nums = [3, 1, 3, 2, 5, 4]gives[1, 2, 3, 3, 4, 5].nums = []gives[].nums = [7]gives[7].nums = [5, 4, 3, 2, 1]gives[1, 2, 3, 4, 5].
