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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Comparison Based Sorting (Rust)

What is the output of this Rust code that uses a comparison based sorting method?

DSA Rust

fn main() {
    let mut arr = [5, 3, 8, 1, 2];
    arr.sort();
    println!("{:?}", arr);
}

A [1, 2, 3, 5, 8]

B [5, 3, 8, 1, 2]

C [8, 5, 3, 2, 1]

D [1, 3, 2, 5, 8]

💡 Hint

Think about what the sort() method does to the array.

The sort() method in Rust sorts the array in ascending order using comparison based sorting algorithms like Timsort or Introsort.

❓ Predict Output

intermediate

Output of Non Comparison Based Sorting (Counting Sort)

What is the output of this Rust code that implements a simple counting sort for small positive integers?

DSA Rust

fn counting_sort(arr: &mut [usize]) {
    let max = *arr.iter().max().unwrap();
    let mut count = vec![0; max + 1];
    for &num in arr.iter() {
        count[num] += 1;
    }
    let mut i = 0;
    for num in 0..=max {
        for _ in 0..count[num] {
            arr[i] = num;
            i += 1;
        }
    }
}

fn main() {
    let mut arr = [4, 2, 2, 8, 3, 3, 1];
    counting_sort(&mut arr);
    println!("{:?}", arr);
}

A [1, 3, 2, 4, 8, 3, 2]

B [8, 4, 3, 3, 2, 2, 1]

C [1, 2, 2, 3, 3, 4, 8]

D [4, 2, 2, 8, 3, 3, 1]

💡 Hint

Counting sort counts occurrences and rebuilds the array in order.

Counting sort counts how many times each number appears and then writes them back in sorted order.

🧠 Conceptual

advanced

Key Difference Between Comparison Based and Non Comparison Based Sorting

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

A Comparison based sorting requires extra memory, non comparison based sorting never does.

B Comparison based sorting always runs faster than non comparison based sorting for large data.

C Non comparison based sorting can only sort strings, not numbers.

D Comparison based sorting uses element comparisons to decide order; non comparison based sorting uses other properties like counting or digit positions.

💡 Hint

Think about how each type decides the order of elements.

Comparison based sorting compares elements directly; non comparison based sorting uses techniques like counting or grouping by digits without direct comparisons.

❓ Predict Output

advanced

Output of Radix Sort (Non Comparison Based)

What is the output of this Rust code implementing a simplified radix sort for positive integers?

DSA Rust

fn counting_sort_for_radix(arr: &mut [u32], exp: u32) {
    let n = arr.len();
    let mut output = vec![0; n];
    let mut count = vec![0; 10];

    for &num in arr.iter() {
        let index = ((num / exp) % 10) as usize;
        count[index] += 1;
    }

    for i in 1..10 {
        count[i] += count[i - 1];
    }

    for &num in arr.iter().rev() {
        let index = ((num / exp) % 10) as usize;
        output[count[index] - 1] = num;
        count[index] -= 1;
    }

    for i in 0..n {
        arr[i] = output[i];
    }
}

fn radix_sort(arr: &mut [u32]) {
    let max = *arr.iter().max().unwrap();
    let mut exp = 1;
    while max / exp > 0 {
        counting_sort_for_radix(arr, exp);
        exp *= 10;
    }
}

fn main() {
    let mut arr = [170, 45, 75, 90, 802, 24, 2, 66];
    radix_sort(&mut arr);
    println!("{:?}", arr);
}

A [802, 170, 90, 75, 66, 45, 24, 2]

B [2, 24, 45, 66, 75, 90, 170, 802]

C [170, 45, 75, 90, 802, 24, 2, 66]

D [2, 24, 45, 75, 66, 90, 170, 802]

💡 Hint

Radix sort sorts numbers digit by digit from least significant to most significant.

Radix sort uses counting sort on each digit place, resulting in a fully sorted array in ascending order.

🧠 Conceptual

expert

Time Complexity Limits of Comparison Based Sorting

Which statement correctly describes the theoretical time complexity limit for comparison based sorting algorithms?

A Comparison based sorting algorithms cannot have better than O(n log n) average time complexity.

B Comparison based sorting algorithms have no theoretical time complexity limits.

C Comparison based sorting algorithms always run in O(n^2) time.

D Comparison based sorting algorithms can achieve O(n) average time complexity for any input.

💡 Hint

Think about the decision tree model for comparisons.

