Problem overview
The function selectionSort(nums []int) must sort a slice of integers in ascending order using selection sort. It returns nothing: the slice is rearranged in place. For nums = [3, 1, 3, 2, 5, 4], the slice becomes [1, 2, 3, 3, 4, 5].
The requirement is O(n^2) time and O(1) extra space.
Approach: fix one position at a time
Sorting means putting the elements in order. Selection sort does it by deciding the final value of each position from left to right. For position 0 it finds the smallest value in the whole slice, for position 1 the smallest of what remains, and so on. After the pass for position i, everything before i + 1 is in its final place.
The textbook version scans for the smallest element and swaps once per position. The version in this lesson is a close relative: it compares nums[i] with every later nums[j] and swaps whenever the later value is smaller. While j scans, nums[i] keeps getting replaced by a smaller value, so at the end of the inner loop it holds the minimum of the suffix, just as in the textbook version. It performs more swaps but reaches the same sorted result.
Take [3, 1, 2]. For i = 0: 3 > 1, so swap, giving [1, 3, 2]; then 1 > 2 is false. For i = 1: 3 > 2, so swap, giving [1, 2, 3]. For i = 2 there is nothing after it. The slice is sorted.
The textbook variant
The version above swaps whenever it sees a smaller value. The classic selection sort remembers where the smallest value sits and swaps once per position:
func selectionSortMin(nums []int) {
for i := 0; i < len(nums); i++ {
minIdx := i
for j := i + 1; j < len(nums); j++ {
if nums[j] < nums[minIdx] {
minIdx = j
}
}
nums[i], nums[minIdx] = nums[minIdx], nums[i]
}
}On [3, 1, 3, 2, 5, 4] it also gives [1 2 3 3 4 5]. It makes at most n - 1 useful swaps, while the lesson's version can make many more: a slice in descending order, [5, 4, 3, 2, 1], takes 10 swaps with the lesson's version and only 2 swaps that move anything with the textbook one. Both still do n(n-1)/2 comparisons, so both are O(n^2) time and O(1) space. The lesson's version is shorter and easier to get right, which is why it is used for practice.
Step by step
- Write the outer loop with
ifrom 0 whilei < len(nums). Each pass fixes positioni. - Write the inner loop with
jfromi + 1whilej < len(nums). Positions beforeiare already final, so only later positions are compared. - Compare. If
nums[i] > nums[j], a smaller value sits later and must move to positioni. Using>rather than>=means equal values are never swapped, which avoids pointless work. - Write a helper
swapbelow the main function, with parametersnums []intandi, j int. It savesnums[i]intemp, copiesnums[j]intonums[i], then putstempintonums[j]. Withouttemp, the first assignment would destroy the oldnums[i]. - Call
swap(nums, i, j)inside theif.
The solution in Go
func selectionSort(nums []int) {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i] > nums[j] {
swap(nums, i, j)
}
}
}
}
func swap(nums []int, i, j int) {
temp := nums[i]
nums[i] = nums[j]
nums[j] = temp
}Go details:
- Slices share their array. A slice passed to a function is a small header (pointer, length, capacity) that is copied, but the copy points to the same underlying array. Writing
nums[i] = ...insideswapchanges the elements the caller sees. That is why neither function needs to return the slice. - Appending is different. Reassigning the slice itself inside a function, for example with
append, would not be visible to the caller. Sorting never changes the length, so it is safe. - Parameter lists.
i, j intdeclares twointparameters at once. - A shorter swap. Go allows
nums[i], nums[j] = nums[j], nums[i], which evaluates the right side first, so no temporary is needed. The helper above spells out what happens. - Library sorting. In real programs you would call
sort.Ints(nums); writing the algorithm by hand is the exercise here.
Complexity
Time: O(n^2). The inner loop runs n - 1 - i times for each i, giving n(n-1)/2 comparisons whatever the input looks like. Even an already sorted slice costs the full number of comparisons, though it needs no swaps.
Space: O(1). The sort works inside the given slice and uses a few variables.
When to use it
Selection sort is easy to explain and needs no extra memory, but its quadratic running time makes it unsuitable for large inputs: doubling the length of the slice roughly quadruples the work. Its value is educational. It shows the loop invariant that most sorting algorithms rely on: after the pass for position i, the first i + 1 elements are sorted and are the smallest of the whole slice. For production code, Go's sort package runs in O(n log n).
Edge cases and common mistakes
- Empty or one-element slices. The loops do nothing, and the slice is left as is.
- Duplicates.
[3, 1, 3, 2, 5, 4]keeps both 3s in the result, because equal values are not swapped. - Starting
jati. It compares an element with itself, which wastes a step but is harmless; starting at 0 would undo earlier work and break the sort. - Reversing the comparison.
nums[i] < nums[j]sorts in descending order. - Not sorting a copy. The sort changes the caller's slice. If the original order matters, copy it first.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[3, 1, 2]becomes[1, 2, 3].- An empty slice stays empty.