Insertion Sort Algorithm in DSA C - Execution Trace

Concept Flow - Insertion Sort Algorithm

Start at index 1

↓

Pick key element

↓

Compare with sorted part

↓

Shift elements > key right

↓

Insert key at correct position

↓

Move to next index

↓

Repeat until end of array

↓

Sorted array

Insertion sort picks each element and inserts it into the correct position in the sorted part on its left.

Execution Sample

DSA C

int arr[] = {5, 3, 8, 1, 2};
for (int i = 1; i < 5; i++) {
  int key = arr[i];
  int j = i - 1;
  while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
  }
  arr[j + 1] = key;
}

Sorts the array {5,3,8,1,2} step-by-step by inserting each element into the sorted left side.

Execution Table

Step	Operation	Index i	Key	j	Comparison	Shift?	Array State
1	Pick key	1	3	0	arr[0]=5 > 3	Yes	[5, 5, 8, 1, 2]
2	Shift element	1	3	-1	j < 0	No	[3, 5, 8, 1, 2]
3	Pick key	2	8	1	arr[1]=5 > 8	No	[3, 5, 8, 1, 2]
4	Pick key	3	1	2	arr[2]=8 > 1	Yes	[3, 5, 8, 8, 2]
5	Shift element	3	1	1	arr[1]=5 > 1	Yes	[3, 5, 5, 8, 2]
6	Shift element	3	1	0	arr[0]=3 > 1	Yes	[3, 3, 5, 8, 2]
7	Shift element	3	1	-1	j < 0	No	[1, 3, 5, 8, 2]
8	Pick key	4	2	3	arr[3]=8 > 2	Yes	[1, 3, 5, 8, 8]
9	Shift element	4	2	2	arr[2]=5 > 2	Yes	[1, 3, 5, 5, 8]
10	Shift element	4	2	1	arr[1]=3 > 2	Yes	[1, 3, 3, 5, 8]
11	Shift element	4	2	0	arr[0]=1 > 2	No	[1, 3, 3, 5, 8]
12	Insert key	4	2	0	Insert at j+1=1	No	[1, 2, 3, 5, 8]
13	End	-	-	-	-	-	[1, 2, 3, 5, 8]

💡 i reaches 5, condition i < 5 is False, sorting complete

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 8	Final
i	1	1	2	3	4	5
key	N/A	3	8	1	2	N/A
j	N/A	-1	1	-1	0	N/A
Array	[5, 3, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 8, 1, 2]	[1, 3, 5, 8, 2]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we shift elements instead of swapping?

We shift elements to the right to make space for the key. Swapping repeatedly would be inefficient. See steps 1,4,5 where elements move right to insert the key.

Why does the inner loop stop when j < 0?

Because j < 0 means we reached the start of the array and the key is the smallest so far. See step 2 and 7 where j becomes -1 and loop stops.

Why do we insert key at j+1 after shifting?

After shifting elements greater than key right, j points to one less than the correct position. So key goes at j+1. See step 12 where key=2 inserted at index 1.

Visual Quiz - 3 Questions

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

A [1, 3, 5, 8, 2]

B [3, 3, 5, 8, 2]

C [3, 5, 8, 1, 2]

D [5, 3, 8, 1, 2]

💡 Hint

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

At which step does the key 8 get inserted without any shifts?

A Step 3

B Step 4

C Step 1

D Step 8

💡 Hint

Look for steps where 'Shift?' is 'No' and key is 8 in execution_table.

If the initial array was already sorted, how would the 'Shift?' column change?

A All 'Yes' because elements shift every time

B All 'No' because no elements are greater than key

C Alternating 'Yes' and 'No'

D Only the last step is 'Yes'

💡 Hint

In a sorted array, no element is greater than the key, so no shifts happen.

Concept Snapshot

Insertion Sort Algorithm:
- Start from second element (index 1)
- Pick key and compare with sorted left part
- Shift elements greater than key right
- Insert key at correct position
- Repeat until array end
- Result: sorted array in-place

Full Transcript

Insertion sort works by taking one element at a time from the unsorted part and inserting it into the correct position in the sorted part on the left. We start from index 1, pick the key element, and compare it with elements before it. If elements are greater than the key, we shift them right to make space. When we find the correct spot, we insert the key. This repeats until the whole array is sorted. The execution table shows each step, the key chosen, comparisons, shifts, and the array state after each operation. Key moments clarify why shifting is used instead of swapping, why the inner loop stops when j < 0, and why insertion happens at j+1. The visual quiz tests understanding of array states and behavior during sorting. This method sorts the array in-place with simple steps and is easy to understand for beginners.

Practice

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

easy

A. Build the sorted array one element at a time by inserting elements in the correct position

B. Divide the array into halves and sort each half recursively

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

D. Use a heap data structure to sort elements

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted list by taking one element at a time and placing it in the correct position among the already sorted elements.

