Problem overview
The method Sort(int[] nums) must sort an array of integers into ascending order, using the Selection Sort idea. It returns nothing: it rearranges the array it was given. For nums = {3, 1, 3, 2, 5, 4}, the array ends up as {1, 2, 3, 3, 4, 5}.
The lesson sets the budget at O(n^2) time and O(1) extra space. Sorting happens in place, and the only extra storage is a few variables.
Approach: fix one position at a time
Selection Sort builds the sorted array from the left. On pass i, it makes position i hold the smallest value found from index i to the end. After the pass, everything up to and including i is in its final place, and the next pass only has to deal with the rest.
The idea needs two loops. The outer loop picks the position i to fill. The inner loop looks at every later position j, and whenever nums[j] is smaller than nums[i], it swaps the two. By the end of the inner loop, nums[i] is the minimum of the remaining part.
The textbook version scans for the index of the minimum and swaps once per pass. The lesson's version swaps as soon as it sees a smaller value, which can swap several times in one pass but ends with the same array and has the same O(n^2) cost.
Why does the inner loop end with the minimum in place? Each swap leaves a smaller value at position i, and the value there never gets bigger during the pass. After the loop has looked at every later element, nothing smaller than nums[i] remains to its right, and nothing to its left is larger, because the earlier passes put those values there. So position i is final.
A trace
For {3, 1, 3, 2, 5, 4}, the array after each outer pass is:
after i = 0: 1 3 3 2 5 4
after i = 1: 1 2 3 3 5 4
after i = 2: 1 2 3 3 5 4
after i = 3: 1 2 3 3 5 4
after i = 4: 1 2 3 3 4 5
after i = 5: 1 2 3 3 4 5
Pass 0 swaps 3 with 1, which puts the minimum in front. In pass 1, the 3 at index 1 meets the 2 at index 3 and they swap. The equal 3s in pass 2 do nothing, and pass 4 finally swaps 5 and 4.
Step by step
- Write the outer loop.
int iruns from 0 whilei < nums.Length. Each pass fills positioni. - Write the inner loop.
int jstarts ati + 1and runs whilej < nums.Length. Positions beforeiare already final, so only the indices afterineed comparing. - Compare. If
nums[i] > nums[j], a smaller value sits later in the array and belongs at positioni. Using>rather than>=means equal values are never swapped, which saves useless work. - Write a
Swaphelper. It takes the array and two indices, savesnums[i]intemp, copiesnums[j]intonums[i], then putstempintonums[j]. Withouttemp, the first assignment would destroy the old value ofnums[i]. - Call it. Inside the
if, callSwap(nums, i, j).
The solution in C#
class Solution {
public void Swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void Sort(int[] nums) {
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (nums[i] > nums[j]) {
Swap(nums, i, j);
}
}
}
}
}
The C# details:
- Arrays are reference types. The parameter
numsinSwaprefers to the same array object as the caller's variable, so changingnums[i]inside the helper changes the caller's array. That's whySortcan returnvoidand still sort. - Integers are copied.
iandjare passed by value. Swapping the parameters themselves would change nothing outside; the code swaps the array's elements instead. - Tuple swap. C# can also swap without a temporary variable:
(nums[i], nums[j]) = (nums[j], nums[i]);. This lesson spells out the three steps so the logic is visible. - The built-in. Real programs call
Array.Sort(nums). Writing the sort by hand is practice for understanding nested loops and swaps.
Complexity
Time: O(n^2). The inner loop runs n - 1 times for i = 0, then n - 2, and so on, a total of n(n - 1) / 2 comparisons. This count doesn't depend on the input order: even an already sorted array costs the same comparisons.
Space: O(1). The sort works inside the given array and uses only i, j and temp.
Edge cases and common mistakes
- Empty or one-element arrays. The loops do no swaps, and the array stays as it is.
- Duplicates.
{3, 1, 3, 2, 5, 4}contains two 3s, and both survive. With>, equal values are left alone. - Starting
jati. Thennums[i]is compared with itself, which does nothing useful and wastes one comparison per pass. - Starting
jat 0. Then the inner loop looks at positions that are already sorted and can swap them out of place. - Using
<in the comparison. The array would end up in descending order. - Swapping the wrong things. Swapping the values
iandjinstead ofnums[i]andnums[j]sorts nothing. - Looking for a return value. The method sorts the caller's array in place. A copy of the array is only needed if you want to keep the original order.
Testing
{3, 1, 3, 2, 5, 4}becomes{1, 2, 3, 3, 4, 5}.{5, 4, 3, 2, 1}becomes{1, 2, 3, 4, 5}.{1, 2, 3}stays{1, 2, 3}.{-2, 7, -10, 0}becomes{-10, -2, 0, 7}.- An empty array stays empty.