Problem overview
The method sort receives an array of numbers, nums, and must sort it in ascending order. It returns nothing (void): the sorting happens in place, inside the array that was passed in, and the caller sees the changed array afterwards.
For nums = [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5]. Duplicates are allowed. The statement sets a budget of O(n^2) time and O(1) extra space, which is what a simple nested-loop sort costs.
Approach: fill the array from the left
Selection sort builds the sorted array one position at a time, from left to right. Pass number i makes sure that position i holds the smallest value among the positions i to the end. After that pass, everything before position i + 1 is in its final place, and the next pass only needs to look further right.
The lesson's version finds the smallest value by comparing nums[i] with each later element nums[j]. Whenever a later element is smaller, the two swap. By the end of the inner loop, position i holds the minimum of the rest of the array. The textbook form of selection sort remembers where the minimum is and swaps once per pass. This version swaps more often, but it reaches the same result with less code, and it has the same complexity.
Here is the array [3, 1, 2] traced through the code. At i = 0: 3 > 1, so swap and the array is [1, 3, 2]. Then 1 > 2 is false, so nothing happens. At i = 1: 3 > 2, so swap and the array is [1, 2, 3]. At i = 2 the inner loop has no elements to look at. The array is sorted.
Step by step
- Write the outer loop.
igoes over every index ofnums, declared withlet, starting at 0 and running whilei < nums.length. Each pass fills positioni. - Write the inner loop.
jstarts ati + 1and runs whilej < nums.length. Positions beforeiare already final, so only the positions afterineed comparing. - Compare. Test whether
nums[i] > nums[j]. If so, a smaller value sits later in the array and belongs at positioni. Using>and not>=means equal values are never swapped, which avoids pointless work. - Swap in one line. A destructuring assignment exchanges the two elements without a temporary variable.
The solution in TypeScript
class Solution {
sort(nums: number[]): void {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
}
}
}The language details worth a closer look:
- The destructuring swap. The right side,
[nums[j], nums[i]], builds a new two-element array from the current values of the two positions. Only then does the left side, the pattern[nums[i], nums[j]], assign those values back, in order. Because the right side is complete before any assignment happens, nothing gets overwritten too early. - Semicolons matter before this line. A statement that starts with
[can be read as a continuation of the previous line. In the solution the line before it is anif (...) {header, so there is no problem. If you put the swap after a statement that has no semicolon, such asconst x = y, the two lines are joined into one broken expression. - In place. Arrays are objects, and the parameter
numsrefers to the caller's array, not a copy. Changingnums[i]therefore changes the caller's data, which is why the method can returnvoid. - Numbers compare as numbers. The operator
>on two numbers compares their values, which is what you want here. This is different from the built-innums.sort()with no comparator, which compares elements as strings:[10, 9, 1].sort()gives[1, 10, 9]. To sort numbers with the built-in method, pass a comparator:nums.sort((a, b) => a - b).
Complexity
Time: O(n^2). The inner loop runs n - 1 times for i = 0, n - 2 times for i = 1, and so on. That is n(n - 1) / 2 comparisons whatever the input looks like, even when the array is already sorted. Swaps add at most the same count again, which doesn't change the order of growth.
Space: O(1). The sort rearranges the array it is given. The temporary array in the swap has two elements and exists only for that line, so the extra memory doesn't grow with n.
Edge cases and common mistakes
- Empty or one-element arrays. The inner loop never runs, so the array is left as it is.
- Already sorted input. No swaps happen, but all the comparisons still do. The running time stays quadratic.
- Duplicates.
[3, 1, 3, 2, 5, 4]ends as[1, 2, 3, 3, 4, 5]. Equal values are not swapped, because the test is strict. - Reverse order.
[5, 4, 3, 2, 1]is the worst case for swaps. This version performs 10 of them. - Starting
jat 0. The inner loop would then also comparenums[i]with elements to its left, and swap whenevernums[i]is larger. That pushes the larger values to the front:[3, 1, 2]comes out as[3, 2, 1], in descending order. - Expecting a return value. The method sorts the array it receives and returns nothing. Read the sorted data from
numsafter the call. - Wrong comparison direction. Writing
nums[i] < nums[j]sorts in descending order.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[10, 9, 1]becomes[1, 9, 10].[1, 2, 3]stays[1, 2, 3].[]stays[].