Selection Sort Algorithm in DSA C# - 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→Sorted array done

↩Back to find min element

Selection sort repeatedly finds the smallest element in the unsorted part and swaps it to the front, moving the boundary of sorted and unsorted parts forward.

Execution Sample

DSA C#

int[] arr = {64, 25, 12, 22, 11};
for (int i = 0; i < arr.Length - 1; i++) {
  int minIndex = i;
  for (int j = i + 1; j < arr.Length; j++) {
    if (arr[j] < arr[minIndex]) minIndex = j;
  }
  int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp;
}

Sorts the array by selecting the smallest element from the unsorted part and swapping it with the first unsorted element.

Execution Table

Step	Operation	i	j	minIndex	Array State	Swap Occurred
1	Initialize i=0	0	-	0	[64, 25, 12, 22, 11]	No
2	Compare arr[j]=25 < arr[minIndex]=64	0	1	1	[64, 25, 12, 22, 11]	No
3	Compare arr[j]=12 < arr[minIndex]=25	0	2	2	[64, 25, 12, 22, 11]	No
4	Compare arr[j]=22 < arr[minIndex]=12	0	3	2	[64, 25, 12, 22, 11]	No
5	Compare arr[j]=11 < arr[minIndex]=12	0	4	4	[64, 25, 12, 22, 11]	No
6	Swap arr[i]=64 with arr[minIndex]=11	0	-	4	[11, 25, 12, 22, 64]	Yes
7	Increment i=1	1	-	1	[11, 25, 12, 22, 64]	No
8	Compare arr[j]=12 < arr[minIndex]=25	1	2	2	[11, 25, 12, 22, 64]	No
9	Compare arr[j]=22 < arr[minIndex]=12	1	3	2	[11, 25, 12, 22, 64]	No
10	Compare arr[j]=64 < arr[minIndex]=12	1	4	2	[11, 25, 12, 22, 64]	No
11	Swap arr[i]=25 with arr[minIndex]=12	1	-	2	[11, 12, 25, 22, 64]	Yes
12	Increment i=2	2	-	2	[11, 12, 25, 22, 64]	No
13	Compare arr[j]=22 < arr[minIndex]=25	2	3	3	[11, 12, 25, 22, 64]	No
14	Compare arr[j]=64 < arr[minIndex]=22	2	4	3	[11, 12, 25, 22, 64]	No
15	Swap arr[i]=25 with arr[minIndex]=22	2	-	3	[11, 12, 22, 25, 64]	Yes
16	Increment i=3	3	-	3	[11, 12, 22, 25, 64]	No
17	Compare arr[j]=64 < arr[minIndex]=25	3	4	3	[11, 12, 22, 25, 64]	No
18	Swap arr[i]=25 with arr[minIndex]=25	3	-	3	[11, 12, 22, 25, 64]	No
19	Increment i=4	4	-	4	[11, 12, 22, 25, 64]	No
20	i=4 reached end, sorting done	4	-	-	[11, 12, 22, 25, 64]	No

💡 i reaches array length - 1 (4), sorting is complete

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 15	After Step 18	Final
i	0	1	2	3	4	4
minIndex	0	4	2	3	3	4
j	-	4	4	4	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 swap even if minIndex is the same as i (like in step 18)?

Swapping when minIndex equals i does nothing to the array but keeps the algorithm consistent. Step 18 shows no change in array state, confirming no effect.

Why does the inner loop start from j = i + 1, not from 0?

Because elements before i are already sorted, the inner loop only checks the unsorted part from i+1 to end, as seen in steps 2-5 and 8-10.

Why does the outer loop stop at i = array length - 1?

At i = length - 1, only one element remains which must be in correct place, so sorting is done. Step 20 confirms this termination.

Visual Quiz - 3 Questions

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

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

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

