Comparison Based vs Non Comparison Based Sorting in DSA Javascript - Key Differences

Recall & Review

beginner

What is comparison based sorting?

Sorting methods that decide the order of elements by comparing them with each other, like checking if one number is bigger or smaller than another.

beginner

Name two common comparison based sorting algorithms.

Bubble Sort and Quick Sort are examples of comparison based sorting algorithms.

beginner

What is non comparison based sorting?

Sorting methods that do not compare elements directly but use other information like counting or grouping to sort, such as counting sort or radix sort.

intermediate

Why can non comparison based sorting be faster than comparison based sorting?

Because they use special tricks like counting or grouping, they can sort in linear time for certain types of data, unlike comparison based sorting which usually takes longer.

intermediate

What is the best time complexity possible for comparison based sorting?

The best possible time complexity for comparison based sorting is O(n log n), meaning it takes at least that much time to sort n items by comparing.

Which of these is a comparison based sorting algorithm?

A Quick Sort

B Counting Sort

C Radix Sort

D Bucket Sort

Quick Sort sorts by comparing elements, so it is comparison based.

Non comparison based sorting algorithms usually work best when:

A Data is already sorted

B Data is very large and random

C Data has a limited range of values

D Data is strings only

Non comparison based sorting like counting sort works best when data values are within a limited range.

What is the lower bound time complexity for comparison based sorting?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

Comparison based sorting cannot be faster than O(n log n) in the general case.

Which sorting method uses counting to sort elements?

A Merge Sort

B Heap Sort

C Quick Sort

D Counting Sort

Counting Sort counts the number of occurrences of each value to sort.

Radix Sort is an example of:

A Comparison based sorting

B Non comparison based sorting

C Divide and conquer sorting

D In-place sorting

Radix Sort sorts numbers digit by digit without comparing elements directly.

Explain the main difference between comparison based and non comparison based sorting.

Think about how the algorithms decide the order of elements.

Describe a scenario where non comparison based sorting is more efficient than comparison based sorting.

Consider when counting or grouping helps speed up sorting.

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