Selection Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Selection Sort Algorithm

Start with unsorted array

↓

Set i = 0 (start index)

↓

Find min element from i to end

↓

Swap min element with element at i

↓

Increment i

↓

i < array length - 1?

No→Done

↩Back to find min element

Selection sort repeatedly finds the smallest element in the unsorted part and swaps it with the first unsorted element, moving the boundary forward.

Execution Sample

DSA Go

arr := []int{64, 25, 12, 22, 11}
for i := 0; i < len(arr)-1; i++ {
  minIdx := i
  for j := i+1; j < len(arr); j++ {
    if arr[j] < arr[minIdx] {
      minIdx = j
    }
  }
  arr[i], arr[minIdx] = arr[minIdx], arr[i]
}

This code sorts the array by selecting the smallest element from the unsorted part and swapping it to the front.

Execution Table

Step	Operation	i	j	minIdx	Array State	Action
1	Initialize i=0	0	-	0	[64, 25, 12, 22, 11]	Start outer loop
2	Compare arr[j]=25 < arr[minIdx]=64	0	1	0	[64, 25, 12, 22, 11]	Update minIdx=1
3	Compare arr[j]=12 < arr[minIdx]=25	0	2	1	[64, 25, 12, 22, 11]	Update minIdx=2
4	Compare arr[j]=22 < arr[minIdx]=12	0	3	2	[64, 25, 12, 22, 11]	No change
5	Compare arr[j]=11 < arr[minIdx]=12	0	4	2	[64, 25, 12, 22, 11]	Update minIdx=4
6	Swap arr[i]=64 with arr[minIdx]=11	0	-	4	[11, 25, 12, 22, 64]	Swap elements at 0 and 4
7	Increment i=1	1	-	1	[11, 25, 12, 22, 64]	Start next outer loop
8	Compare arr[j]=12 < arr[minIdx]=25	1	2	1	[11, 25, 12, 22, 64]	Update minIdx=2
9	Compare arr[j]=22 < arr[minIdx]=12	1	3	2	[11, 25, 12, 22, 64]	No change
10	Compare arr[j]=64 < arr[minIdx]=12	1	4	2	[11, 25, 12, 22, 64]	No change
11	Swap arr[i]=25 with arr[minIdx]=12	1	-	2	[11, 12, 25, 22, 64]	Swap elements at 1 and 2
12	Increment i=2	2	-	2	[11, 12, 25, 22, 64]	Start next outer loop
13	Compare arr[j]=22 < arr[minIdx]=25	2	3	2	[11, 12, 25, 22, 64]	Update minIdx=3
14	Compare arr[j]=64 < arr[minIdx]=22	2	4	3	[11, 12, 25, 22, 64]	No change
15	Swap arr[i]=25 with arr[minIdx]=22	2	-	3	[11, 12, 22, 25, 64]	Swap elements at 2 and 3
16	Increment i=3	3	-	3	[11, 12, 22, 25, 64]	Start next outer loop
17	Compare arr[j]=64 < arr[minIdx]=25	3	4	3	[11, 12, 22, 25, 64]	No change
18	Swap arr[i]=25 with arr[minIdx]=25	3	-	3	[11, 12, 22, 25, 64]	Swap elements at 3 and 3 (no change)
19	Increment i=4	4	-	4	[11, 12, 22, 25, 64]	Outer loop ends, array sorted

💡 i reaches 4 which is len(arr)-1, outer loop ends, array is sorted

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 15	After Step 18	Final
i	0	0	1	2	3	4
minIdx	0	4	2	3	3	4
Array	[64, 25, 12, 22, 11]	[11, 25, 12, 22, 64]	[11, 12, 25, 22, 64]	[11, 12, 22, 25, 64]	[11, 12, 22, 25, 64]	[11, 12, 22, 25, 64]

Key Moments - 3 Insights

Why do we update minIdx only when arr[j] < arr[minIdx]?

Because minIdx must always point to the smallest element found so far in the unsorted part. This is shown in steps 2, 3, 5 where minIdx changes only when a smaller element is found.

Why do we swap arr[i] with arr[minIdx] even if minIdx equals i?

Swapping an element with itself does nothing but keeps the algorithm consistent. Step 18 shows this case where swapping arr[3] with arr[3] does not change the array.

Why does the outer loop run only until i < len(arr)-1?

Because after placing the smallest elements up to the second last position, the last element is automatically sorted. The exit note confirms the loop ends at i=4 for array length 5.

Visual Quiz - 3 Questions

Look at the execution table at step 6, what is the array state after the swap?

A [25, 11, 12, 22, 64]

B [64, 25, 12, 22, 11]

C [11, 25, 12, 22, 64]

D [11, 12, 25, 22, 64]

💡 Hint

Check the 'Array State' column at step 6 in the execution_table

At which step does minIdx first change from 0 to 1?

A Step 3

B Step 2

C Step 5

D Step 4

💡 Hint

Look at the 'minIdx' column in execution_table rows 1 to 5

If the array was already sorted, how would the swaps change?

A Swaps would happen only when minIdx != i

B No swaps would occur

C Only one swap at the end

D Swaps would still happen at every step

💡 Hint

Refer to step 18 where swap happens even if minIdx == i, but in sorted array swaps happen only if minIdx differs from i

Concept Snapshot

Selection Sort Algorithm:
- Repeatedly find the smallest element in unsorted part
- Swap it with the first unsorted element
- Move boundary forward by one
- Runs in O(n²) time
- In-place and simple to implement

Full Transcript

Selection sort works by dividing the array into sorted and unsorted parts. It starts at the first element and finds the smallest element in the unsorted part. Then it swaps this smallest element with the first unsorted element. This process repeats by moving the boundary forward until the whole array is sorted. The execution table shows each comparison and swap step by step, tracking the index i, the current minimum index minIdx, and the array state after each operation. Key moments clarify why minIdx updates only when a smaller element is found, why swapping with itself is allowed, and why the outer loop stops before the last element. The visual quiz tests understanding of array states and index changes during sorting.