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

Concept Flow - Comparison Based vs Non Comparison Based Sorting

Start with unsorted array

↓

Comparison Based

↓

Compare pairs

↓

Swap or reorder

↓

Repeat until sorted

↓

Sorted array

Sorting starts with an unsorted array. We decide if sorting uses element comparisons or not. Comparison based sorts compare and swap elements repeatedly. Non comparison based sorts use counting or keys to place elements directly.

Execution Sample

DSA C

int arr[] = {4, 2, 3, 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]) {
      int temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}

This code sorts an array using bubble sort, a comparison based sorting method that swaps elements if they are out of order.

Execution Table

Step	Operation	Array State	Comparison	Swap?	Resulting Array
1	Compare arr[0] and arr[1]	[4, 2, 3, 1]	4 > 2	Yes	[2, 4, 3, 1]
2	Compare arr[1] and arr[2]	[2, 4, 3, 1]	4 > 3	Yes	[2, 3, 4, 1]
3	Compare arr[2] and arr[3]	[2, 3, 4, 1]	4 > 1	Yes	[2, 3, 1, 4]
4	Compare arr[0] and arr[1]	[2, 3, 1, 4]	2 > 3	No	[2, 3, 1, 4]
5	Compare arr[1] and arr[2]	[2, 3, 1, 4]	3 > 1	Yes	[2, 1, 3, 4]
6	Compare arr[0] and arr[1]	[2, 1, 3, 4]	2 > 1	Yes	[1, 2, 3, 4]
7	No more swaps needed	[1, 2, 3, 4]	N/A	No	[1, 2, 3, 4]

💡 Array is sorted after no swaps in a full pass

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
arr	[4, 2, 3, 1]	[2, 4, 3, 1]	[2, 3, 4, 1]	[2, 3, 1, 4]	[2, 3, 1, 4]	[2, 1, 3, 4]	[1, 2, 3, 4]	[1, 2, 3, 4]
i	0	0	0	0	1	1	2	2
j	0	1	2	3	0	1	0	N/A

Key Moments - 3 Insights

Why do comparison based sorts need to compare pairs of elements?

Because they decide order by comparing two elements at a time, as shown in steps 1-6 where each pair is checked and swapped if needed.

How does non comparison based sorting avoid comparing elements?

It uses extra information like counts or keys to place elements directly without comparing pairs, unlike the step-by-step swaps in the table.

Why does the sorting stop after no swaps in a full pass?

Because no swaps mean all elements are in order, as seen in step 7 where no swap occurs and the array is sorted.

Visual Quiz - 3 Questions

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

A [2, 3, 1, 4]

B [2, 4, 3, 1]

C [2, 3, 4, 1]

D [1, 2, 3, 4]

💡 Hint

Check the 'Resulting Array' column at step 3 in the execution table.

At which step does the first swap occur?

A Step 2

B Step 4

C Step 1

D Step 5

💡 Hint

Look at the 'Swap?' column in the execution table starting from step 1.

If we use a non comparison based sort, which operation would NOT appear in the execution table?

A Placing elements by count

B Comparing pairs of elements

C Swapping elements

D Repeating passes until sorted

💡 Hint

Non comparison based sorts do not compare elements, unlike the comparison based steps shown.

Concept Snapshot

Comparison Based Sorting:
- Sort by comparing pairs of elements
- Swap if out of order
- Repeat until no swaps

Non Comparison Based Sorting:
- Use counts or keys
- Place elements directly
- No pairwise comparisons

Choose based on data and constraints.

Full Transcript

Sorting can be done by comparing elements or by using other methods. Comparison based sorting looks at pairs of elements and swaps them if needed, repeating until sorted. Non comparison based sorting uses extra information like counts to place elements without comparing pairs. The example shows bubble sort, a comparison based method, where each step compares and sometimes swaps elements. Sorting stops when a full pass has no swaps, meaning the array is sorted.

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