Insertion Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Insertion Sort Algorithm

Start with second element i=1

↓

Compare current element with elements before it

↓

Shift elements greater than current to the right

↓

Insert current element at correct position

↓

Increment i

↓

i < array length?

No→Sorted array ready

↩Back to Compare

Insertion sort picks each element from the second one, shifts bigger elements to the right, and inserts it in the correct place, repeating until the array is sorted.

Execution Sample

DSA C++

int arr[] = {5, 3, 8, 1, 2};
int n = 5;
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;
}

Sorts the array by inserting each element into its correct position among the previously sorted elements.

Execution Table

Step	Operation	Array State	Comparison	Shift or Insert	Visual State
1	Pick element at i=1 (3)	[5, 3, 8, 1, 2]	5 > 3	Shift 5 right	[5, 5, 8, 1, 2]
2	Insert key 3 at position j+1=0	[5, 5, 8, 1, 2]	N/A	Insert 3	[3, 5, 8, 1, 2]
3	Pick element at i=2 (8)	[3, 5, 8, 1, 2]	5 > 8? No	No shift	[3, 5, 8, 1, 2]
4	Pick element at i=3 (1)	[3, 5, 8, 1, 2]	8 > 1	Shift 8 right	[3, 5, 8, 8, 2]
5	Compare 5 > 1	[3, 5, 8, 8, 2]	5 > 1	Shift 5 right	[3, 5, 5, 8, 2]
6	Compare 3 > 1	[3, 5, 5, 8, 2]	3 > 1	Shift 3 right	[3, 3, 5, 8, 2]
7	Insert key 1 at position j+1=0	[3, 3, 5, 8, 2]	N/A	Insert 1	[1, 3, 5, 8, 2]
8	Pick element at i=4 (2)	[1, 3, 5, 8, 2]	8 > 2	Shift 8 right	[1, 3, 5, 8, 8]
9	Compare 5 > 2	[1, 3, 5, 8, 8]	5 > 2	Shift 5 right	[1, 3, 5, 5, 8]
10	Compare 3 > 2	[1, 3, 5, 5, 8]	3 > 2	Shift 3 right	[1, 3, 3, 5, 8]
11	Compare 1 > 2? No	[1, 3, 3, 5, 8]	1 > 2? No	No shift	[1, 3, 3, 5, 8]
12	Insert key 2 at position j+1=1	[1, 3, 3, 5, 8]	N/A	Insert 2	[1, 2, 3, 5, 8]
13	i=5 equals array length, sorting done	[1, 2, 3, 5, 8]	N/A	Done	[1, 2, 3, 5, 8]

