Sorting Stability and When to Use Which Sort in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stable Sort on Structs

Given the following C++ code that sorts a vector of structs by the 'value' field using a stable sort, what will be the printed output?

DSA C++

struct Item {
    int id;
    int value;
};

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<Item> items = {{1, 5}, {2, 3}, {3, 5}, {4, 2}};
    std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.value < b.value;
    });
    for (const auto& item : items) {
        std::cout << item.id << "-" << item.value << " ";
    }
    return 0;
}

A 4-2 2-3 1-5 3-5

B 4-2 2-3 3-5 1-5

C 2-3 4-2 1-5 3-5

D 2-3 4-2 3-5 1-5

💡 Hint

Stable sort keeps the original order of equal elements.

The stable sort arranges items by their 'value' in ascending order. For items with the same 'value', their original order is preserved. Here, items with value 5 are {1,5} then {3,5}, so they remain in that order after sorting.

🧠 Conceptual

intermediate

When to Prefer Stable Sorts?

Which scenario best explains when you should prefer a stable sorting algorithm over an unstable one?

A When you need to maintain the relative order of records with equal keys after sorting.

B When you want the fastest possible sorting regardless of order of equal elements.

C When sorting small arrays where stability does not matter.

D When you want to sort in descending order only.

💡 Hint

Think about preserving order of equal items.

Stable sorts keep the original order of equal elements, which is important when the order carries meaning, such as sorting by multiple keys in sequence.

❓ Predict Output

advanced

Output of Unstable Sort on Same Data

What is a possible output of the following C++ code using std::sort (which is not guaranteed to be stable) on the same data as before?

DSA C++

struct Item {
    int id;
    int value;
};

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<Item> items = {{1, 5}, {2, 3}, {3, 5}, {4, 2}};
    std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.value < b.value;
    });
    for (const auto& item : items) {
        std::cout << item.id << "-" << item.value << " ";
    }
    return 0;
}

A 2-3 4-2 1-5 3-5

B 4-2 2-3 3-5 1-5

C 4-2 2-3 1-5 3-5

D 1-5 3-5 2-3 4-2

💡 Hint

Unstable sort may reorder equal elements arbitrarily.

std::sort is not guaranteed to be stable, so items with equal 'value' may appear in any order. One possible output is with the two items of value 5 swapped.

🧠 Conceptual

advanced

Choosing Sorting Algorithm Based on Data Size and Stability

You have a large dataset that must be sorted by multiple keys, preserving the order of previous sorts. Which sorting approach is best?

A Use a stable sort once on the most important key only.

B Use an unstable sort once on the most important key only.

C Use a stable sort multiple times, starting from the least important key to the most important key.

D Use an unstable sort multiple times on all keys.

💡 Hint

Think about preserving order across multiple keys.

Sorting multiple keys by repeated stable sorts from least to most important key preserves the order of previous keys, achieving a multi-key sort.

🔧 Debug

expert

Why Does This Sorting Code Fail to Preserve Order?

Consider this C++ code snippet that attempts to sort a vector of pairs by the second element while preserving the original order of pairs with equal second elements. Why does it fail to preserve order?

DSA C++

std::vector<std::pair<int,int>> v = {{1,2}, {2,1}, {3,2}, {4,1}};
std::sort(v.begin(), v.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});
for (auto& p : v) {
    std::cout << "(" << p.first << "," << p.second << ") ";
}

A Because the output loop is missing a newline.

B Because the lambda comparator is incorrect and does not compare properly.

C Because the vector is not initialized correctly.

D Because std::sort is not stable, it can reorder pairs with equal second elements arbitrarily.

💡 Hint

Check if the sorting algorithm preserves order of equal keys.

std::sort is not stable, so it does not guarantee to keep the original order of elements with equal keys. To preserve order, std::stable_sort should be used.

Practice

1. Which of the following sorting algorithms is stable by default?

easy

A. Merge Sort

B. Quick Sort

C. Heap Sort

D. Selection Sort

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of equal elements the same as in the input.

2. Step 2: Check common sorting algorithms

   Merge Sort is stable because it merges sorted halves without changing order of equal elements. Quick Sort, Heap Sort, and Selection Sort are not stable by default.

3. Final Answer:

   Merge Sort -> Option A

4. Quick Check:

   Stable sort = Merge Sort [OK]

