Comparison Based vs Non Comparison Based Sorting in DSA C# - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Comparison Based Sorting Algorithm

What is the output of the following C# code that uses a comparison based sorting method (Bubble Sort) on the array?

DSA C#

int[] arr = {5, 3, 8, 4, 2};
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;
        }
    }
}
foreach (var num in arr) {
    Console.Write(num + " ");
}

A 8 5 4 3 2

B 5 3 8 4 2

C 2 3 4 5 8

D 2 4 3 5 8

💡 Hint

Bubble sort repeatedly swaps adjacent elements if they are in wrong order.

Bubble sort compares adjacent elements and swaps them if the first is greater than the second. After all passes, the array is sorted in ascending order.

❓ Predict Output

intermediate

Output of Non Comparison Based Sorting Algorithm

What is the output of the following C# code that uses a non comparison based sorting method (Counting Sort) on the array?

DSA C#

int[] arr = {4, 2, 2, 8, 3, 3, 1};
int max = 8;
int[] count = new int[max + 1];
for (int i = 0; i < arr.Length; i++) {
    count[arr[i]]++;
}
int index = 0;
for (int i = 0; i <= max; i++) {
    while (count[i] > 0) {
        arr[index++] = i;
        count[i]--;
    }
}
foreach (var num in arr) {
    Console.Write(num + " ");
}

A 1 2 2 3 3 4 8

B 4 2 2 8 3 3 1

C 8 4 3 3 2 2 1

D 1 3 2 2 3 4 8

💡 Hint

Counting sort counts occurrences and places elements in order without comparisons.

Counting sort counts how many times each number appears, then writes them back in order. The final sorted array is ascending.

🧠 Conceptual

advanced

Time Complexity Difference

Which statement correctly describes the time complexity difference between comparison based and non comparison based sorting algorithms?

A Non comparison based sorting algorithms always run slower than comparison based sorting algorithms.

B Comparison based sorting algorithms always run in O(n), while non comparison based sorting algorithms run in O(n log n).

C Both comparison based and non comparison based sorting algorithms have the same time complexity of O(n^2).

D Comparison based sorting algorithms have a lower bound of O(n log n), while some non comparison based sorting algorithms can achieve O(n) time.

💡 Hint

Think about the theoretical lower bound for comparison based sorting.

Comparison based sorting algorithms cannot be faster than O(n log n) in the worst case. Non comparison based algorithms like counting sort can run in O(n) if conditions are right.

🔧 Debug

advanced

Identify the Error in Non Comparison Based Sort Implementation

What error will the following C# code produce when trying to sort an array using a non comparison based sorting method (Radix Sort)?

DSA C#

int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
int max = arr.Max();
int exp = 1;
int n = arr.Length;
int[] output = new int[n];
while (max / exp > 0) {
    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]--;
    }
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    exp *= 10;
}
foreach (var num in arr) {
    Console.Write(num + " ");
}

A No error, outputs sorted array

B IndexOutOfRangeException

C NullReferenceException

D DivideByZeroException

💡 Hint

Check how the output array is indexed inside the loop.

The code uses count[(arr[i] / exp) % 10] as index directly without subtracting 1, causing index out of range error.

🚀 Application

expert

Choosing Sorting Algorithm for Large Range Data

You have a large dataset of integers ranging from 1 to 1,000,000,000. Which sorting approach is most efficient in terms of time and space?

A Use a comparison based sorting algorithm like QuickSort or MergeSort.

B Use Radix Sort with base 10 digits.

C Use Bubble Sort because it is simple and stable.

D Use a non comparison based sorting algorithm like Counting Sort.

💡 Hint

Consider the space requirements of non comparison based sorts for large ranges.

Counting sort requires space proportional to the range, which is huge here. Radix sort is possible but slower than efficient comparison sorts for large ranges. QuickSort or MergeSort are better choices.

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