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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Comparison Based Sorting Algorithm

What is the output of the following Go code that uses a comparison based sorting algorithm (Bubble Sort) on the array?

DSA Go

package main
import (
	"fmt"
)
func bubbleSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}
func main() {
	arr := []int{5, 3, 8, 4, 2}
	bubbleSort(arr)
	fmt.Println(arr)
}

A [8 5 4 3 2]

B [5 3 8 4 2]

C [2 3 4 5 8]

D [2 4 3 5 8]

💡 Hint

Bubble sort repeatedly swaps adjacent elements if they are in wrong order.

The bubble sort algorithm compares adjacent elements and swaps them if the left element is greater than the right. After all passes, the array is sorted in ascending order.

❓ Predict Output

intermediate

Output of Non Comparison Based Sorting Algorithm

What is the output of the following Go code that uses a non comparison based sorting algorithm (Counting Sort) on the array?

DSA Go

package main
import (
	"fmt"
)
func countingSort(arr []int) []int {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	count := make([]int, max+1)
	for _, v := range arr {
		count[v]++
	}
	index := 0
	for i, c := range count {
		for c > 0 {
			arr[index] = i
			index++
			c--
		}
	}
	return arr
}
func main() {
	arr := []int{4, 2, 2, 8, 3, 3, 1}
	sortedArr := countingSort(arr)
	fmt.Println(sortedArr)
}

A [4 2 2 8 3 3 1]

B [1 2 2 3 3 4 8]

C [8 4 3 3 2 2 1]

D [1 3 2 2 3 4 8]

💡 Hint

Counting sort counts occurrences of each number and reconstructs the sorted array.

Counting sort counts how many times each number appears and then writes them back in order. This produces a sorted array in ascending order.

🧠 Conceptual

advanced

Time Complexity Difference

Which statement correctly describes the time complexity difference between comparison based and non comparison based sorting algorithms?

A Comparison based sorting algorithms always run in O(n), while non comparison based sorting algorithms run in O(n log n).

B Non comparison based sorting algorithms have a lower bound of O(n log n), while comparison based can achieve O(n).

C Both comparison based and non comparison based sorting algorithms have the same time complexity of O(n^2).

D Comparison based sorting algorithms have a lower bound of O(n log n), while non comparison based can achieve O(n) under certain conditions.

💡 Hint

Think about the theoretical limits of comparison based sorting.

Comparison based sorting algorithms cannot be faster than O(n log n) in the worst case. Non comparison based algorithms like counting sort can run in O(n) if input constraints allow.

🔧 Debug

advanced

Identify the Bug in Non Comparison Based Sorting

The following Go code attempts to implement Radix Sort (a non comparison based sorting) but produces incorrect output. What is the bug?

DSA Go

package main
import (
	"fmt"
)
func countingSortForRadix(arr []int, exp int) []int {
	output := make([]int, len(arr))
	count := make([]int, 10)
	for i := 0; i < len(arr); i++ {
		index := (arr[i] / exp) % 10
		count[index]++
	}
	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}
	for i := len(arr) - 1; i >= 0; i-- {
		index := (arr[i] / exp) % 10
		output[count[index]-1] = arr[i]
		count[index]--
	}
	return output
}
func radixSort(arr []int) []int {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	exp := 1
	for max/exp > 0 {
		arr = countingSortForRadix(arr, exp)
		exp *= 10
	}
	return arr
}
func main() {
	arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
	sortedArr := radixSort(arr)
	fmt.Println(sortedArr)
}

A The output array index is off by one in countingSortForRadix when assigning output[count[index]] = arr[i].

B The count array size should be 256 instead of 10.

C The loop for max/exp should use >= instead of >.

D The input array is not copied before sorting, causing side effects.

💡 Hint

Check how the output array is indexed during placement.

The count array stores cumulative counts, so the correct index to place the element is count[index] - 1, not count[index]. Using count[index] causes an off-by-one error and overwrites data.

🚀 Application

expert

Choosing Sorting Algorithm for Large Dataset

You have a large dataset of 10 million integers ranging from 0 to 1000. Which sorting algorithm is the best choice to sort this data efficiently?

A Use Counting Sort, a non comparison based sorting algorithm with O(n + k) time where k is the range of input.

B Use Merge Sort, a stable comparison based sorting algorithm with O(n log n) time.

C Use Quick Sort, a comparison based sorting algorithm with average O(n log n) time.

D Use Bubble Sort, a simple comparison based sorting algorithm with O(n^2) time.

💡 Hint

Consider the input range and size when choosing the sorting algorithm.

Counting Sort is ideal here because the input range (0 to 1000) is small compared to the number of elements (10 million). It sorts in O(n + k) time, which is efficient for this case.

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