Comparison Based vs Non Comparison Based Sorting in DSA C# - Visual Comparison

Concept Flow - Comparison Based vs Non Comparison Based Sorting

Start: Unsorted Array

↓

Comparison Based

↓

Compare elements

↓

Swap or reorder

↓

Repeat until sorted

↓

Sorted Array

Sorting starts with an unsorted array, then splits into two main ways: comparison-based sorts that compare and swap elements, and non-comparison sorts that use element properties like counting or bucketing to order without direct comparisons.

Execution Sample

DSA C#

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

This code sorts an array using bubble sort, a comparison-based method that repeatedly swaps adjacent elements if they are in the 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]	N/A	N/A	[1, 2, 4, 7]

💡 Array is sorted after all comparisons and swaps.

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 elements multiple times?

Because each comparison checks if two elements are in the wrong order and swaps them if needed, multiple passes ensure all elements move to their correct positions, as shown in steps 1 to 6 in the execution_table.

How does non-comparison based sorting avoid comparing elements?

Non-comparison sorts use properties like counting occurrences or placing elements into buckets based on value ranges, so they reorder elements without direct comparisons, unlike the bubble sort example in the execution_table.

Why is the final array sorted after step 6 and no swaps in step 7?

Because no swaps mean all elements are in correct order, so the algorithm stops, as indicated in the exit_note and step 7 of the execution_table.

Visual Quiz - 3 Questions

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

A [2, 4, 7, 1]

B [2, 4, 1, 7]

C [4, 2, 7, 1]

D [1, 2, 4, 7]

💡 Hint

Check the 'Resulting Array' column in row for step 3 in execution_table.

At which step does the first swap happen?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

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

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

A The array state would change after each step.

B More swaps would occur to confirm order.

C No swaps would occur, all 'Swap?' columns would be 'No'.

D The algorithm would not run at all.

💡 Hint

Refer to the 'Swap?' column in execution_table and think about what happens if elements are already in order.

Concept Snapshot

Comparison Based Sorting:
- Sorts by comparing and swapping elements
- Examples: Bubble Sort, Quick Sort, Merge Sort
- Time: Usually O(n log n) or worse

Non Comparison Based Sorting:
- Sorts using element properties (counting, bucketing)
- Examples: Counting Sort, Radix Sort, Bucket Sort
- Can be faster for specific data types

Key: Comparison sorts rely on element comparisons; non-comparison sorts do not.

Full Transcript

Sorting algorithms can be divided into two main 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. This process repeats until the entire array is sorted. For example, bubble sort compares adjacent elements and swaps them if needed, as shown in the execution table where the array gradually becomes sorted after several swaps. Non comparison based sorting avoids direct comparisons by using properties of the elements, such as counting how many times each value appears or placing elements into buckets based on their value. This can be more efficient for certain types of data. The key difference is that comparison based sorts rely on comparing elements, while non comparison based sorts use other strategies to order elements without direct comparisons.

Practice

1. Which of the following sorting algorithms is non-comparison based?

easy

A. Merge Sort

B. Quick Sort

C. Counting Sort

D. Heap 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 frequencies and does not compare elements directly.

3. Final Answer:

   Counting Sort -> Option C

4. Quick Check:

   Non-comparison based = Counting Sort [OK]

Hint: Non-comparison sorts use counting or buckets, not element comparisons [OK]

Common Mistakes:

• Confusing Quick Sort as non-comparison
• Thinking Heap Sort is non-comparison
• Assuming all sorts compare elements

2. Which of the following is the correct syntax to call Radix Sort method named RadixSort on an integer array arr in C#?

easy

A. RadixSort(arr);

B. arr.RadixSort();

C. RadixSort<int>(arr);

D. RadixSort arr;

Solution

1. Step 1: Understand method call syntax in C#

   Calling a static method with an array argument uses method name and parentheses with the array inside.

2. Step 2: Analyze options

   RadixSort(arr); uses correct syntax: RadixSort(arr); arr.RadixSort(); tries to call as instance method which is incorrect unless defined so. RadixSort<int>(arr); uses generic syntax unnecessarily. RadixSort arr; is invalid syntax.

