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, just like organizing books by height on a shelf.

🎯 Goal: Build a program that sorts a list of numbers using the insertion sort method, which picks one number at a time and places it in the right spot.

📋 What You'll Learn

Create an array called numbers with the exact values: 8, 3, 5, 1, 9

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

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

Inside the loop, use a variable key to hold the current number at index i

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

Place the key in its correct sorted position

Print the sorted array in one line separated by spaces

💡 Why This Matters

🌍 Real World

Sorting is used in many places like organizing files, arranging data for faster search, or displaying lists in order.

💼 Career

Understanding sorting algorithms like insertion sort helps in software development, data analysis, and preparing for technical interviews.

1

Create the array of numbers

Create an integer array called numbers with these exact values: 8, 3, 5, 1, 9. Also create an integer variable called n and set it to the size of the array, which is 5.

DSA C

# Create the array 'numbers' and the variable 'n'
# Your code here

Hint

Use curly braces to list the numbers inside the array. Set n to 5 because there are 5 numbers.

2

Set up the outer loop for insertion sort

Add a for loop with variable i starting from 1 up to n - 1 to go through each number in the array except the first one.

DSA C

int numbers[] = {8, 3, 5, 1, 9};
int n = 5;

// Add a for loop with i from 1 to n-1
// Your code here

Hint

The loop starts at 1 because the first element is considered sorted.

3

Implement the insertion logic inside the loop

Inside the for loop, create an integer variable key and set it to numbers[i]. Create another integer variable j and set it to i - 1. Then use a while loop that runs while j >= 0 and numbers[j] > key. Inside the while loop, move numbers[j] to numbers[j + 1] and decrease j by 1. After the while loop, place key at numbers[j + 1].

DSA C

int numbers[] = {8, 3, 5, 1, 9};
int n = 5;

for (int i = 1; i < n; i++) {
    // Add insertion sort logic here
    // Your code here
}

Hint

Think of key as the number you want to insert in the right place. Move bigger numbers one step right to make space.

4

Print the sorted array

After the for loop, use a for loop with variable k from 0 to n - 1 to print each number in numbers separated by a space. Use printf("%d ", numbers[k]). Then print a newline with printf("\n").

DSA C

int numbers[] = {8, 3, 5, 1, 9};
int n = 5;

for (int i = 1; i = 0 && numbers[j] > key) {
        numbers[j + 1] = numbers[j];
        j--;
    }
    numbers[j + 1] = key;
}

// Print the sorted array
// Your code here

Hint

Print each number followed by a space, then print a newline after the loop.

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