Sorting and Efficiency

All 15 sorting and efficiency questions

Work through the interactive quiz above first. This is the full sorting and efficiency question set with worked solutions, so students can review any question after attempting it.

1. 1.Code Tracing 01 - Sorting and Efficiency: track the final printed value.

   int[] data = {4, 9, 2, 7, 5, 1};
   int swaps = 0;
   for (int i = 0; i < data.length - 1; i++) {
     for (int j = 0; j < data.length - 1 - i; j++) {
       if (data[j] > data[j + 1]) {
         int t = data[j];
         data[j] = data[j + 1];
         data[j + 1] = t;
         swaps++;
       }
     }
   }
   System.out.print(swaps);

   • 0
   • 10
   • 6
   • 11
   Show worked solution

   Correct answer: 10

   Bubble sort swaps once for every out-of-order adjacent pair it encounters, so the count depends on how unsorted the data was.

2. 2.Code Tracing 12 - Sorting and Efficiency: follow the variable updates.

   int[] data = {6, 7, 4, 9, 7, 3};
   int passes = 0;
   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 t = data[i]; data[i] = data[minIndex]; data[minIndex] = t;
     passes++;
   }
   System.out.print(passes + ":" + data[0]);

   • 5:6
   • 5:9
   • 5:3
   • 6:3
   Show worked solution

   Correct answer: 5:3

   Selection sort always runs exactly length - 1 passes regardless of the starting order, and the smallest value lands first.

3. 3.Code Tracing 28 - Sorting and Efficiency: trace the branch and loop path.

   int[] data = {9, 7, 2, 8, 10, 6};
   for (int i = 1; i < data.length; i++) {
     int key = data[i];
     int j = i - 1;
     while (j >= 0 && data[j] > key) {
       data[j + 1] = data[j];
       j--;
     }
     data[j + 1] = key;
   }
   System.out.print(data[0] + ":" + data[data.length - 1]);

   • 10:2
   • 2:2
   • 2:10
   • 9:6
   Show worked solution

   Correct answer: 2:10

   Insertion sort shifts larger values right until the key finds its slot, leaving the array fully ordered.

4. 4.Code Tracing 39 - Sorting and Efficiency: watch the index changes.

   int[] data = {11, 8, 4, 10, 6, 8};
   for (int i = 0; i < 2; i++) {
     for (int j = 0; j < data.length - 1 - i; j++) {
       if (data[j] > data[j + 1]) {
         int t = data[j];
         data[j] = data[j + 1];
         data[j + 1] = t;
       }
     }
   }
   System.out.print(data[data.length - 1] + ":" + data[data.length - 2]);

   • 8:6
   • 4:8
   • 4:11
   • 11:10
   Show worked solution

   Correct answer: 11:10

   After only two bubble passes the array is not fully sorted, but the two largest values have already settled at the end.

5. 5.Code Tracing 50 - Sorting and Efficiency: evaluate the state change step by step.

   int small = 13;
   int large = 26;
   int smallWork = small * small;
   int largeWork = large * large;
   System.out.print(largeWork / smallWork);

   • 4
   • 2
   • 13
   • 1
   Show worked solution

   Correct answer: 4

   A quadratic algorithm does roughly n-squared work, so doubling the input size multiplies the work by four.

6. 6.What is printed by the following code segment?

   int[] a = {29, 10, 14, 37, 13};
   for (int i = 0; i < 2; i++)
   {
       int m = i;
       for (int j = i + 1; j < a.length; j++)
       {
           if (a[j] < a[m]) { m = j; }
       }
       int t = a[i];
       a[i] = a[m];
       a[m] = t;
   }
   System.out.print(a[0] + " " + a[1] + " " + a[4]);

   • 10 13 29
   • 10 13 37
   • 10 14 29
   • 13 10 29
   Show worked solution

   Correct answer: 10 13 29

   Two passes of selection sort finalise the first two positions and leave 29 where the swap put it.

7. 7.What is printed by the following code segment?

   int[] a = {5, 2, 9, 1};
   for (int i = 1; i < a.length; i++)
   {
       int v = a[i];
       int j = i - 1;
       while (j >= 0 && a[j] > v)
       {
           a[j + 1] = a[j];
           j--;
       }
       a[j + 1] = v;
   }
   System.out.print(a[0] + "" + a[1] + a[2] + a[3]);

   • 5291
   • 1259
   • 9521
   • 1295
   Show worked solution

   Correct answer: 1259

   Insertion sort shifts larger values right and drops each saved value into place.