3. Final Answer:

   RadixSort(arr); -> Option A

4. Quick Check:

   Static method call = RadixSort(arr); [OK]

Hint: Static method calls use MethodName(args) syntax [OK]

Common Mistakes:

• Using instance method call on array
• Adding unnecessary generic syntax
• Writing invalid declaration instead of call

3. What will be the output of the following C# code snippet?

int[] arr = {4, 2, 2, 8, 3, 3, 1};
CountingSort(arr);
Console.WriteLine(string.Join(", ", arr));

void CountingSort(int[] array) {
    int max = array.Max();
    int[] count = new int[max + 1];
    foreach (int num in array) count[num]++;
    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            array[index++] = i;
            count[i]--;
        }
    }
}

medium

A. 8, 4, 3, 3, 2, 2, 1

B. 1, 2, 2, 3, 3, 4, 8

C. 4, 2, 2, 8, 3, 3, 1

D. 1, 1, 2, 2, 3, 3, 4

Solution

1. Step 1: Understand Counting Sort logic

   Counting Sort counts occurrences of each number and then writes them back in sorted order.

2. Step 2: Trace the code with input array

   Input: {4, 2, 2, 8, 3, 3, 1} Count array: counts of 1=1, 2=2, 3=2, 4=1, 8=1 Output array after sorting: 1, 2, 2, 3, 3, 4, 8

3. Final Answer:

   1, 2, 2, 3, 3, 4, 8 -> Option B

4. Quick Check:

   Counting Sort output = sorted array [OK]

Hint: Counting Sort outputs sorted array by frequency count [OK]

Common Mistakes:

• Assuming original array remains unchanged
• Confusing Counting Sort with reverse order
• Miscounting frequencies

4. The following code attempts to implement Radix Sort but has a bug. What is the error?

void RadixSort(int[] arr) {
    int max = arr.Max();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        CountingSortByDigit(arr, exp);
    }
}

void CountingSortByDigit(int[] arr, int exp) {
    int n = arr.Length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Missing step here
}

medium

A. The loop for counting prefix sums should start from 0

B. The count array size should be 100 instead of 10

C. The exponent variable exp should be incremented by 1 each iteration

D. The sorted output array is not copied back to the original array

Solution

1. Step 1: Analyze CountingSortByDigit function

   The function builds output array sorted by digit but does not copy output back to arr.

2. Step 2: Identify missing step

   After building output, we must copy output elements back to arr to update it for next digit sorting.

3. Final Answer:

   The sorted output array is not copied back to the original array -> Option D

4. Quick Check:

   Missing copy back step = bug [OK]

Hint: Radix Sort needs copying output back each digit pass [OK]

Common Mistakes:

• Thinking count array size should be larger
• Starting prefix sum loop incorrectly
• Incrementing exp by 1 instead of multiplying by 10

5. You have an array of 1 million integers ranging from 0 to 1000. Which sorting algorithm is the most efficient choice and why?

hard

A. Counting Sort, because it sorts in O(n + k) time where k is max value

B. Heap Sort, because it uses constant extra space

C. Merge Sort, because it is stable and works well on large data

D. Quick Sort, because it has average O(n log n) time

Solution

1. Step 1: Analyze input size and range

   Array size n = 1,000,000; max value k = 1000 (small compared to n).

2. Step 2: Compare algorithm complexities

   Counting Sort runs in O(n + k) which is O(1,001,000) here, faster than O(n log n) for comparison sorts.

3. Step 3: Choose best algorithm

   Counting Sort is efficient for small range large data, so best choice.

4. Final Answer:

   Counting Sort, because it sorts in O(n + k) time where k is max value -> Option A

5. Quick Check:

   Small range + large n = Counting Sort best [OK]

Hint: Use Counting Sort for large arrays with small value range [OK]

Common Mistakes:

• Choosing Quick Sort ignoring small range advantage
• Preferring Merge Sort for speed over Counting Sort
• Ignoring Counting Sort's linear time benefit