AP CSA Unit 4.15 MCQ Explanations

How to use this page: First try each question without looking at the explanation. Then compare your answer with the key and read why the other choices are not correct.

Answer Explanations

What is the main goal of a sorting algorithm?

AFind the first matching target

BReverse the array without comparing values

CRearrange values into a specified order

DRemove every duplicate value

Correct answer: C. Sorting rearranges an array or ArrayList into a specified order, either ascending from small to large or descending from large to small.

Explanation

The order has to be chosen before any tracing begins, because ascending and descending produce different intermediate states from the same starting data. Sorting changes positions but keeps the same values.

A is not correct: Stopping at the first value that matches a target leaves the rest of the collection in whatever order it started in, so nothing is arranged.
B is not correct: Reversing positions without comparing values ignores the ordering entirely, and no algorithm here can place a value without comparisons.
D is not correct: Sorting keeps the same values and only moves them, so no element is discarded and duplicates stay in the collection.

Selection sort repeatedly does which action?

ASwaps each adjacent pair exactly once

BFinds the smallest remaining item and places it in its correct position

CShifts larger prefix values right and inserts the current value

DChecks each value only for equality with a target

Correct answer: B. Selection sort's inner loop searches the unsorted suffix, stores the index of its smallest value in minIndex, and the outer-loop body then swaps that value into place.

Explanation

Selection sort fixes one position at a time by growing a sorted prefix on the left. After the jth outer-loop iteration, positions 0..j are in final sorted order, so each pass settles the next position permanently.

A is not correct: Selection sort performs one swap at the end of a pass, after the inner loop has searched the whole unsorted suffix, not a swap at every adjacent pair.
C is not correct: Shifting larger prefix values right and inserting the current value is insertion sort's method of moving data, which the section contrasts with selection sort's single swap.
D is not correct: Checking a value only for equality with a target never identifies which remaining value is smallest, so no position could be fixed.

Insertion sort builds what kind of region?

AA final sorted suffix on the right

BA sorted left portion

CAn unsorted left portion

DAlternating sorted positions

Correct answer: B. Insertion sort grows a sorted prefix, so after the jth outer-loop iteration positions 0..j on the left form a sorted region.

Explanation

The prefix is sorted relative to itself, but it is not final: later insertions may shift its values to the right. If j < a.length - 1, then a[j+1] is the next element to insert into that prefix.

A is not correct: The region that grows is on the left and is built by inserting a[j+1] into it, and a selection-sort pass is the one that fixes a position permanently.
C is not correct: The left portion is the part that is already sorted; the part that is not yet sorted lies to the right of it.
D is not correct: The sorted positions are the contiguous run 0..j, since each pass extends that prefix by one more element rather than settling scattered positions.

Which operation is common in insertion sort?

ASwapping the selected minimum directly with each comparison

BRestarting the sorted prefix at index 0 every pass

CShifting larger elements right to make room

DSwapping adjacent out-of-order values until no swaps remain

Correct answer: C. Insertion sort saves the current value in temp, shifts each larger prefix value one position to the right, and then inserts the saved value into the opening.

Explanation

The shifting is what makes room. Saving temp first and updating a[pos] during each shift prevents a value from being lost or duplicated, so the collection keeps the same values throughout.

A is not correct: Swapping a selected minimum into position is selection sort's move, and it happens once per pass after the search, not during insertion sort's shifting.
B is not correct: The sorted prefix grows across passes and is not rebuilt from index 0; each pass starts from the prefix the previous pass left behind.
D is not correct: Repeatedly swapping adjacent out-of-order values is not what the insertion-sort code does; its while loop copies a[pos - 1] forward and writes the saved value once at the end.

Why is tracing sorting algorithms carefully important?

AEvery value reaches its final position after the first pass.

BThe array changes after swaps or shifts.

COnly the loop variables change while the array stays fixed.

DThe outer-loop index always gives the array's final order.

Correct answer: B. Swaps and shifts change the collection as the algorithm runs, so its contents after one pass differ from both the original data and the final order.

Explanation

An intermediate state is the collection's contents before sorting is complete. AP questions may ask for the state after a particular outer-loop iteration, so the new state has to be recorded after every outer-loop pass.

A is not correct: Only the first position is settled by selection sort's first pass, and in insertion sort even prefix values may shift right during later passes.
C is not correct: The whole point of a pass is that values move: selection sort swaps a[j] with a[minIndex], and insertion sort writes into a[pos].
D is not correct: The outer-loop index only says which pass is running; the array's arrangement after that pass has to be traced from the swaps and shifts themselves.

