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

Sorting Stability and When to Use Which Sort

📖 Scenario: You work at a bookstore that keeps a list of books with their titles and prices. Sometimes, books have the same price. You want to sort the books by price but keep the order of books with the same price as they were originally. This is called a stable sort.Later, you want to understand when to use different sorting methods based on speed and stability.

🎯 Goal: You will create a list of books, add a sorting preference, sort the books by price using a stable sort, and then print the sorted list showing how stable sorting keeps the original order for books with the same price.

📋 What You'll Learn

Create an array of book objects with exact titles and prices

Add a variable to choose sorting method

Use a stable sorting method to sort books by price

Print the sorted list showing title and price

💡 Why This Matters

🌍 Real World

Sorting lists of products, books, or any items by price or other attributes is common in online stores and inventory systems. Stable sorting helps keep the original order when items have the same key, which can be important for user experience.

💼 Career

Understanding sorting stability and when to use stable or unstable sorts is important for software developers working on data processing, UI lists, and performance optimization.

1

Create the list of books

Create an array called books with these exact objects in this order: { title: 'Book A', price: 30 }, { title: 'Book B', price: 20 }, { title: 'Book C', price: 30 }, { title: 'Book D', price: 10 }

DSA Javascript

// Create the array books with the given book objects
// Your code here

Hint

Use const books = [ ... ] with objects inside curly braces.

2

Add sorting method choice

Create a variable called useStableSort and set it to true to choose stable sorting

DSA Javascript

const books = [
  { title: 'Book A', price: 30 },
  { title: 'Book B', price: 20 },
  { title: 'Book C', price: 30 },
  { title: 'Book D', price: 10 }
];

// Create useStableSort and set it to true
// Your code here

Hint

Use const useStableSort = true; to set the sorting method.

3

Sort the books by price using stable sort

Use books.sort() with a compare function that compares a.price and b.price to sort the books by price in ascending order. Use the variable useStableSort to decide if sorting should happen.

DSA Javascript

const books = [
  { title: 'Book A', price: 30 },
  { title: 'Book B', price: 20 },
  { title: 'Book C', price: 30 },
  { title: 'Book D', price: 10 }
];

const useStableSort = true;

// Sort books by price using books.sort() and useStableSort
// Your code here

Hint

Use books.sort((a, b) => a.price - b.price) to sort by price ascending.

4

Print the sorted list of books

Use a for loop with variables book to go through books and print each book's title and price in the format Title: Book A, Price: 30

DSA Javascript

const books = [
  { title: 'Book A', price: 30 },
  { title: 'Book B', price: 20 },
  { title: 'Book C', price: 30 },
  { title: 'Book D', price: 10 }
];

const useStableSort = true;

if (useStableSort) {
  books.sort((a, b) => a.price - b.price);
}

// Print each book's title and price
// Your code here

Hint

Use for (const book of books) and console.log with template strings.

Practice

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

easy

A. It keeps the original order of equal elements after sorting

B. It sorts elements faster than unstable algorithms

C. It uses less memory than unstable algorithms

D. It always sorts in ascending order

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of items with equal keys unchanged.

2. Step 2: Compare with other options

   Speed, memory use, or sorting order do not define stability.

3. Final Answer:

   It keeps the original order of equal elements after sorting -> Option A

4. Quick Check:

   Stable sort = keeps equal elements order [OK]

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

Common Mistakes:

• Confusing stability with speed
• Thinking stability means sorting ascending only
• Assuming stable sorts use less memory

2. Which of the following is the correct way to call JavaScript's built-in sort method to sort numbers in ascending order?

easy

A. arr.sort()

B. arr.sort((a, b) => a + b)

C. arr.sort((a, b) => b - a)

D. arr.sort((a, b) => a - b)

Solution

1. Step 1: Understand JavaScript's default sort

   By default, arr.sort() sorts elements as strings, not numbers.

