Comparison Based vs Non Comparison Based Sorting in DSA Go - 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

↓

Combine results

↓

Sorted array

↓

Sorting complete

The flow shows how sorting starts with an unsorted array, then splits into comparison based sorting which compares and swaps elements, or non comparison based sorting which uses counting or keys to place elements directly.

Execution Sample

DSA Go

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

This code sorts an array using bubble sort, a comparison based sorting method that swaps adjacent 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]	-	No	[1, 2, 3, 4]
8	Non Comparison Based: Counting Sort count array	Input: [4, 2, 3, 1]	-	-	Count: [0,1,1,1,1]
9	Place elements by count	Count: [0,1,1,1,1]	-	-	Sorted: [1, 2, 3, 4]
10	Sorting complete	[1, 2, 3, 4]	-	-	[1, 2, 3, 4]

💡 Bubble sort ends when no swaps are needed; counting sort ends after placing elements by counts.

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]
count	N/A	N/A	N/A	N/A	N/A	N/A	N/A	[0,1,1,1,1]

Key Moments - 3 Insights

Why does comparison based sorting need to compare pairs of elements?

Because it decides order by checking which element is bigger or smaller step by step, as shown in steps 1 to 6 in the execution table where pairs are compared and swapped.

How does non comparison based sorting avoid comparing elements?

It uses extra information like counts or keys to place elements directly, as shown in steps 8 and 9 where counts are used to build the sorted array without comparing pairs.

Why does bubble sort stop early when no swaps happen?

Because no swaps mean the array is already sorted, as shown in step 7 where no swap occurs and sorting ends.

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 [1, 2, 3, 4]

D [4, 2, 3, 1]

💡 Hint

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

At which step does bubble sort detect the array is sorted and stop swapping?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for the step where 'No more swaps needed' is noted in the execution table.

If the input array had duplicates, which sorting type would handle it without comparing elements?

A Comparison Based Sorting

B Non Comparison Based Sorting

C Neither

D Both

💡 Hint

Refer to steps 8 and 9 where counting sort uses counts to place elements, which works well with duplicates.

Concept Snapshot

Comparison Based Sorting:
- Sorts by comparing pairs of elements
- Examples: Bubble Sort, Quick Sort
- Usually O(n log n) or worse

Non Comparison Based Sorting:
- Uses keys or counts to place elements
- Examples: Counting Sort, Radix Sort
- Can be faster but needs extra info

Choose based on data and constraints.

Full Transcript

This visual execution compares two main sorting types: comparison based and non comparison based. Comparison based sorting works by comparing pairs of elements and swapping them if needed, repeating until sorted. Bubble sort is an example shown step-by-step. Non comparison based sorting uses extra information like counts or keys to place elements directly without comparing pairs, demonstrated by counting sort steps. The execution table tracks array states and operations. Key moments clarify why comparisons are needed in one and not the other, and when sorting stops. The quiz tests understanding of array states and sorting behavior. The snapshot summarizes key differences and examples.

Practice

1. Which of the following sorting algorithms is non-comparison based?

easy

A. Merge Sort

B. Counting Sort

C. Quick Sort

D. Heap Sort

Solution

1. Step 1: Understand comparison based sorting

   Comparison based sorting algorithms decide order by comparing elements, like Merge Sort, Quick Sort, and Heap Sort.

2. Step 2: Identify non-comparison based sorting

   Counting Sort uses counting and indexing, not direct comparisons, so it is non-comparison based.

3. Final Answer:

   Counting Sort -> Option B

4. Quick Check:

   Counting Sort = Non-comparison based [OK]

Hint: Counting Sort uses counts, not comparisons [OK]

Common Mistakes:

• Confusing Counting Sort with Quick Sort
• Thinking Merge Sort is non-comparison based
• Assuming Heap Sort is non-comparison based

2. Which of the following is the correct syntax to call a non-comparison based sorting function CountingSort(arr []int) in Go?

easy

A. CountingSort{arr}

B. CountingSort arr

C. CountingSort(arr)

D. CountingSort->arr

Solution

1. Step 1: Recall Go function call syntax

   In Go, functions are called with the function name followed by parentheses enclosing arguments.

2. Step 2: Apply syntax to CountingSort

   Calling CountingSort with array arr is done as CountingSort(arr).

3. Final Answer:

   CountingSort(arr) -> Option C

4. Quick Check:

   Function call syntax = CountingSort(arr) [OK]

Hint: Use parentheses for function calls in Go [OK]

Common Mistakes:

• Omitting parentheses in function call
• Using braces {} instead of parentheses
• Using arrow notation which is invalid in Go

3. What will be the output of the following Go code snippet?

arr := []int{4, 2, 7, 1}
CountingSort(arr)
fmt.Println(arr)

Assuming CountingSort sorts the array in ascending order without returning a new array.

medium

A. [1 2 4 7]

B. [4 2 7 1]

C. [7 4 2 1]

D. Compilation error

Solution

1. Step 1: Understand CountingSort behavior

   CountingSort sorts the array in ascending order in-place.

2. Step 2: Apply CountingSort to arr

   Original arr is [4 2 7 1]. After sorting, arr becomes [1 2 4 7].

3. Final Answer:

   [1 2 4 7] -> Option A

4. Quick Check:

   Sorted arr = [1 2 4 7] [OK]

Hint: CountingSort sorts in ascending order in-place [OK]

Common Mistakes:

• Assuming CountingSort returns a new array
• Confusing ascending with descending order
• Thinking code causes compilation error

4. Identify the error in this Go code snippet that attempts to use Radix Sort (a non-comparison based sort):

func RadixSort(arr []int) {
  for i := 0; i < len(arr); i++ {
    // sorting logic here
  }
}

arr := []int{3, 1, 4}
RadixSort(arr)
fmt.Println(arr)

medium

A. Radix Sort requires multiple passes over digits, not just one loop

B. The function should return a new sorted array

C. The loop variable i should start from 1, not 0

D. Radix Sort cannot sort integers

Solution

1. Step 1: Understand Radix Sort process

   Radix Sort sorts numbers digit by digit, requiring multiple passes over digits.

2. Step 2: Analyze given loop

   The code loops only once over array length, missing multiple digit passes needed.

3. Final Answer:

   Radix Sort requires multiple passes over digits, not just one loop -> Option A

4. Quick Check:

   Radix Sort needs multiple digit passes [OK]

Hint: Radix Sort loops over digits, not just array elements [OK]

Common Mistakes:

• Thinking single loop is enough for Radix Sort
• Expecting Radix Sort to return new array always
• Believing Radix Sort cannot sort integers

5. You have an array of 1 million integers ranging only from 0 to 1000. Which sorting approach is best and why?

hard

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

B. Use Bubble Sort because it is simple to implement

C. Use Merge Sort because it is stable

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

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 efficient here since k is small compared to n.

3. Step 3: Choose best sorting method

   Counting Sort is faster than Quick Sort's average O(n log n) for this input.

4. Final Answer:

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

5. Quick Check:

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

Hint: Small range large array? Use Counting Sort [OK]

Common Mistakes:

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