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 Objects with Equal Keys

Consider an array of objects sorted by a stable sorting algorithm by their 'key' field. What will be the output order of the 'name' fields after sorting?

DSA C

struct Item {
    int key;
    char name[10];
};

struct Item arr[] = {
    {2, "apple"},
    {1, "banana"},
    {2, "cherry"},
    {1, "date"}
};

// After stable sort by key ascending, print names in order
for (int i = 0; i < 4; i++) {
    printf("%s ", arr[i].name);
}

A banana apple date cherry

B banana date apple cherry

C date banana cherry apple

D apple cherry banana date

💡 Hint

Stable sort keeps the original order of equal keys.

Since the sort is stable, items with key=1 keep their original order: banana then date. Similarly, items with key=2 keep order: apple then cherry.

🧠 Conceptual

intermediate

When to Prefer Stable Sorts Over Unstable Sorts

Which scenario best explains when you should use a stable sorting algorithm instead of an unstable one?

A When sorting records by multiple fields in sequence, preserving previous order of equal keys matters.

B When you want to sort numbers quickly without caring about original order of equal elements.

C When memory is very limited and you want the fastest possible sort regardless of order.

D When you only have one element to sort.

💡 Hint

Think about sorting by multiple criteria step-by-step.

Stable sorts preserve the order of equal elements, which is important when sorting by multiple fields sequentially (e.g., sort by last name, then by first name).

❓ Predict Output

advanced

Output of Unstable Sort on Equal Keys

What is the possible output of an unstable sorting algorithm sorting this array of integers with duplicates?

DSA C

int arr[] = {4, 2, 2, 3, 4};
// After unstable sort ascending, print array
for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]);
}

A 2 3 2 4 4

B 3 2 2 4 4

C 4 4 3 2 2

D 2 2 3 4 4

💡 Hint

Unstable sort may reorder equal elements arbitrarily, but output must be sorted ascending.

Unstable sort guarantees sorted order but does not guarantee original order of equal elements. The output must be sorted ascending, so only option D is sorted ascending.

🧠 Conceptual

advanced

Choosing Sorting Algorithm Based on Stability and Performance

You have a large dataset of records with multiple fields. You need to sort by one field but also preserve the original order of records with equal keys. Which sorting algorithm is best suited?

A Merge sort, because it is stable and has good performance on large data.

B Heapsort, because it uses less memory but is unstable.

C Quicksort, because it is fast but unstable.

D Selection sort, because it is simple and stable.

💡 Hint

Consider stability and efficiency for large data.

Merge sort is stable and efficient (O(n log n)) for large datasets, making it suitable when stability is required.

🔧 Debug

expert

Identify the Reason for Unstable Behavior in a Custom Sort

This C code attempts to implement a stable insertion sort on an array of structs but does not preserve stability. What causes the instability?

DSA C

struct Item {
    int key;
    char name[10];
};

