Sorting Algorithms FRQ Practice

Responses receive AI feedback against a rubric after submission. Scores are practice estimates.

Question 1 of 5

A bakery records muffin-batch sizes, including a repeated 3, and runs min-based selectionSort.

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

int[] batches = {9, 3, 7, 3, 5};
Pass minIndex chosen Array after the swap
1
2
3
4

(a) Complete the table. If two copies of the minimum exist, use the leftmost remaining one. (b) Explain why pass 1 chooses index 1 rather than index 3. (c) State the final array.

Question 2 of 5

A ferry wait-time board stores minutes in an ArrayList and runs insertionSort.

public static void insertionSort(ArrayList<Integer> data)
{
    for (int i = 1; i < data.size(); i++)
    {
        int next = data.get(i);
        int j = i - 1;
        while (j >= 0 && data.get(j) > next)
        {
            data.set(j + 1, data.get(j));
            j--;
        }
        data.set(j + 1, next);
    }
}

ArrayList<Integer> wait = new ArrayList<Integer>();
wait.add(2);
wait.add(8);
wait.add(5);
wait.add(1);

(a) State the list after each of the three passes. (b) Identify the length of the sorted prefix after pass 2. (c) Explain one shift that happens when 1 is inserted.

Question 3 of 5

Kite-shop spar lengths are ranked largest to smallest with selectionSortMaxFront.

public static void selectionSortMaxFront(int[] data)
{
    for (int i = 0; i < data.length - 1; i++)
    {
        int maxIndex = i;
        for (int j = i + 1; j < data.length; j++)
        {
            if (data[j] > data[maxIndex])
            {
                maxIndex = j;
            }
        }
        int temp = data[i];
        data[i] = data[maxIndex];
        data[maxIndex] = temp;
    }
}

int[] spars = {5, 11, 4, 8};

(a) Show the array after pass 1, pass 2, and pass 3. (b) After pass 1, which index is already a final sorted position? (c) Name the pair of values swapped on pass 2.

Question 4 of 5

A student claims: after the first insertionSort pass, the leftmost value is always in its final sorted index. The starting array is {3, 5, 1}.

public static void insertionSort(int[] data)
{
    for (int i = 1; i < data.length; i++)
    {
        int next = data[i];
        int j = i - 1;
        while (j >= 0 && data[j] > next)
        {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = next;
    }
}

(a) State the array after pass 1 and after pass 2. (b) Use those results to accept or reject the claim. (c) Contrast this with one pass of min-based selectionSort on the same array.

Question 5 of 5

Orchard crate counts {1, 4, 3, 5} are sorted with min-based selectionSort. Some passes swap a value with itself.

public static void selectionSort(int[] data)
{
    for (int i = 0; i < data.length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < data.length; j++)
        {
            if (data[j] < data[minIndex])
            {
                minIndex = j;
            }
        }
        int temp = data[i];
        data[i] = data[minIndex];
        data[minIndex] = temp;
    }
}
Pass minIndex Did the contents change? Array after the pass
1
2
3

(a) Complete the table. (b) Explain what a swap with the same index means. (c) State whether the finished order is still produced.