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

Concept Flow - Comparison Based vs Non Comparison Based Sorting

Start with array

↓

Choose sorting type

↓

Comparison Based

↓

Compare elements

↓

Swap or reorder

↓

Repeat until sorted

↓

Sorted array

Sorting starts with an array, then chooses either comparison-based or non-comparison-based method, each with different steps to produce a sorted array.

Execution Sample

DSA Javascript

const arr = [4, 2, 7, 1];
// Comparison based: Bubble Sort
for(let i=0; i<arr.length-1; i++) {
  for(let j=0; j<arr.length-1-i; j++) {
    if(arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
  }
}

This code sorts an array using comparison-based Bubble Sort by repeatedly swapping adjacent elements if they are in wrong order.

Execution Table

Step	Operation	Array State	Comparison	Swap?	Resulting Array
1	Compare arr[0] and arr[1]	[4, 2, 7, 1]	4 > 2	Yes	[2, 4, 7, 1]
2	Compare arr[1] and arr[2]	[2, 4, 7, 1]	4 > 7	No	[2, 4, 7, 1]
3	Compare arr[2] and arr[3]	[2, 4, 7, 1]	7 > 1	Yes	[2, 4, 1, 7]
4	Compare arr[0] and arr[1]	[2, 4, 1, 7]	2 > 4	No	[2, 4, 1, 7]
5	Compare arr[1] and arr[2]	[2, 4, 1, 7]	4 > 1	Yes	[2, 1, 4, 7]
6	Compare arr[0] and arr[1]	[2, 1, 4, 7]	2 > 1	Yes	[1, 2, 4, 7]
7	No more comparisons needed	[1, 2, 4, 7]	-	No	[1, 2, 4, 7]

💡 Sorting stops when no swaps are needed and array is sorted.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
arr	[4, 2, 7, 1]	[2, 4, 7, 1]	[2, 4, 7, 1]	[2, 4, 1, 7]	[2, 4, 1, 7]	[2, 1, 4, 7]	[1, 2, 4, 7]	[1, 2, 4, 7]

Key Moments - 3 Insights

Why do comparison-based sorts need to compare pairs of elements?

Because they decide order by comparing two elements at a time, as shown in execution_table rows 1-6 where each comparison determines if a swap is needed.

How does non-comparison-based sorting avoid comparing elements?

It uses properties like counting occurrences or placing elements into buckets, not shown in the table but described in concept_flow under 'Use element properties' and 'Count or bucket elements'.

Why does the sorting stop after no swaps in a pass?

Because no swaps mean the array is sorted, as shown in step 7 where no swap occurs and sorting ends.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 3?

A [2, 4, 7, 1]

B [4, 2, 7, 1]

C [2, 4, 1, 7]

D [1, 2, 4, 7]

💡 Hint

Check the 'Resulting Array' column in row 3 of execution_table.

At which step does the first swap happen?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Swap?' column in execution_table; first 'Yes' is at step 1.

If the array was already sorted, how would the execution_table change?

A No swaps would occur in any step

B More swaps would occur

C The array state would change after each step

D The sorting would never stop

💡 Hint

Refer to step 7 where no swaps mean sorting stops; if sorted initially, no swaps happen.

Concept Snapshot

Comparison Based Sorting:
- Sort by comparing pairs
- Swap if out of order
- Examples: Bubble, Quick, Merge

Non Comparison Based Sorting:
- Use element properties
- Count or bucket elements
- Examples: Counting, Radix, Bucket

Full Transcript

Sorting algorithms can be divided into two types: comparison-based and non-comparison-based. Comparison-based sorting works by comparing pairs of elements and swapping them if they are in the wrong order, repeating this until the array is sorted. Non-comparison-based sorting uses properties of elements, like counting or bucketing, to sort without direct comparisons. The example code shows Bubble Sort, a comparison-based method, where adjacent elements are compared and swapped if needed. The execution table traces each comparison and swap step, showing how the array changes until sorted. Key moments clarify why comparisons are needed in one type and how the other avoids them. The visual quiz tests understanding of array states and swap steps. The snapshot summarizes key points for quick review.

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