AP Computer Science a Quiz: Sorting Algorithms

What this quiz covers

This quiz focuses on Sorting Algorithms, giving you a quick way to practice the rules, question types, and explanations that matter most for AP Computer Science a.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

Question 1

1. {8, 10, 4, 6}
2. {4, 8, 10, 6} (correct answer)
3. {4, 6, 8, 10}
4. {4, 10, 8, 6}

Explanation: The initial list is {10, 8, 4, 6}. The first pass inserts 8, resulting in {8, 10, 4, 6}. The second pass takes the next element, 4, and inserts it into the sorted portion {8, 10}. This results in {4, 8, 10, 6}.

Question 2

1. Selection sort, because it always performs the same number of comparisons.
2. Insertion sort, because it is very fast on nearly sorted data.
3. Merge sort, because its worst-case performance is significantly better than that of selection or insertion sort. (correct answer)
4. Both selection sort and insertion sort, as their worst-case performance is identical.

Explanation: While selection sort's comparison count is predictable, its overall runtime complexity is O($n^2$). Insertion sort's worst-case is also O($n^2$). Merge sort has a worst-case runtime of O(n log n), which is much more efficient for large datasets than O($n^2$), making it the best choice for predictable, efficient performance.

Question 3

1. {2, 4, 8, 6, 5} (correct answer)
2. {4, 6, 8, 2, 5}
3. {2, 4, 5, 6, 8}
4. {2, 6, 8, 4, 5}

Explanation: In the first pass (j=0), the smallest element (2) is found and swapped with the element at index 0. The array becomes {2, 4, 8, 6, 5}. In the second pass (j=1), the smallest element in the rest of the array (4) is already at index 1, so it is swapped with itself. The array remains {2, 4, 8, 6, 5}.

Question 4

1. {4, 8, 15, 2, 9, 12}
2. {2, 4, 8, 9, 12, 15} (correct answer)
3. {2, 9, 12, 4, 8, 15}
4. {2, 4, 9, 8, 12, 15}

Explanation: The merge process compares the first elements of each subarray and adds the smaller one to the result. It repeats this until all elements from both subarrays are in the result. The correct merged sequence is {2, 4, 8, 9, 12, 15}.

Question 5

1. [4, 7, 8, 12] with pointers at 15 and 18 (correct answer)
2. [4, 7, 8, 15] with pointers at 23 and 12
3. [4, 7, 8, 12] with pointers at 23 and 18
4. [4, 7, 8] with pointers at 15 and 12

Explanation: Comparison 1: 4 vs 7 → add 4, advance first pointer. Comparison 2: 8 vs 7 → add 7, advance second pointer. Comparison 3: 8 vs 12 → add 8, advance first pointer. Comparison 4: 15 vs 12 → add 12, advance second pointer. Result: [4, 7, 8, 12] with pointers at 15 and 18. Choice B incorrectly adds 15 instead of 12 in the 4th step. Choice C shows correct result but wrong pointer position for first array. Choice D stops one comparison early.

Question 6

1. Selection sort
2. Insertion sort (correct answer)
3. Merge sort
4. Binary sort

Explanation: This description accurately defines insertion sort. Selection sort finds the minimum and swaps. Merge sort divides and conquers. Binary search (not a sort) finds an element in a sorted list.

Question 7

1. To identify the index of the largest value in the sorted portion of the array.
2. To recursively call the sort method on the unsorted portion of the array.
3. To swap the current element with the first element of the array if it is smaller.
4. To shift elements in the sorted portion of the array to make space for the element being inserted. (correct answer)

Explanation: The outer loop of insertion sort selects an element from the unsorted portion. The inner loop then works backward from that element's position through the sorted portion, shifting elements to the right until the correct spot for the selected element is found.

Question 8

1. Selection sort
2. Merge sort
3. Insertion sort (correct answer)
4. A linear search followed by a swap

Explanation: Insertion sort works by taking an element and inserting it into an already sorted sublist. This is directly analogous to taking a new high score and finding its correct place within the existing sorted list of scores.

Question 9

1. The first k + 1 elements of the array are sorted relative to one another. (correct answer)
2. The first k + 1 elements are the smallest k + 1 elements in the entire array.
3. The last k + 1 elements are in their final, sorted positions.
4. The entire array is sorted except for the last k + 1 elements.