void insertionSort(struct Item arr[], int n) {
    for (int i = 1; i < n; i++) {
        struct Item temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j].key >= temp.key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

A The temporary variable 'temp' is overwritten inside the loop causing data loss.

B The loop starts at i=1 instead of i=0 causing first element to be skipped.

C The comparison uses '>=' instead of '>' causing equal keys to be reordered.

D The array is not large enough to hold all elements causing overflow.

💡 Hint

Check how equal keys are handled in the comparison.

Using '>=' means elements with equal keys are shifted, breaking stability. Using '>' preserves stability by not moving equal keys.

Practice

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

easy

A. It sorts elements in descending order

B. It uses less memory than unstable sorts

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

D. It always sorts in linear time

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of elements that compare equal unchanged.

2. Step 2: Compare options with definition

   Only It keeps the original order of equal elements after sorting matches this definition exactly.

3. Final Answer:

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

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 faster sorting
• Assuming stability relates to memory use

2. Which of the following is the correct syntax to call the qsort function in C for sorting an array arr of integers with n elements?

easy

A. qsort(arr, n, compare, sizeof(int));

B. qsort(arr, n, sizeof(int), compare);

C. qsort(arr, sizeof(int), n, compare);

D. qsort(arr, compare, n, sizeof(int));

Solution

1. Step 1: Recall qsort parameter order

   The qsort function parameters are: pointer to array, number of elements, size of each element, and comparison function pointer.

2. Step 2: Match parameters with options

   qsort(arr, n, sizeof(int), compare); matches this order exactly: arr, n, sizeof(int), compare.

3. Final Answer:

   qsort(arr, n, sizeof(int), compare); -> Option B

4. Quick Check:

   qsort syntax = arr, n, size, compare [OK]

Hint: Remember qsort: array, count, size, compare function [OK]

Common Mistakes:

• Mixing up size and count parameters
• Placing compare function in wrong position
• Using wrong order of arguments

3. Consider the following C code snippet using bubble sort on an array of structs with an integer key and a character value. Which output shows the array after sorting by key, preserving stability?

typedef struct {
  int key;
  char value;
} Item;

void bubbleSort(Item arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-i-1; j++) {
      if (arr[j].key > arr[j+1].key) {
        Item temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

int main() {
  Item arr[5] = {{2, 'a'}, {3, 'b'}, {2, 'c'}, {1, 'd'}, {3, 'e'}};
  bubbleSort(arr, 5);
  for (int i = 0; i < 5; i++) {
    printf("%d%c ", arr[i].key, arr[i].value);
  }
  return 0;
}

medium

A. 1d 2a 2c 3b 3e

B. 1d 2c 2a 3e 3b

C. 1d 2c 2a 3b 3e

D. 1d 2a 2c 3e 3b

Solution

1. Step 1: Understand bubble sort stability

   Bubble sort is stable, so equal keys keep their original order.

2. Step 2: Trace sorting of array

   Original order for key=2 is 'a' then 'c', for key=3 is 'b' then 'e'. After sorting by key, order is 1d, 2a, 2c, 3b, 3e.

3. Final Answer:

   1d 2a 2c 3b 3e -> Option A

4. Quick Check:

   Bubble sort stable = keeps order of equal keys [OK]

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

Common Mistakes:

• Assuming bubble sort is unstable
• Swapping equal keys and changing order
• Mixing up output order of equal keys

4. The following code attempts to sort an array using selection sort but does not preserve stability. What change fixes this to make it stable?

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n-1; i++) {
    int min_idx = i;
    for (int j = i+1; j < n; j++) {
      if (arr[j] < arr[min_idx]) {
        min_idx = j;
      }
    }
    int temp = arr[min_idx];
    arr[min_idx] = arr[i];
    arr[i] = temp;
  }
}

medium

A. Sort array in descending order

B. Use bubble sort instead of selection sort

C. Change comparison to <= instead of <

D. Replace swap with shifting elements to insert min element

Solution

1. Step 1: Identify why selection sort is unstable

   Selection sort swaps min element directly, which can reorder equal elements and break stability.

2. Step 2: Fix by shifting elements

   Instead of swapping, shift elements right and insert min element at correct position to keep order.

3. Final Answer:

   Replace swap with shifting elements to insert min element -> Option D

4. Quick Check:

   Stable selection sort = shift, not swap [OK]

Hint: Shift elements instead of swap for stable selection sort [OK]

Common Mistakes:

• Just changing comparison operator
• Switching to bubble sort without reason
• Sorting in wrong order

5. You have a large dataset with many duplicate keys and need to sort it by key while preserving the order of duplicates. The dataset is too large to fit in memory, so you must use external sorting. Which sorting algorithm is best suited for this task?

hard

A. External merge sort because it is stable and handles large data

B. Quick sort because it is fastest in average case

C. Heap sort because it uses constant memory

D. Selection sort because it is simple to implement

Solution

1. Step 1: Understand requirements for large data and stability

   Large data needs external sorting; stability is required to keep duplicate order.

2. Step 2: Match algorithm features

   External merge sort is stable and designed for large data using disk; quicksort and heapsort are unstable and in-memory; selection sort is inefficient.

3. Final Answer:

   External merge sort because it is stable and handles large data -> Option A

4. Quick Check:

   Large stable sort = external merge sort [OK]

Hint: Use external merge sort for large stable sorting [OK]

Common Mistakes:

• Choosing quicksort ignoring stability
• Picking heapsort without external support
• Using simple sorts for large data