AP CSA Searching and Sorting Algorithms 2

Question 1

In insertion sort, how are elements processed?

Accepted Answer

Each element is inserted into its correct position among already-sorted elements

Answer

Insertion sort builds a sorted portion by taking each new element and inserting it at the correct position in the already-sorted left portion.

Question 2

Which of the following sorts has average-case time complexity of O(n log n)?

Accepted Answer

Merge sort

Answer

Merge sort divides the array in half recursively and merges in O(n) time per level, giving O(n log n) overall.

Question 3

What does `Arrays.sort(arr)` use internally in Java for primitive arrays?

Accepted Answer

A variant of quicksort (dual-pivot quicksort)

Answer

Java's Arrays.sort() for primitives uses a dual-pivot quicksort, which provides excellent average-case performance in practice.

Question 4

How many comparisons does binary search make in the worst case on an array of 16 elements?

Accepted Answer

4

Answer

Binary search on 16 elements: 16→8→4→2→1, taking log₂(16) = 4 comparisons in the worst case.

Question 5

Which sort is stable (preserves relative order of equal elements) in AP CSA context?

Accepted Answer

Merge sort

Answer

Merge sort is stable because equal elements are never swapped past each other during the merge step, preserving their original relative order.

AP CSA - Advanced Placement Computer Science A Practice Test