Comparison Based vs Non Comparison Based Sorting in DSA C++ - Visual Comparison

Concept Flow - Comparison Based vs Non Comparison Based Sorting

Start: Unsorted Array

↓

Choose Sorting Type

↓

Comparison Based

↓

Compare elements

↓

Swap or reorder

↓

Repeat until sorted

↓

Sorted Array

The flow shows starting with an unsorted array, choosing between comparison-based or non-comparison-based sorting, then following their distinct processes to produce a sorted array.

Execution Sample

DSA C++

int arr[] = {4, 2, 7, 1};
// Comparison based: Bubble Sort
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3 - i; j++) {
    if (arr[j] > arr[j+1]) std::swap(arr[j], arr[j+1]);
  }
}

This code sorts an array using comparison-based bubble sort by repeatedly swapping adjacent elements if they are in wrong order.

Execution Table

Step	Sorting Type	Operation	Array State	Details
1	Comparison Based	Compare arr[0]=4 and arr[1]=2	[4, 2, 7, 1]	4 > 2 → Swap
2	Comparison Based	Swap arr[0] and arr[1]	[2, 4, 7, 1]	Array after swap
3	Comparison Based	Compare arr[1]=4 and arr[2]=7	[2, 4, 7, 1]	4 < 7 → No swap
4	Comparison Based	Compare arr[2]=7 and arr[3]=1	[2, 4, 7, 1]	7 > 1 → Swap
5	Comparison Based	Swap arr[2] and arr[3]	[2, 4, 1, 7]	Array after swap
6	Comparison Based	Compare arr[0]=2 and arr[1]=4	[2, 4, 1, 7]	2 < 4 → No swap
7	Comparison Based	Compare arr[1]=4 and arr[2]=1	[2, 4, 1, 7]	4 > 1 → Swap
8	Comparison Based	Swap arr[1] and arr[2]	[2, 1, 4, 7]	Array after swap
9	Comparison Based	Compare arr[0]=2 and arr[1]=1	[2, 1, 4, 7]	2 > 1 → Swap
10	Comparison Based	Swap arr[0] and arr[1]	[1, 2, 4, 7]	Array after swap
11	Comparison Based	No more swaps needed	[1, 2, 4, 7]	Array is sorted
12	Non Comparison Based	Count elements frequency	[1, 2, 4, 7]	Count array: counts of each element
13	Non Comparison Based	Calculate positions	[1, 2, 4, 7]	Prefix sums for positions
14	Non Comparison Based	Place elements in output	[1, 2, 4, 7]	Rebuild sorted array
15	Non Comparison Based	Sorted array ready	[1, 2, 4, 7]	No comparisons used

💡 Sorting completes when array is fully ordered or rebuilt without comparisons.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 10	Final
arr	[4, 2, 7, 1]	[2, 4, 7, 1]	[2, 4, 1, 7]	[1, 2, 4, 7]	[1, 2, 4, 7]
count_array	N/A	N/A	N/A	N/A	[freq of 1=1, 2=1, 4=1, 7=1]
positions	N/A	N/A	N/A	N/A	[pos for 1=0, 2=1, 4=2, 7=3]

Key Moments - 3 Insights

Why does comparison-based sorting need to compare elements multiple times?

Because it decides order by comparing pairs repeatedly until no swaps are needed, as shown in steps 1-10 where multiple comparisons and swaps happen.

How does non-comparison-based sorting avoid comparing elements?

It uses element properties like counting frequency and positions (steps 12-15) to place elements directly without comparing them.

Can non-comparison-based sorting work on any data type?

No, it works only when elements have properties like integers in a known range, unlike comparison-based which works on any data.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 5?

A [1, 2, 4, 7]

B [2, 4, 7, 1]

C [2, 4, 1, 7]

D [4, 2, 7, 1]

💡 Hint

Check the 'Array State' column at step 5 in the execution_table.

At which step does the comparison-based sorting finish sorting the array?

A Step 11

B Step 10

C Step 12

D Step 15

💡 Hint

Look for the step where 'No more swaps needed' and 'Array is sorted' appear.

If the array had elements outside a known range, which sorting type would still work?

A Non Comparison Based

B Comparison Based

C Both

D Neither

💡 Hint

Refer to key_moments about data type restrictions for non-comparison-based sorting.

Concept Snapshot

Comparison Based Sorting:
- Sorts by comparing and swapping elements
- Examples: Bubble, Quick, Merge Sort
- Works on any data type

Non Comparison Based Sorting:
- Uses element properties (counting, buckets)
- Examples: Counting Sort, Radix Sort
- Requires known range or special properties

Choose based on data and efficiency needs.

Full Transcript

This visual execution compares two sorting types: comparison-based and non-comparison-based. Starting with an unsorted array, comparison-based sorting repeatedly compares and swaps elements until sorted, shown step-by-step with array states changing after each swap. Non-comparison-based sorting counts element frequencies and uses positions to rebuild the sorted array without comparisons. Key moments clarify why comparison-based sorting needs multiple comparisons and why non-comparison-based sorting depends on element properties. The quizzes test understanding of array states during sorting and applicability of each method. The snapshot summarizes key differences and use cases.

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