The lower bound for comparison based sorting is O(n log n) due to the number of comparisons needed to order n elements.

Practice

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

easy

A. Heap Sort

B. Merge Sort

C. Quick Sort

D. Counting 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 element values directly to sort without comparing elements.

3. Final Answer:

   Counting Sort -> Option D

4. Quick Check:

   Non-comparison based = Counting Sort [OK]

Hint: Non-comparison sorts use element values, not comparisons [OK]

Common Mistakes:

• Confusing Merge Sort as non-comparison
• Thinking Quick Sort is non-comparison
• Assuming Heap Sort is non-comparison

2. Which of the following is the correct Rust syntax to call a non-comparison based sorting function counting_sort on a mutable vector arr?

easy

A. counting_sort(&mut arr);

B. counting_sort(arr);

C. counting_sort(&arr);

D. counting_sort(mut arr);

Solution

1. Step 1: Understand Rust borrowing rules for mutable vectors

   To modify a vector inside a function, we pass a mutable reference using &mut.

2. Step 2: Identify correct function call syntax

   Calling counting_sort(&mut arr); passes a mutable reference correctly.

3. Final Answer:

   counting_sort(&mut arr); -> Option A

4. Quick Check:

   Mutable reference call = counting_sort(&mut arr); [OK]

Hint: Use &mut to pass mutable vector to sorting function [OK]

Common Mistakes:

• Passing vector without reference
• Passing immutable reference &arr
• Using invalid syntax like mut arr

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

let mut arr = vec![4, 2, 2, 8, 3, 3, 1];
counting_sort(&mut arr);
println!("{:?}", arr);

Assuming counting_sort correctly sorts the vector in ascending order.

medium

A. [1, 2, 3, 4, 8]

B. [1, 2, 2, 3, 3, 4, 8]

C. [8, 4, 3, 3, 2, 2, 1]

D. [4, 2, 2, 8, 3, 3, 1]

Solution

1. Step 1: Understand counting sort behavior

   Counting sort sorts elements in ascending order, preserving duplicates.

2. Step 2: Sort the given vector

   Sorted vector is [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option B

4. Quick Check:

   Sorted ascending = [1, 2, 2, 3, 3, 4, 8] [OK]

Hint: Counting sort outputs sorted ascending with duplicates intact [OK]

Common Mistakes:

• Reversing order to descending
• Removing duplicates incorrectly
• Printing original unsorted array

4. The following Rust code attempts to sort a vector using counting sort but causes a compilation error. What is the error?

fn counting_sort(arr: Vec<i32>) {
    // sorting logic
}

fn main() {
    let mut data = vec![3, 1, 4];
    counting_sort(data);
    println!("{:?}", data);
}

medium

A. Missing mutable keyword for data

B. counting_sort function missing return type

C. Cannot print data after move error

D. Syntax error in println! macro

Solution

1. Step 1: Identify ownership move in function call

   Passing data by value moves ownership to counting_sort.

2. Step 2: Understand why println! causes error

   After move, data is invalid in main, so printing causes compilation error.

3. Final Answer:

   Cannot print data after move error -> Option C

4. Quick Check:

   Ownership moved, data invalid after call [OK]

Hint: Passing vector by value moves ownership, invalid after call [OK]

Common Mistakes:

• Assuming mutable keyword fixes ownership move
• Thinking missing return type causes error
• Blaming println! syntax

5. You have a large dataset of integers ranging from 0 to 1000. Which sorting approach is more efficient and why?

hard

A. Counting Sort is best due to O(n + k) time with small range

B. Quick Sort is best due to average O(n log n) time

C. Bubble Sort is best for simplicity

D. Merge Sort is best for stable sorting

Solution

1. Step 1: Analyze dataset characteristics

   Dataset has integers in range 0 to 1000, so k=1001 is small compared to n.

2. Step 2: Compare sorting algorithm complexities

   Counting Sort runs in O(n + k), which is efficient for small k. Quick, Merge are O(n log n). Bubble Sort is slow O(n²).

3. Step 3: Choose best approach

   Counting Sort is more efficient here due to linear time with small range.

4. Final Answer:

   Counting Sort is best due to O(n + k) time with small range -> Option A

5. Quick Check:

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

Hint: Small range data? Use Counting Sort for linear time [OK]

Common Mistakes:

• Choosing Quick Sort ignoring range advantage
• Picking Bubble Sort for large data
• Ignoring Counting Sort's linear time benefit