C [25, 11, 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 the minIndex first change from its initial value during the first outer loop iteration?

A Step 3

B Step 5

C Step 2

D Step 6

💡 Hint

Look at the 'minIndex' column changes in steps 2 to 5 in the execution_table.

If the array was already sorted, how would the 'Swap Occurred' column change?

A No swaps would occur at all

B Swaps would occur only when minIndex != i

C Swaps would occur only when i is even

D Swaps would occur at every step

💡 Hint

Refer to steps like 18 where minIndex equals i and no swap occurs.

Concept Snapshot

Selection Sort Algorithm:
- Repeatedly find the smallest element in unsorted part
- Swap it with the first unsorted element
- Move boundary of sorted part forward
- Outer loop runs from 0 to length-2
- Inner loop finds minIndex from i+1 to end
- Time complexity: O(n²), in-place sorting

Full Transcript

Selection sort works by dividing the array into sorted and unsorted parts. It starts at the first element, finds the smallest element in the unsorted part, and swaps it with the current position. This process repeats by moving the starting index forward until the entire array is sorted. The inner loop finds the minimum element index, and the outer loop swaps it to the front. The algorithm stops when the starting index reaches the second last element because the last element will already be sorted. The execution table shows each comparison, minIndex updates, and swaps, with the array state after each operation.

Practice

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

easy

A. Divide the list into halves and sort each half separately

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

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

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

Solution

1. Step 1: Understand selection sort process

   Selection sort works by finding the smallest element in the unsorted part and swapping it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Unlike divide and conquer or adjacent swaps, selection sort directly selects the minimum each time.

3. Final Answer:

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

4. Quick Check:

   Selection sort = find minimum repeatedly [OK]

Hint: Selection sort picks smallest element each pass [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[minIndex] in C# during selection sort?

easy

A. arr[i], arr[minIndex] = arr[minIndex], arr[i];

B. arr[i] = arr[minIndex]; arr[minIndex] = arr[i];

C. temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;

D. swap(arr[i], arr[minIndex]);

Solution

1. Step 1: Understand swapping in C#

   C# does not support tuple unpacking or direct swap functions; we use a temporary variable to swap values.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; uses a temp variable correctly. arr[i] = arr[minIndex]; arr[minIndex] = arr[i]; overwrites arr[i] before assigning arr[minIndex]. swap(arr[i], arr[minIndex]); is invalid syntax. arr[i], arr[minIndex] = arr[minIndex], arr[i]; is Python style, not C#.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; -> Option C

4. Quick Check:

   Use temp variable to swap in C# [OK]

Hint: Use temp variable to swap in C# [OK]

Common Mistakes:

• Trying to swap without a temp variable
• Using Python or other language syntax
• Overwriting one element before saving it

3. What will be the output of the following C# code snippet after applying selection sort?

int[] arr = {64, 25, 12, 22, 11};
// Apply selection sort here
for (int i = 0; i < arr.Length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < arr.Length; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}
Console.WriteLine(string.Join(", ", arr));

medium

A. 11, 12, 22, 25, 64

B. 64, 25, 12, 22, 11

C. 25, 12, 22, 11, 64

D. 11, 22, 12, 25, 64

Solution

1. Step 1: Trace the selection sort iterations

   First pass finds 11 (smallest) and swaps with 64. Array: [11, 25, 12, 22, 64]. Second pass finds 12 and swaps with 25. Array: [11, 12, 25, 22, 64]. Third pass finds 22 and swaps with 25. Array: [11, 12, 22, 25, 64]. Fourth pass finds 25 (already in place). Final sorted array is [11, 12, 22, 25, 64].

2. Step 2: Confirm final output

   The printed output is the sorted array joined by commas.

3. Final Answer:

   11, 12, 22, 25, 64 -> Option A

4. Quick Check:

   Selection sort output = sorted array [OK]

Hint: Selection sort outputs sorted array ascending [OK]

Common Mistakes:

• Not swapping correctly during iterations
• Confusing indexes and swapping wrong elements
• Assuming original array stays unchanged

4. Identify the error in the following selection sort code snippet and choose the correct fix:

int[] arr = {3, 1, 4, 2};
for (int i = 0; i < arr.Length; i++) {
    int minIndex = i;
    for (int j = i + 1; j < arr.Length; j++) {
        if (arr[j] > arr[minIndex]) {
            minIndex = j;
        }
    }
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

medium

A. Change 'if (arr[j] > arr[minIndex])' to 'if (arr[j] < arr[minIndex])'

B. Change outer loop to 'for (int i = 0; i < arr.Length - 1; i++)'

C. Remove the swap code inside the loop

D. Initialize minIndex to 0 instead of i

Solution

1. Step 1: Analyze the comparison condition

   The code uses 'arr[j] > arr[minIndex]' which finds the maximum instead of minimum, so it sorts in descending order, not ascending.

2. Step 2: Correct the comparison for ascending order

   Changing the condition to 'arr[j] < arr[minIndex]' finds the minimum element as required by selection sort.

3. Final Answer:

   Change 'if (arr[j] > arr[minIndex])' to 'if (arr[j] < arr[minIndex])' -> Option A

4. Quick Check:

   Comparison must find minimum element [OK]

Hint: Use '<' to find minimum in selection sort [OK]

Common Mistakes:

• Using '>' instead of '<' in inner loop
• Looping one extra time causing index errors
• Not swapping elements properly

5. Given an array int[] arr = {5, 3, 8, 6, 2, 7, 4, 1}, how many swaps will the selection sort algorithm perform to sort it in ascending order?

hard

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand swap count in selection sort

   Selection sort swaps once per outer loop iteration if the minimum is not already at the current position.

2. Step 2: Count swaps for given array

   Array length is 8, so outer loop runs 7 times (0 to 6). Each iteration finds minimum and swaps if needed. Here, minimum is at current index in one iteration, so total swaps are 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Swaps = number of times minimum is not at current index [OK]

Hint: Selection sort swaps at most n-1 times, but only when needed [OK]

Common Mistakes:

• Counting swaps as number of elements
• Assuming swaps happen every iteration
• Confusing swaps with comparisons