Searching and Sorting Algorithms Flashcards
6 cards from real AP CSA practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Searching and Sorting Algorithms flashcards as text
In insertion sort, how are elements processed?
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.
Which of the following sorts has average-case time complexity of O(n log n)?
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.
What does `Arrays.sort(arr)` use internally in Java for primitive arrays?
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.
How many comparisons does binary search make in the worst case on an array of 16 elements?
Answer: 4
Binary search on 16 elements: 16→8→4→2→1, taking log₂(16) = 4 comparisons in the worst case.
Which sort is stable (preserves relative order of equal elements) in AP CSA context?
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.
What is the best-case time complexity of bubble sort when the array is already sorted?
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.