Which algorithm usually uses a variable such as minIndex?

AInsertion sort

BLinear search

CBinary search

DSelection sort

Correct answer: D. In selection sort, the inner loop searches the unsorted suffix and stores the index of its smallest value in minIndex, which the swap then uses.

Explanation

Selection sort needs to remember where the smallest remaining value sits so that it can swap it with a[j] once the inner loop finishes. For descending order the comparison is reversed so the pass selects the largest remaining value instead.

A is not correct: Insertion sort tracks temp and pos instead, because it shifts values right and inserts the saved value rather than selecting a minimum to swap.
B is not correct: Selecting a minimum index across the unsorted suffix is not what the section attributes to that algorithm; minIndex appears only in the selection sort code.
C is not correct: The section introduces minIndex as part of selection sort's inner search over the unsorted suffix, not as part of that algorithm.

When sorting strings alphabetically, which condition detects that s comes before min?

As == min

Bs.compareTo(min) > 0

Cs.equals(min)

Ds.compareTo(min) < 0

Correct answer: D. compareTo returns a negative result when the calling string comes before the argument, so a result less than 0 means s comes first alphabetically.

Explanation

Numeric values can be ordered with <, but String objects use compareTo. Zero means the two strings are equal and a positive result means the calling string comes after the argument.

A is not correct: This compares the two references with == rather than asking which string comes first, so it gives no alphabetical ordering at all.
B is not correct: A positive result means the calling string comes after the argument, so this condition selects the later string instead of the earlier one.
C is not correct: equals only reports whether the strings match, which is the case compareTo signals with zero, and it never says which comes first.

What must be preserved after sorting?

AEvery element's original index

BThe same elements, rearranged into order

COnly one copy of each distinct value

DThe original comparison count

Correct answer: B. Sorting changes positions but keeps the same values, so the finished collection holds exactly the original elements arranged into the requested order.

Explanation

If a swap or shift overwrites a value before it is saved, the result is not a valid sorting of the original data. That is why insertion sort saves temp before shifting and selection sort saves a[j] before the swap.

A is not correct: Positions are exactly what sorting changes, so an element keeping its original index would mean the algorithm had not moved anything.
C is not correct: Nothing is removed by a swap or a shift, so repeated values still appear as many times as they did before sorting.
D is not correct: A count of comparisons is not part of the collection's contents, and the section asks that the values themselves be preserved through every pass.

Consider the following method. For {7, 2, 9, 1}, what does the array contain after the pass with j = 0 finishes?

public static void selectionSort(int[] a) {
    for (int j = 0; j < a.length - 1; j++) {
        int minIndex = j;
        for (int k = j + 1; k < a.length; k++) {
            if (a[k] < a[minIndex]) {
                minIndex = k;
            }
        }
        int temp = a[j];
        a[j] = a[minIndex];
        a[minIndex] = temp;
    }
}

A{1, 2, 9, 7}

B{1, 2, 7, 9}

C{2, 7, 9, 1}

D{1, 7, 9, 2}

Correct answer: A. With j = 0 the inner loop searches indexes 1 through 3 and leaves minIndex at the index of 1, which is then swapped with 7.

Explanation

A pass is one complete iteration of the outer loop, and selection sort makes a single swap at the end of it. The swap sends 7 to the position the smallest value vacated, so only two positions change.

B is not correct: This is the fully sorted array, but one pass of the outer loop fixes only position 0; the remaining positions are still the unsorted suffix.
C is not correct: This is what shifting the prefix right and inserting the saved value produces, not what a single swap of a[j] and a[minIndex] produces.
D is not correct: This moves 2 to the end, but the swap exchanges only a[j] and a[minIndex], and 2 sits at neither of those indexes.

Q10

Consider the following method. For {7, 2, 9, 1}, what does the array contain after the pass with j = 1 finishes?

public static void insertionSort(int[] a) {
    for (int j = 1; j < a.length; j++) {
        int temp = a[j];
        int pos = j;

        while (pos > 0 && temp < a[pos - 1]) {
            a[pos] = a[pos - 1];
            pos--;
        }
        a[pos] = temp;
    }
}

A{1, 2, 7, 9}

B{7, 2, 9, 1}

C{2, 7, 9, 1}

D{2, 7, 1, 9}

Correct answer: C. With j = 1 the saved value is smaller than the value before it, so that larger value shifts one position right and the saved value is inserted at index 0.

Explanation

The while loop stops as soon as pos reaches 0 or the saved value is no longer smaller than a[pos - 1]. Only the prefix through index j can change during a pass.

