Searching and Sorting Algorithms

Linear search and binary search

Linear search

Linear search starts at the first item and checks each one in turn until it finds the target or runs out of list.

FUNCTION linearSearch(items, target)
    FOR position FROM 0 TO LENGTH(items) - 1 DO
        IF items[position] = target THEN
            RETURN position
        END IF
    END FOR
    RETURN -1
END FUNCTION

Its strength is that it makes no demands on the data. The list can be in any order, and no preparation is needed. Its weakness is speed: on a list of n items the worst case is n comparisons, so searching a million records could mean a million checks.

Binary search

Binary search only works on a sorted list. It looks at the middle item, and because the list is sorted, one comparison tells it which half the target must be in. The other half is discarded entirely.

1. Find the middle item of the search area.
2. If it is the target, stop.
3. If the target is smaller, discard the middle item and everything above it.
4. If the target is larger, discard the middle item and everything below it.
5. Repeat on what is left, until the target is found or nothing remains.

FUNCTION binarySearch(items, target)
    SET low TO 0
    SET high TO LENGTH(items) - 1
    WHILE low <= high DO
        SET mid TO (low + high) DIV 2
        IF items[mid] = target THEN
            RETURN mid
        ELSE IF items[mid] < target THEN
            SET low TO mid + 1
        ELSE
            SET high TO mid - 1
        END IF
    END WHILE
    RETURN -1
END FUNCTION

Worked example

Find 23 in [4, 8, 15, 16, 23, 42, 50].

Three comparisons. Linear search would have taken five.

Bubble sort

Bubble sort repeatedly walks through the list comparing each pair of neighbours and swapping them if they are the wrong way round. After the first full pass the largest value has been carried all the way to the end, which is where the name comes from.

PROCEDURE bubbleSort(items)
    SET swapped TO TRUE
    WHILE swapped = TRUE DO
        SET swapped TO FALSE
        FOR i FROM 0 TO LENGTH(items) - 2 DO
            IF items[i] > items[i + 1] THEN
                SET temp TO items[i]
                SET items[i] TO items[i + 1]
                SET items[i + 1] TO temp
                SET swapped TO TRUE
            END IF
        END FOR
    END WHILE
END PROCEDURE

Tracing one pass

Start with [7, 3, 9, 2].

• Compare 7 and 3. Wrong order, swap: [3, 7, 9, 2]
• Compare 7 and 9. Correct order, leave: [3, 7, 9, 2]
• Compare 9 and 2. Wrong order, swap: [3, 7, 2, 9]

End of pass one. 9 is now in its final position. Pass two produces [3, 2, 7, 9], pass three produces [2, 3, 7, 9], and pass four makes no swaps at all, which is how the algorithm knows it has finished.

Why the swapped flag matters

Without the flag the algorithm has no way of knowing the list is already sorted, and would carry on making pointless passes. With it, a list that is already in order is confirmed sorted in a single pass. This is why bubble sort is respectable on nearly sorted data and dreadful on everything else.

Merge sort

Merge sort uses divide and conquer. It splits the list in half over and over until every piece holds a single item, then builds the answer back up by merging pairs of sorted pieces.

The insight it rests on is that a list of one item is already sorted, and that merging two sorted lists is easy: compare the first item of each, take the smaller, repeat.

Divide

[6, 2, 8, 4, 1] splits into [6, 2] and [8, 4, 1], which split into [6], [2], [8] and [4, 1], and finally [4, 1] splits into [4] and [1].

Merge

• Merge [6] and [2] to get [2, 6]
• Merge [4] and [1] to get [1, 4]
• Merge [8] and [1, 4] to get [1, 4, 8]
• Merge [2, 6] and [1, 4, 8] to get [1, 2, 4, 6, 8]

Why it is fast, and what it costs

Splitting a list of n items in half repeatedly takes about log₂n rounds, and each round of merging touches every item once. On a list of 1000 items that is roughly 10 rounds of 1000 operations, about 10000 steps, against bubble sort's worst case of nearly 500000. The comparison is not close.

The cost is memory. Merge sort has to hold the sub lists separately while it merges them, so it needs additional space roughly the size of the original list. Bubble sort works in place and needs room for a single temporary variable. On a device with very little RAM that trade off can decide the choice.

Choosing and comparing

Edexcel asks you to compare algorithms and justify a choice. The marks are in the reasoning, so learn the trade offs rather than a ranking.

Building the justification

The structure that scores is: name the algorithm, give the property of the data that makes it suitable, then give the consequence.

"For a list of 50000 sorted product codes searched thousands of times a day, binary search is the better choice. The list is already sorted, so the precondition costs nothing, and each comparison eliminates half of the remaining codes, so a search takes at most about 16 comparisons instead of up to 50000. Over thousands of searches that difference is enormous."

Key terms you must be able to define

Linear search

A search that checks each item in a list in turn from the start until the target is found or the end is reached.

Binary search

A search that repeatedly examines the middle item of a sorted list and discards the half that cannot contain the target.

Bubble sort

A sort that repeatedly compares adjacent items and swaps them if they are in the wrong order until a pass makes no swaps.

Merge sort

A sort that repeatedly divides the list into halves until each holds one item, then merges the pieces back together in order.

Divide and conquer

A strategy that solves a problem by breaking it into smaller instances of the same problem and combining the results.

Pass

One complete run through the list by a sorting algorithm.

Comparison

One test of two values against each other, used as the standard measure of how much work a search or sort does.

Efficiency

A measure of the resources an algorithm uses, usually the number of comparisons or steps and the amount of memory required.

In place

A description of an algorithm that rearranges the data using almost no additional memory.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

Every question here rewards the same two moves: trace accurately and justify with a trade off.

Traces must show the state after each step. A merge sort question asking you to show the divide stage wants every level of splitting written out, not just the final answer. A bubble sort question asking for the list after two passes wants the list after pass one as well, because that is where the working marks live.

Every advantage has a matching cost. Binary search is faster but demands a sorted list. Merge sort is faster but demands more memory. Bubble sort is slow but simple and works in place. An answer that gives an advantage without acknowledging the cost is an average answer.

Quote numbers when you can. "Binary search would take at most 17 comparisons on 100000 records instead of up to 100000" is far stronger than "binary search is quicker", and it takes the same amount of time to write.

• Be able to trace a binary search on a sorted list of nine items and state the number of comparisons
• Be able to give the list after each pass of a bubble sort on a list of five values
• Be able to draw the full divide and merge stages of a merge sort on six values
• Be able to state the worst case number of comparisons for linear and binary search on n items
• Be able to justify a choice of algorithm for a stated scenario in three sentences

Mistakes that cost marks here