Insertion Sort Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Insertion Sort on a small list

What is the output of the following insertion sort code when sorting the list [4, 3, 2, 1]?

DSA Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [4, 3, 2, 1]
insertion_sort(arr)
print(arr)

A [1, 2, 3, 4]

B [1, 3, 2, 4]

C [4, 3, 2, 1]

D [2, 3, 4, 1]

💡 Hint

Insertion sort moves smaller elements to the front step by step.

Insertion sort compares each element with those before it and inserts it in the correct position, resulting in a sorted list.

🧠 Conceptual

intermediate

Number of comparisons in insertion sort best case

In the best case, when the input list is already sorted, how many comparisons does insertion sort make for a list of size n?

A n^2

B n * (n - 1) / 2

C n - 1

D n

💡 Hint

Best case means no shifting is needed.

In the best case, each element is compared once with the previous element, so total comparisons are n - 1.

❓ Predict Output

advanced

Output after partial insertion sort steps

What is the state of the list after the second iteration (i=2) of insertion sort on [5, 3, 4, 1]?

DSA Python

def insertion_sort_partial(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        if i == 2:
            print(arr)
            break

arr = [5, 3, 4, 1]
insertion_sort_partial(arr)

A [3, 4, 5, 1]

B [3, 5, 4, 1]

C [4, 3, 5, 1]

D [5, 3, 4, 1]

💡 Hint

Insertion sort sorts elements up to the current index.

After sorting first three elements, the list becomes [3, 4, 5, 1].

🔧 Debug

advanced

Identify the error in insertion sort code

What error will this insertion sort code cause when run on [2, 1]? Code: for i in range(1, len(arr)): key = arr[i] j = i while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key

DSA Python

arr = [2, 1]
for i in range(1, len(arr)):
    key = arr[i]
    j = i
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key
print(arr)

A SyntaxError

B [1, 2]

C [2, 1]

D IndexError

💡 Hint

Check the starting value of j and array indexing.

j is initialized to i instead of i-1. The while condition arr[j] > key is arr[i] > arr[i], which is false, so the loop is not entered. Then arr[j + 1] = key accesses arr[i + 1], which is out of range, causing IndexError.

❓ Predict Output

expert

Insertion sort on linked list output

What is the output of the following code for insertion sort on the linked list 4 -> 2 -> 3 -> 1 -> null?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def insertion_sort_linked_list(head):
    if not head or not head.next:
        return head
    sorted_head = head
    current = head.next
    sorted_head.next = None
    while current:
        temp = current.next
        if current.val < sorted_head.val:
            current.next = sorted_head
            sorted_head = current
        else:
            search = sorted_head
            while search.next and search.next.val < current.val:
                search = search.next
            current.next = search.next
            search.next = current
        current = temp
    return sorted_head

# Create linked list 4 -> 2 -> 3 -> 1 -> null
head = Node(4)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(1)

sorted_head = insertion_sort_linked_list(head)

# Print sorted linked list
result = []
current = sorted_head
while current:
    result.append(current.val)
    current = current.next
print(result)

A [4, 3, 2, 1]

B [1, 2, 3, 4]

C [2, 3, 1, 4]

D [1, 3, 2, 4]

💡 Hint

Insertion sort on linked list inserts nodes in sorted order one by one.

The insertion sort rearranges nodes to ascending order: 1 -> 2 -> 3 -> 4 -> null.

Practice

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

easy

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

B. Divide the list into halves and sort each half separately

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

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

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds a 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

   Options A, B, and D describe other sorting algorithms: bubble sort, merge sort, and selection sort respectively.

3. Final Answer:

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

4. Quick Check:

   Insertion sort = Insert elements in order [OK]

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

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking insertion sort divides the list
• Mixing insertion sort with selection sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort on a list arr of length n in Python?

easy

A. for i in range(0, n-1):

B. for i in range(n):

C. for i in range(1, n):

D. for i in range(n-1, 0, -1):

Solution

1. Step 1: Identify insertion sort loop start

   The outer loop starts from index 1 because the first element (index 0) is considered sorted.

2. Step 2: Check options

   for i in range(1, n): correctly uses range(1, n). Options B and C start from 0 which is incorrect. for i in range(n-1, 0, -1): loops backwards which is not standard for insertion sort.

3. Final Answer:

   for i in range(1, n): -> Option C

4. Quick Check:

   Start loop at 1 for insertion sort [OK]

Hint: Start outer loop from 1, not 0 [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using reverse loop incorrectly
• Confusing loop ranges

3. What will be the output of the following code snippet?

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [4, 3, 2, 1]
insertion_sort(arr)
print(arr)

medium

A. [4, 3, 2, 1]

B. [1, 2, 3, 4]

C. [1, 3, 2, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace the insertion sort on input

   The list [4, 3, 2, 1] is sorted step-by-step by moving smaller elements leftwards until fully sorted.

2. Step 2: Final sorted list

   After sorting, the list becomes [1, 2, 3, 4].

3. Final Answer:

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

4. Quick Check:

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

Hint: Insertion sort outputs sorted ascending list [OK]

Common Mistakes:

• Assuming original list remains unchanged
• Confusing output with partial sorting
• Misreading the while loop condition

4. Find the error in the following insertion sort code:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i
        while j > 0 and arr[j-1] > key:
            arr[j] = arr[j-1]
            j -= 1
        arr[j] = key

arr = [3, 1, 2]
insertion_sort(arr)
print(arr)

medium

A. The for loop should start from 0, not 1

B. The while loop condition should be j >= 0, not j > 0

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

D. The variable j should start at i - 1, not i

Solution

1. Step 1: Check initialization of j

   In insertion sort, j should start at i - 1 to compare the key with previous elements using the standard condition arr[j] > key.

2. Step 2: Verify other parts

   The while loop condition and assignment are correct. The for loop correctly starts at 1.

3. Final Answer:

   The variable j should start at i - 1, not i -> Option D

4. Quick Check:

   j = i - 1 to compare previous elements [OK]

Hint: Start j at i-1 to compare with previous elements [OK]

Common Mistakes:

• Using j = i instead of standard j = i-1
• Changing while loop condition incorrectly
• Misplacing key assignment inside loop

5. Given a list arr = [5, 3, 8, 6, 2], how many total shifts (element moves) will insertion sort perform to sort the list in ascending order?

hard

A. 6

B. 8

C. 7

D. 5

Solution

1. Step 1: Trace shifts during sorting

   Insertion sort shifts elements to insert the key in the correct place:
   - i=1 (key=3): shift 5 right (1 shift)
   - i=2 (key=8): no shift (0 shifts)
   - i=3 (key=6): shift 8 right (1 shift)
   - i=4 (key=2): shift 8, 6, 5, 3 right (4 shifts)

2. Step 2: Calculate total shifts

   Total shifts = 1 + 0 + 1 + 4 = 6 shifts. But note that each shift moves one element one position right. Counting carefully:
   At i=1: 1 shift
   At i=3: 1 shift
   At i=4: 4 shifts
   Total = 6 shifts

3. Step 3: Recount carefully

   Actually, at i=4, elements 3,5,6,8 are shifted right one by one (4 shifts). Total shifts = 1 + 0 + 1 + 4 = 6.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Count shifts per insertion = 6 [OK]

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

Common Mistakes:

• Counting comparisons instead of shifts
• Missing multiple shifts in one insertion
• Confusing shifts with swaps