Explanation: The invariant for insertion sort is that after k passes (corresponding to inserting the element at original index k), the first k+1 elements (from index 0 to k) form a sorted subarray. However, these are not necessarily the smallest elements of the entire array.

Question 10

1. The first k elements are sorted relative to each other but are not necessarily the k smallest elements.
2. The last k elements of the array are in their final sorted positions.
3. The first k elements of the array are the k smallest elements and are in their final sorted positions. (correct answer)
4. The element at index k is smaller than all elements at indices greater than k.

Explanation: The defining property (or invariant) of selection sort is that after the k-th pass, the first k positions of the array are filled with the k smallest elements of the array in sorted order. These elements will not be moved again.

Question 11

1. {8, 3, 5, 1}and{4, 6, 2, 7}
2. {1, 3, 5, 8}and{2, 4, 6, 7} (correct answer)
3. {1, 2, 3, 4}and{5, 6, 7, 8}
4. {3, 8, 1, 5}and{4, 6, 2, 7}

Explanation: Merge sort first splits the array into {8, 3, 5, 1} and {4, 6, 2, 7}. It then recursively sorts each half. The sorted left half becomes {1, 3, 5, 8}, and the sorted right half becomes {2, 4, 6, 7}. The final step is to merge these two sorted subarrays.

Question 12

1. Selection sort
2. Insertion sort (correct answer)
3. Merge sort
4. Both selection sort and insertion sort will perform the same number of comparisons.

Explanation: For an already sorted array (best-case scenario), insertion sort is extremely efficient. It will make only n-1 comparisons. Selection sort and merge sort will perform the same number of comparisons as they would for any other array of the same size, which is significantly more than n-1.

Question 13

1. Selection sort will perform zero swaps because the minimum is always at the end of the unsorted section.
2. Insertion sort will perform the maximum number of shifts and comparisons for an array of this size. (correct answer)
3. Merge sort will require no recursive calls because the array is already ordered in a specific way.
4. Insertion sort will perform zero shifts because each element is already in its correct relative position.

Explanation: A reverse-sorted array is the worst-case input for insertion sort. For each element to be inserted, it must be compared with and shifted past every element in the already-sorted subsection, leading to the maximum number of operations.

Question 14

1. {1, 2, 3, 5, 8, 4} (correct answer)
2. {1, 2, 8, 5, 3, 4}
3. {1, 2, 3, 4, 5, 8}
4. {1, 2, 4, 5, 3, 8}

Explanation: 1st swap (j=0): min is 1, swap with 3 -> {1, 8, 2, 5, 3, 4}. 2nd swap (j=1): min is 2, swap with 8 -> {1, 2, 8, 5, 3, 4}. 3rd swap (j=2): min is 3, swap with 8 -> {1, 2, 3, 5, 8, 4}. This is the state after the third swap completes.

Question 15

1. [2, 4, 1, 5, 6, 8] with pivot 5 now at index 3
2. [6, 2, 4, 1, 5, 8] with pivot 5 now at index 4
3. [2, 4, 1, 5, 8, 6] with pivot 5 now at index 3 (correct answer)
4. [4, 2, 1, 5, 6, 8] with pivot 5 now at index 3

Explanation: With pivot 5 (last element), partitioning should place all elements ≤ 5 to the left and all elements > 5 to the right. Elements ≤ 5: [2, 4, 1] and elements > 5: [6, 8]. After partitioning: [2, 4, 1, 5, 8, 6] or similar arrangement with pivot at index 3. Choice A incorrectly places 6 before the pivot. Choice B doesn't move the pivot to its correct position. Choice D is missing element 8.

Question 16

1. 0 shifts, because 12 is already in correct position
2. 3 shifts, moving elements 5, 10, and 15 to the right
3. 2 shifts, moving elements 10 and 15 to the right
4. 1 shift, moving only the element 15 to the right (correct answer)

