PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q7(b)

Data Structure and Algorithms · 3 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Explain which elementary sorting algorithm (i.e. Bubble, Insertion, Selection) you choose when the input data is in almost sorted form.

Solution

Best Choice for Almost-Sorted Data: Insertion Sort: Insertion sort is the optimal elementary sorting choice for almost-sorted inputs because it is adaptive and performs minimal swaps/shifts:

  1. When each element is at most positions away from its sorted location (or only a few inversions exist), the inner while (j >= 0 && A[j] > key) loop terminates almost immediately.
  2. Thus Insertion sort runs in time with space.
  3. By contrast, Selection sort always performs comparisons regardless of initial order, and even flag-optimized Bubble sort typically does more writes/passes when small elements sit near the end.
Answer:

Choose Insertion Sort for almost-sorted input because it is naturally adaptive, running in best/near-sorted time with minimal comparisons and shifts, unlike Selection sort ( always).

All past exam questions for Data Structure and Algorithms