Sorting Algorithms
Help Questions
AP Computer Science A › Sorting Algorithms
A programmer needs to use the binary search algorithm on a list of items. What is a necessary precondition for the list of items?
The list must be sorted.
The list must be stored in an ArrayList.
The list must not contain any duplicate values.
The list must contain a number of elements that is a power of two.
Explanation
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 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?
{4, 6, 8, 10}
{8, 10, 4, 6}
{4, 8, 10, 6}
{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}.
What is the characteristic behavior of the insertion sort algorithm when it is used to sort an array that is already in ascending order?
It performs a minimal number of comparisons and no shifts, exhibiting its best-case performance.
It fails to sort the array correctly and enters an infinite loop.
It performs the maximum number of comparisons and shifts, exhibiting its worst-case performance.
Its performance is identical to its performance on a randomly ordered array.
Explanation
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.
A programmer is choosing a sorting algorithm for a large dataset. The primary concern is ensuring the algorithm has a predictable and efficient runtime, even in the worst case. Which of the covered algorithms best fits this requirement?
Selection sort, because it always performs the same number of comparisons.
Insertion sort, because it is very fast on nearly sorted data.
Both selection sort and insertion sort, as their worst-case performance is identical.
Merge sort, because its worst-case performance is significantly better than that of selection or insertion sort.
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.
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)?
{2, 4, 5, 6, 8}
{2, 6, 8, 4, 5}
{2, 4, 8, 6, 5}
{4, 6, 8, 2, 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}.
In the merge sort algorithm, the merge step is responsible for combining two sorted subarrays into a single sorted array. If the two subarrays to be merged are {4, 8, 15} and {2, 9, 12}, what is the resulting merged array?
{2, 4, 9, 8, 12, 15}
{4, 8, 15, 2, 9, 12}
{2, 4, 8, 9, 12, 15}
{2, 9, 12, 4, 8, 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}.
An integer array data is initialized with the values {7, 3, 9, 4, 1}. The insertionSort method is called with data as the argument. What are the contents of data after three complete iterations of the outer for loop (the loop with variable j)?
{3, 4, 7, 9, 1}
{1, 3, 7, 4, 9}
{1, 3, 4, 7, 9}
{3, 7, 4, 9, 1}
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.
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?
Selection sort
Insertion sort
Merge sort
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.
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?
Approximately $$n^2 / 2$$ swaps in the worst case
Zero swaps in the best case
Exactly n swaps
Exactly n - 1 swaps
Explanation
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.
Which statement accurately compares selection sort and insertion sort?
Selection sort always performs fewer swaps than insertion sort in the worst case.
Selection sort is a recursive algorithm, while insertion sort is an iterative algorithm.
The number of comparisons made by both algorithms is independent of the initial order of elements.
Insertion sort is generally more efficient than selection sort for arrays that are already nearly sorted.
Explanation
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.