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
What is the key operation that makes binary search efficient compared to linear search?
Answer: Eliminating half the remaining elements with each comparison
Binary search eliminates half the search space with each comparison by using the sorted order to discard the irrelevant half.
Which sorting algorithm is most efficient for nearly-sorted arrays?
Answer: Insertion sort
Insertion sort performs very few swaps on nearly-sorted data and approaches O(n) performance in that case.
In the AP CSA exam, what is the standard way to search for a value in an unsorted ArrayList?
Answer: Sequential (linear) search
An unsorted ArrayList requires sequential search since binary search requires sorted data, and ArrayList has no built-in hash lookup.
What does `Collections.sort(list)` require of the objects in the list?
Answer: They must implement the Comparable interface
Collections.sort() uses the natural ordering defined by the Comparable interface's compareTo method on the list's elements.
How many passes does selection sort make over an array of n elements?
Answer: n-1
Selection sort makes n-1 passes because after n-1 placements the last element is automatically in place, requiring no additional pass.
What is the output of a correctly implemented binary search when the target is not in the array in AP CSA conventions?
Answer: -1
By convention in AP CSA, a binary search returns -1 (or a negative value) to indicate the target was not found in the array.