CPX4Searching, Sorting and Efficiency

A linear search compares each item in a list with the target, one at a time from the start, until it finds the target or reaches the end of the list.

• Start at index 0. Compare the item with the target (the value you are looking for).
• If they match, the target is found: stop. If not, move on to the next index.
• If the end of the list is reached without a match, the target is not in the list.
• It works on an unsorted list, because it checks every item in turn.
• Pearson's code uses a while loop with a Boolean found flag, so the loop has one exit and stops as soon as the target is found.

 1  # -------------------------------------------
 2  # Global variables
 3  # -------------------------------------------
 4  seedPackets = [415, 207, 388, 130, 562, 249]
 5  target = 0
 6  index = 0
 7  found = False
 8  
 9  # -------------------------------------------
10  # Main program
11  # -------------------------------------------
12  target = int (input ("Packet number: "))
13  while ((found == False) and (index < len (seedPackets))):
14      if (seedPackets[index] == target):
15          found = True
16      else:
17          index = index + 1
18  
19  if (found == True):
20      print ("Found at index", index)
21  else:
22      print ("Not found")

Looking for 130: four compares, then the search stops

Linear search

A search that compares each item with the target in turn, from the start, until the target is found or the end of the list is reached.

Target

The value the search is looking for.

If the list is in ascending order, a linear search can stop early: once the current item is bigger than the target, the target can't be further along.

• Add a second Boolean flag, often called passed. It becomes True when the current item is greater than the target.
• The loop carries on only while the target is not found and not passed and there are items left.
• This saves compares when the target is missing: there is no need to check the rest of the list.
• It only works on sorted data. On an unsorted list, a bigger item tells you nothing about the items after it.

 1  # -------------------------------------------
 2  # Global variables
 3  # -------------------------------------------
 4  plotNumbers = [104, 112, 118, 125, 131, 140, 147, 156]
 5  target = 0
 6  index = 0
 7  found = False
 8  passed = False
 9  
10  # -------------------------------------------
11  # Main program
12  # -------------------------------------------
13  target = int (input ("Plot number: "))
14  while ((found == False) and (passed == False) and (index < len (plotNumbers))):
15      if (plotNumbers[index] == target):
16          found = True
17      elif (plotNumbers[index] > target):
18          passed = True
19      else:
20          index = index + 1
21  
22  if (found == True):
23      print ("Plot is on the list")
24  else:
25      print ("Plot is not on the list")

Passed flag

A Boolean set to True when the current item is greater than the target, so a search of a sorted list can stop early.

A binary search compares the target with the middle item of a sorted list. If they don't match, it discards the middle item and the half that can't contain the target, then repeats on what is left.

• The list must be sorted first (numbers in order, or words in alphabetical order).
• Keep a start index and an end index. At first they are the first and last indexes.
• Mid-point = (start + end) // 2, which rounds down. Rounding up is also accepted if you use it every time.
• Middle item equals the target: found. Middle item less than the target: discard the lower half and the mid-point, so start = mid + 1. Middle item greater: discard the higher half and the mid-point, so end = mid − 1.
• Repeat until the target is found, or there are no items left (start is greater than end).
• You need to trace a binary search by hand, but you don't have to write the code for one.

Looking for 20, which isn't there: four mid-points, then nothing is left

Binary search

A search of a sorted list that compares the target with the middle item and, if it doesn't match, discards the middle item and the half that can't hold the target, repeating until found or no items are left.

Mid-point

The index halfway between start and end: (start + end) // 2.

Pearson asks you to trace a binary search in a table with these columns. Show the calculation of each mid-point, not just its value.

• This table is the search for 42. Item 4 is 23, which is less than 42, so the lower half (indexes 0 to 4) goes and start becomes 5.
• Item 7 is 42: found after only two compares. A linear search would have needed eight.
• “Lower” means the lower half is discarded (the middle item was too small). “Higher” means the higher half is discarded (the middle item was too big).

A bubble sort makes passes through a list. In each pass it compares each pair of neighbouring items and swaps them if they are in the wrong order.

• A pass compares items 0 and 1, then 1 and 2, and so on to the end: a list of n items has n − 1 compares per pass.
• After pass 1 (ascending order), the largest item is in its final place. After each pass, one more item is in place.
• The sort stops after a pass with no swaps: nothing was out of order, so the list is sorted. That last pass still counts as a pass.
• A swap uses a temporary variable, so one value isn't overwritten before it has been copied.
• You need to trace a bubble sort by hand. You don't have to write the code for one.

Pass 1 on 7, 3, 9, 2, 5: the largest item moves to the end

Bubble sort

A sort that makes passes through a list, comparing neighbouring items and swapping them if they are out of order, until a pass makes no swaps.

Pass

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

Swap

Exchanging the positions of two items.

A merge sort splits a list in half again and again until every list holds one item, then merges pairs of lists back together in order until one sorted list is left.

• A list of one item is already sorted, which is why the splitting stops there.
• To merge two sorted lists, compare the front items, move the smaller one to the new list, and repeat. When one list is empty, copy the rest of the other.
• Merging and sorting happen together: each merge produces a list that is in order.
• If a list has an odd number of items, one half gets one more than the other.
• You need to trace a merge sort by hand. In Paper 2 you may be asked to write code that merges two sorted lists (that is in the Python lists topic).

Split to single items, then merge in order

Merge sort

A sort that splits a list into single items, then repeatedly merges pairs of lists in order until one sorted list remains.

Merge

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

Divide and conquer means solving a problem by breaking it into smaller parts of the same kind, dealing with each part, and (if needed) combining the results.

Divide and conquer

Solving a problem by repeatedly breaking it into smaller problems of the same type, then combining the results.

Pearson measures how efficient an algorithm is by the number of compares, the number of passes through a loop and the use of memory. Fewer compares and passes means less processing time.

• Memory: bubble sort is an in-place sort: it rearranges items inside the original list and needs only one extra variable for swaps.
• Merge sort is an out-of-place sort: it builds new lists as it merges, so it needs more memory than bubble sort.
• On a large list, merge sort makes far fewer compares than bubble sort, so it usually takes much less time.
• Fitness for purpose asks whether the algorithm does what is needed: use test data and logical reasoning to check it gives the right result, including for edge cases such as a missing target or an empty list.

In place v out of place

In-place sort

A sort that rearranges the items within the original list, needing very little extra memory (bubble sort).

Out-of-place sort

A sort that builds new lists as it works, so it needs extra memory (merge sort).

Fitness for purpose

Whether an algorithm does what it is meant to do, checked with logical reasoning and test data.

• Pick by the situation: how big the list is, whether it is sorted, how often it changes and how much memory there is.
• A device with very little memory (an embedded system, for example) may use bubble sort even though it is slower.
• A list that is searched thousands of times a day is worth keeping sorted, so binary search can be used.