CS3Searching and Sorting Algorithms

AQA: a linear search is an algorithm that sequentially checks each element in an array or list until a match is found or the end is reached.

• Start at the first item. Compare it with the item you are looking for (the target).
• If they match, stop: the item is found. If not, move to the next item.
• If you reach the end without a match, the item isn’t in the list.
• It works on unsorted lists as well as sorted ones.
• Best case: the target is first, so 1 comparison. Worst case: it is last or not there at all, so one comparison per item (n for a list of n items).

items ← [14, 3, 27, 8, 19, 5]
target ← USERINPUT
found ← False
i ← 0
WHILE found = False AND i < LEN(items)
   IF items[i] = target THEN
      found ← True
   ELSE
      i ← i + 1
   ENDIF
ENDWHILE

A linear search checks one item at a time, from the start

Linear search

An algorithm that sequentially checks each element in an array or list until a match is found or the end is reached.

Target

The item being searched for.

AQA: a binary search compares a search item to the middle item of an array or list. If they do not match, half of the array or list can be eliminated and the search continues in the other half. The array or list needs to be sorted.

• Set low to the first index and high to the last.
• Find the middle: mid ← (low + high) DIV 2. Compare the item at mid with the target.
• Equal: found. Middle item smaller than the target: the target must be to the right, so low ← mid + 1. Larger: it must be to the left, so high ← mid - 1.
• Repeat. If low becomes greater than high, there is nothing left to check, so the item isn’t there.
• Strings can be binary searched too, if they are in alphabetical order.

low ← 0
high ← LEN(items) - 1
found ← False
WHILE found = False AND low ≤ high
   mid ← (low + high) DIV 2
   IF items[mid] = target THEN
      found ← True
   ELSE IF items[mid] < target THEN
      low ← mid + 1
   ELSE
      high ← mid - 1
   ENDIF
ENDWHILE

Finding 30: each comparison throws away the half that can’t hold it

Binary search

An algorithm that compares a search item to the middle item of an array or list; if they don’t match, half of the list is eliminated and the search continues in the other half. The list must be sorted.

• If a list changes often, keeping it sorted for binary search costs time. A linear search can be used straight away.
• For a short list, the difference in time is tiny, so the simpler linear search is fine.

AQA: a bubble sort works by making passes through the array or list. Whilst making a pass, we compare neighbours and swap them if they are out of order. After a series of passes, the array or list will be sorted.

• A pass compares items 0 and 1, then 1 and 2, and so on to the end.
• If a pair is out of order, swap them. A swap needs a temporary variable, so one value isn’t overwritten before it is copied.
• After the first pass (ascending order), the largest item is in its final place at the end. After each pass, one more item is in place.
• Stopping: a list of n items is sorted after at most n − 1 passes. Most versions stop as soon as a pass makes no swaps, because then the list must be in order.

swapped ← True
WHILE swapped = True
   swapped ← False
   FOR i ← 0 TO LEN(items) - 2
      IF items[i] > items[i + 1] THEN
         temp ← items[i]
         items[i] ← items[i + 1]
         items[i + 1] ← temp
         swapped ← True
      ENDIF
   ENDFOR
ENDWHILE

The first pass: the largest item “bubbles” to the end

Bubble sort

A sort that makes passes through a list, comparing neighbours and swapping them if they are out of order, until the list is sorted.

Pass

One run through the list, comparing each pair of neighbours once.

Swap

Exchanging two items, using a temporary variable to hold one of them.

AQA often asks you to show the list each time it changes, which means after every swap, not just after every pass.

AQA: the merge sort is a ‘divide-and-conquer’ algorithm. The original array or list is broken down into smaller and smaller parts until we have individual elements. The merge sort continues by building back sorted groups until we end with the full sorted result.

• Split the list in half, then split each half, until every list holds one item. A list of one item is already sorted.
• Merge pairs of lists back together in order. Keep merging until there is one list.
• Merging and sorting are the same step. Each merge produces a sorted list, because items are taken in order.
• If a list has an odd number of items, one half gets one more item than the other.

Merge sort

A divide-and-conquer sort: the list is broken down until there are individual elements, then sorted groups are built back up until the whole list is sorted.

Merge

Combine two sorted lists into one sorted list by repeatedly taking the smaller front item.

Divide and conquer

Solving a problem by splitting it into smaller problems, solving those and combining the results.

• Draw a new row for each round of splitting, until every box holds one item.
• Then draw a new row for each round of merging. Each merge joins two neighbouring lists from the row above, in order.
• A list of 8 items takes 3 rounds of splitting and 3 rounds of merging.

Split down to single items, then merge back up in order

• For a large, unsorted list, merge sort is the better choice: it takes far less time.
• For a small or nearly sorted list, or where memory is tight, bubble sort can be the better choice.

Paper 1 may ask you to write your own search. When it says so, don’t use Python’s built-in shortcuts such as if target in names or names.index(target).

• i starts at 0, and i < len(names) stops the loop before it runs off the end.
• The loop stops as soon as the name is found, or when every item has been checked.
• The result is output once, after the loop.

names = ["Ola", "Kit", "Raj", "Bea", "Tom"]
target = input("Name to find: ")
found = False
i = 0
while i < len(names) and not found:
    if names[i] == target:
        found = True
    else:
        i = i + 1
if found:
    print(f"{target} is at position {i}")
else:
    print(f"{target} is not in the list")