Past exam question: 2062 Baishakh (Regular / Back), Q7(b)
Open in the Padhaiko appQuestion
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:
- 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. - Thus Insertion sort runs in time with space.
- 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).