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

↓

Is i < array length - 1?

No→Sorted array ready

↩Back to find min element

Selection sort repeatedly finds the smallest element from the unsorted part and swaps it with the first unsorted element, moving the boundary forward until the array is sorted.

Execution Sample

DSA C

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

This code sorts the array using selection sort by selecting the minimum element in each pass and swapping it to the front.

Execution Table

Step	Operation	Current i	Current j	Min Index	Array State	Swap Performed
1	Initialize i=0	0	-	0	[64, 25, 12, 22, 11]	No
2	Compare arr[j]=25 < arr[min_idx]=64	0	1	1	[64, 25, 12, 22, 11]	No
3	Compare arr[j]=12 < arr[min_idx]=25	0	2	2	[64, 25, 12, 22, 11]	No
4	Compare arr[j]=22 < arr[min_idx]=12	0	3	2	[64, 25, 12, 22, 11]	No
5	Compare arr[j]=11 < arr[min_idx]=12	0	4	4	[64, 25, 12, 22, 11]	No
6	Swap arr[i]=64 with arr[min_idx]=11	0	-	4	[11, 25, 12, 22, 64]	Yes
7	Initialize i=1	1	-	1	[11, 25, 12, 22, 64]	No
8	Compare arr[j]=12 < arr[min_idx]=25	1	2	2	[11, 25, 12, 22, 64]	No
9	Compare arr[j]=22 < arr[min_idx]=12	1	3	2	[11, 25, 12, 22, 64]	No
10	Compare arr[j]=64 < arr[min_idx]=12	1	4	2	[11, 25, 12, 22, 64]	No
11	Swap arr[i]=25 with arr[min_idx]=12	1	-	2	[11, 12, 25, 22, 64]	Yes
12	Initialize i=2	2	-	2	[11, 12, 25, 22, 64]	No
13	Compare arr[j]=22 < arr[min_idx]=25	2	3	3	[11, 12, 25, 22, 64]	No
14	Compare arr[j]=64 < arr[min_idx]=22	2	4	3	[11, 12, 25, 22, 64]	No
15	Swap arr[i]=25 with arr[min_idx]=22	2	-	3	[11, 12, 22, 25, 64]	Yes
16	Initialize i=3	3	-	3	[11, 12, 22, 25, 64]	No
17	Compare arr[j]=64 < arr[min_idx]=25	3	4	3	[11, 12, 22, 25, 64]	No
18	Swap arr[i]=25 with arr[min_idx]=25	3	-	3	[11, 12, 22, 25, 64]	Yes (same element)
19	i=4 reached n-1, sorting done	4	-	-	[11, 12, 22, 25, 64]	No

💡 i reached n-1 (4), no more passes needed, array is sorted

Variable Tracker

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

Swapping the element with itself does not change the array but keeps the algorithm consistent. Step 18 shows a swap with the same element, which is harmless and part of the process.

Why does the inner loop start from j = i + 1 instead of 0?

Because elements before i are already sorted, so we only look for the minimum in the unsorted part from i+1 to end. This is shown in steps 2-5 for i=0.

When does the algorithm stop?

The algorithm stops when i reaches n-1 (step 19), because the last element is then in place and no further passes are needed.

Visual Quiz - 3 Questions

Look at the execution table at step 11. What is the array state after the swap?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 11 in the execution_table.

At which step does the minimum element 11 get placed at the start of the array?

A Step 1

B Step 6

C Step 18

D Step 15

💡 Hint

Look for the first swap operation involving 11 in the execution_table.

If the array was already sorted, how would the swap operations change?

A Swaps would happen randomly

B No swaps would occur at all

C Swaps would still happen but always with the same element

D Swaps would happen only at the last step

💡 Hint

Refer to step 18 where a swap with the same element occurs even when the array is sorted.

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
- Repeat until array is sorted
- Time complexity: O(n²), simple but inefficient for large arrays

Full Transcript

Selection sort works by dividing the array into sorted and unsorted parts. It starts at the beginning, finds the smallest element in the unsorted part, and swaps it with the first unsorted element. This process repeats, moving the boundary forward until the entire array is sorted. The inner loop finds the minimum element, and the outer loop moves through the array. Swapping with the same element is allowed and does not affect correctness. The algorithm stops when the last element is reached. The example array [64, 25, 12, 22, 11] is sorted step-by-step, showing comparisons, minimum index updates, and swaps until the final sorted array [11, 12, 22, 25, 64] is achieved.