A is not correct: This is the fully sorted array, but the pass with j = 1 inserts only one element into the prefix; the later elements have not been inserted yet.
B is not correct: This is the starting array, which would mean no shift happened, but the saved value is smaller than the value before it so the while condition is true.
D is not correct: The last two positions lie beyond index j, and insertion sort's pass only shifts values inside the prefix and writes the saved value into a[pos].

Q11

Two sorting methods are applied to the same array. Which statement correctly identifies the two methods?

Starting array:  {6, 4, 8, 2}

After one outer pass:
  Method 1 -> {2, 4, 8, 6}
  Method 2 -> {4, 6, 8, 2}

AMethod 1 is insertion sort, and Method 2 is selection sort.

BMethod 1 is selection sort, and Method 2 is insertion sort.

CBoth methods are selection sort, run in different directions.

DBoth methods are insertion sort, run in different directions.

Correct answer: B. Method 1's result shows one swap that brought the smallest remaining value to the front, while Method 2's result shows a larger prefix value shifted right so the next element could be inserted.

Explanation

A selection-sort pass fixes the next position permanently with a single swap, so the value that used to sit at index 0 reappears at the index the minimum vacated. An insertion-sort pass changes only the prefix through index j, leaving the rest of the array untouched.

A is not correct: The labels are exchanged: shifting the prefix and inserting is insertion sort's move, and moving the smallest remaining value into place with one swap is selection sort's.
C is not correct: The two results are not the same kind of change; one swaps a value in from the far end while the other leaves the last position untouched.
D is not correct: Insertion sort does not exchange a value with the end of the array, so the result whose last element changed cannot come from an insertion-sort pass.

Q12

Consider the following method. Which statement completes the swap?

public static void sort(ArrayList<Integer> a) {
    for (int j = 0; j < a.size() - 1; j++) {
        int min = j;
        for (int k = j + 1; k < a.size(); k++) {
            if (a.get(k) < a.get(min)) {
                min = k;
            }
        }
        Integer temp = a.get(j);
        ______
        a.set(min, temp);
    }
}

Aa.add(j,a.get(min));

Ba.set(min,a.get(j));

Ca.get(j)=a.get(min);

Da.set(j,a.get(min));

Correct answer: D. For an ArrayList, replacing a stored element is done with set, so the missing line writes the minimum's value into position j.

Explanation

Sorting an ArrayList still comes down to indexes, swaps, and shifts; the difference is syntax, so use get and set instead of brackets. Since temp already holds the old value at j, overwriting position j is safe and the following line finishes the swap.

A is not correct: add inserts a new element at that index rather than replacing one, which changes the size of the list instead of exchanging two values.
B is not correct: This writes into position min, and the very next line writes temp there as well, so the value selected as the minimum never reaches position j.
C is not correct: get returns an element rather than naming a storage location, so it cannot appear on the left of an assignment the way brackets can.

Q13

Consider the following method, which counts the shifts performed by insertion sort. What is returned for an array that is already in ascending order?

public static int countShifts(int[] a) {
    int shifts = 0;
    for (int j = 1; j < a.length; j++) {
        int temp = a[j];
        int i = j;
        while (i > 0 && temp < a[i - 1]) {
            a[i] = a[i - 1];
            shifts++;
            i--;
        }
        a[i] = temp;
    }
    return shifts;
}

Athe number of elements in the array

Bone less than the number of elements

C0

D1

Correct answer: C. For data already in ascending order the saved value is never smaller than the value before it, so the while condition fails immediately on every pass and shifts is never incremented.

Explanation

The counter is increased only inside the while loop, which runs one shift at a time. This is the situation the trace describes when a value already fits and no shift is needed.

A is not correct: The counter starts at 0 and rises only when a shift actually happens, so it cannot end up matching the number of elements when nothing moves.
B is not correct: The outer loop does run a.length - 1 times, but entering a pass is not the same as shifting; the body of the while loop is what increments the counter.
D is not correct: Not even one shift occurs, because temp < a[i - 1] is false on the first check of every pass when the data is already ascending.

What to review next

Practice tracing both algorithms on the same short array and writing down the collection after each outer-loop pass, not just the final order. For selection sort, check that the inner loop starts at j + 1 and runs while k < a.length, and confirm that positions 0..j are final after the jth pass. For insertion sort, check that the outer loop uses j < a.length so the last element is not skipped, and follow how temp is saved before the shifts write into a[pos]. Then repeat the selection sort trace on an ArrayList version, replacing brackets with get and set and replacing < with compareTo for String elements.