Insertion Sort Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the outer loop from the second element in the array.

DSA C

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;
}

Drag options to blanks, or click blank then click option'

A2

B0

C1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop at 0 causes unnecessary comparisons.

Starting loop at n causes no sorting.

The insertion sort starts from the second element (index 1) because the first element is considered sorted.

2fill in blank

medium

Complete the code to correctly shift elements greater than the key to the right.

DSA C

while (j >= 0 && arr[j] [1] key) {
    arr[j + 1] = arr[j];
    j--;
}

Drag options to blanks, or click blank then click option'

A>

B<=

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' causes incorrect shifting.

Using '==' causes no movement.

We shift elements that are greater than the key to the right to make space for the key.

3fill in blank

hard

Fix the error in the code to place the key at the correct position after shifting.

DSA C

arr[[1]] = key;

Drag options to blanks, or click blank then click option'

Aj + 1

Bi

Cj

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using j places key in wrong index.

Using i places key at original position.

After shifting, the correct position for the key is at index j + 1.

4fill in blank

hard

Fill both blanks to create a function header and call for insertion sort.

DSA C

[1] insertionSort(int arr[], int n) {
    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;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    [2];
    return 0;
}

Drag options to blanks, or click blank then click option'

Avoid

Bint

CinsertionSort(arr, n)

DinsertionSort(n, arr)

Attempts:

3 left

💡 Hint

Common Mistakes

Using int as return type causes warnings.

Swapping arguments in function call causes errors.

The function returns nothing, so use 'void'. The call passes array and size in correct order.

5fill in blank

hard

Fill all three blanks to print the sorted array after insertion sort.

DSA C

for (int [1] = 0; [2] < n; [3]++) {
    printf("%d ", arr[i]);
}

Drag options to blanks, or click blank then click option'

Ai

Bj

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causes compilation errors.

Using 'j' or 'k' inconsistently causes errors.

The loop variable is 'i' used consistently to print all elements.

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