Insertion Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Insertion Sort on a small array

What is the output of the following Go code that uses insertion sort on the array [4, 3, 2, 1]?

DSA Go

package main
import "fmt"
func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}
func main() {
    arr := []int{4, 3, 2, 1}
    insertionSort(arr)
    fmt.Println(arr)
}

A [1 3 2 4]

B [4 3 2 1]

C [1 2 3 4]

D [2 3 4 1]

💡 Hint

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

Insertion sort sorts the array in ascending order by inserting each element into its correct position in the sorted part of the array.

❓ Predict Output

intermediate

Insertion Sort with duplicate elements

What will be the output after running insertion sort on the array [5, 3, 5, 2, 2]?

DSA Go

package main
import "fmt"
func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}
func main() {
    arr := []int{5, 3, 5, 2, 2}
    insertionSort(arr)
    fmt.Println(arr)
}

A [5 3 5 2 2]

B [3 2 2 5 5]

C [2 3 5 2 5]

D [2 2 3 5 5]

💡 Hint

Duplicates should be placed next to each other in sorted order.

Insertion sort keeps duplicates in order and sorts the array ascendingly.

🧠 Conceptual

advanced

Time complexity of insertion sort in worst case

What is the time complexity of insertion sort in the worst case scenario?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

💡 Hint

Worst case happens when the array is sorted in reverse order.

Insertion sort compares each element with all previous elements in worst case, leading to O(n^2) time.

🔧 Debug

advanced

Identify the bug in this insertion sort code

What error will this Go code produce when running insertion sort?

DSA Go

package main
import "fmt"
func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}
func main() {
    arr := []int{3, 1, 2}
    insertionSort(arr)
    fmt.Println(arr)
}

A Runtime panic: index out of range

B [1 2 3]

C [3 1 2]

D Syntax error: missing colon

💡 Hint

Check the initial value of j and array indexing inside the loop.

j starts at i instead of i-1, causing arr[j] to access out of range when j == len(arr).

🚀 Application

expert

Number of shifts in insertion sort for a given array

How many times will elements be shifted (moved) during insertion sort on the array [8, 4, 3, 7, 6]?

A 4

B 6

C 5

D 7

💡 Hint

Count each time an element is moved to the right during sorting.

Shifts happen when elements are moved to make space for the key. Counting carefully gives 6 shifts.

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. Build the sorted array one element at a time by inserting elements into their correct position

C. Swap adjacent elements if they are in 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 the sorted list by taking one element at a time and placing it in the correct position relative to the already sorted part.

2. Step 2: Compare with other sorting methods

   Other options describe merge sort (B), bubble sort (C), and selection sort (D), which are different algorithms.

3. Final Answer:

   Build the sorted array one element at a time by inserting elements into their correct position -> Option B

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 or selection sort
• Thinking insertion sort divides array recursively
• Assuming insertion sort swaps all elements repeatedly

2. Which of the following Go code snippets correctly starts the outer loop for insertion sort on a slice arr?

easy

A. for i := 1; i < len(arr); i++ {

B. for i := 0; i < len(arr); i++ {

C. for i := len(arr)-1; i >= 0; i-- {

D. for i := 1; i <= len(arr); i++ {

Solution

1. Step 1: Identify correct loop start for insertion sort

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

2. Step 2: Check loop conditions

   Loop runs while i is less than length of array. for i := 1; i < len(arr); i++ { matches this exactly.

3. Final Answer:

   for i := 1; i < len(arr); i++ { -> Option A

4. Quick Check:

   Start from index 1 to end [OK]

Hint: Start outer loop at 1, not 0, for insertion sort [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using <= instead of < in loop condition
• Looping backwards incorrectly

3. What will be the output slice after running insertion sort on arr := []int{4, 3, 2, 1}?

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace insertion sort on given array

   Start with 4 (sorted). Insert 3 before 4 -> [3,4,2,1]. Insert 2 before 3 -> [2,3,4,1]. Insert 1 before 2 -> [1,2,3,4].

2. Step 2: Confirm final sorted slice

   The array is sorted in ascending order: [1, 2, 3, 4].

3. Final Answer:

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

4. Quick Check:

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

Hint: Insertion sort outputs sorted ascending array [OK]

Common Mistakes:

• Assuming no change in array
• Stopping sorting early
• Mixing up partial sorted states

4. Identify the error in this Go insertion sort snippet:

for i := 1; i < len(arr); i++ {
    key := arr[i]
    j := i - 1
    for j >= 0 && arr[j] > key {
        arr[j+1] = arr[j]
        j--
    }
    arr[j] = key
}

medium

A. The outer loop should start from i := 0

B. The inner loop condition should be arr[j] < key

C. The variable key should be declared outside the loop

D. The final assignment should be arr[j+1] = key, not arr[j] = key

Solution

1. Step 1: Analyze inner loop and final assignment

   After shifting elements greater than key, the correct position is j+1, but code assigns key to arr[j], which is incorrect.

2. Step 2: Correct the assignment

   It should be arr[j+1] = key to place key in the right spot after shifting.

3. Final Answer:

   The final assignment should be arr[j+1] = key, not arr[j] = key -> Option D

4. Quick Check:

   Insert key at arr[j+1] after shifting [OK]

Hint: Assign key to arr[j+1], not arr[j], after shifting [OK]

Common Mistakes:

• Assigning key to wrong index after inner loop
• Reversing comparison operator in inner loop
• Starting outer loop at 0

5. Given a slice arr := []int{5, 2, 9, 1, 5, 6}, how many total element shifts occur during insertion sort?

hard

A. 7

B. 6

C. 8

D. 5

Solution

1. Step 1: Trace shifts for each insertion

   Insert 2: shift 5 -> 1 shift
   Insert 9: no shift -> 0 shifts
   Insert 1: shift 9, 5, 2 -> 3 shifts
   Insert 5: shift 9, 5 -> 2 shifts
   Insert 6: shift 9 -> 1 shift

2. Step 2: Sum all shifts

   Total shifts = 1 + 0 + 3 + 2 + 1 = 7 shifts.

3. Step 3: Verify options

   7 is present as 7.

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Count shifts carefully for each insertion [OK]

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

Common Mistakes:

• Counting comparisons instead of shifts
• Missing shifts when multiple elements move
• Confusing shifts with swaps