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

Sorting Stability and When to Use Which Sort

📖 Scenario: You work in a small bookstore. You have a list of books with their titles and prices. You want to sort the books by price but keep the original order for books with the same price. This helps you keep the order in which books arrived when prices are equal.

🎯 Goal: Learn how to sort a list of books by price while keeping the order stable for books with the same price. Understand when to use stable sorting methods.

📋 What You'll Learn

Create a list of books with exact titles and prices

Create a variable to hold the sorting key

Sort the list of books by price using a stable sort

Print the sorted list showing title and price

💡 Why This Matters

🌍 Real World

Sorting products, books, or any items by price or other attributes while keeping the original order for equal values is common in stores, websites, and apps.

💼 Career

Understanding stable sorting helps in data processing, UI display, and backend systems where order matters for equal keys.

1

Create the list of books

Create a list called books with these exact dictionaries in this order: {'title': 'Book A', 'price': 20}, {'title': 'Book B', 'price': 10}, {'title': 'Book C', 'price': 20}, {'title': 'Book D', 'price': 15}

DSA Python

# Create the list called books with the exact dictionaries
# Your code here

Hint

Use a list of dictionaries. Each dictionary has keys 'title' and 'price'.

2

Create the sorting key variable

Create a variable called sort_key that is a function to get the 'price' from each book dictionary

DSA Python

books = [
    {'title': 'Book A', 'price': 20},
    {'title': 'Book B', 'price': 10},
    {'title': 'Book C', 'price': 20},
    {'title': 'Book D', 'price': 15}
]
# Create sort_key to get price from each book
# Your code here

Hint

Use a lambda function that takes one book and returns its price.

3

Sort the books by price using stable sort

Use the sort() method on books with the key=sort_key argument to sort the list by price while keeping the original order for books with the same price

DSA Python

books = [
    {'title': 'Book A', 'price': 20},
    {'title': 'Book B', 'price': 10},
    {'title': 'Book C', 'price': 20},
    {'title': 'Book D', 'price': 15}
]
sort_key = lambda book: book['price']
# Sort books by price using sort() with key=sort_key
# Your code here

Hint

Use the list's sort() method with the key parameter set to sort_key.

4

Print the sorted list of books

Use a for loop with variables book to iterate over books and print each book's title and price in the format Title: Book Title, Price: PriceValue

DSA Python

books = [
    {'title': 'Book A', 'price': 20},
    {'title': 'Book B', 'price': 10},
    {'title': 'Book C', 'price': 20},
    {'title': 'Book D', 'price': 15}
]
sort_key = lambda book: book['price']
books.sort(key=sort_key)
# Print each book's title and price
# Your code here

Hint

Use a for loop to print each book's title and price exactly as shown.

Practice

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

easy

A. It keeps the original order of equal elements unchanged.

B. It sorts the elements in ascending order only.

C. It uses less memory than unstable sorts.

D. It always sorts in place without extra space.

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps elements with the same value in the same order as they appeared originally.

2. Step 2: Compare options with definition

   Only It keeps the original order of equal elements unchanged. describes this property correctly. Other options describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Stable sort = keeps order of equal elements [OK]

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

Common Mistakes:

• Confusing stability with sorting order
• Thinking stability means less memory use
• Assuming all sorts are stable

2. Which of the following Python sorting methods is stable by default?

easy

A. sorted() function

B. list.sort() method

C. Neither sorted() nor list.sort()

D. Both sorted() and list.sort()

Solution

1. Step 1: Recall Python sorting stability

   Both sorted() and list.sort() use Timsort, which is stable.

2. Step 2: Check options

   Options A and B are each correct alone, but Both sorted() and list.sort() correctly states both are stable.

3. Final Answer:

   Both sorted() and list.sort() -> Option D

4. Quick Check:

   Python sorts are stable by default [OK]

Hint: Python's built-in sorts are stable by default [OK]

Common Mistakes:

• Thinking only one method is stable
• Confusing stability with sorting order
• Assuming custom sorts are stable by default

3. Consider this list of tuples representing (name, score):

data = [("Alice", 90), ("Bob", 90), ("Charlie", 85)]

What will be the output after sorting by score using sorted(data, key=lambda x: x[1])?

medium

A. [('Charlie', 85), ('Bob', 90), ('Alice', 90)]

B. [('Alice', 90), ('Bob', 90), ('Charlie', 85)]

C. [('Charlie', 85), ('Alice', 90), ('Bob', 90)]

D. [('Bob', 90), ('Alice', 90), ('Charlie', 85)]

Solution

1. Step 1: Understand sorting by score

   The sort uses the second item (score) as key, sorting ascending: 85, 90, 90.

2. Step 2: Check stability for equal scores

   Since Python's sort is stable, 'Alice' and 'Bob' keep their original order for score 90.

3. Final Answer:

   [('Charlie', 85), ('Alice', 90), ('Bob', 90)] -> Option C

4. Quick Check:

   Stable sort keeps 'Alice' before 'Bob' [OK]

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

Common Mistakes:

• Swapping order of equal elements
• Sorting descending by mistake
• Ignoring stability property

4. You wrote this code to sort a list of dictionaries by 'age':

people = [{'name': 'Ann', 'age': 25}, {'name': 'Ben', 'age': 20}, {'name': 'Cara', 'age': 25}]
people.sort(key=lambda x: x['age'])
print(people)

But the output does not keep the original order of people with the same age. What is the likely cause?

medium

A. The key function is incorrect.

B. The dictionaries are unordered, causing instability.

C. The list.sort() method is stable, so no cause.

D. The sort method used is unstable.

Solution

1. Step 1: Recall Python sort stability

   Python's list.sort() is stable, so it keeps order of equal keys.

2. Step 2: Understand dictionary order

   Before Python 3.7, dictionaries did not preserve insertion order, so printing may show different order.

3. Step 3: Identify cause

   If using older Python or unordered dicts, the printed order may seem unstable even if sort is stable.

4. Final Answer:

   The dictionaries are unordered, causing instability. -> Option B

5. Quick Check:

   Unordered dicts can hide stable sort [OK]

Hint: Unordered dicts can hide stable sort effects [OK]

Common Mistakes:

• Blaming sort method instead of dict order
• Changing key function unnecessarily
• Ignoring Python version differences

5. You have a list of student records with (name, grade, age). You want to sort by grade ascending, then by age descending, but keep the original order for students with same grade and age. Which sorting approach is best?

hard

A. Use a stable sort twice: first by age descending, then by grade ascending.

B. Use an unstable sort once with a combined key (grade, -age).

C. Use a stable sort once with key (grade, age).

D. Sort by age ascending, then by grade descending using stable sorts.

Solution

1. Step 1: Understand multi-level sorting with stability

   To sort by multiple keys and keep original order for ties, use stable sorts starting from the last key.

2. Step 2: Apply sorting order

   First sort by age descending (second key), then by grade ascending (first key), both stable.

3. Step 3: Check options

   Use a stable sort twice: first by age descending, then by grade ascending. matches this approach. Others either use unstable sort or wrong key order.

4. Final Answer:

   Use a stable sort twice: first by age descending, then by grade ascending. -> Option A

5. Quick Check:

   Stable sorts chained preserve multi-key order [OK]

Hint: Sort by last key first with stable sort, then first key [OK]

Common Mistakes:

• Sorting keys in wrong order
• Using unstable sort for multi-key sorting
• Ignoring descending order for age