Linear and binary search; bubble and selection sort – IB Computer Science exam questions with mark scheme

1Core4 marks

A sorted list is stored as data = [3, 8, 12, 19, 25, 31, 40, 47] (indices 0 to 7). A binary search looks for the value 31. Count each examination of a middle item as one comparison. The midpoint is calculated as mid = (low + high) // 2, starting with low = 0 and high = 7.

(a) State the value of mid and the item examined in the first comparison. [2]

(b) Show how low and high change, and state how many comparisons are needed to find 31. [2]

First mid = (0 + 7) // 2 = 3(1)
Item examined is data[3] = 19(1)
19 < 31 so the lower half is discarded: low becomes 4 (high stays 7); second mid = 5 gives data[5] = 31(1)
Found after 2 comparisons(1)
Answer: (a) mid = 3, item 19. (b) low = 4, high = 7; 2 comparisons.
Examiner tip: Show the midpoint calculation; students often forget to move low to mid + 1 and instead set low = mid.

2Standard4 marks

A bubble sort with a swapped flag is applied to [5, 2, 9, 1, 6]. In each pass adjacent items are compared from left to right and swapped if out of order. The algorithm stops after a pass in which no swap occurs.

(a) Write down the list after the first pass. [1]

(b) State the number of swaps made in the first pass. [1]

(c) Determine the total number of passes the algorithm makes, including the final pass. Show the list after each pass. [2]

After pass 1: [2, 5, 1, 6, 9](1)
3 swaps in pass 1 (5↔2, 9↔1, 9↔6)(1)
Pass 2 gives [2, 1, 5, 6, 9] and pass 3 gives [1, 2, 5, 6, 9] (list sorted after pass 3)(1)
Pass 4 makes no swaps so the algorithm stops: 4 passes in total(1)
Answer: (a) [2, 5, 1, 6, 9] (b) 3 (c) 4 passes
Examiner tip: The extra pass with no swaps is needed to detect that the list is sorted; many students stop at 3.

3Hard5 marks

A sorted list holds 1000 customer ID numbers.

(a) State the maximum number of comparisons a linear search needs. [1]

(b) Calculate the maximum number of comparisons a binary search needs, counting one comparison for each item examined. Show your working. [2]

(c) The list is replaced by an unsorted list of 1000 IDs. Explain why binary search cannot be used on this list, and why sorting it with selection sort just to carry out one search would not be worthwhile. [2]

(a) 1000 comparisons (item is last or absent)(1)
(b) Each comparison halves the list: 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 (ten list sizes), or uses ⌊log₂ 1000⌋ + 1, or 2⁹ = 512 < 1000 ≤ 1024 = 2¹⁰(1)
Maximum = 10 comparisons(1)
(c) Binary search relies on the data being in order so that half of it can be discarded after each comparison; in an unsorted list the discarded half could contain the target(1)
Selection sort is O(n²) (about 1000 × 999 ÷ 2 = 499 500 comparisons), far more than the at most 1000 comparisons (O(n)) of a linear search, so one linear search is cheaper(1)
Answer: (a) 1000 (b) 10 (c) binary search needs sorted data; selection sort is O(n²) (≈ 500 000 comparisons), far more than one O(n) linear search (≤ 1000).
Examiner tip: Give the number 10, not just 'log n'; show the halving sequence or the log₂ calculation.

Stuck on Linear and binary search; bubble and selection sort?

Get it sorted in a free 30-minute session

We work through your weakest questions on this topic on Zoom. I reply the same day.

Free 30-min session on this topic Send me 5 questions a day

4Core4 marks

A selection sort arranges the list [29, 14, 37, 8, 21, 11] into ascending order. In each pass the smallest item in the unsorted part of the list is found and swapped into the first position of the unsorted part.

(a) Write down the list after each of the first three passes. [3]

(b) State the total number of passes a selection sort makes on a list of 6 items. [1]

(a) Pass 1: [8, 14, 37, 29, 21, 11] (8 and 29 swapped)(1)
Pass 2: [8, 11, 37, 29, 21, 14] (11 and 14 swapped)(1)
Pass 3: [8, 11, 14, 29, 21, 37] (14 and 37 swapped); follow through an earlier error if each later pass is a correct selection-sort step from the candidate's previous list(1)
(b) 5 passes / n − 1(1)
Answer: (a) [8, 14, 37, 29, 21, 11]; [8, 11, 37, 29, 21, 14]; [8, 11, 14, 29, 21, 37] (b) 5
Examiner tip: Students often write the bubble-sort result (largest item moving to the end) instead of swapping the minimum into the front position.

