PadhaikoAll subjects

Past exam question: 2064 Jestha, Q7

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

What are the conflicting efficiency considerations in various sorting methods? Compare and contrast the efficiency of Bubble sort, Quick sort, Insertion sort and Selection sort algorithms with an example.

Solution

Conflicting Efficiency Considerations in Sorting: Designing or choosing a sorting algorithm balances competing trade-offs:

  1. Time vs. Auxiliary Space: Merge sort guarantees worst-case time but needs extra memory, while Quick sort is stack space on average but risks worst-case time.
  2. Average Speed vs. Worst-Case Guarantee: Quick sort is fastest in practice due to cache locality, yet has an worst case unless randomized/median-of-three pivot is used.
  3. Stability vs. In-Place Execution: Making fast sorts stable usually demands memory (Merge sort), whereas in-place Quick/Heap/Selection sorts are generally unstable.
  4. Adaptivity vs. Predictability: Insertion sort runs in on nearly sorted inputs, whereas Selection sort always takes comparisons but minimizes swaps to .

Efficiency Comparison with Example Input [5, 1, 4, 2, 8]:

AlgorithmBestAverageWorstSpaceStable?Notes on [5, 1, 4, 2, 8]
Bubble SortYesMany adjacent swaps (5<->1, 5<->4, 5<->2, ...)
Insertion SortYesShifts elements into sorted prefix; very fast if nearly sorted
Selection SortNoAlways 10 comparisons here, at most 4 swaps
Quick SortNoPartitions around pivot 5 in-place
Answer:

Sorting methods trade off worst-case vs. average time, in-place memory vs. stability, and comparison count vs. swap count. Bubble/Insertion/Selection run in average time ( best for Bubble/Insertion, minimum swaps for Selection), while Quick sort achieves average in-place speed ( worst case).

All past exam questions for Data Structure and Algorithms