AFL 1 - part 2

Consider Insertion Sort applied to an array of n distinct elements. In the worst-case scenario (i.e., the array is reverse sorted), what is the exact total number of comparisons performed?

• n(n – 1)/2

• n(n – 1)/2 + (n – 1)

• n²/2

• n²

Answer explanation

In the worst-case, the inner loop of Insertion Sort makes 1 comparison for the 2nd element, 2 for the 3rd, and so on up to n–1 comparisons for the last element. Summing these gives 1 + 2 + … + (n – 1) = n(n – 1)/2 comparisons.

Regardless of the initial order of the elements, what is the exact number of comparisons performed by Selection Sort when sorting an array of n elements?

• n(n + 1)/2

• n(n – 1)/2

• (n – 1)²

• n²

Answer explanation

In Selection Sort, the algorithm scans the unsorted portion for each of the n–1 positions. The first pass makes (n – 1) comparisons, the second makes (n – 2), and so on. The total is (n – 1) + (n – 2) + … + 1 = n(n – 1)/2, regardless of input order.

Which algorithm shows adaptive behavior that significantly reduces the number of comparisons on nearly sorted input, and why?

• Insertion Sort, because it quickly detects that few or no shifts are needed.

• Selection Sort, because it avoids scanning the entire unsorted segment.

• Insertion Sort, because its number of swaps is always minimal.

• Selection Sort, because it makes fewer comparisons when the array is nearly sorted.

Answer explanation

Insertion Sort benefits from nearly sorted input because its inner loop terminates early when the current element is already in the correct position, resulting in O(n) time in the best-case scenario. In contrast, Selection Sort always makes the same number of comparisons.

In terms of write operations, which algorithm is typically more efficient, and what is the maximum number of swaps (or writes) it performs on an array of n elements?

• Insertion Sort, with up to n(n – 1)/2 writes

• Selection Sort, with up to n – 1 writes

• Insertion Sort, with up to n – 1 writes

• Selection Sort, with up to n(n – 1)/2 writes

Answer explanation

Standard Selection Sort makes one swap per outer loop iteration (if a swap is needed), for a maximum of n – 1 swaps. Insertion Sort, particularly a swap-based implementation, may require far more writes due to repeated swapping, making Selection Sort more write-efficient when writes are expensive.

Both Insertion Sort and Selection Sort are considered in-place algorithms. What is their extra space complexity, and what does this imply about additional memory usage?

• O(n), meaning they require additional memory proportional to the input size

• O(1), meaning they use only a constant amount of extra memory

• O(log n), due to recursion overhead in Insertion Sort

• O(n²), since they create auxiliary matrices

Answer explanation

Both algorithms rearrange the input array without needing extra data structures (beyond a few temporary variables), so their extra space complexity is O(1).

For Insertion Sort, the average-case number of comparisons on an array of n distinct elements is approximately:

• n(n – 1)/2

• n²/4

• n log n

• n/2

Answer explanation

A probabilistic analysis shows that, on average, Insertion Sort performs about n²/4 comparisons. This result comes from averaging the cost of inserting each element into the sorted portion.

Stability is a critical property in sorting when elements have secondary keys. Which of the following is true regarding stability for the two algorithms in their standard implementations?

• Both Insertion Sort and Selection Sort are stable by default.

• Insertion Sort is stable by default, while Selection Sort is not stable unless modified.

• Selection Sort is stable by default, while Insertion Sort is not.

• Neither is stable, and both require additional mechanisms to ensure stability.

Answer explanation

Insertion Sort is inherently stable because it inserts elements without disrupting the relative order of equal items. Standard Selection Sort, however, may swap non-adjacent elements and thus is not stable without modifications.

If the cost of a write (swap or move) is significantly higher than that of a comparison, which algorithm is more attractive for systems with expensive write operations, and why?

• Insertion Sort, because it minimizes comparisons.

• Selection Sort, because it performs at most n – 1 swaps.

• Insertion Sort, because it always runs in O(n) time.

• Selection Sort, because it avoids any swaps on nearly sorted data.

Answer explanation

Since Selection Sort performs at most n – 1 swaps regardless of the input (while its comparisons remain O(n²)), it is more attractive in environments where writes are costly, even though its number of comparisons is high.

Analyzing the loop invariants of the two algorithms, which of the following best describes how they gradually build the sorted portion of the array?

• Insertion Sort builds a sorted portion at the beginning by shifting elements, while Selection Sort builds it by repeatedly selecting the maximum element from the unsorted portion.

• Insertion Sort builds a sorted portion at the end of the array, while Selection Sort creates a sorted subarray in the middle.

• Insertion Sort builds the sorted portion from the beginning by inserting each element in its proper place, whereas Selection Sort repeatedly finds the minimum element from the unsorted portion and swaps it with the first unsorted element.

• Both algorithms build the sorted portion by performing adjacent swaps until the entire array is sorted.

Answer explanation

In Insertion Sort, the algorithm maintains a sorted subarray at the beginning and inserts each new element into its proper location. In Selection Sort, the algorithm finds the smallest element in the unsorted region and swaps it with the element at the beginning of that region, thereby growing the sorted portion from the front.

For Quick Sort, which pivot selection strategy is known to reduce the chance of encountering worst-case O(n²) performance on nearly sorted inputs?

• Always selecting the first element

• Always selecting the last element

• Randomized pivot selection

• Median-of-three pivot selection

Answer explanation

The median-of-three technique chooses the pivot as the median of the first, middle, and last elements. This heuristic tends to avoid poor partitions—especially on nearly sorted arrays—thereby reducing the probability of worst-case behavior.