Select the Sorting Algorithms that are stable. (A) Quick Sort (B) Bubble Sort (C) Insertion Sort (D) Merge…

Question

Select the Sorting Algorithms that are stable. (A) Quick Sort (B) Bubble Sort (C) Insertion Sort (D) Merge Sort (E) Shell Sort Choose the correct answer from the options given below:

Accepted Answer

Correct answer: C — Concept: A sorting algorithm is called stable if, for any two elements with equal keys, their original relative order survives into the final sorted output — whenever key[i] = key[j] and element i appears before element j in the input, element i must still appear before element j after sorting. In practice, an algorithm is classified by checking a simpler sufficient test: if every internal move, swap, or merge step only ever repositions two elements when one is strictly greater than the other, and never repositions two elements that are merely equal, the final order among ties is guaranteed to survive — this is the standard way the five algorithms below are checked, one at a time. Application: Checking each of the five listed algorithms against that test: Algorithm What it actually moves Can two equal keys get reordered? Quick Sort Partitions around a pivot, swapping elements across the pivot boundary Yes — an element equal to another can be swapped to the far side of it during partitioning Bubble Sort Swaps only two adjacent elements, and only when the left one is strictly greater No — two equal elements are never swapped, since neither is strictly greater than the other Insertion Sort Shifts elements right only while they are strictly greater than the key being inserted No — an equal key stops the shift and is never pushed past another equal key Merge Sort Merges two sorted runs, drawing from whichever run's front element compares smaller Depends on the tie rule — only stable if the merge step always draws from the left run first on equal keys; general/in-place variants do not enforce this Shell Sort Runs insertion-sort-like passes over elements that are h positions apart, with h shrinking each pass Yes — an element can be carried past a DIFFERENT key during one gap pass and past another key during a later, smaller-gap pass, so two equal keys can end up in a different relative order across the full sequence of passes even though no single pass ever swaps the two equal keys directly against each other So Quick Sort directly fails the test (a single partition step can reposition two equal keys against each other), Shell Sort fails it across its sequence of gap passes, and Merge Sort's stability is conditional on an implementation choice (which run the merge draws from on a tie) rather than guaranteed by the algorithm itself. This question's accepted classification matches the exam's own official answer key for this exact question (UGC NET Computer Science, August 2024): the credited stable set is Bubble Sort and Insertion Sort only. Some textbook treatments additionally count the canonical merge (one that always takes the left run on a tie) as stable, but no offered option pairs Merge Sort with only Bubble Sort and Insertion Sort — so that theoretical nuance does not change which of the FOUR OFFERED options is correct; the official key resolves it to Bubble Sort and Insertion Sort. Cross-check: Trace an array carrying a tagged duplicate key through both a stable and an unstable algorithm from the table above. Input: [3a, 1, 3b, 2], where 3a and 3b carry the same key 3, and 3a appears first. Bubble Sort: pass 1 compares (3a,1) — 3>1, swap, giving [1,3a,3b,2]; compares (3a,3b) — equal, no swap; compares (3b,2) — 3>2, swap, giving [1,3a,2,3b]. Pass 2 compares (3a,2) — 3>2, swap, giving [1,2,3a,3b]; compares (3a,3b) — equal, no swap. The array is now sorted as [1,2,3a,3b] — 3a stays immediately before 3b throughout. Quick Sort (Lomuto partition, pivot = last element = 2): scanning left to right, 1 is less than the pivot so it is swapped to the front, giving [1,3a,3b,2]; 3a and 3b are both greater than the pivot so neither moves during the scan. The final step swaps the pivot into place by exchanging it with the first element greater than the pivot — that is 3a — giving [1,2,3b,3a]. A single partition step has swapped the pivot (2) with 3a while leaving 3b untouched, so 3b now sits before 3a — the relative order of the two equal keys has flipped in one pass, exactly the reordering Quick Sort carries no guarantee against. This confirms the same conclusion the classification table gives: among the five, only Bubble Sort and Insertion Sort are guaranteed to preserve the order of equal keys, matching the exam's official key of Bubble Sort and Insertion Sort.

Answer

A. (A), (B), (C) and (E) Only

Answer

B. (A), (D) and (E) Only

Answer

C. (B) and (C) Only

Answer

D. (B), (C) and (E) Only.

Algorithm	What it actually moves	Can two equal keys get reordered?
Quick Sort	Partitions around a pivot, swapping elements across the pivot boundary	Yes — an element equal to another can be swapped to the far side of it during partitioning
Bubble Sort	Swaps only two adjacent elements, and only when the left one is strictly greater	No — two equal elements are never swapped, since neither is strictly greater than the other
Insertion Sort	Shifts elements right only while they are strictly greater than the key being inserted	No — an equal key stops the shift and is never pushed past another equal key
Merge Sort	Merges two sorted runs, drawing from whichever run's front element compares smaller	Depends on the tie rule — only stable if the merge step always draws from the left run first on equal keys; general/in-place variants do not enforce this
Shell Sort	Runs insertion-sort-like passes over elements that are h positions apart, with h shrinking each pass	Yes — an element can be carried past a DIFFERENT key during one gap pass and past another key during a later, smaller-gap pass, so two equal keys can end up in a different relative order across the full sequence of passes even though no single pass ever swaps the two equal keys directly against each other

Select the Sorting Algorithms that are stable. (A) Quick Sort (B) Bubble Sort…