Comparison Based vs Non Comparison Based Sorting in DSA C - Complexity Comparison

Time Complexity: Comparison Based vs Non Comparison Based Sorting

O(n^2) for comparison based, O(n + k) for non comparison based

Understanding Time Complexity

Sorting is a common task where we arrange items in order. Different sorting methods take different times depending on how they work.

We want to understand how the time needed grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of these two sorting approaches.

// Comparison Based Sorting (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 Sorting (Counting Sort)
void countingSort(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) max = arr[i];
  }
  int count[max+1];
  for (int i = 0; i <= max; i++) count[i] = 0;
  for (int i = 0; i < n; i++) count[arr[i]]++;
  int index = 0;
  for (int i = 0; i <= max; i++) {
    while (count[i]-- > 0) {
      arr[index++] = i;
    }
  }
}
    

Bubble Sort compares and swaps elements repeatedly. Counting Sort counts occurrences and places elements directly.

Identify Repeating Operations

Look at the main repeated steps in each method.

• Bubble Sort primary operation: Nested loops comparing pairs of elements.
• Bubble Sort how many times: Outer loop runs n times, inner loop runs up to n times, so about n x n = n² times.
• Counting Sort primary operation: Counting each element and then placing them back.
• Counting Sort how many times: Counting loop runs n times, then placing loop runs max + 1 times, so roughly n + max.

How Execution Grows With Input

See how the work grows as the list size grows.

Input Size (n)	Bubble Sort Ops (approx.)	Counting Sort Ops (approx.)
10	100 (10²)	10 + max
100	10,000 (100²)	100 + max
1000	1,000,000 (1000²)	1000 + max

Bubble Sort grows very fast as n grows (squares). Counting Sort grows roughly linearly with n and max value.

Final Time Complexity

Time Complexity: O(n²) for comparison based (Bubble Sort), O(n + k) for non comparison based (Counting Sort), where k is max value.

This means Bubble Sort gets much slower as list grows, but Counting Sort can be faster if max value is not too big.

Common Mistake

[X] Wrong: "All sorting methods take about the same time because they all sort the list."

[OK] Correct: Different methods use different steps. Some compare many pairs, others count and place directly, so time can be very different.

Interview Connect

Understanding how sorting time grows helps you choose the right method and explain your choices clearly in interviews. It shows you know how to handle different data sizes and types.

Self-Check

"What if the maximum value in Counting Sort is much larger than the number of elements? How would that affect the time complexity?"

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