5Core4 marks

A social media app stores usernames in a list, for example users = ["kai_02", "zoe.m", "raj99", "zoe.m", "lena_k"]. The list is not in any order.

Construct a function find_user(users, target), in Python or Java, that uses a linear search to return the index of the first occurrence of target in users, or −1 if target is not in the list. [4]

Loop through every index of the list, from 0 to len(users) − 1 (Java: users.length / size()); accept a while loop with a counter correctly initialised and incremented(1)
Compare the current element with target (users[i] == target; Java .equals(); allow == in Java)(1)
Return the current index as soon as a match is found (so the first occurrence is returned); accept setting a flag/found index and exiting the loop(1)
Return −1 only after the loop has finished without a match; do not award if −1 is returned inside the loop on the first non-match(1)

Examiner tip: The most common error is putting else: return -1 inside the loop, which stops the search after checking only the first item.

6Standard4 marks

The array cities shown below is sorted into alphabetical order. A binary search is used to look for "Nairobi". It starts with low = 0 and high = 9, uses mid = (low + high) // 2 (integer division), and stops when the item is found or when low > high.

(a) Trace the binary search by stating the values of low, high and mid, and the item examined, at each step. [3]

(b) State the result of the search and the number of items examined. [1]

(a) Step 1: low = 0, high = 9, mid = 4, examines "Lima"; "Nairobi" comes after "Lima" so low becomes 5(1)
Step 2: low = 5, high = 9, mid = 7, examines "Paris"; "Nairobi" comes before "Paris" so high becomes 6(1)
Step 3: low = 5, high = 6, mid = 5, examines "Madrid" (low becomes 6); Step 4: low = 6, high = 6, mid = 6, examines "Oslo" (high becomes 5); both steps needed for the mark(1)
(b) low (6) > high (5) so the search stops: "Nairobi" is not found / returns −1 / false, after 4 items examined(1)
Answer: Lima (mid 4) → Paris (mid 7) → Madrid (mid 5) → Oslo (mid 6); low = 6 > high = 5, not found (−1) after 4 items.
Examiner tip: Students forget to set low = mid + 1 / high = mid − 1 (not mid), which changes every later midpoint.

7Standard4 marks

A programmer writes the following bubble sort to put a list of daily temperatures into ascending order.

1  def bubble_sort(temps):
2      n = len(temps)
3      for i in range(n - 1):
4          for j in range(n - i):
5              if temps[j] > temps[j + 1]:
6                  temps[j], temps[j + 1] = temps[j + 1], temps[j]
7      return temps

When it is called with bubble_sort([18, 22, 15, 30, 9]) the program crashes.

(a) Identify the line that contains the error and explain why the program crashes. [2]

(b) Write the corrected line. [1]

(a) Line 4 (the inner loop range); do not accept line 5 alone unless the explanation refers to the loop bound(1)
In the first pass (i = 0), j reaches n − 1 = 4, so temps[j + 1] is temps[5], which is outside the list / index out of range (IndexError)(1)
(b) for j in range(n - 1 - i):; accept range(n - i - 1); Java equivalent for (int j = 0; j < n - 1 - i; j++); accept range(n - 1) (works but does unnecessary comparisons)(1)
(c) Line 5: change > to < (if temps[j] < temps[j + 1]:); accept <=(1)
Answer: (a) Line 4: j goes up to n − 1 so temps[j + 1] is out of range (b) for j in range(n - 1 - i): (c) change > to < in line 5.
Examiner tip: Say exactly which index goes out of range and when (first pass, j = 4 accesses temps[5]); 'the loop is wrong' is not enough.

8Hard5 marks

A small sensor device stores readings in flash memory, where every write to memory is slow and wears the memory out. The list [60, 50, 40, 30, 20, 10] must be sorted into ascending order. Two algorithms are being considered:

a bubble sort that makes all n − 1 passes, each pass comparing adjacent pairs up to the end of the unsorted part
a selection sort that swaps only when the smallest item is not already in position

(a) Calculate the number of swaps made by each algorithm on this list. [2]

(b) Show that both algorithms make the same number of comparisons on this list. [1]

(d) State the space complexity of both algorithms and explain why. [1]