2. Step 2: Use compare function for numeric ascending

   The compare function (a, b) => a - b sorts numbers ascending correctly.

3. Final Answer:

   arr.sort((a, b) => a - b) -> Option D

4. Quick Check:

   Numeric ascending sort uses (a, b) => a - b [OK]

Hint: Use (a, b) => a - b for ascending numeric sort [OK]

Common Mistakes:

• Using arr.sort() alone for numbers
• Using (a, b) => b - a for ascending order
• Using (a, b) => a + b which is invalid

3. Consider the array of objects:

const items = [
  {name: 'apple', price: 50},
  {name: 'banana', price: 20},
  {name: 'cherry', price: 50},
  {name: 'date', price: 20}
];
items.sort((a, b) => a.price - b.price);

What will be the order of items after sorting?

medium

A. [{banana,20}, {date,20}, {cherry,50}, {apple,50}]

B. [{date,20}, {banana,20}, {cherry,50}, {apple,50}]

C. [{banana,20}, {date,20}, {apple,50}, {cherry,50}]

D. [{date,20}, {banana,20}, {apple,50}, {cherry,50}]

Solution

1. Step 1: Understand the sort comparator

   The comparator sorts by price ascending: 20 then 50.

2. Step 2: Check stability of JavaScript sort

   JavaScript's sort is stable in modern engines, so equal price items keep original order.

3. Step 3: Apply stability to equal price items

   For price 20, original order is banana then date; for 50, apple then cherry.

4. Final Answer:

   [{banana,20}, {date,20}, {apple,50}, {cherry,50}] -> Option C

5. Quick Check:

   Stable sort keeps equal price order [OK]

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

Common Mistakes:

• Assuming unstable sort changes order of equal items
• Mixing up banana and date order
• Ignoring stability of JavaScript sort

4. The following code tries to sort an array of strings by length, which may not keep the original order of equal length strings:

const arr = ['bat', 'cat', 'apple', 'dog'];
arr.sort((a, b) => a.length - b.length);

What is the main reason the original order of equal length strings might not be preserved?

medium

A. Strings cannot be sorted by length

B. JavaScript's sort is unstable in some engines

C. The comparator function is incorrect

D. The array contains duplicates

Solution

1. Step 1: Check comparator correctness

   The comparator (a, b) => a.length - b.length correctly compares string lengths.

2. Step 2: Understand JavaScript sort stability

   JavaScript's sort is stable in modern engines but may be unstable in older engines, causing order change.

3. Final Answer:

   JavaScript's sort is unstable in some engines -> Option B

4. Quick Check:

   Unstable sort breaks equal element order [OK]

Hint: Old JS engines have unstable sort, losing order [OK]

Common Mistakes:

• Blaming comparator function
• Thinking strings can't be sorted by length
• Assuming duplicates cause instability

5. You have a list of student records with name and score. You want to sort by score ascending but keep the original order for students with the same score. Which sorting algorithm should you choose and why?

hard

A. MergeSort, because it is stable and sorts efficiently

B. QuickSort, because it is fast but unstable

C. HeapSort, because it uses less memory

D. BubbleSort, because it is simple and stable

Solution

1. Step 1: Identify need for stability

   We want to keep original order for equal scores, so stability is required.

2. Step 2: Choose algorithm with stability and efficiency

   MergeSort is stable and efficient (O(n log n)), suitable for this task.

3. Step 3: Compare other options

   QuickSort is fast but unstable; HeapSort is unstable; BubbleSort is stable but inefficient.

4. Final Answer:

   MergeSort, because it is stable and sorts efficiently -> Option A

5. Quick Check:

   Stable + efficient = MergeSort [OK]

Hint: Stable and efficient sort for equal keys: MergeSort [OK]

Common Mistakes:

• Choosing QuickSort ignoring instability
• Picking BubbleSort despite inefficiency
• Confusing HeapSort as stable