Comparison Based vs Non Comparison Based Sorting in DSA Python - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a Small Array

What is the output of the following Python code that uses Counting Sort on the array [4, 2, 2, 8, 3, 3, 1]?

DSA Python

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

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

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

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

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

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

💡 Hint

Counting sort counts how many times each number appears and then reconstructs the sorted list.

Counting sort counts the frequency of each number and then outputs them in order. The input array has duplicates, so the output includes all duplicates sorted.

🧠 Conceptual

intermediate

Time Complexity of Comparison Based Sorting

Which of the following is the best known lower bound on the time complexity of any comparison based sorting algorithm?

A O(n)

B O(n^2)

C O(n log n)

D O(log n)

💡 Hint

Think about the minimum number of comparisons needed to distinguish all permutations.

Comparison based sorting algorithms cannot do better than O(n log n) in the worst case because they must distinguish between n! permutations.

❓ Predict Output

advanced

Output of Radix Sort on a List of Integers

What is the output of the following Python code that uses Radix Sort on the list [170, 45, 75, 90, 802, 24, 2, 66]?

DSA Python

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]


def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)

A [802, 170, 90, 75, 66, 45, 24, 2]

B [2, 24, 45, 66, 75, 90, 170, 802]

C [2, 24, 45, 66, 75, 170, 90, 802]

D [24, 2, 45, 66, 75, 90, 170, 802]

💡 Hint

Radix sort sorts numbers digit by digit starting from least significant digit.

Radix sort sorts the array by processing digits from least significant to most significant, resulting in a fully sorted array.

🧠 Conceptual

advanced

Which Sorting Algorithm is Non Comparison Based?

Which of the following sorting algorithms does NOT use comparisons between elements to sort the array?

A Merge Sort

B Quick Sort

C Heap Sort

D Counting Sort

💡 Hint

Non comparison based sorting uses counting or digit extraction instead of comparing elements.

Counting Sort counts the occurrences of each element and sorts based on counts without comparing elements.

🧠 Conceptual

expert

Why Can't Comparison Based Sorting Beat O(n log n)?

Why is it impossible for any comparison based sorting algorithm to have a worst-case time complexity better than O(n log n)?

A Because the number of possible orderings of n elements is n!, and distinguishing them requires at least log2(n!) comparisons.

B Because comparison based sorting algorithms always use nested loops.

C Because memory limitations prevent faster sorting.

D Because non comparison based sorting algorithms are always faster.

💡 Hint

Think about how many different ways n elements can be arranged and how comparisons help identify the correct order.

The decision tree model shows that to distinguish all n! permutations, at least log2(n!) comparisons are needed, which is O(n log n).

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