Sorting Stability and When to Use Which Sort in DSA Rust - Build from Scratch

Sorting Stability and When to Use Which Sort

📖 Scenario: You work in a small library. You have a list of books with their titles and publication years. You want to sort the books by year but keep the order of books with the same year as they were originally. This is called a stable sort.Later, you want to sort the books by title alphabetically, where stability is not important.

🎯 Goal: You will create a list of books, then sort them by year using a stable sort, and then sort them by title using an unstable sort. You will see how stable sorting keeps the original order for books with the same year.

📋 What You'll Learn

Create a list of books with exact titles and years

Create a variable to hold the sorted list

Use a stable sort to sort books by year

Use an unstable sort to sort books by title

Print the list after each sort showing title and year

💡 Why This Matters

🌍 Real World

Sorting lists of items like books, products, or records where order matters for duplicates.

💼 Career

Understanding sorting stability helps in data processing, UI display, and database query optimization.

1

Create the list of books

Create a variable called books as a vector of tuples with these exact entries: ("The Hobbit", 1937), ("1984", 1949), ("Animal Farm", 1945), ("Brave New World", 1932), ("Fahrenheit 451", 1953), ("The Catcher in the Rye", 1951), ("Lord of the Flies", 1954), ("The Great Gatsby", 1925), ("To Kill a Mockingbird", 1960), ("The Hobbit", 1937) (note the duplicate title with same year).

DSA Rust

# Create the books vector with exact tuples
# Your code here

Hint

Use let mut books = vec![ ... ]; with tuples inside the vector.

2

Create a variable for the stable sorted list by year

Create a variable called stable_sorted_books and set it to a clone of books.

DSA Rust

fn main() {
    let mut books = vec![
        ("The Hobbit", 1937),
        ("1984", 1949),
        ("Animal Farm", 1945),
        ("Brave New World", 1932),
        ("Fahrenheit 451", 1953),
        ("The Catcher in the Rye", 1951),
        ("Lord of the Flies", 1954),
        ("The Great Gatsby", 1925),
        ("To Kill a Mockingbird", 1960),
        ("The Hobbit", 1937),
    ];
    // Clone books into stable_sorted_books
    // Your code here
}

Hint

Use let mut stable_sorted_books = books.clone(); to copy the list.

3

Sort the books by year using a stable sort

Use stable_sorted_books.sort_by_key(|book| book.1) to sort the books by year in a stable way.

DSA Rust

fn main() {
    let mut books = vec![
        ("The Hobbit", 1937),
        ("1984", 1949),
        ("Animal Farm", 1945),
        ("Brave New World", 1932),
        ("Fahrenheit 451", 1953),
        ("The Catcher in the Rye", 1951),
        ("Lord of the Flies", 1954),
        ("The Great Gatsby", 1925),
        ("To Kill a Mockingbird", 1960),
        ("The Hobbit", 1937),
    ];
    let mut stable_sorted_books = books.clone();
    // Sort stable_sorted_books by year using stable sort
    // Your code here
}

Hint

Use sort_by_key on stable_sorted_books with the year as key.

4

Sort the original books by title using an unstable sort and print both lists

Use books.sort_unstable_by_key(|book| book.0) to sort the original books by title. Then print stable_sorted_books and books with a loop showing title and year.

DSA Rust

fn main() {
    let mut books = vec![
        ("The Hobbit", 1937),
        ("1984", 1949),
        ("Animal Farm", 1945),
        ("Brave New World", 1932),
        ("Fahrenheit 451", 1953),
        ("The Catcher in the Rye", 1951),
        ("Lord of the Flies", 1954),
        ("The Great Gatsby", 1925),
        ("To Kill a Mockingbird", 1960),
        ("The Hobbit", 1937),
    ];
    let mut stable_sorted_books = books.clone();
    stable_sorted_books.sort_by_key(|book| book.1);
    // Sort books by title using unstable sort
    // Print stable_sorted_books and books
    // Your code here
}

Hint

Use sort_unstable_by_key on books with title as key. Then print both lists with loops.

Practice

1. What does it mean when a sorting algorithm is stable?

easy

A. It uses less memory than unstable sorts

B. It sorts elements in ascending order only

C. It always runs faster than unstable sorts

D. It keeps the original order of equal elements unchanged

Solution

1. Step 1: Understand stability in sorting

   A stable sort means if two elements are equal, their order stays the same as before sorting.

2. Step 2: Compare options with definition

   Only It keeps the original order of equal elements unchanged matches this meaning. Other options describe unrelated properties.

3. Final Answer:

   It keeps the original order of equal elements unchanged -> Option D

