Comparison Based vs Non Comparison Based Sorting in DSA C - Build Both Approaches

Comparison Based vs Non Comparison Based Sorting

📖 Scenario: You work in a warehouse where you need to organize boxes by their weight. Some boxes have weights that are small whole numbers, while others have larger or more varied weights. You want to learn two ways to sort these boxes: one by comparing each box's weight to others, and another by using the weight values directly without comparing each pair.

🎯 Goal: Build two sorting methods in C: one that sorts an array of integers by comparing elements (comparison based), and another that sorts using counting (non comparison based). Then, print the sorted arrays to see the difference.

📋 What You'll Learn

Create an integer array with exact values

Create a variable for the maximum value in the array

Implement comparison based sorting using bubble sort

Implement non comparison based sorting using counting sort

Print both sorted arrays exactly as specified

💡 Why This Matters

🌍 Real World

Sorting is used everywhere, like organizing products by weight or price in warehouses and stores.

💼 Career

Understanding sorting helps in software development, data analysis, and optimizing tasks that involve ordering data.

1

Create the array of box weights

Create an integer array called weights with these exact values: 4, 2, 7, 3, 2, 8, 1 and an integer size set to 7.

DSA C

# Create the array weights and size variable
// Your code here

Hint

Use square brackets to create the array and assign the exact numbers inside curly braces.

2

Find the maximum weight

Create an integer variable called max_weight and set it to the maximum value in the weights array, which is 8.

DSA C

int weights[] = {4, 2, 7, 3, 2, 8, 1};
int size = 7;
// Create max_weight variable and set it to 8
// Your code here

Hint

Just assign the number 8 to the variable max_weight.

3

Sort using comparison based bubble sort

Write a bubble sort using for loops with variables i and j to sort the weights array in ascending order by comparing elements.

DSA C

int weights[] = {4, 2, 7, 3, 2, 8, 1};
int size = 7;
int max_weight = 8;
// Implement bubble sort to sort weights in ascending order
// Your code here

Hint

Use nested loops to compare adjacent elements and swap if out of order.

4

Sort using non comparison based counting sort and print results

Implement counting sort using an integer array count of size max_weight + 1. Count occurrences of each weight in weights, then overwrite weights with sorted values. Finally, print both sorted arrays using printf in this format: Comparison Sort: 1 2 2 3 4 7 8 and Counting Sort: 1 2 2 3 4 7 8.

DSA C

int weights[] = {4, 2, 7, 3, 2, 8, 1};
int size = 7;
int max_weight = 8;

for (int i = 0; i  weights[j + 1]) {
            int temp = weights[j];
            weights[j] = weights[j + 1];
            weights[j + 1] = temp;
        }
    }
}
// Implement counting sort and print both sorted arrays
// Your code here

Hint

Use an array to count each weight's frequency, then rebuild the sorted array. Use printf to show results.

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