Sorting Stability and When to Use Which Sort in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a stable sort using std::stable_sort.

DSA C++

#include <vector>
#include <algorithm>

std::vector<int> data = {4, 2, 5, 2, 3};
std::stable_sort(data.begin(), data.[1]());

Drag options to blanks, or click blank then click option'

Arend

Bbegin

Crbegin

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using begin() twice instead of begin() and end()

Using reverse iterators which sort in reverse order

std::stable_sort requires the range from begin() to end() to sort the entire vector stably.

2fill in blank

medium

Complete the code to check if a sorting algorithm is stable by comparing original and sorted vectors.

DSA C++

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

struct Item {
    int key;
    char value;
};

std::vector<Item> items = {{1, 'a'}, {2, 'b'}, {1, 'c'}};

std::stable_sort(items.begin(), items.end(), [](const Item &a, const Item &b) {
    return a.key < b.key;
});

for (const auto& item : items) {
    std::cout << item.key[1];
}

Drag options to blanks, or click blank then click option'

A << '\n'

B << ' '

C << ','

D << '.'

Attempts:

3 left

💡 Hint

Common Mistakes

Printing keys without spaces causing output to be hard to read

Using newline which prints each key on a new line

Printing keys separated by spaces helps visualize the order and check stability.

3fill in blank

hard

Fix the error in the code that attempts to use std::sort to maintain stability.

DSA C++

#include <vector>
#include <algorithm>

struct Record {
    int id;
    int score;
};

std::vector<Record> records = {{1, 90}, {2, 90}, {3, 80}};

std::sort(records.begin(), records.end(), [](const Record &a, const Record &b) {
    return a.score [1] b.score;
});

Drag options to blanks, or click blank then click option'

A>

B<=

C<

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' or '>=' in comparator causing runtime errors

Expecting std::sort to be stable

std::sort is not stable regardless of comparator, but the comparator must use strict weak ordering with '<' to avoid errors.

4fill in blank

hard

Fill both blanks to create a lambda comparator that sorts by score descending and then by id ascending.

DSA C++

auto cmp = [](const Record &a, const Record &b) {
    if (a.score [1] b.score) return true;
    if (a.score == b.score) return a.id [2] b.id;
    return false;
};

Drag options to blanks, or click blank then click option'

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' for score causing ascending order instead of descending

Using '>' for id causing descending order instead of ascending

To sort descending by score, use '>' and for ascending by id, use '<'.

5fill in blank

hard

Fill all three blanks to create a stable sort call that sorts a vector of pairs by first element ascending and second element descending.

DSA C++

std::stable_sort(pairs.begin(), pairs.end(), [](const auto &a, const auto &b) {
    if (a.first [1] b.first) return true;
    if (a.first [3] b.first) return a.second [2] b.second;
    return false;
});

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' for first element causing descending order

Using '<' for second element causing ascending order

Using '!=' instead of '==' for equality check

Sort ascending by first element using '<', descending by second element using '>', and check equality with '=='.

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