Practice · Sorting · Learning Hub

Q1

In their usual array implementations, which of the simple sorts from CPS 1231 is not stable?

A Insertion sort B Bubble sort C Selection sort D All three are stable

Q2

What does this code print?

int[] a = {5, 2, 9, 1, 7, 3};
for (int i = 1; i <= 3; i++) {
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key) {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = key;
}
System.out.println(Arrays.toString(a));

A [2, 5, 9, 1, 7, 3] B [1, 2, 5, 9, 7, 3] C [1, 2, 3, 5, 7, 9] D [2, 5, 1, 9, 7, 3]

Q3

Insertion sort is run on an array of n elements that is already sorted. How many element comparisons (a[j] > key) does it make?

A 0 B n − 1 C n log₂ n D n(n − 1)/2

Q4

A sensor log of n readings is "almost sorted": every reading is at most 3 positions away from where it belongs. What is the running time of insertion sort on it?

A O(n) B O(n log n) C O(n²), as always for insertion sort D O(3ⁿ)

Q5

What is the extra memory used by the array merge sort in this chapter, apart from the recursion stack?

A O(1) B O(log n) C O(n) D O(n log n)

Q6

The merge method of this chapter merges the sorted halves [1, 4, 6] and [2, 3, 5]. How many times is the comparison a[i] <= a[j] evaluated?

A 3 B 5 C 6 D 9

Q7

A student writes the merge test as if (a[i] < a[j]) instead of if (a[i] <= a[j]). What changes?

A The array is no longer sorted correctly when it contains duplicates B It still sorts correctly, but equal elements from the right half are now placed first, so the sort is no longer stable C The merge loop never terminates on duplicates D Nothing at all: < and <= behave identically in a merge

Q8

What is the running time of the top-down merge sort of this chapter on an array that is already sorted?

A Θ(n), because each merge finishes early B Θ(n log n) C Θ(n²) D Θ(log n)

Q9

The Lomuto partition(a, 0, 6) from this chapter is called on a = {7, 2, 9, 4, 3, 8, 5}. What is the array afterwards, and what does the method return?

A [2, 4, 3, 5, 9, 8, 7], returns 3 B [2, 3, 4, 5, 7, 8, 9], returns 3 C [4, 2, 3, 5, 9, 8, 7], returns 3 D [2, 4, 3, 5, 7, 8, 9], returns 4

Q10

The Lomuto partition(a, 0, 4) is called on a = {4, 8, 1, 6, 3}. What is the result?

A [1, 3, 4, 6, 8], returns 1 B [1, 3, 4, 6, 8], returns 2 C [1, 8, 4, 6, 3], returns 0 D [3, 8, 1, 6, 4], returns 0

Q11

Quick sort with the Lomuto partition (pivot = last element) sorts the already sorted array {0, 1, 2, 3, 4, 5, 6, 7}. How many element comparisons are made in total?

A 24 B 28 C 56 D 64

Q12

Which pivot rule stops quick sort from going quadratic on already sorted or reverse-sorted arrays?

A Always use the first element B Always use the last element C Use the median of the first, middle and last elements D Always use the second element a[lo + 1]

Q13

The quickSort of this chapter recurses on both sides of the pivot. In the worst case, how deep can the recursion get for n elements?

A O(1) B O(log n) C O(n) D O(n log n)

Q14

Why is quick sort with the Lomuto partition not a stable sort?

A Because it is recursive B Because a swap can move an element past an equal element lying between the two swapped positions C Because it uses O(log n) stack space D Because it compares with <= instead of <

Q15

Which statement about heap sort is correct?

A O(n log n) in the worst case, O(1) extra space, not stable B O(n log n) on average but O(n²) in the worst case, like quick sort C O(n log n) in the worst case and stable, but needs O(n) extra space D O(n) on already sorted input, like insertion sort

Q16

Counting sort (values 0..4) is applied to {3, 1, 4, 1, 0, 3}. What does the count array contain after the prefix-sum step, before any element is placed?

A [1, 2, 0, 2, 1] B [1, 3, 3, 5, 6] C [0, 1, 3, 3, 5] D [1, 3, 3, 5, 5]

Q17

For which task is counting sort a poor choice?

A Sorting 2 million exam marks between 0 and 100 B Sorting 10 000 ages between 0 and 120 C Sorting 1 000 customer IDs that range from 0 to 1 000 000 000 D Sorting 365 000 day-of-year values (1–366)

