Sorting Stability and When to Use Which Sort in DSA C - Execution Trace

Concept Flow - Sorting Stability and When to Use Which Sort

Start with unsorted array

↓

Choose sorting algorithm

↓

Check if stability needed?

Yes→Use stable sort

↓

Use unstable sort

↓

Perform sorting steps

↓

Sorted array with stability info

↓

End

Shows the decision flow for choosing a sorting algorithm based on stability needs and performing the sort.

Execution Sample

DSA C

int arr[] = {4, 2, 3, 2, 1};
// Stable sort example: Insertion Sort
for (int i = 1; i < 5; i++) {
  int key = arr[i];
  int j = i - 1;
  while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j]; j--;
  }
  arr[j + 1] = key;
}

This code sorts an array using insertion sort, which is stable and keeps equal elements in original order.

Execution Table

Step	Operation	Array State	Comparison	Swap or Shift	Stability Effect
1	Pick key=2 at index 1	[4, 2, 3, 2, 1]	Compare 4 > 2	Shift 4 right	Stable: equal elements keep order
2	Insert key=2 at index 0	[2, 4, 3, 2, 1]	N/A	Insert key	Stable
3	Pick key=3 at index 2	[2, 4, 3, 2, 1]	Compare 4 > 3	Shift 4 right	Stable
4	Insert key=3 at index 1	[2, 3, 4, 2, 1]	N/A	Insert key	Stable
5	Pick key=2 at index 3	[2, 3, 4, 2, 1]	Compare 4 > 2	Shift 4 right	Stable
6	Compare 3 > 2	N/A	N/A	Shift 3 right	Stable
7	Insert key=2 at index 1	[2, 2, 3, 4, 1]	N/A	Insert key	Stable
8	Pick key=1 at index 4	[2, 2, 3, 4, 1]	Compare 4 > 1	Shift 4 right	Stable
9	Compare 3 > 1	N/A	N/A	Shift 3 right	Stable
10	Compare 2 > 1	N/A	N/A	Shift 2 right	Stable
11	Compare 2 > 1	N/A	N/A	Shift 2 right	Stable
12	Insert key=1 at index 0	[1, 2, 2, 3, 4]	N/A	Insert key	Stable
13	Sorting complete	[1, 2, 2, 3, 4]	N/A	N/A	Stable sorted array

💡 All elements sorted with insertion sort preserving original order of equal elements (stable).

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 12	Final
arr	[4, 2, 3, 2, 1]	[2, 4, 3, 2, 1]	[2, 3, 4, 2, 1]	[2, 2, 3, 4, 1]	[1, 2, 2, 3, 4]	[1, 2, 2, 3, 4]
key	N/A	2	3	2	1	N/A
j	N/A	0	1	1	0	N/A

Key Moments - 3 Insights

Why does insertion sort keep the order of equal elements?

Because it only shifts elements greater than the key, not equal ones, so equal elements stay in their original order (see steps 5-7 in execution_table).

What happens if stability is not needed? Can we use any sort?

Yes, if stability is not required, faster but unstable sorts like quicksort can be used (not shown here), which may reorder equal elements.

How do we decide which sorting algorithm to use?

Check if stability is needed and data size: use stable sorts like insertion or merge sort if order matters; use faster unstable sorts like quicksort if order doesn't matter (see concept_flow).

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 7?

A [2, 3, 4, 2, 1]

B [2, 2, 3, 4, 1]

C [1, 2, 2, 3, 4]

D [4, 2, 3, 2, 1]

💡 Hint

Check the 'Array State' column at step 7 in execution_table.

At which step does the smallest element 1 get inserted into the array?

A Step 12

B Step 10

C Step 8

D Step 13

💡 Hint

Look for 'Insert key=1' operation in execution_table.

If we used quicksort instead of insertion sort, what would likely change in the execution_table?

A The array would be sorted and stable

B The array would remain unsorted

C The array would be sorted but stability might be lost

D No changes, quicksort is stable

💡 Hint

Recall that quicksort is generally unstable, unlike insertion sort shown here.

Concept Snapshot

Sorting Stability and Usage Guide:
- Stable sort keeps equal elements in original order.
- Use stable sorts (Insertion, Merge) when order matters.
- Use unstable sorts (Quicksort, Heapsort) for speed if order doesn't matter.
- Stability depends on how elements are compared and moved.
- Choose sort based on data size, stability need, and performance.

Full Transcript

This lesson shows how sorting stability affects the order of equal elements during sorting. We trace insertion sort, a stable algorithm, sorting an array step-by-step. The array changes by shifting elements greater than the key, preserving the order of equal elements. We see how to decide which sorting algorithm to use based on stability needs and data size. Stable sorts keep equal elements in original order, unstable sorts may not but can be faster. The execution table tracks each step, array state, comparisons, and stability effects. Key moments clarify why insertion sort is stable and when to choose stable or unstable sorts. Visual quiz questions test understanding of array states and sorting choices. The quick reference summarizes stability and usage rules for sorting algorithms.

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