Practice

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

easy

A. Divide the list and merge sorted parts

B. Swap adjacent elements if they are in wrong order

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

D. Insert elements into their correct position one by one

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

   Unlike bubble sort (swapping adjacent) or merge sort (divide and conquer), selection sort selects the minimum each time.

3. Final Answer:

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

4. Quick Check:

   Selection sort = find minimum and swap [OK]

Hint: Selection sort picks smallest and swaps front [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it sorts by inserting elements
• Believing it divides and merges lists

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

easy

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

B. temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp;

C. swap(arr[i], arr[min_idx]);

D. arr[i] = arr[min_idx]; arr[min_idx] = arr[i];

Solution

1. Step 1: Understand swapping in C

   C does not have built-in swap; we use a temporary variable to hold one value during swap.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; uses a temp variable correctly. arr[i] = arr[min_idx]; arr[min_idx] = arr[i]; overwrites arr[i] before saving. swap(arr[i], arr[min_idx]); is invalid syntax in C. arr[i], arr[min_idx] = arr[min_idx], arr[i]; is Python syntax, not C.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; -> Option B

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 temp variable
• Using Python or other language syntax
• Overwriting values before saving

3. What will be the output array after the first pass of selection sort on arr = {29, 10, 14, 37, 13}?

medium

A. {10, 29, 14, 37, 13}

B. {29, 10, 14, 37, 13}

C. {13, 10, 14, 37, 29}

D. {10, 14, 29, 37, 13}

Solution

1. Step 1: Find minimum in entire array

   Minimum element is 10 at index 1.

2. Step 2: Swap minimum with first element

   Swap 29 (index 0) with 10 (index 1). Array becomes {10, 29, 14, 37, 13}.

3. Final Answer:

   {10, 29, 14, 37, 13} -> Option A

4. Quick Check:

   First pass swaps smallest to front [OK]

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

Common Mistakes:

• Not swapping after finding minimum
• Swapping with wrong index
• Confusing first pass with full sort

4. Identify the error in this selection sort snippet and choose the fix:

for (int i = 0; i < n; i++) {
  int min_idx = i;
  for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[min_idx])
      min_idx = j;
  }
  arr[i] = arr[min_idx];
  arr[min_idx] = arr[i];
}

medium

A. Swap lines overwrite values; use a temp variable to swap

B. Change inner loop to start from j = 0

C. Remove inner loop; selection sort doesn't need it

D. Use arr[min_idx] = arr[j] instead of arr[min_idx] = arr[i]

Solution

1. Step 1: Analyze swap lines

   Lines arr[i] = arr[min_idx]; arr[min_idx] = arr[i]; overwrite arr[min_idx] with arr[i] after first assignment, losing original value.

2. Step 2: Correct swap method

   Use a temporary variable to hold arr[i], then assign arr[i] = arr[min_idx], then arr[min_idx] = temp to swap correctly.

3. Final Answer:

   Swap lines overwrite values; use a temp variable to swap -> Option A

4. Quick Check:

   Swap needs temp variable to avoid overwrite [OK]

Hint: Use temp variable to swap, not direct assignments [OK]

Common Mistakes:

• Swapping without temp variable
• Changing loop start incorrectly
• Removing necessary inner loop

5. Given the array arr = {64, 25, 12, 22, 11}, after fully sorting it using selection sort, what is the final sorted array?

hard

A. {64, 25, 12, 22, 11}

B. {11, 22, 12, 25, 64}

C. {25, 11, 12, 22, 64}

D. {11, 12, 22, 25, 64}

Solution

1. Step 1: Perform selection sort passes

   Pass 1: min=11, swap with 64 -> {11,25,12,22,64}
   Pass 2: min=12, swap with 25 -> {11,12,25,22,64}
   Pass 3: min=22, swap with 25 -> {11,12,22,25,64}
   Pass 4: min=25, no swap needed -> {11,12,22,25,64}

2. Step 2: Confirm final sorted array

   After all passes, array is sorted ascending: {11, 12, 22, 25, 64}.

3. Final Answer:

   {11, 12, 22, 25, 64} -> Option D

4. Quick Check:

   Selection sort fully sorts ascending [OK]

Hint: Selection sort sorts ascending by swapping minimum each pass [OK]

Common Mistakes:

• Stopping after first pass
• Not swapping correctly
• Mixing up element positions