Insertion Sort Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the basic idea behind the Insertion Sort Algorithm?

Insertion Sort builds the sorted list one element at a time by taking each element and inserting it into its correct position among the previously sorted elements.

beginner

How does Insertion Sort handle the elements during sorting?

It picks the next element and compares it backward with the sorted part, shifting larger elements one position ahead to make space for the new element.

intermediate

What is the time complexity of Insertion Sort in the worst case?

The worst-case time complexity is O(n²), which happens when the input list is sorted in reverse order.

intermediate

Why is Insertion Sort efficient for nearly sorted data?

Because it only shifts elements when necessary, so if the data is almost sorted, fewer shifts are needed, making it close to O(n) time.

beginner

Show the first three steps of Insertion Sort on the array [5, 3, 8, 6].

Step 1: [5, 3, 8, 6] (start with first element sorted) Step 2: [3, 5, 8, 6] (insert 3 before 5) Step 3: [3, 5, 8, 6] (8 is already in correct place)

What does Insertion Sort do with each new element it processes?

A Swaps it with the last element

B Inserts it into the correct position in the sorted part

C Ignores it if it is larger than the previous

D Removes duplicates

Insertion Sort inserts each new element into its correct position among the already sorted elements.

What is the best-case time complexity of Insertion Sort?

A O(n)

B O(n log n)

C O(n²)

D O(log n)

When the array is already sorted, Insertion Sort only compares each element once, resulting in O(n) time.

Which of these is true about Insertion Sort?

A It requires extra memory proportional to input size

B It sorts by dividing the array into halves

C It is faster than Quick Sort on large random data

D It is a stable sorting algorithm

Insertion Sort is stable because it does not change the relative order of equal elements.

In Insertion Sort, what happens when the current element is smaller than elements in the sorted part?

A The current element is swapped with the first element

B The current element is discarded

C Those elements are shifted right to make space

D The array is reversed

Elements larger than the current element are shifted one position to the right to insert the current element correctly.

Which scenario causes the worst-case performance for Insertion Sort?

A Array is sorted in reverse order

B Array is already sorted

C Array has all equal elements

D Array is empty

When the array is sorted in reverse order, Insertion Sort must shift every element for each insertion, causing O(n²) time.

Explain how Insertion Sort works step-by-step on a small array.

Think about sorting playing cards in your hand.

Describe the time complexity of Insertion Sort and when it performs best and worst.

Consider how many shifts happen depending on the order of the input.

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