4. Quick Check:

   Stable sort = keeps equal elements order [OK]

Hint: Stable means equal items keep their order [OK]

Common Mistakes:

• Confusing stability with sorting order
• Thinking stability means faster sorting
• Assuming stability means less memory use

2. Which Rust standard library method sorts a slice with a stable sort without requiring a comparator closure?

easy

A. slice.sort_unstable_by()

B. slice.sort_unstable()

C. slice.sort()

D. slice.sort_by()

Solution

1. Step 1: Recall Rust slice sorting methods

   Rust's slice.sort() uses a stable sorting algorithm.

2. Step 2: Differentiate stable and unstable methods

   sort_unstable() and sort_unstable_by() are unstable sorts. sort_by() is stable but requires a comparator.

3. Final Answer:

   slice.sort() -> Option C

4. Quick Check:

   slice.sort() = stable sort [OK]

Hint: Use sort() for stable sorting in Rust [OK]

Common Mistakes:

• Choosing sort_unstable() thinking it's stable
• Confusing sort_by() with unstable sort
• Not knowing sort() is stable by default

3. Given the Rust code below, what is the output?

let mut data = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd')];
data.sort();
println!("{:?}", data);

medium

A. [(1, 'b'), (2, 'd'), (3, 'a'), (3, 'c')]

B. [(1, 'b'), (2, 'd'), (3, 'c'), (3, 'a')]

C. [(3, 'a'), (3, 'c'), (2, 'd'), (1, 'b')]

D. [(2, 'd'), (1, 'b'), (3, 'a'), (3, 'c')]

Solution

1. Step 1: Understand sorting of tuples in Rust

   Rust sorts tuples by first element, then second if first are equal. Here, sorting by integer first.

2. Step 2: Apply stable sort to keep order of equal keys

   Elements with key 3 are (3, 'a') then (3, 'c'). Stable sort keeps this order.

3. Final Answer:

   [(1, 'b'), (2, 'd'), (3, 'a'), (3, 'c')] -> Option A

4. Quick Check:

   Stable sort keeps (3, 'a') before (3, 'c') [OK]

Hint: Stable sort keeps equal keys in original order [OK]

Common Mistakes:

• Swapping order of equal keys
• Ignoring tuple sorting rules
• Assuming unstable sort by default

4. The following Rust code uses sort_unstable() but the order of equal elements is important. What is the main issue?

let mut items = [(2, 'x'), (1, 'y'), (2, 'z')];
items.sort_unstable();
println!("{:?}", items);

medium

A. The code will not compile because sort_unstable() requires a comparator

B. The order of (2, 'x') and (2, 'z') may change, breaking stability

C. The code will panic at runtime due to unstable sort

D. The output will always be sorted and stable

Solution

1. Step 1: Understand sort_unstable() behavior

   sort_unstable() sorts faster but does not guarantee stable order of equal elements.

2. Step 2: Identify problem with equal keys

   Elements with key 2 may swap order, so (2, 'x') and (2, 'z') order can change, which breaks stability.

3. Final Answer:

   The order of (2, 'x') and (2, 'z') may change, breaking stability -> Option B

4. Quick Check:

   Unstable sort = order of equal keys can change [OK]

Hint: Unstable sort can reorder equal elements [OK]

Common Mistakes:

• Thinking unstable sort always panics
• Assuming unstable sort requires comparator
• Believing unstable sort keeps order

5. You have a list of student records with fields (score: i32, name: &str). You want to sort by score ascending but keep the original order of students with the same score. Which sorting method should you use in Rust and why?

hard

A. Use sort() because it is stable and preserves order of equal scores

B. Use sort_unstable() because it is faster and order doesn't matter

C. Use sort_unstable_by() with a custom comparator for stability

D. Use sort_by() but it is unstable so order may change

Solution

1. Step 1: Identify requirement for stability

   We want to keep original order of students with same score, so stable sort is needed.

2. Step 2: Choose Rust method that is stable

   sort() is stable and sorts ascending by default. sort_unstable() is faster but unstable. sort_unstable_by() is unstable even with comparator. sort_by() is stable but Use sort_by() but it is unstable so order may change claims it is unstable incorrectly.

3. Final Answer:

   Use sort() because it is stable and preserves order of equal scores -> Option A

4. Quick Check:

   Stable sort needed = use sort() [OK]

Hint: Stable sort keeps order of equal keys; use sort() [OK]

Common Mistakes:

• Choosing unstable sort for speed ignoring order
• Thinking sort_unstable_by() is stable
• Misunderstanding sort_by() stability