8. 8.What is printed by the following code segment?

   int[] a = {4, 3, 2, 1};
   int swaps = 0;
   for (int i = 0; i < a.length - 1; i++)
   {
       for (int j = 0; j < a.length - 1 - i; j++)
       {
           if (a[j] > a[j + 1])
           {
               int t = a[j];
               a[j] = a[j + 1];
               a[j + 1] = t;
               swaps++;
           }
       }
   }
   System.out.print(swaps);

   • 4
   • 3
   • 6
   • 12
   Show worked solution

   Correct answer: 6

   A fully reversed array of four elements needs every adjacent pair swapped, which is six exchanges.

9. 9.What is printed by the following code segment?

   int[] a = {1, 2, 3, 4};
   int swaps = 0;
   for (int i = 0; i < a.length - 1; i++)
   {
       for (int j = 0; j < a.length - 1 - i; j++)
       {
           if (a[j] > a[j + 1]) { swaps++; }
       }
   }
   System.out.print(swaps);

   • 6
   • 3
   • 4
   • 0
   Show worked solution

   Correct answer: 0

   An already sorted array needs no exchanges, though the comparisons still run.

10. 10.After three passes of selection sort on an array of eight elements, which statement is true?

    • The first three elements are in their final sorted positions.
    • The last three elements are in their final sorted positions.
    • The array is fully sorted.
    • The first three elements are sorted relative to each other but may still move.
    Show worked solution

    Correct answer: The first three elements are in their final sorted positions.

    Selection sort finalises one position per pass because it always selects the true minimum of what remains.

11. 11.After three passes of insertion sort on an array of eight elements, which statement is true?

    • The first three elements are in their final sorted positions.
    • The first four elements are sorted relative to each other but may still move.
    • The array is fully sorted.
    • No ordering exists until the final pass.
    Show worked solution

    Correct answer: The first four elements are sorted relative to each other but may still move.

    Insertion sort grows a sorted prefix, but a later element can still be inserted into the middle of it.

12. 12.What is printed by the following code segment?

    int[] a = {1, 3, 5};
    int[] b = {2, 4, 6};
    int[] out = new int[6];
    int i = 0;
    int j = 0;
    for (int k = 0; k < out.length; k++)
    {
        if (j >= b.length || (i < a.length && a[i] <= b[j]))
        {
            out[k] = a[i++];
        }
        else { out[k] = b[j++]; }
    }
    System.out.print(out[0] + "" + out[3] + out[5]);

    • 135
    • 123
    • 146
    • 246
    Show worked solution

    Correct answer: 146

    The merge step interleaves two sorted inputs, producing 1, 2, 3, 4, 5, 6.

13. 13.Which statement about merge sort is true?

    • It repeatedly swaps adjacent out-of-order elements.
    • It selects the smallest remaining element on each pass.
    • It requires the input to be sorted already.
    • It splits the data in half repeatedly, sorts each half, then merges the sorted halves.
    Show worked solution

    Correct answer: It splits the data in half repeatedly, sorts each half, then merges the sorted halves.

    Merge sort divides until each piece is trivially sorted and then combines the pieces in order.

14. 14.What is printed by the following code segment?

    int[] a = {3, 1, 2};
    boolean sorted = false;
    int passes = 0;
    while (!sorted)
    {
        sorted = true;
        passes++;
        for (int j = 0; j < a.length - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                sorted = false;
            }
        }
    }
    System.out.print(passes);

    • 2
    • 3
    • 1
    • 4
    Show worked solution

    Correct answer: 2

    One pass sorts this array and a second confirming pass makes no swaps, so the flag stops the loop there.

15. 15.An array of 1000 elements is sorted by selection sort and then by merge sort. Which comparison is accurate?

    • Both do the same amount of work because both sort the array.
    • Merge sort does substantially less work because its cost grows more slowly.
    • Selection sort is faster because it makes fewer swaps.
    • Merge sort is slower because it uses extra memory.
    Show worked solution

    Correct answer: Merge sort does substantially less work because its cost grows more slowly.

    Selection sort compares roughly every pair while merge sort halves the problem, and the gap widens as the input grows.