Sorting Algorithms FRQ Practice

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

Question 1 of 5

A lantern crew stores hang times in an ArrayList and runs min-based selectionSort.

public static void selectionSort(ArrayList<Integer> data)
{
    for (int i = 0; i < data.size() - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < data.size(); j++)
        {
            if (data.get(j) < data.get(minIndex))
            {
                minIndex = j;
            }
        }
        int temp = data.get(i);
        data.set(i, data.get(minIndex));
        data.set(minIndex, temp);
    }
}

ArrayList<Integer> hang = new ArrayList<Integer>();
hang.add(5);
hang.add(1);
hang.add(8);
hang.add(3);
Pass List after the pass Value swapped into the next left slot
1
2
3

(a) Complete the table for all three passes. (b) Identify the two indexes swapped on pass 2. (c) Explain why the value placed on the left during pass 1 will not move again.

Question 2 of 5

Cider-mill barrel ages start as {7, 4, 9, 2} and are sorted with insertionSort.

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, after pass 2, and after pass 3. (b) After pass 1, is 4 in its final sorted index? Justify with the later array. (c) Describe how the sorted prefix grows, and note that an inserted value is in the correct place among that prefix only.

Question 3 of 5

Tide markers are sorted by placing the largest remaining value into the next right-hand final slot.

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

int[] marks = {8, 3, 10, 6};
Pass i in the outer loop Array after the swap
1 3
2 2
3 1

(a) Complete the after-swap column. (b) After pass 1, which index holds a value that is already in its final sorted position? (c) Explain how this max-based pass differs from min-based selection that fills the left side first.

Question 4 of 5

The same starting array {5, 2, 8, 1, 4} is processed two ways: two passes of min-based selectionSort, and two passes of insertionSort.

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;
    }
}

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 two selection passes and after two insertion passes. (b) Which algorithm has already locked two values into finished sorted indexes? (c) Explain why the insertion result can still change at those same left indexes on a later pass.

Question 5 of 5

A loom logs thread lengths in an ArrayList and runs insertionSort. Complete the shift table, then explain the movement.

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> thread = new ArrayList<Integer>();
thread.add(9);
thread.add(6);
thread.add(4);
thread.add(8);
Pass Value being inserted Number of shifts List after the pass
1 6
2 4
3 8

(a) Fill the missing columns. (b) State the final list. (c) Explain why these passes shift elements in the sorted prefix rather than swapping the next value into a finished slot.