Why Sorting Matters and How It Unlocks Other Algorithms in DSA Rust - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sorting and Searching in Rust

What is the printed output of this Rust code that sorts a vector and then searches for a value?

DSA Rust

fn main() {
    let mut numbers = vec![10, 3, 5, 8, 2];
    numbers.sort();
    let pos = numbers.binary_search(&5);
    println!("Sorted: {:?}, Position: {:?}", numbers, pos);
}

A Sorted: [2, 3, 5, 8, 10], Position: Err(2)

B Sorted: [10, 8, 5, 3, 2], Position: Ok(2)

C Sorted: [2, 3, 5, 8, 10], Position: Ok(2)

D Sorted: [2, 3, 5, 8, 10], Position: Ok(3)

💡 Hint

Remember that sort() arranges numbers in ascending order and binary_search returns Ok(index) if found.

The vector is sorted ascending: [2, 3, 5, 8, 10]. The number 5 is at index 2, so binary_search returns Ok(2).

🧠 Conceptual

intermediate

Why Sorting Helps in Finding Duplicates

Why is sorting a useful first step when trying to find duplicates in a list?

A Because sorting changes the values to unique identifiers.

B Because sorting groups equal elements together, making duplicates easy to spot by checking neighbors.

C Because sorting removes duplicates automatically.

D Because sorting reverses the list, which helps find duplicates.

💡 Hint

Think about how duplicates appear after sorting.

Sorting places equal elements next to each other, so duplicates appear as neighbors and can be found by simple adjacent comparisons.

🔧 Debug

advanced

Why Does This Merge Sort Code Fail?

This Rust code tries to merge two sorted slices but produces wrong output. What is the bug?

DSA Rust

fn merge(left: &[i32], right: &[i32]) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    while i < left.len() {
        result.push(left[i]);
        i += 1;
    }
    while j < right.len() {
        result.push(right[j]);
        j += 1;
    }
    result
}

A The indices i and j should start at 1, not 0.

B The comparison should be <= instead of < in the first while loop.

C The function should return a slice, not a Vec.

D The conditions in the last two while loops should be < not <= to avoid out-of-bounds access.

💡 Hint

Check the loop conditions when accessing array elements by index.

Using <= causes the code to access one index beyond the slice length, causing a runtime panic. Changing to < fixes this.

🚀 Application

advanced

Using Sorting to Find the Median

Given an unsorted list of numbers, which approach correctly finds the median using sorting?

A Sort the list, then pick the middle element if odd length, or average the two middle elements if even length.

B Sort the list, then pick the first element as the median.

C Sort the list, then pick the last element as the median.

D Sort the list, then sum all elements and divide by the length.

💡 Hint

Median is the middle value after sorting.

Median is the center value in sorted order. For odd length, it's the middle element. For even length, it's the average of the two middle elements.

❓ Predict Output

expert

Output of Sorting Custom Structs with PartialOrd

What is the output of this Rust code that sorts a vector of custom structs by their 'value' field?

DSA Rust

use std::cmp::Ordering;

#[derive(Debug)]
struct Item {
    name: &'static str,
    value: i32,
}

impl PartialEq for Item {
    fn eq(&self, other: &Self) -> bool {
        self.value == other.value
    }
}

impl Eq for Item {}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.value.cmp(&other.value))
    }
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.value.cmp(&other.value)
    }
}

fn main() {
    let mut items = vec![
        Item { name: "apple", value: 5 },
        Item { name: "banana", value: 2 },
        Item { name: "cherry", value: 7 },
    ];
    items.sort();
    for item in items {
        println!("{}:{}", item.name, item.value);
    }
}

A

banana:2
apple:5
cherry:7

B

banana:2
cherry:7
apple:5

C

cherry:7
apple:5
banana:2

D

apple:5
banana:2
cherry:7

💡 Hint

Sorting uses the 'value' field ascending order.

The items are sorted by value ascending: banana(2), apple(5), cherry(7). The print shows name:value per line.

Practice

1. Why is sorting an important step before applying many algorithms in data processing?

easy

A. It removes duplicate data automatically

B. It encrypts data for security

C. It organizes data to make searching and comparisons faster

D. It compresses data to save space

Solution

1. Step 1: Understand sorting's role in data organization

   Sorting arranges data in order, which helps algorithms work efficiently by reducing complexity.

