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

Concept Flow - Comparison Based vs Non Comparison Based Sorting

Start with unsorted array

↓

Comparison Based

↓

Compare pairs

↓

Swap if needed

↓

Repeat until sorted

↓

Sorted array

↓

Sorting Done

Sorting starts with an unsorted array. If sorting compares elements, it uses comparison-based methods. Otherwise, it uses non-comparison methods like counting or bucketing.

Execution Sample

DSA Python

arr = [4, 2, 7, 1]
# Comparison based: Bubble Sort
for i in range(len(arr)):
    for j in range(len(arr)-i-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

This code sorts the array using bubble sort, a comparison-based method that swaps elements if they are in the wrong order.

Execution Table

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

💡 Sorting stops when a full pass completes with no swaps, meaning array is sorted.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	Final
arr	[4, 2, 7, 1]	[2, 4, 7, 1]	[2, 4, 1, 7]	[1, 2, 4, 7]	[1, 2, 4, 7]
i (outer loop)	0	0	0	2	3
j (inner loop)	0	0	2	0	0
swap_occurred	False	True	True	True	False

Key Moments - 3 Insights

Why do we need to compare pairs of elements in comparison-based sorting?

Because comparison-based sorting decides order by comparing two elements at a time, as shown in steps 1-6 where pairs are compared and swapped if needed.

How does non-comparison based sorting avoid comparing elements?

It uses element properties like counting occurrences or placing elements into buckets, then reconstructs the sorted array without direct comparisons.

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

No swaps mean all elements are in correct order, so the array is sorted, as shown in the exit step where swap_occurred is False.

Visual Quiz - 3 Questions

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

A [2, 4, 7, 1]

B [2, 4, 1, 7]

C [4, 2, 7, 1]

D [1, 2, 4, 7]

💡 Hint

Check the 'Resulting Array' column at step 3 in the execution_table.

At which step does the condition '4 > 1' become true and cause a swap?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look for the comparison '4 > 1' in the 'Comparison' column of execution_table.

If the array was already sorted, how would the 'swap_occurred' variable change in variable_tracker?

A It would be True after every step

B It would be False from the start

C It would alternate between True and False

D It would be True only at the last step

💡 Hint

Refer to the 'swap_occurred' row in variable_tracker and the exit condition in execution_table.

Concept Snapshot

Comparison Based Sorting:
- Sorts by comparing pairs of elements
- Examples: Bubble Sort, Quick Sort
- Uses swaps based on comparisons

Non Comparison Based Sorting:
- Sorts using element properties (counting, bucketing)
- Examples: Counting Sort, Radix Sort
- No direct element comparisons

Full Transcript

Sorting algorithms can be divided into two types: comparison based and non comparison based. Comparison based sorting works by comparing pairs of elements and swapping them if they are in the wrong order. This process repeats until the array is sorted. Bubble sort is a simple example where adjacent elements are compared and swapped. Non comparison based sorting does not compare elements directly. Instead, it uses properties like counting occurrences or placing elements into buckets to sort. The sorting finishes when no swaps are needed in comparison based methods, indicating the array is sorted. This visual trace shows step-by-step how bubble sort compares and swaps elements until the array is sorted.

Practice

1. Which of the following sorting algorithms is not based on comparing elements?

easy

A. Quick Sort

B. Merge Sort

C. Counting Sort

D. Heap 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 counting frequencies and does not compare elements directly.

3. Final Answer:

   Counting Sort -> Option C

4. Quick Check:

   Non-comparison based = Counting Sort [OK]

Hint: Counting Sort uses counts, no element comparisons [OK]

Common Mistakes:

• Confusing Counting Sort with Quick Sort
• Thinking Merge Sort is non-comparison based
• Assuming Heap Sort doesn't compare elements

2. Which of the following is the correct syntax to call a non-comparison based sorting function counting_sort(arr) in Python?

easy

A. counting_sort(arr)

B. counting_sort arr

C. counting_sort{arr}

D. counting_sort[arr]

Solution

1. Step 1: Recall Python function call syntax

   Functions are called with parentheses enclosing arguments, like func(args).

2. Step 2: Match syntax with options

   Only counting_sort(arr) uses correct parentheses syntax.

3. Final Answer:

   counting_sort(arr) -> Option A

4. Quick Check:

   Function call uses parentheses [OK]

Hint: Use parentheses () to call functions in Python [OK]

Common Mistakes:

• Using square brackets instead of parentheses
• Omitting parentheses when calling functions
• Using curly braces which are invalid for calls

3. What will be the output of the following Python code using Counting Sort on the array [4, 2, 2, 8, 3, 3, 1]?

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

medium

A. [1, 2, 2, 3, 3, 4, 8]

B. [8, 4, 3, 3, 2, 2, 1]

C. [1, 3, 2, 4, 8]

D. [4, 2, 2, 8, 3, 3, 1]

Solution

1. Step 1: Count frequencies of each number

   Count array will have counts: 1->1, 2->2, 3->2, 4->1, 8->1, others 0.

2. Step 2: Build sorted array by repeating each number count times

   Sorted array is [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option A

4. Quick Check:

   Counting Sort output = sorted array [OK]

Hint: Counting Sort outputs sorted array by frequency counts [OK]

Common Mistakes:

• Confusing original array with sorted output
• Reversing the sorted order
• Missing duplicates in output

4. The following code attempts to implement Counting Sort but has a bug. What is the error?

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * max_val
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

print(counting_sort([1, 4, 1, 2, 7, 5]))

medium

A. Using extend instead of append causes error

B. count array size is too small, missing last element count

C. max_val should be min_val

D. Loop range should be over arr, not count

Solution

1. Step 1: Check count array size

   Count array size is max_val, but should be max_val + 1 to include max element index.

2. Step 2: Identify impact of size error

   Missing last index causes IndexError or missing counts for max element.

3. Final Answer:

   count array size is too small, missing last element count -> Option B

4. Quick Check:

   Count array size = max_val + 1 needed [OK]

Hint: Count array must cover all values including max [OK]

Common Mistakes:

• Ignoring off-by-one error in count array size
• Thinking extend causes error
• Confusing max_val with min_val

5. You have a large list of integers ranging from 0 to 1000. Which sorting algorithm is best to sort this list efficiently and why? A) Quick Sort because it has average O(n log n) time B) Counting Sort because it sorts in O(n + k) time where k is max value C) Merge Sort because it is stable and always O(n log n) D) Bubble Sort because it is simple to implement

hard

A. Quick Sort because it has average O(n log n) time

B. Bubble Sort because it is simple to implement

C. Merge Sort because it is stable and always O(n log n)

D. Counting Sort because it sorts in O(n + k) time where k is max value

Solution

1. Step 1: Analyze input range and size

   Input values are integers from 0 to 1000, so k = 1000 is small compared to n (large list).

2. Step 2: Choose sorting algorithm based on time complexity

   Counting Sort runs in O(n + k), which is efficient for small k and large n, better than O(n log n).

3. Final Answer:

   Counting Sort because it sorts in O(n + k) time where k is max value -> Option D

4. Quick Check:

   Small range + large list = Counting Sort best [OK]

Hint: Use Counting Sort for small range large list [OK]

Common Mistakes:

• Choosing Quick Sort ignoring input range
• Preferring Bubble Sort despite poor performance
• Ignoring Counting Sort's linear time advantage