Insertion Sort Algorithm in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Insertion Sort on a small array

What is the output of the following JavaScript code after sorting the array using insertion sort?

DSA Javascript

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

const result = insertionSort([5, 3, 8, 4, 2]);
console.log(result);

A [2, 3, 4, 5, 8]

B [5, 3, 4, 2, 8]

C [8, 5, 4, 3, 2]

D [3, 2, 4, 5, 8]

💡 Hint

Remember insertion sort places each element in its correct position by comparing backwards.

Insertion sort iterates through the array, inserting each element into its correct position among the previously sorted elements. The final sorted array is [2, 3, 4, 5, 8].

🧠 Conceptual

intermediate

Number of comparisons in insertion sort best case

What is the number of comparisons insertion sort makes when the input array is already sorted?

A n * (n - 1) / 2 comparisons

B n - 1 comparisons

C n^2 comparisons

D 0 comparisons

💡 Hint

In the best case, the inner loop does not shift elements.

When the array is already sorted, insertion sort compares each element once with the previous one, resulting in n - 1 comparisons.

❓ Predict Output

advanced

Output after partial insertion sort steps

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

DSA Javascript

function insertionSortPartial(arr) {
  for (let i = 1; i <= 2; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

const partialResult = insertionSortPartial([7, 2, 5, 3]);
console.log(partialResult);

A [7, 2, 5, 3]

B [2, 5, 3, 7]

C [2, 7, 5, 3]

D [2, 5, 7, 3]

💡 Hint

Trace the first two passes of insertion sort carefully.

After the first iteration, the array becomes [2, 7, 5, 3]. After the second iteration, 5 is inserted before 7, resulting in [2, 5, 7, 3].

🔧 Debug

advanced

Identify the error in this insertion sort implementation

What error does the following insertion sort code produce when run?

DSA Javascript

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] < key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

console.log(insertionSort([4, 3, 2, 1]));

A The array is sorted in descending order instead of ascending

B Infinite loop causing program to hang

C TypeError because of undefined variable

D SyntaxError due to missing semicolon

💡 Hint

Check the comparison operator in the while loop.

The condition arr[j] < key causes the algorithm to sort in descending order, not ascending. No syntax or runtime errors occur.

🚀 Application

expert

Insertion sort on linked list output

Given a singly linked list with nodes containing values [4, 1, 3, 2], what is the linked list after applying insertion sort?

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function insertionSortLinkedList(head) {
  if (!head) return head;
  let sorted = null;
  let current = head;
  while (current) {
    let next = current.next;
    if (!sorted || sorted.value >= current.value) {
      current.next = sorted;
      sorted = current;
    } else {
      let temp = sorted;
      while (temp.next && temp.next.value < current.value) {
        temp = temp.next;
      }
      current.next = temp.next;
      temp.next = current;
    }
    current = next;
  }
  return sorted;
}

// Initial linked list: 4 -> 1 -> 3 -> 2 -> null
// After sorting, what is the linked list?

A 4 -> 3 -> 2 -> 1 -> null

B 1 -> 3 -> 2 -> 4 -> null

C 1 -> 2 -> 3 -> 4 -> null

D 2 -> 1 -> 3 -> 4 -> null

💡 Hint

Insertion sort on linked list inserts nodes in ascending order by value.

The insertion sort algorithm rearranges the nodes so the linked list is sorted ascending: 1 -> 2 -> 3 -> 4 -> null.

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 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 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: dividing (merge sort), swapping adjacent (bubble sort), selecting smallest (selection 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 it divides the array like merge sort
• Mixing it up with selection sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort in JavaScript for an array arr?

easy

A. for(let i = 0; i < arr.length; i++)

B. for(let i = 1; i < arr.length; i++)

C. for(let i = arr.length - 1; i >= 0; i--)

D. for(let i = 0; i <= arr.length; i++)

Solution

1. Step 1: Identify starting index for insertion sort

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

2. Step 2: Check loop condition correctness

   The loop runs while i < arr.length to cover all elements. Starting at 0 or going beyond length is incorrect.

3. Final Answer:

   for(let i = 1; i < arr.length; i++) -> Option B

4. Quick Check:

   Start loop at 1 for insertion sort [OK]

Hint: Start outer loop at 1, not 0, in 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 of the following JavaScript code?

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

console.log(insertionSort([4, 2, 7, 1]));

medium

A. [2, 1, 4, 7]

B. [4, 2, 7, 1]

C. [1, 4, 2, 7]

D. [1, 2, 4, 7]

Solution

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

   key=2, compare with 4, shift 4 right, insert 2 at index 0 -> [2,4,7,1]

2. Step 2: Trace remaining iterations

   i=2: key=7, no shift -> [2,4,7,1]; i=3: key=1, shift 7,4,2 right, insert 1 at index 0 -> [1,2,4,7]

3. Final Answer:

   [1, 2, 4, 7] -> Option D

4. Quick Check:

   Sorted array = [1, 2, 4, 7] [OK]

Hint: Insertion sort outputs sorted array in ascending order [OK]

Common Mistakes:

• Not shifting elements correctly
• Returning original array without sorting
• Confusing key placement index

4. Find the error in this insertion sort code snippet:

function insertionSort(arr) {
  for(let i = 1; i <= arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

medium

A. The outer loop condition should be i < arr.length instead of <=.

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

C. The key should be assigned after the while loop, not before.

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

Solution

1. Step 1: Check outer loop boundary

   The loop runs from 1 to arr.length inclusive, but array indices go from 0 to arr.length - 1, so i < arr.length is correct.

2. Step 2: Verify other parts

   Inner loop condition and key assignment are correct; j starts at i - 1 to compare with previous elements.

3. Final Answer:

   The outer loop condition should be i < arr.length instead of <=. -> Option A

4. Quick Check:

   Loop must not exceed array length [OK]

Hint: Use i < arr.length to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= causes index out of range error
• Changing inner loop condition incorrectly
• Misplacing key assignment

5. Given the array [3, 0, -2, 5, 1], after the second iteration (i=2) of insertion sort, what will the array look like?

hard

A. [0, 3, -2, 5, 1]

B. [0, -2, 3, 5, 1]

C. [-2, 0, 3, 5, 1]

D. [3, 0, -2, 5, 1]

Solution

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

   key=0, compare with 3, shift 3 right, insert 0 at index 0 -> [0,3,-2,5,1]

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

   key=-2, compare with 3 and 0, shift both right, insert -2 at index 0 -> [-2,0,3,5,1]

3. Final Answer:

   [-2, 0, 3, 5, 1] -> Option C

4. Quick Check:

   After 2 iterations, array is partially sorted [OK]

Hint: After i-th iteration, first i+1 elements are sorted [OK]

Common Mistakes:

• Not shifting all larger elements
• Inserting key at wrong position
• Confusing iteration count with index