2. Step 2: Connect sorting to faster searching and comparisons

   When data is sorted, algorithms like binary search can quickly find elements, improving speed.

3. Final Answer:

   It organizes data to make searching and comparisons faster -> Option C

4. Quick Check:

   Sorting improves search speed = B [OK]

Hint: Sorting arranges data to speed up searches and comparisons [OK]

Common Mistakes:

• Thinking sorting removes duplicates automatically
• Confusing sorting with encryption or compression

2. Which of the following is the correct Rust syntax to sort a mutable vector nums in ascending order?

easy

A. nums.sort();

B. nums.sorted();

C. sort(nums);

D. nums.sort_by_desc();

Solution

1. Step 1: Identify Rust's method to sort vectors

   Rust's standard library provides the sort() method for mutable vectors to sort in ascending order.

2. Step 2: Check each option's correctness

   nums.sort(); uses nums.sort(); which is correct. nums.sorted(); uses a non-existent method sorted(). sort(nums); is a function call not valid in Rust. nums.sort_by_desc(); sorts descending, which is not asked.

3. Final Answer:

   nums.sort(); -> Option A

4. Quick Check:

   Rust vector sort method = A [OK]

Hint: Use vec.sort() to sort mutable vectors ascending [OK]

Common Mistakes:

• Using non-existent methods like sorted()
• Trying to call sort as a free function
• Confusing ascending and descending sort methods

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

let mut nums = vec![3, 1, 4, 1, 5];
nums.sort();
println!("{:?}", nums);

medium

A. Compilation error

B. [5, 4, 3, 1, 1]

C. [3, 1, 4, 1, 5]

D. [1, 1, 3, 4, 5]

Solution

1. Step 1: Understand the initial vector and sorting

   The vector nums starts as [3, 1, 4, 1, 5]. Calling nums.sort() sorts it in ascending order.

2. Step 2: Determine the sorted vector

   Sorting gives [1, 1, 3, 4, 5]. The print statement outputs this vector.

3. Final Answer:

   [1, 1, 3, 4, 5] -> Option D

4. Quick Check:

   Sorted vector output = A [OK]

Hint: Sorting arranges numbers from smallest to largest [OK]

Common Mistakes:

• Confusing ascending with descending order
• Expecting original order after sort
• Thinking sort causes compile errors

4. The following Rust code tries to sort a vector but causes a compilation error. What is the error and how to fix it?

let nums = vec![2, 3, 1];
nums.sort();

medium

A. Error: Missing semicolon; fix by adding semicolon after vector declaration

B. Error: Cannot borrow immutable variable as mutable; fix by declaring nums as mutable

C. Error: sort() method does not exist for vectors; fix by importing a crate

D. No error; code runs fine

Solution

1. Step 1: Identify the variable mutability

   The vector nums is declared immutable with let. The sort() method requires a mutable reference.

2. Step 2: Fix by making the vector mutable

   Change declaration to let mut nums = vec![2, 3, 1]; to allow sorting.

3. Final Answer:

   Error: Cannot borrow immutable variable as mutable; fix by declaring nums as mutable -> Option B

4. Quick Check:

   Mutable vector needed for sort() = C [OK]

Hint: Declare vector mutable with mut before sorting [OK]

Common Mistakes:

• Trying to sort immutable vectors
• Thinking sort() needs external crates
• Ignoring Rust's mutability rules

5. You have a list of student scores: vec![88, 95, 70, 100, 85]. You want to find the median score efficiently. Which approach best uses sorting to unlock this algorithm?

hard

A. Sort the scores and pick the middle element after sorting

B. Sum all scores and divide by the number of scores

C. Find the maximum and minimum scores and average them

D. Shuffle the scores randomly and pick any element

Solution

1. Step 1: Understand median calculation

   The median is the middle value in a sorted list, so sorting is necessary to find it correctly.

2. Step 2: Apply sorting to find the median

   Sort the vector to get [70, 85, 88, 95, 100]. The middle element (3rd) is 88, the median.

3. Final Answer:

   Sort the scores and pick the middle element after sorting -> Option A

4. Quick Check:

   Median requires sorted data = D [OK]

Hint: Sort first, then pick middle for median [OK]

Common Mistakes:

• Using average instead of median
• Ignoring sorting before median calculation
• Picking random elements without sorting