Bird
Raised Fist0
DSA Goprogramming~5 mins

Comparison Based vs Non Comparison Based Sorting in DSA Go - Complexity Comparison

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Comparison Based vs Non Comparison Based Sorting
O(n^2) for comparison based, O(n + k) for non comparison based
Understanding Time Complexity

Sorting is a common task in programming. Different sorting methods have different speeds depending on how they work.

We want to understand how the time taken grows as the list to sort gets bigger.

Scenario Under Consideration

Analyze the time complexity of these two sorting approaches.


// Comparison based sorting example (Bubble Sort)
func bubbleSort(arr []int) {
  n := len(arr)
  for i := 0; i < n-1; i++ {
    for j := 0; j < n-i-1; j++ {
      if arr[j] > arr[j+1] {
        arr[j], arr[j+1] = arr[j+1], arr[j]
      }
    }
  }
}

// Non-comparison based sorting example (Counting Sort)
func countingSort(arr []int, maxVal int) []int {
  count := make([]int, maxVal+1)
  for _, val := range arr {
    count[val]++
  }
  index := 0
  for val, c := range count {
    for c > 0 {
      arr[index] = val
      index++
      c--
    }
  }
  return arr
}

Bubble Sort compares elements to sort, Counting Sort uses counting without direct comparisons.

Identify Repeating Operations

Look at the loops and repeated steps in each method.

  • Bubble Sort primary operation: Comparing and swapping pairs inside nested loops.
  • Bubble Sort how many times: About n x n times (nested loops over array size).
  • Counting Sort primary operation: Counting occurrences and then placing elements back.
  • Counting Sort how many times: Counting loop runs n times, placement loop runs maxVal times.
How Execution Grows With Input

How does the work increase when the list grows?

Input Size (n)Bubble Sort Ops (approx.)Counting Sort Ops (approx.)
10100 (10x10)10 + maxVal
10010,000 (100x100)100 + maxVal
10001,000,000 (1000x1000)1000 + maxVal

Bubble Sort grows much faster as n grows (squares), Counting Sort grows mostly with n plus the range maxVal.

Final Time Complexity

Time Complexity: O(nĀ²) for comparison based (Bubble Sort), O(n + k) for non comparison based (Counting Sort), where k is maxVal.

Bubble Sort gets much slower as list grows; Counting Sort can be faster if maxVal is not too big.

Common Mistake

[X] Wrong: "All sorting methods take about the same time because they all sort the list."

[OK] Correct: Some methods compare elements many times, others use counting and can be faster if conditions are right.

Interview Connect

Knowing how sorting methods differ helps you choose the right tool and explain your choices clearly in interviews.

Self-Check

What if the range of input values (maxVal) is much larger than the number of elements? How would that affect Counting Sort's time complexity?

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard