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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a small array

What is the output of the following C++ code that uses Counting Sort on the array [4, 2, 2, 8, 3, 3, 1]?

DSA C++

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

void countingSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    vector<int> count(max_val + 1, 0);
    for (int num : arr) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

A 1 2 3 4 8

B 1 2 2 3 3 4 8

C 8 4 3 3 2 2 1

D 2 2 3 3 4 8 1

💡 Hint

Counting Sort counts occurrences and then rebuilds the array in sorted order.

Counting Sort counts how many times each number appears and then writes them back in order. So the sorted array is 1 2 2 3 3 4 8.

🧠 Conceptual

intermediate

Time Complexity of Comparison Based Sorting

Which of the following is the best known lower bound on the time complexity of any comparison based sorting algorithm for n elements?

A O(n)

B O(n^2)

C O(n log n)

D O(log n)

💡 Hint

Think about the decision tree model for comparisons.

Comparison based sorting algorithms cannot do better than O(n log n) in the worst case because of the number of comparisons needed to distinguish all permutations.

❓ Predict Output

advanced

Output of Radix Sort on integers

What is the output of the following C++ code that uses Radix Sort on the array [170, 45, 75, 90, 802, 24, 2, 66]?

DSA C++

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

void countingSortForRadix(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<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 = 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];
}

void radixSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    for (int exp = 1; max_val / exp > 0; exp *= 10) {
        countingSortForRadix(arr, exp);
    }
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

A 802 170 90 75 66 45 24 2

B 2 24 45 75 66 90 170 802

C 24 2 45 66 75 90 170 802

D 2 24 45 66 75 90 170 802

💡 Hint

Radix Sort sorts numbers digit by digit starting from least significant digit.

Radix Sort sorts the array by each digit from right to left, resulting in the sorted array: 2 24 45 66 75 90 170 802.

🧠 Conceptual

advanced

Which sorting algorithm is NOT comparison based?

Among the following sorting algorithms, which one does NOT rely on comparing elements to sort the array?

A Counting Sort

B Heap Sort

C Merge Sort

D Quick Sort

💡 Hint

Counting Sort uses counting frequencies instead of comparisons.

Counting Sort sorts by counting the number of occurrences of each value, not by comparing elements.

🧠 Conceptual

expert

Why can't comparison based sorting be faster than O(n log n)?

Why is it impossible for any comparison based sorting algorithm to have a worst-case time complexity better than O(n log n)?

A Because the number of possible orderings of n elements is n!, and the decision tree height must be at least log2(n!) which is O(n log n)

B Because computers cannot perform comparisons faster than O(n log n)

C Because memory limitations prevent faster sorting

D Because non comparison based sorting algorithms are always slower

💡 Hint

Think about how many different ways n elements can be arranged.

The number of permutations of n elements is n!. To distinguish all permutations, a comparison based sorting algorithm must have at least log2(n!) comparisons, which is O(n log n).

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