Sorting Algorithms Questions and Answers

Answer: D

The worst case times are \(\Theta(n^{2})\), \(\Theta(n\log n)\), and \(\Theta(n^{2})\).

Insertion sort: on reverse-sorted input each element shifts past all the earlier ones, \(1 + 2 + \cdots + (n-1) = \Theta(n^{2})\). Merge sort: it always halves the array and merges in linear time, \(\Theta(n\log n)\) in every case. Quick sort: if the pivot is always the smallest or largest element (for example the first element of sorted input), each partition removes only one element, giving \(\Theta(n^{2})\).

Quick sort's \(\Theta(n\log n)\) is its average case, which is the trap in the other options; insertion sort's worst case is never \(n\log n\).

Answer: D

The true statements are I and IV only.

I: the standard quicksort picks the first (or last) element as pivot. On sorted input that pivot is the smallest (or largest) element, every partition is maximally unbalanced, and the running time is \(\Theta(n^{2})\).

IV: insertion sort compares each new element only with its left neighbour, finds it already in place and moves on, so sorted input takes \(\Theta(n)\).

II is not taken as true: bubble sort with the usual check for a pass with no swaps stops after one pass over sorted input, \(\Theta(n)\); the key assumes this standard version, since a bubble sort without the check would take \(\Theta(n^{2})\). III is false: merge sort always splits and merges fully, so it takes \(\Theta(n\log n)\) on any input, never \(\Theta(n)\).