Comparison Based vs Non Comparison Based Sorting in DSA Go - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a comparison-based sort using Go's built-in function.

DSA Go

import "sort"

func sortNumbers(nums []int) {
    sort.[1](nums)
}

Drag options to blanks, or click blank then click option'

AInts

Bsort

CSort

DSortNumbers

Attempts:

3 left

💡 Hint

Common Mistakes

Using lowercase 'sort' which is the package name, not a function.

Using 'Sort' which is not a valid function in the sort package.

The correct function to sort a slice of ints in Go is sort.Ints.

2fill in blank

medium

Complete the code to implement counting sort, a non-comparison based sorting algorithm.

DSA Go

func countingSort(arr []int, maxVal int) []int {
    count := make([]int, maxVal+1)
    for _, num := range arr {
        count[[1]]++
    }
    // rest of the code omitted
    return nil
}

Drag options to blanks, or click blank then click option'

Anum

Barr

Ccount

DmaxVal

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole array 'arr' as an index.

Using 'maxVal' or 'count' as an index which are not correct.

We increment the count for each number in the input array, so num is the correct index.

3fill in blank

hard

Fix the error in the code that attempts to compare two integers for sorting.

DSA Go

func compare(a, b int) bool {
    return a [1] b
}

Drag options to blanks, or click blank then click option'

A==

B>

C=

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' which is assignment, not comparison.

Using '==' which checks equality, not order.

For sorting in descending order, the comparison should be a > b.

4fill in blank

hard

Fill both blanks to complete the code that builds a frequency map for radix sort.

DSA Go

func buildFrequency(arr []int, digit int) map[int]int {
    freq := make(map[int]int)
    for _, num := range arr {
        d := (num / [1]) % [2]
        freq[d]++
    }
    return freq
}

Drag options to blanks, or click blank then click option'

Adigit

B10

Cnum

Darr

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'num' or 'arr' as divisor which are incorrect.

Using a number other than 10 for the modulus in base 10.

To extract the digit at a certain place, divide by digit and mod by 10.

5fill in blank

hard

Complete the code to complete the code that creates a map of word lengths filtered by length condition.

DSA Go

func filterWords(words []string) map[int]int {
    result := make(map[int]int)
    for _, word := range words {
        if len(word) [1] 3 {
            result[[len(word)]]++
        }
    }
    return result
}

Drag options to blanks, or click blank then click option'

A>

B<=

C[

D]

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' which filters shorter or equal lengths.

Using parentheses instead of brackets for indexing.

The condition filters lengths greater than 3, and the map key uses brackets to index the length for frequency count.

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