Comparison Based vs Non Comparison Based Sorting in DSA Javascript - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Comparison Based Sorting Algorithm

What is the output of the following JavaScript code that uses a comparison based sorting method?

DSA Javascript

const arr = [5, 3, 8, 1, 2];
arr.sort((a, b) => a - b);
console.log(arr.join(' -> ') + ' -> null');

A 1 -> 3 -> 2 -> 5 -> 8 -> null

B 5 -> 3 -> 8 -> 1 -> 2 -> null

C 8 -> 5 -> 3 -> 2 -> 1 -> null

D 1 -> 2 -> 3 -> 5 -> 8 -> null

💡 Hint

Remember that the sort method with (a, b) => a - b sorts numbers in ascending order.

The sort method compares elements and arranges them from smallest to largest, so the output is sorted ascending.

❓ Predict Output

intermediate

Output of Non Comparison Based Sorting Algorithm

What is the output of the following JavaScript code that uses a non comparison based sorting method (counting sort) on a small array?

DSA Javascript

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (const num of arr) count[num]++;
  const sorted = [];
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      sorted.push(i);
      count[i]--;
    }
  }
  return sorted;
}
const arr = [4, 2, 2, 8, 3, 3, 1];
const sortedArr = countingSort(arr);
console.log(sortedArr.join(' -> ') + ' -> null');

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

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

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

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

💡 Hint

Counting sort counts occurrences and outputs sorted values in order.

Counting sort outputs elements in ascending order by counting their frequency.

🧠 Conceptual

advanced

Time Complexity Difference

Which statement correctly describes the time complexity difference between comparison based and non comparison based sorting algorithms?

A Non comparison based sorting algorithms can achieve linear time O(n) under certain conditions, while comparison based sorting algorithms cannot do better than O(n log n).

B Both comparison based and non comparison based sorting algorithms always run in O(n log n) time regardless of input.

C Comparison based sorting algorithms have a best time complexity of O(n), while non comparison based sorting algorithms always run in O(n log n).

D Comparison based sorting algorithms are always faster than non comparison based sorting algorithms.

💡 Hint

Think about the theoretical lower bound for comparison based sorting.

Comparison based sorting algorithms have a lower bound of O(n log n). Non comparison based algorithms like counting sort can run in O(n) if input range is limited.

❓ Predict Output

advanced

Output of Non Comparison Based Sorting Algorithm (Radix Sort)

What is the output of the following JavaScript code that uses a non comparison based sorting method (radix sort)?

DSA Javascript

function radixSort(arr) {
  const max = Math.max(...arr);
  let exp = 1;
  while (Math.floor(max / exp) > 0) {
    const output = new Array(arr.length).fill(0);
    const count = new Array(10).fill(0);
    for (let i = 0; i < arr.length; i++) {
      const index = Math.floor(arr[i] / exp) % 10;
      count[index]++;
    }
    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }
    for (let i = arr.length - 1; i >= 0; i--) {
      const index = Math.floor(arr[i] / exp) % 10;
      output[count[index] - 1] = arr[i];
      count[index]--;
    }
    arr = output;
    exp *= 10;
  }
  return arr;
}
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(arr).join(' -> ') + ' -> null');

A TypeError: Assignment to constant variable.

B Outputs sorted array correctly: 2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

C ReferenceError: arr is not defined.

D RangeError: Maximum call stack size exceeded.

💡 Hint

This is a correct implementation of LSD radix sort using counting sort per digit.

The code correctly implements radix sort (non-comparison based) and outputs the sorted array.

🚀 Application

expert

Choosing Sorting Algorithm for Large Dataset with Small Range

You have a large dataset of 10 million integers, but all values are between 0 and 1000. Which sorting algorithm is the best choice for fastest sorting?

A MergeSort (comparison based) because it guarantees O(n log n) time and is stable.

B QuickSort (comparison based) because it has average O(n log n) time and works well on large datasets.

C Counting Sort (non comparison based) because it can sort in O(n) time when the range is small.

D Bubble Sort (comparison based) because it is simple and easy to implement.

💡 Hint

Consider the input range and how it affects non comparison based sorting.

Counting sort is ideal for large datasets with small value ranges because it sorts in linear time O(n + k), where k is the range size.