Comparison Based vs Non Comparison Based Sorting in DSA Javascript - Trade-offs & Analysis

Mental Model

Sorting can be done by comparing elements or by using their values directly without comparing.

Analogy: Imagine sorting books by comparing their titles one by one (comparison) versus sorting mail by zip codes using bins (non-comparison).

Array: [4, 2, 7, 1, 3]
Comparison sort: compare pairs -> swap if needed
Non-comparison sort: place each number in a bucket based on value

Dry Run Walkthrough

Input: array: [4, 2, 7, 1, 3]

Goal: Show how comparison based and non comparison based sorting organize the array

Step 1: Comparison sort compares 4 and 2, swaps because 4 > 2

[2, 4, 7, 1, 3]

Why: We need to order elements by comparing pairs

Step 2: Comparison sort compares 4 and 7, no swap needed

[2, 4, 7, 1, 3]

Why: 4 is less than 7, so order is correct

Step 3: Comparison sort compares 7 and 1, swaps because 7 > 1

[2, 4, 1, 7, 3]

Why: 7 is bigger than 1, so swap to move smaller number forward

Step 4: Non-comparison sort places 1 in bucket 1

Buckets: 1:[1], 2:[], 3:[], 4:[], 7:[]

Why: Directly use value to place element

Step 5: Non-comparison sort places 2 in bucket 2

Buckets: 1:[1], 2:[2], 3:[], 4:[], 7:[]

Why: Each number goes to its own bucket

Step 6: Non-comparison sort places 3, 4, 7 in their buckets

Buckets: 1:[1], 2:[2], 3:[3], 4:[4], 7:[7]

Why: All elements sorted by direct placement

Step 7: Non-comparison sort collects buckets in order

[1, 2, 3, 4, 7]

Why: Concatenate buckets to get sorted array

Result:

Comparison sort final: [1, 2, 3, 4, 7]
Non-comparison sort final: [1, 2, 3, 4, 7]

Annotated Code

DSA Javascript

class ComparisonSort {
  static bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
      for (let j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          // swap arr[j] and arr[j+1]
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
      }
    }
    return arr;
  }
}

class NonComparisonSort {
  static countingSort(arr, maxVal) {
    let count = new Array(maxVal + 1).fill(0);
    for (let num of arr) {
      count[num]++;
    }
    let sorted = [];
    for (let i = 0; i <= maxVal; i++) {
      while (count[i] > 0) {
        sorted.push(i);
        count[i]--;
      }
    }
    return sorted;
  }
}

const input = [4, 2, 7, 1, 3];
const sortedComparison = ComparisonSort.bubbleSort([...input]);
const sortedNonComparison = NonComparisonSort.countingSort([...input], 7);

console.log('Comparison sort final:', sortedComparison.join(', '));
console.log('Non-comparison sort final:', sortedNonComparison.join(', '));

if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }

compare adjacent elements and swap if out of order

for (let num of arr) { count[num]++; }

count frequency of each number using direct indexing

while (count[i] > 0) { sorted.push(i); count[i]--; }

append each number count[i] times to sorted array

Output

Comparison sort final: 1, 2, 3, 4, 7

Non-comparison sort final: 1, 2, 3, 4, 7

Complexity Analysis

Time: O(n^2) for comparison sort because it compares pairs repeatedly; O(n + k) for non-comparison sort where k is max value

Space: O(1) extra space for comparison sort; O(k) extra space for non-comparison sort due to counting array

vs Alternative: Comparison sorts work on any data but can be slower; non-comparison sorts are faster but need limited value ranges

Edge Cases

empty array

returns empty array immediately

DSA Javascript

for (let i = 0; i < n - 1; i++) {

array with one element

returns the same single element array

DSA Javascript

for (let i = 0; i < n - 1; i++) {

array with duplicate values

sorts correctly including duplicates

DSA Javascript

count[num]++;

When to Use This Pattern

When sorting numbers with a known small range, consider non-comparison sorting for speed; otherwise, use comparison sorting for general data.

Common Mistakes

Mistake: Trying non-comparison sort on data with large or unknown range
Fix: Use comparison sort or limit input range before non-comparison sort

Mistake: Not swapping elements correctly in comparison sort
Fix: Use a proper swap method or destructuring assignment

Summary

Comparison based sorting orders elements by comparing pairs; non-comparison sorting uses element values directly to sort.

Use comparison sorting for general data and non-comparison sorting when values are integers in a small range.

The key insight is that non-comparison sorting can be faster by avoiding comparisons but only works with limited value types.

Practice

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