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.