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 code that uses Counting Sort on the array [4, 2, 2, 8, 3, 3, 1]?

DSA C

void countingSort(int arr[], int n) {
    int output[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]]++;
    for (int i = 1; i <= max; 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];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 8 4 3 3 2 2 1

B 1 2 2 3 3 4 8

C 1 2 3 4 8 2 3

D 2 2 3 3 4 8 1

💡 Hint

Counting Sort counts occurrences and places elements in order without comparing pairs.

Counting Sort counts how many times each number appears, then uses that to place numbers in sorted order. The output is the sorted array: 1 2 2 3 3 4 8.

🧠 Conceptual

intermediate

Time complexity comparison of sorting algorithms

Which of the following statements correctly compares the average time complexities of comparison based and non comparison based sorting algorithms?

A Comparison based sorting algorithms have a lower bound of O(n log n), while non comparison based can achieve O(n) under certain conditions.

B Comparison based sorting algorithms can run in O(n), but non comparison based sorting always runs in O(n log n).

C Both comparison based and non comparison based sorting algorithms have the same average time complexity of O(n log n).

D Non comparison based sorting algorithms always have worse time complexity than comparison based sorting.

💡 Hint

Think about the theoretical lower bound for comparison based sorting.

Comparison based sorting algorithms cannot do better than O(n log n) on average due to decision tree limits. Non comparison based algorithms like Counting Sort or Radix Sort can achieve O(n) if input constraints allow.

🔧 Debug

advanced

Identify the error in this Radix Sort implementation snippet

What error will occur when running this Radix Sort code snippet on the array [170, 45, 75, 90, 802, 24, 2, 66]?

DSA C

void countingSortForRadix(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 = 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];
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortForRadix(arr, n, exp);
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A Logical error: the array remains unsorted after execution.

B Runtime error due to accessing count array out of bounds.

C No error; the code runs and outputs the sorted array correctly.

D Compilation error due to missing header files.

💡 Hint

Check how the count array is indexed and updated.

The code correctly implements Radix Sort using Counting Sort as a subroutine. It sorts the array properly without errors.

❓ Predict Output

advanced

Output of Quick Sort partition step

Given the array [10, 7, 8, 9, 1, 5], what is the array state after the first partition call of Quick Sort with pivot as last element?

DSA C

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int pi = partition(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 1 5 8 9 10 7

B 5 1 7 8 9 10

C 10 7 8 9 1 5

D 1 5 7 8 9 10

💡 Hint

Pivot is last element; elements less than pivot move left.

After partition, elements less than pivot (5) are moved left, pivot placed at correct position index 1. The array becomes: 1 5 8 9 10 7.

🧠 Conceptual

expert

Why non comparison based sorting cannot sort arbitrary data?

Which reason best explains why non comparison based sorting algorithms like Counting Sort or Radix Sort cannot be used to sort arbitrary data types like floating point numbers or strings of arbitrary length?

A Because non comparison based sorting algorithms modify the data in place, which is unsafe for complex data types.

B Because non comparison based sorting algorithms rely on comparing elements pairwise, which is not possible for arbitrary data.

C Because non comparison based sorting algorithms have higher time complexity for arbitrary data types.

D Because non comparison based sorting requires data to be integers within a known range to count occurrences efficiently.

💡 Hint

Think about what Counting Sort needs to work efficiently.

Non comparison based sorts like Counting Sort require the input to be integers in a limited range to count frequencies. Arbitrary data types like floats or strings don't fit this requirement easily.

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