- Which of the following statements best describes the divide-and-conquer strategy used by the merge sort algorithm?
Answer: It repeatedly divides the list in half until it has lists of size one, then merges them back together in sorted order.
Merge sort is a classic example of a divide-and-conquer algorithm. It recursively breaks down the problem (sorting a list) into smaller, identical subproblems (sorting halves of the list) until they become trivial (a list of one is sorted), and then combines the results.
- A selection sort algorithm is modified to sort in descending order instead of ascending order. Given the array [3, 9, 1, 7, 5], after exactly 2 passes of this modified selection sort, what will be the state of the array?
Answer: [9, 7, 1, 3, 5] with the first two positions correctly sorted
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.
- In a standard implementation of the insertion sort algorithm, what is the purpose of the inner loop (or a loop-like structure such as a
while statement)? Answer: To shift elements in the sorted portion of the array to make space for the element being inserted.
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.
- In a merge sort algorithm, two sorted subarrays [4, 8, 15, 23] and [7, 12, 18] are being merged. The merge process uses two pointers, initially at the beginning of each subarray. After exactly 4 comparison operations during the merge, which elements will have been placed into the result array?
Answer: [4, 7, 8, 12] with pointers at 15 and 18
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.
- An insertion sort algorithm is processing the array [10, 5, 15, 3, 12]. The algorithm has just completed inserting the element at index 3 (value 3) into its correct position. If the next step processes the element at index 4, how many element shifts will occur during this next insertion?
Answer: 1 shift, moving only the element 15 to the right
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.
- Which sorting algorithm operates by building up a sorted subsection of the list one item at a time, taking the next item from the unsorted section and inserting it into its correct position within the sorted section?
Answer: Insertion sort
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.
- The selection sort algorithm is applied to the array
{3, 8, 2, 5, 1, 4}. What is the state of the array immediately after the call to swap elements for the third time? Answer: {1, 2, 3, 5, 8, 4}
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.
- Consider sorting the array
{1, 2, 3, 4, 5}. Which of the following sorting algorithms will complete its process with the FEWEST number of element value comparisons? Answer: Insertion sort
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.
- What is the characteristic behavior of the insertion sort algorithm when it is used to sort an array that is already in ascending order?
Answer: It performs a minimal number of comparisons and no shifts, exhibiting its best-case performance.
For an already sorted array, insertion sort is highly efficient. In each pass, it compares the current element only with the one before it and finds it is in the correct place, requiring no shifts. This is its best-case scenario.
- Which statement accurately compares selection sort and insertion sort?
Answer: Insertion sort is generally more efficient than selection sort for arrays that are already nearly sorted.
Insertion sort's performance improves as the array becomes more sorted. For a nearly sorted array, it performs very few shifts and comparisons, making it more efficient than selection sort, whose number of comparisons is always the same regardless of the initial order.
- A programmer needs to use the binary search algorithm on a list of items. What is a necessary precondition for the list of items?
Answer: The list must be sorted.
Binary search works by repeatedly dividing the search interval in half. This process only works correctly if the list is sorted, allowing the algorithm to eliminate half of the remaining elements in each step.
- An insertion sort algorithm is being traced through an array of integers. At a certain point during execution, the array appears as [2, 5, 7, 11, 3, 8, 1, 9]. The next element to be inserted is currently at index 4 (value 3). After this insertion step is completed, which statement about the array's state is most accurate?
Answer: Elements 5, 7, 11 will shift one position to the right, and 3 will be placed at index 1
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.
- Consider the selection sort algorithm sorting an array of
n distinct elements into ascending order. What is the total number of swaps performed by the algorithm in all cases? Answer: Exactly n - 1 swaps
Selection sort performs exactly one swap at the end of each pass of its outer loop, even if an element is swapped with itself. Since there are n - 1 passes, there are n - 1 swaps.
- A hybrid sorting algorithm uses insertion sort for subarrays of size 5 or smaller, and quicksort for larger arrays. Given an array of 12 elements that gets partitioned by quicksort into subarrays of sizes 4, 1, and 7, which statement best describes what happens next in the sorting process?
Answer: The subarray of size 4 uses insertion sort, size 1 needs no sorting, size 7 uses quicksort
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.
- An
ArrayList of Integer objects, list, initially contains {10, 8, 4, 6}. If a standard insertion sort algorithm is applied to list, what is the content of list after the second pass of the outer loop completes? Answer: {4, 8, 10, 6}
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}.
- A program needs to maintain a sorted list of high scores. As new scores are generated, they are added to the list, which must remain sorted. The logic of which sorting algorithm is most analogous to the process of adding a new score to the already sorted list?
Answer: Insertion sort
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.
- After
k passes of the outer loop of a selection sort algorithm that sorts an array into ascending order, which of the following is guaranteed to be true? Answer: The first k elements of the array are the k smallest elements and are in their final sorted positions.
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.
- An integer array
nums is initialized with the values {6, 4, 8, 2, 5}. The selectionSort method is called with nums as the argument. What are the contents of nums after two complete iterations of the outer for loop (the loop with variable j)? Answer: {2, 4, 8, 6, 5}
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}.
- The merge sort algorithm is applied to the array
{8, 3, 5, 1, 4, 6, 2, 7}. What are the contents of the two subarrays that are combined during the final merge step of the algorithm? Answer: {1, 3, 5, 8} and {2, 4, 6, 7}
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.
- After
k passes of the outer loop of an insertion sort algorithm (where the loop runs from index 1 to length - 1) that sorts an array into ascending order, which of the following is guaranteed to be true? Answer: The first k + 1 elements of the array are sorted relative to one another.
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.
