Singapore H2 Computing Wiki

Paper 2 Search and Sort Drills

3 min read

Paper 2 Search and Sort Drills

These are original Paper 2-style implementation drills. They focus on writing working Python functions, testing them, and showing output.

Detailed answers and model code are in Paper 2 Search and Sort Answers.

Revise these first:

Questions

Question 1: Linear Search Function

Write a function linear_search(values, target) that returns the index of target, or -1 if it is not found. Test it with the calls below and show the output. [5]

print(linear_search([12, 5, 9, 21], 9))
print(linear_search([12, 5, 9, 21], 7))

Question 2: Linear Search Count

Write a function count_until_found(values, target) that returns the number of items checked before the target is found. If the target is absent, return the number of items in the list. Test it with the calls below. [5]

print(count_until_found([6, 3, 8, 2], 8))
print(count_until_found([6, 3, 8, 2], 5))

Question 3: Binary Search Function

Write a function binary_search(values, target) that returns the index of target, or -1 if it is not found. The function may assume that values is already sorted in ascending order. Test it with the calls below. [8]

print(binary_search([4, 9, 15, 21, 28, 34, 42], 28))
print(binary_search([4, 9, 15, 21, 28, 34, 42], 20))

Question 4: Binary Search With Comparison Count

Write a function binary_search_count(values, target) that returns a tuple (index, comparisons). index should be -1 if the target is absent. Count one comparison each time the target is compared with the middle value. Test it with the calls below. [9]

print(binary_search_count([2, 5, 8, 11, 14, 17, 20], 17))
print(binary_search_count([2, 5, 8, 11, 14, 17, 20], 7))

Question 5: Bubble Sort Function

Write a function bubble_sort(values) that returns a new sorted list in ascending order without changing the original list. Test it with the call below. [7]

data = [6, 2, 9, 1, 5]
print(bubble_sort(data))
print(data)

Question 6: Optimised Bubble Sort

Write a function bubble_sort_passes(values) that performs bubble sort and returns the number of complete passes made. Stop early if a pass makes no swaps. Test it with the calls below. [8]

print(bubble_sort_passes([1, 2, 3, 4]))
print(bubble_sort_passes([4, 3, 2, 1]))

Question 7: Insertion Sort Function

Write a function insertion_sort(values) that returns a new sorted list in ascending order. Test it with the call below. [7]

print(insertion_sort([7, 3, 5, 2]))

Question 8: Merge Two Sorted Lists

Write a function merge_sorted(left, right) that merges two sorted lists into one sorted list. Test it with the call below. [8]

print(merge_sorted([2, 6, 9], [1, 5, 10, 12]))

Question 9: Sort Records by Key

The list below stores records in the form [name, score].

records = [["Nora", 64], ["Ivan", 82], ["Mina", 75], ["Omar", 82]]

Write a function sort_by_score(records) that returns a new list sorted by score in descending order. If two scores are equal, keep their original relative order; that is, the sort should be stable for equal scores. Test the function and show the output. [10]

Question 10: Search After Sorting

Write a program that:

  1. stores the list [31, 12, 44, 18, 27, 9];
  2. sorts it in ascending order using your own insertion sort function;
  3. uses binary search to find the value 27;
  4. prints the sorted list and the index of 27 in the sorted list. [10]

Review Checklist

You should be able to:

  • write functions with clear return values;
  • test found and not-found search cases;
  • preserve original lists when asked to return a new list;
  • implement bubble, insertion, merge helper, and binary search logic;
  • show output evidence for every required test.

Graph View

Backlinks