Q18

LSD radix sort (base 10, stable counting pass per digit) is applied to {170, 45, 75, 90, 802, 24, 2, 66}. What is the array after the first pass (units digit)?

A [170, 90, 2, 802, 24, 45, 75, 66] B [170, 90, 802, 2, 24, 45, 75, 66] C [802, 2, 24, 45, 66, 170, 75, 90] D [2, 24, 45, 66, 75, 90, 170, 802]

Q19

Why must each digit pass of LSD radix sort be stable?

A Otherwise the counting array could overflow B A tie on the current digit must keep the order produced by the lower digits, or that earlier work is lost C Stability makes each pass run in O(n) instead of O(n log n) D It is not required; any sort per digit gives the same result

Q20

Bucket sort puts each value x from [0, 1) into bucket (int) (x * n) (n buckets), insertion-sorts each bucket, and concatenates. When is its expected time O(n)?

A Always, whatever the input B When the values are spread roughly uniformly over [0, 1) C Only when the input is already sorted D When all values are equal

Q21

In the decision-tree argument for the lower bound on comparison sorting, why must the tree for inputs of size n have at least n! leaves?

A Because every comparison has n! possible outcomes B Because each of the n! orderings of distinct keys needs a different output rearrangement, and each leaf gives only one C Because the tree must be complete D Because the algorithm makes n! comparisons

Q22

What is the smallest number of comparisons that any comparison-based algorithm needs, in the worst case, to sort 4 distinct elements?

A 3 B 4 C 5 D 6

Q23

What does this code print?

String[] w = {"pear", "fig", "kiwi", "plum", "apple", "date"};
Arrays.sort(w, (x, y) -> x.length() - y.length());
System.out.println(Arrays.toString(w));

A [fig, date, kiwi, pear, plum, apple] B [fig, pear, kiwi, plum, date, apple] C [fig, pear, plum, kiwi, date, apple] D [apple, pear, kiwi, plum, date, fig]

Q24

What happens when you compile and run this code?

int[] a = {3, 1, 2};
Arrays.sort(a, (x, y) -> y - x);
System.out.println(Arrays.toString(a));

A It prints [3, 2, 1] B It prints [1, 2, 3]: the comparator is ignored for primitives C Compilation error: there is no Arrays.sort for an int[] with a comparator D It compiles but throws a ClassCastException

Q25

Which statement about the Java library's sorts is correct?

A Arrays.sort(int[]) uses merge sort so that it is stable B Arrays.sort(int[]) uses a dual-pivot quick sort; object sorts such as Arrays.sort(String[]) and List.sort use the stable TimSort C All Arrays.sort overloads use heap sort to guarantee O(n log n) D Collections.sort copies the list into an int[] and uses quick sort

Q26

Which algorithm is the best choice for each task? (1) 5 million exam marks, integers 0–100. (2) 1 million order objects already sorted by customer, to be re-sorted by date while keeping orders with the same date in customer order.

A (1) quick sort, (2) heap sort B (1) counting sort, (2) a stable sort such as merge sort / TimSort C (1) insertion sort, (2) quick sort D (1) merge sort, (2) selection sort

Q27 Short answer

Explain why quick sort with a last-element pivot takes quadratic time on an already sorted array, and give two ways to avoid it.

Q28 Short answer

Sketch the decision-tree argument showing that every comparison-based sorting algorithm needs Ω(n log n) comparisons in the worst case.

Q29 Short answer

LSD radix sort sorts n 32-bit integers in O(n) time (4 passes, one per byte). Does this contradict the Ω(n log n) lower bound? Explain.

Q30 Short answer

Arrays.sort(int[]) and Arrays.sort(Object[]) use different algorithms. Name them and explain the reason for the difference.

Q31 Programming

Write public static long countInversions(int[] a) that returns the number of pairs i < j with a[i] > a[j] in O(n log n) time, without modifying a. For {2, 4, 1, 3, 5} it returns 3. Hint: adapt merge sort — when an element of the right half is copied before the remaining elements of the left half, how many inversions does that reveal?

Q32 Programming

Write public static int select(int[] a, int k) that returns the k-th smallest element (k = 0 is the minimum) using the Lomuto partition, without sorting the whole array (quickselect). It may rearrange a. For {7, 2, 9, 4, 3} and k = 2 it returns 4.