Bird
Raised Fist0
DSA Javascriptprogramming~5 mins

Comparison Based vs Non Comparison Based Sorting in DSA Javascript - Complexity Comparison

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Comparison Based vs Non Comparison Based Sorting
O(nĀ²) for comparison based, O(n + k) for non comparison based
Understanding Time Complexity

Sorting is a common task where we arrange items in order. Different sorting methods take different times depending on how they work.

We want to understand how the time to sort grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of these two sorting approaches.


// Comparison based sorting example (Bubble Sort)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// Non-comparison based sorting example (Counting Sort)
function countingSort(arr, max) {
  const count = new Array(max + 1).fill(0);
  for (let num of arr) count[num]++;
  let index = 0;
  for (let i = 0; i < count.length; i++) {
    while (count[i]-- > 0) {
      arr[index++] = i;
    }
  }
  return arr;
}

Bubble Sort compares elements to sort, Counting Sort uses counts without direct comparisons.

Identify Repeating Operations

Look at the loops and repeated steps in each method.

  • Bubble Sort: Two nested loops comparing pairs of elements.
  • Counting Sort: One loop to count, one loop to rebuild the array.
  • Dominant operation: Bubble Sort's nested comparisons dominate time.
How Execution Grows With Input

As the list size grows, how does the work increase?

Input Size (n)Bubble Sort Ops (approx.)Counting Sort Ops (approx.)
10~100 comparisons~10 counts + 10 rebuild
100~10,000 comparisons~100 counts + 100 rebuild
1000~1,000,000 comparisons~1000 counts + 1000 rebuild

Bubble Sort grows much faster (square of n), Counting Sort grows roughly linearly with n.

Final Time Complexity

Time Complexity: O(nĀ²) for comparison based (Bubble Sort), O(n + k) for non-comparison based (Counting Sort)

Bubble Sort gets much slower as list grows; Counting Sort stays faster if numbers are in a small range.

Common Mistake

[X] Wrong: "All sorting methods take about the same time because they all sort the list."

[OK] Correct: Some methods compare items many times, others use counting tricks that can be much faster for certain data.

Interview Connect

Knowing how sorting methods differ helps you choose the right tool and explain your choices clearly in interviews.

Self-Check

What if the input numbers for Counting Sort were very large? How would that affect its time complexity?

Practice

(1/5)
1. Which of the following sorting algorithms is non-comparison based?
easy
A. Heap Sort
B. Merge Sort
C. Quick Sort
D. Counting Sort

Solution

  1. Step 1: Understand comparison based sorting

    Comparison based sorting algorithms decide order by comparing elements, like Merge Sort, Quick Sort, and Heap Sort.

  2. Step 2: Identify non-comparison based sorting

    Counting Sort uses counting of element frequencies instead of comparisons, so it is non-comparison based.

  3. Final Answer:

    Counting Sort -> Option D

  4. Quick Check:

    Non-comparison based = Counting Sort [OK]
Hint: Counting Sort uses counts, no element comparisons [OK]
Common Mistakes:
  • Confusing Quick Sort as non-comparison
  • Thinking Merge Sort is non-comparison
  • Assuming Heap Sort is non-comparison
2. Which of the following is the correct syntax to call a non-comparison based sorting function countingSort(arr) in JavaScript?
easy
A. countingSort(arr);
B. countingSort arr;
C. countingSort{arr};
D. countingSort[arr];

Solution

  1. Step 1: Recall JavaScript function call syntax

    Functions are called with parentheses enclosing arguments, like func(args).

  2. Step 2: Match syntax with options

    Only countingSort(arr); uses correct parentheses syntax for function call.

  3. Final Answer:

    countingSort(arr); -> Option A

  4. Quick Check:

    Function call syntax = countingSort(arr); [OK]
Hint: Use parentheses () to call functions in JavaScript [OK]
Common Mistakes:
  • Using square brackets [] instead of parentheses
  • Missing parentheses around arguments
  • Using curly braces {} incorrectly
3. What will be the output of the following JavaScript code?
function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  arr.forEach(num => count[num]++);
  let sorted = [];
  count.forEach((c, num) => {
    for (let i = 0; i < c; i++) sorted.push(num);
  });
  return sorted;
}

const arr = [3, 1, 4, 1, 5];
console.log(countingSort(arr));
medium
A. [1, 1, 3, 4, 5]
B. [3, 1, 4, 1, 5]
C. [5, 4, 3, 1, 1]
D. [1, 3, 4, 5]

Solution

  1. Step 1: Count frequencies of each number

    Input array is [3,1,4,1,5]. Counting frequencies: 1 appears 2 times, 3 once, 4 once, 5 once.

  2. Step 2: Build sorted array from counts

    Using counts, output array is [1,1,3,4,5] in ascending order.

  3. Final Answer:

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

  4. Quick Check:

    Counting Sort output = sorted ascending array [OK]
Hint: Counting Sort outputs sorted array by frequency counts [OK]
Common Mistakes:
  • Confusing input and output arrays
  • Assuming original order is preserved
  • Thinking output is reversed
4. The following code attempts to implement Counting Sort but has a bug. What is the bug?
function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max).fill(0);
  arr.forEach(num => count[num]++);
  let sorted = [];
  count.forEach((c, num) => {
    for (let i = 0; i < c; i++) sorted.push(num);
  });
  return sorted;
}
medium
A. Should use Math.min instead of Math.max
B. Array count size should be max + 1
C. Should initialize count with zeros
D. Should not use forEach on count array

Solution

  1. Step 1: Check count array size

    Count array size is max, but indices go from 0 to max, so size must be max + 1.

  2. Step 2: Identify impact of wrong size

    Without max + 1 size, count[max] index is undefined, causing errors or missing counts.

  3. Final Answer:

    Array count size should be max + 1 -> Option B

  4. Quick Check:

    Count array size = max + 1 [OK]
Hint: Count array size must cover max index + 1 [OK]
Common Mistakes:
  • Using max instead of max + 1 for array size
  • Confusing max with min
  • Ignoring array initialization
5. You have an array of integers ranging from 0 to 1000. Which sorting algorithm is best to sort this array efficiently and why?
hard
A. Quick Sort, because it has average O(n log n) time
B. Merge Sort, because it is stable and uses divide and conquer
C. Counting Sort, because it sorts in O(n + k) where k is range size
D. Heap Sort, because it uses a binary heap structure

Solution

  1. Step 1: Analyze input constraints

    Array elements range from 0 to 1000, so range size k = 1001, which is small and fixed.

  2. Step 2: Choose sorting algorithm based on range

    Counting Sort runs in O(n + k), which is efficient for small k, better than O(n log n) comparison sorts.

  3. Step 3: Confirm Counting Sort suitability

    Counting Sort is non-comparison based and ideal for small integer ranges.

  4. Final Answer:

    Counting Sort, because it sorts in O(n + k) where k is range size -> Option C

  5. Quick Check:

    Small range + Counting Sort = efficient sorting [OK]
Hint: Use Counting Sort for small integer ranges [OK]
Common Mistakes:
  • Choosing Quick Sort ignoring range size
  • Assuming Merge Sort is always best
  • Not considering non-comparison sorts
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard