Insertion Sort Algorithm in DSA C++ - Build from Scratch

Insertion Sort Algorithm

📖 Scenario: You have a small list of numbers that you want to arrange from smallest to largest. This is like organizing books on a shelf by their height, one by one.

🎯 Goal: Build a program that sorts a list of numbers using the insertion sort method, showing how the list becomes sorted step by step.

📋 What You'll Learn

Create an array called arr with the exact values: 8, 3, 5, 4, 6

Create an integer variable called n that stores the size of arr

Use a for loop with variable i starting from 1 to n - 1

Inside the loop, use a variable key to hold the current element arr[i]

Use a while loop with variable j to move elements greater than key one position ahead

Insert the key at the correct sorted position

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Sorting small lists manually is useful in simple apps like organizing scores, names, or small datasets where quick sorting is needed without complex tools.

💼 Career

Understanding insertion sort helps in grasping basic sorting concepts, which are foundational for many programming and data processing jobs.

1

Create the initial array

Create an integer array called arr with the exact values: 8, 3, 5, 4, 6.

DSA C++

# Create the array arr with values 8, 3, 5, 4, 6
// Your code here

Hint

Use C++ array syntax: int arr[] = {values};

2

Set the size of the array

Create an integer variable called n that stores the size of the array arr using sizeof(arr) / sizeof(arr[0]).

DSA C++

int arr[] = {8, 3, 5, 4, 6};
// Create an integer variable n to store the size of arr
// Your code here

Hint

Use sizeof(arr) / sizeof(arr[0]) to get the number of elements.

3

Implement the insertion sort logic

Use a for loop with variable i from 1 to n - 1. Inside the loop, create an integer key equal to arr[i]. Then create an integer j equal to i - 1. Use a while loop to move elements greater than key one position ahead by setting arr[j + 1] = arr[j] and decrementing j. After the while loop, insert key at position j + 1.

DSA C++

int arr[] = {8, 3, 5, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
// Write the insertion sort algorithm below
// Your code here

Hint

Follow the insertion sort steps: pick key, shift larger elements, insert key.

4

Print the sorted array

Use a for loop with variable i from 0 to n - 1 to print each element of arr separated by spaces using std::cout. End with a newline.

DSA C++

int arr[] = {8, 3, 5, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 1; i = 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}
// Print the sorted array elements separated by spaces
// Your code here

Hint

Use a loop to print each element followed by a space, then print a newline.

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