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 using bins (non comparison based).

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

Comparison based: compare pairs and swap -> gradually sorted
Non comparison based: use value properties (like digits) to place directly into buckets

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 methods to see differences

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 larger elements towards the end

Step 2: Compare 4 and 7, no swap needed

[2, 4, 7, 1, 3]

Why: 4 is less than 7, order is correct

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

[2, 4, 1, 7, 3]

Why: Move larger element 7 towards the end

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

[2, 4, 1, 3, 7]

Why: 7 moves to the last position

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 directly

Step 6: Rebuild sorted array by placing numbers in order based on counts

[1, 2, 3, 4, 7]

Why: Direct placement avoids comparisons

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Comparison based sort: Bubble Sort
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); // swap if out of order
            }
        }
    }
}

// Non comparison based sort: Counting Sort (works for positive integers)
void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int max_val = arr[0];
    for (int val : arr) {
        if (val > max_val) max_val = val; // find max value
    }
    vector<int> count(max_val + 1, 0);
    for (int val : arr) {
        count[val]++; // count occurrences
    }
    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            arr[index++] = i; // place values in order
            count[i]--;
        }
    }
}

void printArray(const vector<int>& arr) {
    for (int val : arr) {
        cout << val << " ";
    }
    cout << "\n";
}

int main() {
    vector<int> arr1 = {4, 2, 7, 1, 3};
    vector<int> arr2 = arr1; // copy for second sort

    cout << "Original array: ";
    printArray(arr1);

    bubbleSort(arr1);
    cout << "After comparison based sort (Bubble Sort): ";
    printArray(arr1);

    countingSort(arr2);
    cout << "After non comparison based sort (Counting Sort): ";
    printArray(arr2);

    return 0;
}

if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); }

swap elements if current is greater to move larger elements right

for (int val : arr) { if (val > max_val) max_val = val; }

find maximum value to size count array

for (int val : arr) { count[val]++; }

count occurrences of each value

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

place values back into array in sorted order

Output

Original array: 4 2 7 1 3 

After comparison based sort (Bubble Sort): 1 2 3 4 7 

After non comparison based sort (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, because it counts and places directly

Space: O(1) extra space for comparison based (in-place swaps); O(k) extra space for non comparison based due to count array

vs Alternative: Comparison based sorts work on any data but are slower (at best O(n log n)); non comparison based sorts are faster for limited range data but need extra space and can't sort arbitrary data

Edge Cases

empty array

both sorts handle gracefully without errors

DSA C++

if (arr.empty()) return;

array with one element

array remains unchanged, no swaps or counts needed

DSA C++

for loops naturally skip or run once without issue

array with duplicates

both sorts correctly sort and keep duplicates

DSA C++

count[val]++ handles duplicates in counting sort

When to Use This Pattern

When sorting integers or data with limited range, consider non comparison based sorting for faster performance; otherwise, use comparison based sorting for general data.

Common Mistakes

Mistake: Trying to use counting sort on negative or non-integer data
Fix: Use comparison based sorting or adapt counting sort to handle negatives carefully

Mistake: Assuming non comparison based sorts always faster regardless of data
Fix: Remember non comparison based sorts depend on data range and type

Summary

Comparison based sorting uses element comparisons to order data; non comparison based sorting uses data properties like counts or digits.

Use comparison based sorting for general data and non comparison based sorting for integers with limited range for better speed.

The key insight is that non comparison based sorting avoids pairwise comparisons by leveraging data characteristics directly.

Practice

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

easy

A. Heap Sort

B. Merge Sort

C. Counting Sort

D. Quick Sort

Solution

1. Step 1: Understand comparison based sorting

   Comparison based sorting algorithms decide order by comparing elements pairwise, like Merge Sort, Quick Sort, and Heap Sort.

2. Step 2: Identify non-comparison based sorting

   Counting Sort uses element values as indices to count occurrences, not comparisons.

3. Final Answer:

   Counting Sort -> Option C

4. Quick Check:

   Counting Sort is 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 counting

2. Which of the following is the correct syntax to call Radix Sort function named radixSort on an integer array arr of size n in C++?

easy

A. radixSort(arr, n);

B. radixSort(n, arr);

C. radixSort(arr);

D. radixSort(&arr, n);

Solution

1. Step 1: Understand typical function parameters

   Sorting functions usually take the array and its size as parameters, in that order.

2. Step 2: Match syntax with parameters

   radixSort(arr, n); passes array and size correctly. radixSort(n, arr); reverses order, C misses size, D passes address incorrectly.

3. Final Answer:

   radixSort(arr, n); -> Option A

4. Quick Check:

   Array then size is standard [OK]

Hint: Array first, size second in sorting calls [OK]

Common Mistakes:

• Swapping parameter order
• Omitting size parameter
• Passing address of array incorrectly

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

int arr[] = {4, 2, 7, 1};
int n = 4;
// Using Counting Sort
void countingSort(int arr[], int n) {
    int max_val = 7;
    int count[8] = {0};
    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;
        }
    }
}

countingSort(arr, n);
for (int i = 0; i < n; i++) std::cout << arr[i] << " ";

medium

A. 7 4 2 1

B. 4 2 7 1

C. 1 2 7 4

D. 1 2 4 7

Solution

1. Step 1: Count frequencies of each element

   Count array records: count[1]=1, count[2]=1, count[4]=1, count[7]=1, others 0.

2. Step 2: Rebuild array in sorted order

   Loop from 0 to 7, placing elements according to counts: 1, 2, 4, 7.

3. Final Answer:

   1 2 4 7 -> Option D

4. Quick Check:

   Counting Sort outputs sorted array [OK]

Hint: Counting Sort outputs sorted elements in ascending order [OK]

Common Mistakes:

• Confusing counting array indices
• Not rebuilding array correctly
• Assuming original order remains

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

void countingSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};
    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 = 0; i < n; i++) {
        output[count[(arr[i] / exp) % 10]] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

medium

A. The output array index is off by one in the third loop

B. Count array size should be 100, not 10

C. The count array is not initialized to zero

D. The final copy loop should start from n-1 to 0

Solution

1. Step 1: Analyze output array indexing in third loop

   Indexing uses count[...] directly, but count array is cumulative, so index should be count[...] - 1.

2. Step 2: Identify correct fix

   Subtract 1 from count[...] when indexing output to avoid skipping first position.

3. Final Answer:

   The output array index is off by one in the third loop -> Option A

4. Quick Check:

   Output index = count[...] - 1 needed [OK]

Hint: Output index in counting sort is count[...] - 1 [OK]

Common Mistakes:

• Ignoring off-by-one in output indexing
• Changing count array size unnecessarily
• Not initializing count array

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

hard

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

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

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

D. Heap Sort, because it uses constant extra space

Solution

1. Step 1: Analyze input size and range

   Array size n=1,000,000; range k=1001 (0 to 1000).

2. Step 2: Compare sorting complexities

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

3. Final Answer:

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

4. Quick Check:

   Small range + large n favors Counting Sort [OK]

Hint: Small range with large n? Use Counting Sort [OK]

Common Mistakes:

• Choosing Quick Sort ignoring range
• Preferring stable sort without need
• Ignoring Counting Sort efficiency on small range