Level 1 — RecognitionSorting & Searching

Sorting & Searching

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Chapter: 3.6 Sorting & Searching Level: 1 — Recognition (MCQ + Matching + True/False with justification) Time Limit: 20 minutes Total Marks: 30

Section A — Multiple Choice (1 mark each, 10 marks)

Q1. Which sorting algorithm runs in $O(n)$ time on an already-sorted array?

(a) Selection sort
(b) Insertion sort
(c) Merge sort
(d) Heap sort

Q2. The worst-case time complexity of Quick sort is:

(a) $O(n \log n)$
(b) $O(n)$
(c) $O(n^2)$
(d) $O(\log n)$

Q3. Which of the following is a stable sorting algorithm?

(a) Heap sort
(b) Selection sort (standard)
(c) Merge sort
(d) Quick sort (standard)

Q4. Counting sort has time complexity:

(a) $O(n \log n)$
(b) $O(n + k)$ where $k$ is the range of keys
(c) $O(n^2)$
(d) $O(d(n+k))$

Q5. The lower bound for any comparison-based sort is:

(a) $\Omega(n)$
(b) $\Omega(\log n)$
(c) $\Omega(n \log n)$
(d) $\Omega(n^2)$

Q6. Binary search on a sorted array of $n$ elements runs in:

(a) $O(n)$
(b) $O(\log n)$
(c) $O(n \log n)$
(d) $O(1)$

Q7. Which algorithm guarantees worst-case $O(n)$ time to find the $k$ -th smallest element?

(a) Randomized quickselect
(b) Median-of-medians selection
(c) Heap sort then index
(d) Bubble sort then index

Q8. LSD radix sort processes digits:

(a) From most significant to least significant
(b) From least significant to most significant
(c) In random order
(d) All at once

Q9. Heap sort is best described as:

(a) $O(n \log n)$ , in-place, not stable
(b) $O(n^2)$ , in-place, stable
(c) $O(n \log n)$ , not in-place, stable
(d) $O(n + k)$ , in-place, stable

Q10. Bucket sort achieves expected linear time when the input is:

(a) Reverse sorted
(b) Drawn from a uniform distribution
(c) All equal
(d) Nearly sorted

Section B — Matching (1 mark each, 6 marks)

Q11. Match each algorithm (left) to its correct average-case complexity (right). Write pairs like A–3.

Algorithm		Complexity
A. Merge sort		1. $O(n^2)$
B. Bubble sort		2. $O(n + k)$
C. Counting sort		3. $O(n \log n)$
D. Radix sort (LSD)		4. $O(d(n+k))$

Q12. Match each partition/pivot concept to its description. Write pairs like A–3.

Term		Description
A. Lomuto partition		1. Choosing pivot at random to avoid worst case
B. Hoare partition		2. Single index scan, pivot placed at final position
C. Randomization		3. Two pointers moving inward from both ends
D. Worst-case pivot		4. Always picking smallest/largest element

Section C — True/False WITH Justification (2 marks each: 1 for T/F, 1 for reason, 14 marks)

Q13. Selection sort performs fewer swaps than bubble sort in general. (T/F + justify)

Q14. Merge sort sorts in place using $O(1)$ extra memory. (T/F + justify)

Q15. Counting sort can directly sort an array of arbitrary floating-point numbers. (T/F + justify)

Q16. A comparison sort can beat $\Omega(n \log n)$ in the worst case. (T/F + justify)

Q17. Binary search can be applied to an unsorted array to guarantee finding an element. (T/F + justify)

Q18. Randomized quicksort has expected running time $O(n \log n)$ regardless of the input arrangement. (T/F + justify)

Q19. In a rotated sorted array with distinct elements, a modified binary search can still find a target in $O(\log n)$ . (T/F + justify)

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 — (b) Insertion sort. On a sorted array, each element triggers only one comparison and no shifts, giving $O(n)$ ; this is why insertion sort wins on nearly-sorted data. (1)

Q2 — (c) $O(n^2)$ . Worst case occurs with bad pivots (e.g., already-sorted with first/last pivot) producing unbalanced partitions of size $n-1$ and $0$ ; the recurrence $T(n)=T(n-1)+O(n)$ gives $O(n^2)$ . (1)

Q3 — (c) Merge sort. Merge preserves relative order of equal keys by taking the left element on ties; heap/selection/standard quick reorder equal keys. (1)

Q4 — (b) $O(n+k)$ . One pass to count ( $O(n)$ ) plus a pass over the key range $k$ to build the output. (1)

Q5 — (c) $\Omega(n \log n)$ . Decision-tree argument: $n!$ leaves require height $\ge \log_2(n!) = \Theta(n \log n)$ . (1)

Q6 — (b) $O(\log n)$ . Search space halves each step: $\log_2 n$ iterations. (1)

Q7 — (b) Median-of-medians selection. Guarantees a pivot in the middle 30–70% range, yielding worst-case linear time; quickselect is only expected $O(n)$ . (1)

Q8 — (b) least → most significant. LSD stabilizes lower digits first so higher digits dominate the final order. (1)

Q9 — (a) $O(n \log n)$ , in-place, not stable. (1)

Q10 — (b) uniform distribution. Even spread means each bucket holds $O(1)$ elements on average. (1)

Section B

Q11 (1 mark, all correct): A–3, B–1, C–2, D–4. (1)

Q12 (1 mark, all correct): A–2, B–3, C–1, D–4. (1)

Section C (1 mark T/F + 1 mark justification)

Q13 — TRUE. Selection sort makes at most $n-1$ swaps (one per pass), whereas bubble sort may swap on every inversion, up to $O(n^2)$ swaps. (T=1, reason=1)

Q14 — FALSE. Standard merge sort needs $O(n)$ auxiliary array for merging; it is not in-place. (T/F=1, reason=1)

Q15 — FALSE. Counting sort requires integer keys usable as array indices over a bounded range; arbitrary floats cannot index a count array. (1+1)

Q16 — FALSE. The decision-tree lower bound $\Omega(n\log n)$ holds for all comparison sorts; only non-comparison sorts (counting/radix) beat it. (1+1)

Q17 — FALSE. Binary search assumes sorted order; on unsorted data the halving decision is invalid and it may miss the element. (1+1)

Q18 — TRUE. Random pivots make the expectation over pivot choices independent of input order; expected comparisons $= O(n\log n)$ . (1+1)

Q19 — TRUE. At least one half of the split around mid is sorted; comparing target to endpoints of the sorted half decides which side to recurse, keeping $O(\log n)$ . (1+1)

[
  {"claim":"Worst-case quicksort recurrence T(n)=T(n-1)+n sums to Theta(n^2)",
   "code":"n=symbols('n', positive=True, integer=True); k=symbols('k'); total=summation(k,(k,1,n)); result = (simplify(total - n*(n+1)/2)==0)"},
  {"claim":"Comparison-sort lower bound: log2(n!) is Theta(n log n) (Stirling leading term)",
   "code":"import sympy as sp; n=sp.symbols('n', positive=True); expr=sp.log(sp.factorial(n),2); lead=sp.limit(expr/(n*sp.log(n,2)), n, sp.oo); result=(lead==1)"},
  {"claim":"Binary search iterations on n=1024 equal log2(n)=10",
   "code":"import math; result = (math.floor(math.log2(1024))==10)"},
  {"claim":"Counting sort complexity O(n+k): for n=100,k=1000 cost model n+k=1100",
   "code":"n=100; k=1000; result = ((n+k)==1100)"}
]