(a) Bubble sort: 15 swaps (every compared pair is out of order: 5 + 4 + 3 + 2 + 1)(1)
Selection sort: 3 swaps (60↔10, 50↔20, 40↔30; passes 4 and 5 need no swap); do not accept 5 (the stem states that no swap is made when the smallest item is already in position)(1)
(b) Both make 5 + 4 + 3 + 2 + 1 = 15 comparisons / n(n − 1)/2 = 6 × 5 / 2 = 15(1)
(c) Selection sort, because it makes far fewer swaps/writes (3 vs 15) for the same number of comparisons, so it is faster on flash and causes less wear; follow through from (a)(1)
(d) O(1) / constant for both, because they sort in place, needing only a fixed number of extra variables (e.g. a temp/index) regardless of n; do not accept O(n) referring to the list itself(1)
Answer: (a) bubble 15, selection 3 (b) both 15 = 5+4+3+2+1 (c) selection sort: fewer writes (d) O(1), in-place.
Examiner tip: Many candidates assume both quadratic sorts do the same amount of work; here the number of swaps (writes) is what decides.

9Hard5 marks

A student times a sorting program on lists of random integers of different sizes. The graph shows the measured times, with a dashed curve of best fit.

(a) Describe what happens to the time taken when the number of items is doubled, using values from the graph. [1]

(b) Deduce the time complexity of the algorithm in Big O notation, and state one sorting algorithm from this course that it is consistent with. [1]

(d) The program uses a bubble sort with a swapped flag. Explain why sorting 12 000 items that are already in order would take far less time than your answer to (c). [1]

(a) Doubling n multiplies the time by 4, e.g. 1000 items 0.15 s → 2000 items 0.60 s (or 2000 → 4000: 0.60 s → 2.40 s)(1)
(b) O(n²) / quadratic AND bubble sort or selection sort (either)(1)
(c) 12 000 is 3 × 4000 (or 12 × 1000), so time × 3² = 9 (or × 12² = 144): 2.40 × 9 or 0.15 × 144(1)
≈ 21.6 s; accept 21–22 s(1)
(d) No swaps occur in the first pass, so the flag stays false and the sort stops after one pass of n − 1 (11 999) comparisons, i.e. O(n) / linear best case instead of O(n²)(1)
Answer: (a) time ×4 when n doubles (b) O(n²), e.g. bubble or selection sort (c) 2.40 × 9 ≈ 21.6 s (d) one pass, no swaps, stops: O(n).
Examiner tip: In (c), scale by the square of the size ratio; multiplying by 3 (linear scaling) gives 7.2 s and loses both marks.

10Stretch6 marks

A quiz app stores players' names and scores in two parallel lists, so that names[i] scored scores[i], for example:

names  = ["Ines", "Tomas", "Priya", "Kofi", "Mei"]
scores = [72, 85, 64, 91, 85]

(a) Construct a procedure sort_scores(names, scores), in Python or Java, that uses a selection sort to arrange the scores into descending order, keeping each name with its score. [5]

(b) State the contents of names after your procedure has run on the example data. [1]

(a) Outer loop over positions 0 to n − 2 (accept 0 to n − 1)(1)
At the start of each pass, set the index of the largest so far to the first position of the unsorted part (e.g. biggest = i)(1)
Inner loop from i + 1 to n − 1, comparing scores[j] > scores[biggest] and updating biggest = j; accept >=(1)
After the inner loop, swap scores[i] with scores[biggest] (correct use of a temporary variable or simultaneous assignment)(1)
Swap names[i] with names[biggest] in the same pass, so names stay aligned with scores; do not award if names are sorted separately/alphabetically(1)
(b) ["Kofi", "Tomas", "Mei", "Ines", "Priya"]; accept Mei before Tomas if the candidate's code uses >= (follow through from their code)(1)

Answer:

def sort_scores(names, scores):
    n = len(scores)
    for i in range(n - 1):
        biggest = i
        for j in range(i + 1, n):
            if scores[j] > scores[biggest]:
                biggest = j
        if biggest != i:
            scores[i], scores[biggest] = scores[biggest], scores[i]
            names[i], names[biggest] = names[biggest], names[i]

(b) ["Kofi", "Tomas", "Mei", "Ines", "Priya"]

Examiner tip: Candidates who swap only the scores lose the link between each player and their score; every swap must be applied to both lists.

Stuck on this topic?

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.

Free 30-minute session