💡 i reaches array length 5, no more elements to insert, array is sorted

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	Final
i	1	1	1	2	3	3	3	3	4	4	4	4	4	5
key	3	3	3	8	1	1	1	1	2	2	2	2	2	N/A
j	0	-1	-1	1	1	0	-1	-1	2	1	0	0	0	N/A
Array	[5, 3, 8, 1, 2]	[5, 5, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 8, 8, 2]	[3, 5, 5, 8, 2]	[3, 3, 5, 8, 2]	[1, 3, 5, 8, 2]	[1, 3, 5, 8, 8]	[1, 3, 5, 5, 8]	[1, 3, 3, 5, 8]	[1, 3, 3, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we shift elements to the right instead of swapping directly?

We shift elements to the right to make space for the key element to be inserted at the correct position. This is shown in steps 1, 4, 5, 6, 8, 9, and 10 where elements are moved right before inserting the key.

Why does the inner loop stop when arr[j] <= key?

The inner loop stops because the correct position for the key is found when the element at j is less than or equal to the key. This is shown in step 11 where 1 > 2 is false, so no more shifting happens.

What happens when the key is already greater than the previous element?

No shifting is needed and the key stays in place. This is shown in step 3 where 5 > 8 is false, so the array remains unchanged.

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 [1, 2, 3, 5, 8]

💡 Hint

Check the 'Array State' column in row with Step 7 in execution_table.

At which step does the condition 'arr[j] > key' become false for the first time?

A Step 6

B Step 11

C Step 3

D Step 9

💡 Hint

Look at the 'Comparison' column in execution_table rows to find where 'arr[j] > key' is false.

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

A All shifts would be replaced by inserts

B No shifts would occur, only inserts at the same position

C Shifts would increase because elements are moved more

D The array would be reversed

💡 Hint

Refer to variable_tracker and execution_table to see when shifts happen and when they don't.

Concept Snapshot

Insertion Sort Algorithm:
- Start from second element (index 1)
- Compare with previous elements
- Shift larger elements right
- Insert current element at correct position
- Repeat until array is sorted
- Time: O(n^2), Space: O(1)

Full Transcript

Insertion sort works by taking each element from the second position onward and inserting it into the correct place among the elements before it. We compare the current element (key) with elements to its left. If those elements are bigger, we shift them one position to the right to make space. When we find the right spot, we insert the key. This repeats until the whole array is sorted. The execution table shows each step with array states, comparisons, shifts, and insertions. Variables i, j, and key track the current positions and values. Key moments clarify why shifting is done instead of swapping, when the inner loop stops, and what happens if the array is already sorted. The visual quiz tests understanding of array states and conditions during sorting. Insertion sort is simple but can be slow for large arrays.

Practice

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

easy

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

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

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

D. Select the smallest element and swap it with the first unsorted element

Solution

1. Step 1: Understand the insertion process

   Insertion sort takes one element at a time and inserts it into the correct position in the already sorted part of the array.

2. Step 2: Compare with other sorting methods

   Unlike divide and conquer (merge sort) or swapping adjacent elements (bubble sort), insertion sort builds the sorted array gradually by insertion.

3. Final Answer:

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

4. Quick Check:

   Insertion sort = Insert elements correctly one by one [OK]

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

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking it divides array like merge sort
• Assuming it swaps only smallest elements

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

easy

A. for (int j = i + 1; j < n && arr[j] < key; j++)

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

C. for (int j = 0; j < i && arr[j] < key; j++)

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

Solution

1. Step 1: Identify the inner loop role

   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 the correct loop condition

   The loop continues while j >= 0 and arr[j] > key, decrementing j each time.

3. Final Answer:

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

4. Quick Check:

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

Hint: Inner loop moves backward while element is greater than key [OK]

Common Mistakes:

• Using j++ instead of j-- in inner loop
• Checking arr[j] < key instead of > key
• Starting inner loop from wrong index

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

medium

A. [2, 3, 4, 1]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [1, 2, 3, 4]

Solution

1. Step 1: Trace first iteration

   Insert 3 into sorted part {4}: shift 4 right, array becomes {3,4,2,1}.

2. Step 2: Trace second iteration

   Insert 2 into {3,4}: shift 4 and 3 right, array becomes {2,3,4,1}.

3. Step 3: Trace third iteration

   Insert 1 into {2,3,4}: shift all right, array becomes {1,2,3,4}.

4. Final Answer:

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

5. Quick Check:

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

Hint: Insertion sort sorts ascending by shifting larger elements right [OK]

Common Mistakes:

• Assuming array stays same if reversed
• Stopping after first iteration
• Not shifting all larger elements

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 comparison in while should be arr[j] > key, not arr[j] < key

B. The loop should start from i = 0 instead of i = 1

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

D. The decrement j-- should be j++ inside the while loop

Solution

1. Step 1: Understand the while loop condition

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

2. Step 2: Identify the incorrect comparison

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

3. Final Answer:

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

4. Quick Check:

   Shift elements greater than key, so condition is arr[j] > key [OK]

Hint: While loop compares arr[j] > key to shift larger elements [OK]

Common Mistakes:

• Using wrong comparison sign in while condition
• Starting loop from wrong index
• Misplacing key assignment inside loop

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

hard

A. 6

B. 7

C. 10

D. 5

Solution

1. Step 1: Insert 2 into {5}

   Shift 5 right (1 shift). Array: {2, 5, 9, 1, 5, 6}

2. Step 2: Insert 9 into {2, 5}

   No shift needed since 9 > 5 (0 shifts).

3. Step 3: Insert 1 into {2, 5, 9}

   Shift 9, 5, 2 right (3 shifts). Array: {1, 2, 5, 9, 5, 6}

4. Step 4: Insert 5 into {1, 2, 5, 9}

   Shift 9 right (1 shift, stops at 5 == 5). Array: {1, 2, 5, 5, 9, 6}

5. Step 5: Insert 6 into {1, 2, 5, 5, 9}

   Shift 9 right (1 shift). Array: {1, 2, 5, 5, 6, 9}

6. Final Answer:

   6 -> Option A

7. Quick Check:

   Total shifts = 1 + 0 + 3 + 1 + 1 = 6 [OK]

Hint: Count shifts by tracing each insertion carefully [OK]

Common Mistakes:

• Counting only swaps, not shifts
• Missing shifts for repeated elements
• Confusing key placement with shifts