Hint: Remember: Merge Sort is stable, Quick Sort is not [OK]

Common Mistakes:

• Thinking Quick Sort is stable
• Confusing stability with time complexity
• Assuming all comparison sorts are stable

2. Which syntax correctly declares a stable sort call on a vector v in C++ STL?

easy

A. v.stable_sort();

B. std::sort(v.begin(), v.end(), stable);

C. std::stable_sort(v.begin(), v.end());

D. std::sort_stable(v.begin(), v.end());

Solution

1. Step 1: Recall C++ STL stable sort syntax

   The function is std::stable_sort with two iterators as arguments.

2. Step 2: Check options for correctness

   std::stable_sort(v.begin(), v.end()); matches correct syntax. Options A, B, and D are invalid or do not exist in STL.

3. Final Answer:

   std::stable_sort(v.begin(), v.end()); -> Option C

4. Quick Check:

   Correct stable sort syntax = std::stable_sort(v.begin(), v.end()); [OK]

Hint: Use std::stable_sort with iterators for stable sorting [OK]

Common Mistakes:

• Using std::sort for stable sorting
• Calling non-existent member functions
• Passing wrong arguments to sort functions

3. What is the output of the following C++ code snippet?

struct Item {
  int key;
  char id;
};

std::vector<Item> v = {{2, 'a'}, {1, 'b'}, {2, 'c'}};
std::stable_sort(v.begin(), v.end(), [](Item x, Item y) { return x.key < y.key; });
for (auto &item : v) std::cout << item.key << item.id << ' ';

medium

A. 2c 2a 1b

B. 1b 2c 2a

C. 2a 2c 1b

D. 1b 2a 2c

Solution

1. Step 1: Understand stable_sort behavior

   stable_sort sorts by key ascending but keeps relative order of equal keys.

2. Step 2: Sort vector and trace output

   Keys sorted: 1, 2, 2. For key=2, 'a' comes before 'c' in original, so order stays '2a' then '2c'. Output: "1b 2a 2c "

3. Final Answer:

   1b 2a 2c -> Option D

4. Quick Check:

   Stable sort keeps order of equal keys [OK]

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

Common Mistakes:

• Assuming equal keys reorder arbitrarily
• Confusing stable_sort with sort
• Ignoring the lambda comparator effect

4. Identify the error in this code snippet that tries to use stable sort on an array:

int arr[] = {3, 1, 2};
std::stable_sort(arr, arr + 3);
for (int i = 0; i < 3; i++) std::cout << arr[i] << ' ';

medium

A. No error; code runs correctly

B. Array pointers used incorrectly in stable_sort

C. stable_sort cannot be used on arrays

D. Missing comparator function causes error

Solution

1. Step 1: Check stable_sort usage on arrays

   std::stable_sort accepts pointers as iterators, so arr and arr+3 are valid.

2. Step 2: Verify code correctness

   Code sorts array {3,1,2} to {1,2,3} and prints correctly. No error present.

3. Final Answer:

   No error; code runs correctly -> Option A

4. Quick Check:

   stable_sort works with array pointers [OK]

Hint: stable_sort works with pointers, no comparator needed for default order [OK]

Common Mistakes:

• Thinking stable_sort needs vector only
• Assuming comparator is mandatory
• Confusing pointers with iterators

5. You have a list of employees with fields name and age. You want to sort them by age but keep the original order for employees with the same age. Which sorting algorithm should you use and why?

hard

A. Heap Sort, because it uses less memory

B. Stable Sort (like Merge Sort), to preserve order of equal ages

C. Quick Sort, because it is faster on average

D. Selection Sort, because it is simple to implement

Solution

1. Step 1: Understand requirement for stability

   We want to keep original order for employees with same age, so sorting must be stable.

2. Step 2: Choose sorting algorithm based on stability

   Merge Sort or any stable sort preserves order of equal keys. Quick Sort, Heap Sort, Selection Sort are not stable by default.

3. Final Answer:

   Stable Sort (like Merge Sort), to preserve order of equal ages -> Option B

4. Quick Check:

   Stable sort needed to keep order [OK]

Hint: Use stable sort to keep order of equal keys [OK]

Common Mistakes:

• Choosing faster but unstable sorts
• Ignoring stability requirement
• Confusing simplicity with correctness