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

Recall & Review

beginner

What is the main 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 already sorted elements.

beginner

In Insertion Sort, what happens when the current element is smaller than the elements before it?

The elements larger than the current element are shifted one position to the right to make space, and then the current element is inserted in the correct position.

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

Show the state of the array after inserting the third element in the array [4, 3, 2, 1] using Insertion Sort.

After inserting the third element (2), the array looks like [2, 3, 4, 1].

intermediate

Why is Insertion Sort efficient for nearly sorted data?

Because it only shifts elements when necessary, Insertion Sort performs fewer operations when the list is almost sorted, making it close to O(n) in such cases.

What does Insertion Sort do with the current element during sorting?

A Removes it from the list

B Swaps it with the last element

C Ignores it if it is smaller

D Inserts it into the correct position among sorted elements

Insertion Sort inserts the current 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)

The best case is when the array is already sorted, so Insertion Sort only makes one pass, resulting in O(n) time.

Which of these is true about Insertion Sort?

A It sorts by dividing the list into halves

B It always uses extra memory

C It is a stable sorting algorithm

D It is faster than Quick Sort for large lists

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

During Insertion Sort, what happens if the current element is larger than all sorted elements?

A It stays in its place

B It is placed at the beginning

C It is removed

D It swaps with the smallest element

If the current element is larger than all sorted elements, it stays in its place as it is already in the correct position.

Which real-life activity is similar to Insertion Sort?

A Filing papers randomly

B Sorting playing cards in your hand

C Cutting a cake into pieces

D Shuffling a deck of cards

Insertion Sort is like sorting playing cards one by one into the right position in your hand.

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

Think about how you sort cards in your hand.

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

Consider how many shifts happen in different list orders.

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 in their correct position

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

   Unlike divide and conquer (merge sort) or swapping adjacent elements (bubble sort), insertion sort inserts elements directly into their correct place.

3. Final Answer:

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

4. Quick Check:

   Insertion sort = Insert elements correctly one by one [OK]

Hint: Insertion sort inserts elements into sorted part step-by-step [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking it divides array like merge sort
• Assuming it swaps only smallest elements

2. Which of the following Rust code snippets correctly starts the insertion sort outer loop?

easy

A. for i in 1..arr.len() {

B. for i in 0..arr.len() {

C. for i in (1..arr.len()).rev() {

D. for i in 0..arr.len()-1 {

Solution

1. Step 1: Identify insertion sort loop start

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

2. Step 2: Check Rust range syntax

   The range 1..arr.len() correctly iterates from index 1 to the last index (exclusive of arr.len()).

3. Final Answer:

   for i in 1..arr.len() { -> Option A

4. Quick Check:

   Start loop at 1 for insertion sort [OK]

Hint: Insertion sort outer loop starts at index 1 [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using reversed range incorrectly
• Off-by-one errors in range

3. What will be the output of the following Rust code after running insertion sort on arr = [4, 3, 1, 5]?

let mut arr = vec![4, 3, 1, 5];
for i in 1..arr.len() {
    let key = arr[i];
    let mut j = i;
    while j > 0 && arr[j - 1] > key {
        arr[j] = arr[j - 1];
        j -= 1;
    }
    arr[j] = key;
}
println!("{:?}", arr);

medium

A. [3, 4, 1, 5]

B. [4, 3, 1, 5]

C. [1, 3, 4, 5]

D. [1, 4, 3, 5]

Solution

1. Step 1: Trace first iteration (i=1)

   key=3, compare with 4; 4 > 3 so shift 4 right, insert 3 at index 0. Array: [3,4,1,5]

2. Step 2: Trace second iteration (i=2)

   key=1, compare with 4 and 3; both >1 so shift them right, insert 1 at index 0. Array: [1,3,4,5]

3. Step 3: Trace third iteration (i=3)

   key=5, compare with 4; 4 < 5 so no shift, insert 5 at index 3. Array unchanged: [1,3,4,5]

4. Final Answer:

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

5. Quick Check:

   Sorted array after insertion sort = [1, 3, 4, 5] [OK]

Hint: Trace each key insertion step-by-step [OK]

Common Mistakes:

• Not shifting elements correctly
• Off-by-one errors in while loop
• Printing original array without sorting

4. Identify the bug in this Rust insertion sort snippet:

let mut arr = vec![2, 5, 3];
for i in 1..arr.len() {
    let key = arr[i];
    let mut j = i - 1;
    while j >= 0 && arr[j] > key {
        arr[j + 1] = arr[j];
        j -= 1;
    }
    arr[j + 1] = key;
}

medium

A. The key is not assigned correctly

B. The array is not mutable

C. The for loop range is incorrect

D. The variable j is unsigned and j >= 0 check causes infinite loop

Solution

1. Step 1: Analyze variable j type and condition

   In Rust, usize is unsigned, so j >= 0 is always true, causing infinite loop when j underflows.

2. Step 2: Understand while loop behavior

   When j reaches 0 and decrements, it wraps to a large number, so loop never ends.

3. Final Answer:

   The variable j is unsigned and j >= 0 check causes infinite loop -> Option D

4. Quick Check:

   Unsigned j with j >= 0 causes infinite loop [OK]

Hint: Unsigned index can't be checked with j >= 0 safely [OK]

Common Mistakes:

• Ignoring unsigned integer wrap-around
• Assuming j can be negative
• Not using a different loop condition

5. You want to modify insertion sort in Rust to sort a vector of tuples Vec<(i32, String)> by the integer value. Which change is needed in the comparison inside the while loop?

hard

A. Change arr[j - 1] > key to arr[j - 1].0 > key.0

B. Change arr[j - 1] > key to arr[j - 1].1 > key.1

C. No change needed, tuples compare automatically by second element

D. Change arr[j - 1] > key to arr[j - 1].1.len() > key.1.len()

Solution

1. Step 1: Understand tuple sorting by first element

   To sort by the integer part of the tuple, compare the first element (.0) of each tuple.

2. Step 2: Modify comparison in while loop

   Replace arr[j - 1] > key with arr[j - 1].0 > key.0 to compare integers correctly.

3. Final Answer:

   Change arr[j - 1] > key to arr[j - 1].0 > key.0 -> Option A

4. Quick Check:

   Compare tuple first elements for sorting [OK]

Hint: Compare tuple.0 to sort by integer part [OK]

Common Mistakes:

• Comparing string part instead of integer
• Assuming tuples compare by second element automatically
• Using length of string for comparison