Problem overview
The function sort(nums: IntArray) must sort the array in ascending order, using selection sort. It returns nothing: the array itself is rearranged. For nums = [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5]. The statement allows O(n^2) time and O(1) extra space, so the sort has to work in place, without building a second array.
Approach: fix one position at a time
Selection sort builds the sorted array from the left. For each position i, it makes sure that nums[i] holds the smallest value found from index i to the end. After the pass for i = 0 the smallest value of the whole array is first. After the pass for i = 1 the second smallest is second, and so on. Positions to the left of i are never touched again, because they are already final.
The lesson does this with two nested loops. For a position i, the inner loop looks at every later position j. When nums[j] is smaller than nums[i], the two values are swapped. By the end of the inner loop, nothing smaller than nums[i] is left to its right, so position i is final.
This swaps as soon as it sees a smaller value, which can happen several times in one pass. The textbook version scans first to find the index of the minimum and swaps once at the end of the pass. Both end up with the same sorted array and the same O(n^2) number of comparisons; the lesson uses the simpler version, which needs no extra variable for the index.
The trace for [3, 1, 3, 2, 5, 4] shows the array after each value of i:
i=0: [1, 3, 3, 2, 5, 4]
i=1: [1, 2, 3, 3, 5, 4]
i=2: [1, 2, 3, 3, 5, 4]
i=3: [1, 2, 3, 3, 5, 4]
i=4: [1, 2, 3, 3, 4, 5]
i=5: [1, 2, 3, 3, 4, 5]After i = 0, the 1 is in front. After i = 1, the 2 has come to position 1, and the passes in the middle find nothing to change.
Step by step
- Outer loop over positions. Use
for (i in 0 until nums.size). Each pass settles the value at indexi. - Inner loop over the rest. Inside it, loop
jover(i + 1) until nums.size. Only the indices afterineed a look, because everything beforeiis already in place. - Compare. Write
if (nums[i] > nums[j]). A smaller value atjbelongs at positioni. With>instead of>=, equal values are left alone, which avoids pointless swaps. - Write a
swaphelper. It takes the array and two indices, savesnums[i]in a temporaryval, copiesnums[j]intonums[i], and puts the saved value intonums[j]. Without the temporary, the first assignment would overwrite a value that is still needed. - Call it. Inside the
if, runswap(nums, i, j). The helper gets a reference to the same array, so the change is visible insortand to the caller.
The solution in Kotlin
class Solution {
fun swap(nums: IntArray, i: Int, j: Int) {
val temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
fun sort(nums: IntArray) {
for (i in 0 until nums.size) {
for (j in (i + 1) until nums.size) {
if (nums[i] > nums[j]) {
swap(nums, i, j)
}
}
}
}
}
The Kotlin details worth knowing:
- Arrays are passed by reference. An
IntArrayparameter points to the caller's array, so writingnums[i] = ...insideswapchanges the original. That is why neither function needs to return anything. - Function parameters are read-only. You can't assign a new array to
numsinside the function. You can still change its elements. val temp. The temporary is assigned once, sovalis the right choice.untilexcludes the end.0 until nums.sizecovers the valid indices0tonums.size - 1. Wheni + 1equalsnums.size, the inner range is empty and the loop body doesn't run.- Standard library. Kotlin has
nums.sort()forIntArray, which sorts in place. The exercise asks you to write the algorithm yourself. - Output. Print an
IntArraywithcontentToString(). Printing the array itself shows only an object reference.
Complexity
Time: O(n^2). The inner loop makes n - 1 comparisons for i = 0, n - 2 for i = 1, and so on, which adds up to n(n - 1) / 2. The number of comparisons doesn't depend on the order of the input: a sorted array costs the same number of comparisons as a reversed one. Only the number of swaps varies.
Space: O(1). The sort uses the loop variables and one temporary value while swapping, and rearranges the array in place.
Edge cases and common mistakes
- Empty or one-element arrays. The loops have nothing to compare, so the array stays as it is.
- Already sorted input. No condition is true, so no swap happens, but all the comparisons still run.
- Reversed input.
[5, 4, 3, 2, 1]becomes[1, 2, 3, 4, 5]. This version makes 10 comparisons and 10 swaps for it. - Duplicates and negatives.
[3, 1, 3, 2, 5, 4]keeps both 3s, and[-1, -5, 0, -1]becomes[-5, -1, -1, 0]. - Starting
jati. That compares an element with itself, which does no harm but wastes a step. Startingjat 0 is worse: it would swap larger values into earlier positions and undo finished work. - Swapping without a temporary. Writing
nums[i] = nums[j]thennums[j] = nums[i]leaves both positions with the same value and loses one number. - Wrong comparison direction.
nums[i] < nums[j]would sort in descending order. - Expecting a stable sort. Swapping across distances can reorder equal values. Here they are plain integers, so it makes no visible difference.
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, -5, 0, -1]becomes[-5, -1, -1, 0].[2, 2, 2]stays[2, 2, 2].[7]stays[7], and[]stays[].