Comparison Based vs Non Comparison Based Sorting in DSA Rust - Build Both Approaches

Comparison Based vs Non Comparison Based Sorting

📖 Scenario: You work in a warehouse where you need to organize boxes by their weight. Some boxes have weights that can be compared directly, while others have weights represented as categories. You want to learn two ways to sort these boxes: by comparing weights directly and by using a counting method for categories.

🎯 Goal: Build two sorting methods in Rust: one that sorts a list of numbers by comparing them, and another that sorts a list of categories using counting. Then print the sorted results.

📋 What You'll Learn

Create a vector called weights with the numbers 40, 10, 50, 20, 30

Create a vector called categories with the strings "small", "large", "medium", "small", "large"

Sort the weights vector using comparison-based sorting

Sort the categories vector using counting sort logic

Print both sorted vectors

💡 Why This Matters

🌍 Real World

Sorting is used everywhere, like organizing boxes by weight or grouping items by category in warehouses or stores.

💼 Career

Understanding different sorting methods helps in choosing the best approach for data processing tasks in software development and data analysis.

1

Create the initial data vectors

Create a vector called weights with the numbers 40, 10, 50, 20, 30 and a vector called categories with the strings "small", "large", "medium", "small", "large".

DSA Rust

# Create the vectors weights and categories
# Your code here

Hint

Use vec![...] to create vectors with exact values.

2

Prepare a count map for categories

Create a mutable HashMap called count_map to count how many times each category appears in categories. Use std::collections::HashMap.

DSA Rust

fn main() {
    let mut weights = vec![40, 10, 50, 20, 30];
    let categories = vec!["small", "large", "medium", "small", "large"];

    // Create count_map HashMap
    // Your code here
}

Hint

Import HashMap and create it with HashMap::new().

3

Sort weights and count categories

Sort the weights vector using weights.sort(). Then use a for loop with variable category to iterate over categories.iter() and update count_map by increasing the count for each category.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut weights = vec![40, 10, 50, 20, 30];
    let categories = vec!["small", "large", "medium", "small", "large"];

    let mut count_map: HashMap = HashMap::new();

    // Sort weights and count categories
    // Your code here
}

Hint

Use weights.sort() to sort numbers. Use for category in categories.iter() to loop. Use count_map.entry(category).or_insert(0) to count.

4

Print the sorted weights and sorted categories

Print the sorted weights vector using println!("Sorted weights: {:?}", weights). Then create a new vector sorted_categories by repeating each category from ["small", "medium", "large"] according to its count in count_map. Finally, print sorted_categories using println!("Sorted categories: {:?}", sorted_categories).

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut weights = vec![40, 10, 50, 20, 30];
    let categories = vec!["small", "large", "medium", "small", "large"];

    let mut count_map: HashMap = HashMap::new();

    weights.sort();

    for category in categories.iter() {
        let counter = count_map.entry(category).or_insert(0);
        *counter += 1;
    }

    // Print sorted weights and sorted categories
    // Your code here
}

Hint

Print the sorted weights vector. Then build sorted_categories by repeating each category by its count. Print sorted_categories.

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