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.