Comparison Based vs Non Comparison Based Sorting in DSA C - 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 based) versus sorting mail by zip codes directly into bins (non-comparison based).

Array: [4, 2, 7, 1, 3]
Comparison Based: compare pairs -> swap if needed
Non Comparison Based: use value as index -> place in correct bin

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using both comparison based and non comparison based sorting

Step 1: Start comparison based sort (Bubble Sort): compare 4 and 2, swap because 4 > 2

[2, 4, 7, 1, 3]

Why: We swap to move smaller elements forward

Step 2: Compare 4 and 7, no swap because 4 < 7

[2, 4, 7, 1, 3]

Why: No swap needed if order is correct

Step 3: Compare 7 and 1, swap because 7 > 1

[2, 4, 1, 7, 3]

Why: Smaller element moves forward

Step 4: Compare 7 and 3, swap because 7 > 3

[2, 4, 1, 3, 7]

Why: Move smaller element forward

Step 5: Start non comparison based sort (Counting Sort): count occurrences of each number

Counts: 1->1, 2->1, 3->1, 4->1, 7->1

Why: Counting sort uses counts to place elements

Step 6: Place elements back in order using counts

[1, 2, 3, 4, 7]

Why: Elements placed directly by value count

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>

// Comparison based sort: Bubble Sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Non comparison based sort: Counting Sort (assumes max value known)
void countingSort(int arr[], int n, int max_val) {
    int count[max_val + 1];
    memset(count, 0, sizeof(count));

    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr1[] = {4, 2, 7, 1, 3};
    int arr2[] = {4, 2, 7, 1, 3};
    int n = 5;
    int max_val = 7;

    bubbleSort(arr1, n);
    printf("Bubble Sort: ");
    printArray(arr1, n);

    countingSort(arr2, n, max_val);
    printf("Counting Sort: ");
    printArray(arr2, n);

    return 0;
}

if (arr[j] > arr[j + 1]) {

compare adjacent elements to decide swap

count[arr[i]]++;

count occurrences of each element

while (count[i] > 0) { arr[index++] = i; count[i]--; }

place elements back in sorted order using counts

Output

Bubble Sort: 1 2 3 4 7 

Counting Sort: 1 2 3 4 7 

Complexity Analysis

Time: O(n^2) for comparison based (Bubble Sort) because it compares pairs repeatedly; O(n + k) for non comparison based (Counting Sort) where k is max value

Space: O(1) extra space for Bubble Sort; O(k) extra space for Counting Sort to store counts

vs Alternative: Comparison based sorts work on any data but are slower; non comparison based sorts are faster but need value range knowledge and work only on integers

Edge Cases

Empty array

No sorting needed, functions handle gracefully

DSA C

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

Array with one element

Already sorted, no swaps or changes

DSA C

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

Array with duplicate values

Counting sort counts duplicates correctly; bubble sort swaps as needed

DSA C

count[arr[i]]++;

When to Use This Pattern

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

Common Mistakes

Mistake: Using counting sort on data with unknown or large range causing large memory use
Fix: Only use counting sort when max value is known and small

Mistake: Assuming comparison based sorts are always slower without considering data size
Fix: Remember comparison based sorts work on any data type and small arrays efficiently

Summary

Comparison based sorting uses element comparisons to order data; non comparison based sorting uses element values directly.

Use comparison based sorting for general data and unknown ranges; use non comparison based sorting for integers with small known ranges for faster sorting.

The key insight is that non comparison based sorting avoids pairwise comparisons by using element values as direct positions.

Practice

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

easy

A. Quick Sort

B. Merge Sort

C. Counting Sort

D. Heap Sort

Solution

1. Step 1: Understand comparison based sorting

   Merge Sort, Quick Sort, and Heap Sort sort by comparing elements to decide order.

2. Step 2: Identify non-comparison based sorting

   Counting Sort uses counting frequencies, not comparisons, to sort elements.

3. Final Answer:

   Counting Sort -> Option C

4. Quick Check:

   Counting Sort = Non-comparison based [OK]

Hint: Counting Sort uses counts, not comparisons [OK]

Common Mistakes:

• Confusing Quick Sort as non-comparison
• Thinking Heap Sort is non-comparison
• Assuming all sorts use comparisons

2. Which of the following is the correct syntax to call Radix Sort function in C if the function is defined as void radixSort(int arr[], int n);?

easy

A. radixSort();

B. radixSort(n, arr);

C. radixSort(arr);

D. radixSort(arr, n);

Solution

1. Step 1: Check function definition

   The function expects an integer array and its size as parameters in order.

2. Step 2: Match call with definition

   Calling radixSort(arr, n); matches the expected parameters and order.

3. Final Answer:

   radixSort(arr, n); -> Option D

4. Quick Check:

   Function call matches parameters [OK]

Hint: Match function parameters order exactly [OK]

Common Mistakes:

• Swapping parameters order
• Missing array size argument
• Calling without arguments

3. What will be the output array after applying Counting Sort on arr = {4, 2, 2, 8, 3, 3, 1}?

medium

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

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

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

D. [8, 4, 3, 3, 2, 2, 1]

Solution

1. Step 1: Count frequencies of each element

   1:1, 2:2, 3:2, 4:1, 8:1

2. Step 2: Place elements in sorted order by frequency

   Sorted array is [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 [OK]

Common Mistakes:

• Not counting duplicates correctly
• Reversing order
• Confusing input with output

4. The following code snippet attempts to perform Counting Sort but has a bug. What is the bug?

void countingSort(int arr[], int n) {
  int output[n];
  int count[10] = {0};
  for (int i = 0; i <= n; i++) {
    count[arr[i]]++;
  }
  for (int i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  for (int i = n - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }
  for (int i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

medium

A. Loop condition should be i < n instead of i <= n in first for loop

B. Count array size is too small

C. Output array is not initialized

D. Final copy loop should run from i = 1

Solution

1. Step 1: Analyze first for loop range

   The loop runs from i=0 to i<=n, which accesses arr[n], out of bounds.

2. Step 2: Correct loop condition

   It should be i < n to avoid accessing outside array bounds.

3. Final Answer:

   Loop condition should be i < n instead of i <= n in first for loop -> Option A

4. Quick Check:

   Array index out of bounds fixed by i < n [OK]

Hint: Check loop bounds carefully for array indexing [OK]

Common Mistakes:

• Ignoring off-by-one errors
• Assuming count array size is wrong without input info
• Thinking output array needs initialization

5. You have an array of integers where values range from 0 to 1000. Which sorting algorithm is best to sort this array efficiently and why?

hard

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

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

C. Merge Sort, because it is stable and works well on linked lists

D. Heap Sort, because it uses a heap data structure

Solution

1. Step 1: Analyze input constraints

   Values range from 0 to 1000, so range k = 1001 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 compared to comparison sorts O(n log n).

3. Final Answer:

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

4. Quick Check:

   Small range favors Counting Sort [OK]

Hint: Small range arrays use Counting Sort for linear time [OK]

Common Mistakes:

• Choosing Quick Sort ignoring range advantage
• Confusing stability with speed
• Ignoring Counting Sort's range dependency