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).