AP CSA Searching and Sorting Algorithms 2 — Questions and Answers
Question 1: In insertion sort, how are elements processed?
- Each element is inserted into its correct position among already-sorted elements (Correct answer)
- Adjacent elements are swapped if out of order
- The minimum is selected and moved front
- The array is recursively divided
Correct answer: Each element is inserted into its correct position among already-sorted elements
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)?
- Merge sort (Correct answer)
- Bubble sort
- Selection sort
- Insertion sort
Correct answer: Merge sort
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?
- A variant of quicksort (dual-pivot quicksort) (Correct answer)
- Merge sort
- Bubble sort
- Insertion sort
Correct answer: A variant of quicksort (dual-pivot quicksort)
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?
- 4 (Correct answer)
- 16
- 8
- 2
Correct answer: 4
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?
- Merge sort (Correct answer)
- Selection sort
- Quicksort
- Heap sort
Correct answer: Merge sort
Merge sort is stable because equal elements are never swapped past each other during the merge step, preserving their original relative order.
Question 6: What is the best-case time complexity of bubble sort when the array is already sorted?
- O(n) (Correct answer)
- O(n²)
- O(log n)
- O(1)
Correct answer: O(n)
An optimized bubble sort can detect no swaps occurred in a pass and terminate early, giving O(n) for an already-sorted array.
AP CSA Searching and Sorting Algorithms 2
In insertion sort, how are elements processed?