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.

Practice

1. What is the main idea behind the Selection Sort algorithm?

easy

A. Repeatedly find the smallest element and move it to the front

B. Divide the list into halves and merge sorted halves

C. Swap adjacent elements if they are in wrong order repeatedly

D. Use a pivot to partition the list into smaller parts

Solution

1. Step 1: Understand selection sort process

   Selection sort finds the smallest element in the unsorted part and swaps it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Other options describe merge sort, bubble sort, and quicksort, which are different algorithms.

3. Final Answer:

   Repeatedly find the smallest element and move it to the front -> Option A

4. Quick Check:

   Selection sort = find smallest and swap [OK]

Hint: Selection sort always picks the smallest next element [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it divides list like merge sort
• Assuming it uses a pivot like quicksort

2. Which of the following is the correct way to start the outer loop for selection sort in Go for an array arr of length n?

easy

A. for i := 1; i < n; i++ {

B. for i := 0; i < n-1; i++ {

C. for i := 0; i <= n; i++ {

D. for i := 1; i <= n; i++ {

Solution

1. Step 1: Understand loop range for selection sort

   The outer loop runs from 0 to n-2 because the last element will be sorted automatically after previous passes.

2. Step 2: Check each option's correctness

   for i := 0; i < n-1; i++ { uses i < n-1, which is correct. Others either go out of bounds or start at wrong index.

3. Final Answer:

   for i := 0; i < n-1; i++ { -> Option B

4. Quick Check:

   Outer loop runs 0 to n-2 [OK]

Hint: Outer loop stops at n-2 because last element is sorted [OK]

Common Mistakes:

• Using <= n causing index out of range
• Starting loop at 1 instead of 0
• Loop running too many times

3. What will be the output of the following Go code snippet after applying one full pass of selection sort on the array?

arr := []int{29, 10, 14, 37, 13}
n := len(arr)
minIndex := 0
for j := 1; j < n; j++ {
    if arr[j] < arr[minIndex] {
        minIndex = j
    }
}
arr[0], arr[minIndex] = arr[minIndex], arr[0]
fmt.Println(arr)

medium

A. [10 13 14 37 29]

B. [13 10 14 37 29]

C. [29 10 14 37 13]

D. [10 29 14 37 13]

Solution

1. Step 1: Find minimum element index in full array

   Minimum element is 10 at index 1, so minIndex = 1.

2. Step 2: Swap arr[0] and arr[minIndex]

   Swap arr[0] (29) with arr[1] (10), resulting in [10 29 14 37 13].

3. Final Answer:

   [10 29 14 37 13] -> Option D

4. Quick Check:

   First pass places smallest element at front [OK]

Hint: First pass swaps smallest element to front [OK]

Common Mistakes:

• Not swapping elements after finding minimum
• Confusing minIndex with current index
• Printing array before swap

4. Identify the error in the following Go code implementing selection sort:

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {
        minIndex := i
        for j := i + 1; j <= n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

medium

A. Swap should be done only if minIndex != i

B. minIndex should be initialized outside the outer loop

C. Inner loop condition should be j < n, not j <= n

D. Outer loop should run from i := 1 to n-1

Solution

1. Step 1: Check inner loop boundary

   Inner loop uses j <= n, which causes index out of range error because valid indices are 0 to n-1.

2. Step 2: Correct inner loop condition

   It should be j < n to stay within array bounds.

3. Final Answer:

   Inner loop condition should be j < n, not j <= n -> Option C

4. Quick Check:

   Array indices go from 0 to n-1 [OK]

Hint: Array indices end at n-1, not n [OK]

Common Mistakes:

• Using <= n causing runtime panic
• Initializing minIndex outside outer loop
• Unnecessary swap checks

5. Given the array arr := []int{64, 25, 12, 22, 11}, after how many swaps will the array be fully sorted using selection sort, and what will be the final sorted array?

hard

A. 4 swaps; [11 12 22 25 64]

B. 5 swaps; [11 12 22 25 64]

C. 4 swaps; [64 25 12 22 11]

D. 3 swaps; [11 12 22 25 64]

Solution

1. Step 1: Count swaps in each selection sort pass

   Pass 1: swap 64 and 11 -> [11 25 12 22 64]
   Pass 2: swap 25 and 12 -> [11 12 25 22 64]
   Pass 3: swap 25 and 22 -> [11 12 22 25 64]
   Pass 4: swap 25 and 25 (no change, but swap counted as 1)
   Total swaps = 4 (last swap is with itself, usually counted as swap)

2. Step 2: Final sorted array

   The array after sorting is [11 12 22 25 64].

3. Final Answer:

   4 swaps; [11 12 22 25 64] -> Option A

4. Quick Check:

   Selection sort swaps once per pass, total n-1 swaps [OK]

Hint: Selection sort swaps once per pass, total n-1 swaps [OK]

Common Mistakes:

• Counting swaps incorrectly when swapping element with itself
• Assuming more swaps than passes
• Confusing sorted array with original