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 weights. Some boxes have small weights (0 to 9 kg), and others have larger weights. You want to sort these boxes quickly using two different methods: one that compares boxes directly and one that uses their weight values without direct comparison.

🎯 Goal: Build two sorting methods in C++: one using comparison-based sorting (Bubble Sort) and one using non-comparison-based sorting (Counting Sort). See how they sort the same list of box weights.

📋 What You'll Learn

Create an array called boxes with these exact weights: 4, 2, 7, 3, 8, 2, 3, 0, 9, 1

Create an integer variable called size that stores the number of boxes

Write a function called bubbleSort that sorts the boxes array using comparison-based sorting

Write a function called countingSort that sorts the boxes array using non-comparison-based sorting

Print the sorted arrays after each sorting method

💡 Why This Matters

🌍 Real World

Sorting items quickly is important in warehouses, online stores, and many apps to organize data efficiently.

💼 Career

Understanding different sorting methods helps in choosing the right algorithm for performance in software development and data processing jobs.

1

Create the boxes array

Create an integer array called boxes with these exact weights: 4, 2, 7, 3, 8, 2, 3, 0, 9, 1 and an integer variable called size that stores the number of boxes.

DSA C++

// Your code here

Hint

Use int boxes[] = {4, 2, 7, 3, 8, 2, 3, 0, 9, 1}; to create the array and int size = sizeof(boxes) / sizeof(boxes[0]); to get its length.

2

Write the bubbleSort function

Write a function called bubbleSort that takes an integer array arr and its size as parameters and sorts the array using comparison-based bubble sort.

DSA C++

int boxes[] = {4, 2, 7, 3, 8, 2, 3, 0, 9, 1};
int size = sizeof(boxes) / sizeof(boxes[0]);

// Your code here

Hint

Use two nested loops to compare adjacent elements and swap if the left one is bigger.

3

Write the countingSort function

Write a function called countingSort that takes an integer array arr and its size as parameters and sorts the array using non-comparison-based counting sort. Assume all weights are between 0 and 9.

DSA C++

int boxes[] = {4, 2, 7, 3, 8, 2, 3, 0, 9, 1};
int size = sizeof(boxes) / sizeof(boxes[0]);

void bubbleSort(int arr[], int size) {
    for (int i = 0; i  arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Your code here

Hint

Count how many times each weight appears, then overwrite the array with sorted weights.

4

Print sorted arrays after both sorts

Call bubbleSort(boxes, size) and print the sorted array with the label "Bubble Sort:". Then reset boxes to the original array, call countingSort(boxes, size), and print the sorted array with the label "Counting Sort:". Use a for loop with variable i to print elements separated by spaces.

DSA C++

Hint

Call bubbleSort(boxes, size), print the array, reset boxes to original, call countingSort(boxes, size), and print again.

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