2. Step 2: Compare with other sorting methods

   Other options describe different algorithms: divide and conquer is merge sort, swapping adjacent elements is bubble sort, and heap data structure is heap sort.

3. Final Answer:

   Build the sorted array one element at a time by inserting elements in the correct position -> Option A

4. Quick Check:

   Insertion sort = Insert elements step-by-step [OK]

Hint: Insertion sort inserts elements one by one in order [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking insertion sort divides array recursively
• Mixing up heap sort with insertion sort

2. Which of the following is the correct syntax for the inner loop in insertion sort in C?

easy

A. for (int j = n - 1; j > i; j--)

B. for (int j = 0; j < i; j++)

C. for (int j = i - 1; j >= 0 && arr[j] > key; j--)

D. for (int j = i + 1; j < n; j++)

Solution

1. Step 1: Identify inner loop role in insertion sort

   The inner loop moves backward from the current element's previous index, shifting elements greater than the key to the right.

2. Step 2: Match syntax with this logic

   for (int j = i - 1; j >= 0 && arr[j] > key; j--) correctly uses a loop starting from i-1 down to 0, checking if arr[j] > key and decrementing j.

3. Final Answer:

   for (int j = i - 1; j >= 0 && arr[j] > key; j--) -> Option C

4. Quick Check:

   Inner loop moves backward while arr[j] > key [OK]

Hint: Inner loop goes backward checking elements > key [OK]

Common Mistakes:

• Using forward loop instead of backward
• Not checking arr[j] > key condition
• Incorrect loop boundaries

3. What will be the output array after running insertion sort on int arr[] = {4, 3, 2, 1};?

medium

A. [4, 3, 2, 1]

B. [1, 3, 2, 4]

C. [2, 3, 4, 1]

D. [1, 2, 3, 4]

Solution

1. Step 1: Trace insertion sort on given array

   Start with 4, then insert 3 before 4, array becomes [3,4,2,1]. Insert 2 before 3, array becomes [2,3,4,1]. Insert 1 before 2, array becomes [1,2,3,4].

2. Step 2: Confirm final sorted array

   After all insertions, the array is sorted ascending: [1, 2, 3, 4].

3. Final Answer:

   [1, 2, 3, 4] -> Option D

4. Quick Check:

   Sorted ascending = [1, 2, 3, 4] [OK]

Hint: Insertion sort sorts ascending step-by-step [OK]

Common Mistakes:

• Assuming array stays the same
• Mixing up partial sorted arrays
• Not moving elements correctly

4. Identify the error in this insertion sort snippet:

for (int i = 1; i < n; i++) {
  int key = arr[i];
  int j = i - 1;
  while (j >= 0 && arr[j] < key) {
    arr[j + 1] = arr[j];
    j--;
  }
  arr[j + 1] = key;
}

medium

A. The loop should start from i = 0, not i = 1

B. The comparison in while loop should be arr[j] > key, not arr[j] < key

C. The assignment arr[j + 1] = key is outside the loop

D. Variable j should be incremented, not decremented

Solution

1. Step 1: Understand insertion sort comparison logic

   Insertion sort shifts elements greater than key to the right, so condition must be arr[j] > key.

2. Step 2: Check given code's while condition

   The code uses arr[j] < key, which incorrectly shifts smaller elements, breaking sorting.

3. Final Answer:

   The comparison in while loop should be arr[j] > key, not arr[j] < key -> Option B

4. Quick Check:

   Correct comparison is arr[j] > key [OK]

Hint: Shift elements greater than key, so use > in condition [OK]

Common Mistakes:

• Using < instead of > in while condition
• Starting loop from wrong index
• Misplacing key assignment

5. Given an array int arr[] = {5, 2, 9, 1, 5, 6};, how many total shifts (element moves) does insertion sort perform to sort it?

hard

A. 6

B. 9

C. 7

D. 10

Solution

1. Step 1: Trace insertion sort shifts step-by-step

   Start with array: [5,2,9,1,5,6]
   i=1 (key=2): shift 5 right (1 shift) -> [2,5,9,1,5,6]
   i=2 (key=9): no shift (0 shifts)
   i=3 (key=1): shift 9, then 5, then 2 right (3 shifts) -> [1,2,5,9,5,6]
   i=4 (key=5): shift 9 right (1 shift) -> [1,2,5,5,9,6]
   i=5 (key=6): shift 9 right (1 shift) -> [1,2,5,5,6,9]
   Total shifts = 1 + 0 + 3 + 1 + 1 = 6 shifts

2. Step 2: Confirm total shifts

   Counting carefully, total shifts are 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count shifts carefully = 6 [OK]

Hint: Count each element move during insertion steps [OK]

Common Mistakes:

• Counting only key placements, not shifts
• Missing multiple shifts in one iteration
• Confusing swaps with shifts