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)\).

Answer: D

Selection sort calls swap N-1 times.

Selection sort makes N-1 passes. In each pass it scans the unsorted part to find the smallest element and then swaps it into the first unsorted position, one swap per pass. After N-1 passes the last element is automatically in place. (An implementation that skips swapping an element with itself can do fewer, but the standard count is N-1.)

\(N^{2}\) is the order of the number of comparisons, about N(N-1)/2, not swaps. N log N is the cost of efficient sorts such as merge sort, and log N is far too few to move N elements into place.

Answer: A

Bubble sort is O(n) in the best case and O(\(n^{2}\)) in the worst case.

Bubble sort with the usual 'swapped' flag stops as soon as a pass makes no swaps. On an already sorted array the first pass of n-1 comparisons makes no swaps, so the best case is O(n). On a reverse-sorted array every pass swaps, and about n(n-1)/2 comparisons and swaps are needed, so the worst case is O(\(n^{2}\)).

O(n log n) is the complexity of merge sort and of heap sort, not of bubble sort, which rules out options B, C and D.