What's covered
Key facts
Binary Search
Binary search starts by checking the middle item of the list.
Bubble Sort
Bubble sort works on a list of any size.
Comparing Algorithm Efficiency
A sorted phone book is the classic case where binary search beats linear by a large margin.
Flowcharts — Shapes and Meaning
Arrows (flowlines) join the shapes and show the direction the algorithm moves through them.
Linear Search
Linear search finds the item fastest when the target is at (or near) the start of the list.
Pseudocode Basics
Common pseudocode forms for assigning a value are SET x TO 5 or x ← 5.
Trace Tables
Trace a snippet by updating the variable column at each step: starting x = 0, after SET x TO x+5 then SET x TO x*2, x ends at 10.
Binary Search
On a large sorted list, binary search is much faster than linear search.
Bubble Sort
At each step bubble sort compares two adjacent items.
Comparing Algorithm Efficiency
Bubble sort is slow on a large list: it can need many passes, each comparing every adjacent pair, so it takes far longer than searching a list or sorting a short one.
Sample questions
A taste of the 63 questions in this topic, answers marked. Sign up to practise the full set with spaced repetition.
Which item does binary search look at first?
- •A random item
- •The first item
- •The last item
- ✓The middle item
How does bubble sort sort a list?
- •Finds the smallest item and moves it first
- •Inserts each item into its correct position
- •Splits the list in half each pass
- ✓Swaps neighbouring pairs repeatedly
Why compare two algorithms solving the same problem?
- ✓One may be more efficient
- •To check they produce the same code
- •To decide which programmer wrote better comments
- •To find which one uses more variables
Which shape represents a decision in a flowchart?
- ✓Diamond shape
- •Oval shape
- •Parallelogram shape
- •Rectangle shape
How does a linear search work?
- ✓Checks each item one by one until the target is found
- •Hashes the target value to compute the index of the item directly
- •Repeatedly halves the list, checking only the middle item each time
- •Sorts the list first, then jumps to the position where the target should be
Why use pseudocode?
- •Convert binary to decimal numbers
- ✓Plan an algorithm in plain language
- •Run the algorithm on the CPU directly
- •Send the algorithm over the network
Try it for four weeks. Free.
One school. Unlimited classes. No card limit. No teacher limit. If your students aren't practising daily by the end of the trial, you owe us nothing.