Explanation: When you encounter insertion sort questions, focus on understanding that the algorithm builds a sorted portion from left to right, inserting each new element into its correct position within the already-sorted section. After inserting the element at index 3 (value 3), the array looks like [3, 5, 10, 15, 12]. The first four elements are now sorted, and we're ready to process the element at index 4, which has value 12. To insert 12 into the sorted portion [3, 5, 10, 15], we compare it with elements from right to left. First, 12 < 15, so 15 shifts one position right. Next, 12 > 10, so we stop—12 belongs between 10 and 15. This requires exactly one shift. Looking at the wrong answers: Choice A incorrectly assumes 12 is already in position, but insertion sort must still compare and potentially move elements even when the final position doesn't change much. Choice B suggests 3 shifts, which would happen if 12 were smaller than 5, requiring all elements from 5 onward to move. Choice C proposes 2 shifts, which would occur if 12 were smaller than 10 but larger than 5, requiring both 10 and 15 to move. The correct answer is D—only 15 needs to shift right to make room for 12. Study tip: When tracing insertion sort, always work backwards through the sorted portion, counting each element that's larger than your target value. Each larger element represents one shift operation.

Question 17

1. All three subarrays will be sorted using insertion sort since they're all ≤ 7 elements
2. The size 1 subarray is ignored, while sizes 4 and 7 both use quicksort recursively
3. Only the subarray of size 7 continues with quicksort, others use insertion sort
4. The subarray of size 4 uses insertion sort, size 1 needs no sorting, size 7 uses quicksort (correct answer)

Explanation: When you encounter hybrid sorting algorithms, focus on understanding the decision criteria that determine which algorithm to use at each step. Hybrid algorithms combine different sorting methods to optimize performance by leveraging each algorithm's strengths. In this problem, the hybrid algorithm uses a size threshold of 5 elements: insertion sort for arrays with 5 or fewer elements, and quicksort for larger arrays. After the initial quicksort partition creates subarrays of sizes 4, 1, and 7, you need to apply the size rule to each subarray independently. The correct approach is option D: the size-4 subarray uses insertion sort (4 ≤ 5), the size-1 subarray needs no sorting (already sorted by definition), and the size-7 subarray continues with quicksort (7 > 5). Option A incorrectly assumes that being "≤ 7 elements" matters, but the threshold is 5, not 7. Option B makes two errors: it ignores the size-1 subarray correctly but wrongly applies quicksort to the size-4 subarray, which should use insertion sort since 4 ≤ 5. Option C correctly identifies that only the size-7 subarray continues with quicksort, but it incorrectly states that "others use insertion sort" when the size-1 subarray doesn't need any sorting algorithm. Remember that in hybrid sorting problems, always check each subarray's size against the specified threshold independently. Single-element arrays are automatically sorted and require no further processing, while larger subarrays follow the algorithm's size-based rules.

Question 18

1. [9, 7, 1, 3, 5] with the first two positions correctly sorted (correct answer)
2. [9, 7, 5, 1, 3] with all elements in final sorted order
3. [9, 5, 1, 7, 3] with maximum elements moved to front
4. [7, 9, 1, 3, 5] with first pass finding second maximum

Explanation: Pass 1: Find maximum (9) in entire array, swap with first position: [9, 3, 1, 7, 5]. Pass 2: Find maximum (7) in remaining portion [3, 1, 7, 5], swap with second position: [9, 7, 1, 3, 5]. Choice B shows the complete sorted array after all passes. Choice C shows an incorrect arrangement after pass 2. Choice D incorrectly suggests finding the second maximum in the first pass.

Question 19

1. {1, 3, 4, 7, 9}
2. {3, 4, 7, 9, 1} (correct answer)
3. {3, 7, 4, 9, 1}
4. {1, 3, 7, 4, 9}

Explanation: Pass 1 (j=1): Insert 3 -> {3, 7, 9, 4, 1}. Pass 2 (j=2): Insert 9 (no change) -> {3, 7, 9, 4, 1}. Pass 3 (j=3): Insert 4 -> {3, 4, 7, 9, 1}. This is the state of the array after the third pass completes.

Question 20

1. Elements 2, 5, 7, 11 will all shift one position to the right, and 3 will be placed at index 0
2. Elements 5, 7, 11 will shift one position to the right, and 3 will be placed at index 1 (correct answer)
3. Elements 7 and 11 will shift one position to the right, and 3 will be placed at index 2
4. Only element 11 will shift one position to the right, and 3 will be placed at index 3

Explanation: In insertion sort, element 3 needs to find its correct position in the already sorted portion [2, 5, 7, 11]. Since 3 > 2 but 3 < 5, it should be inserted between 2 and 5. This means 5, 7, and 11 must shift right, and 3 goes to index 1. Choice A incorrectly assumes 3 goes before 2. Choice C assumes 3 goes between 5 and 7. Choice D assumes 3 goes between 7 and 11.