Ways of searching and sorting

The most straightforward way to search is the linear search (sequential search). Compare one at a time from the front until you find it. It is exactly the for loop you wrote.

Its strength is that it assumes nothing. Unsorted, full of gaps — go along from one end and the answer comes out regardless.

Its weakness is the effort: with bad luck you look at the very last one. With n items you compare n times in the worst case and n/2 times on average.

What matters here is the relation that twice the data means twice the effort. It grows in a straight line, in proportion. That is the "linear" in linear search.

Binary search is the way that throws away half the range with each comparison against the middle.

Look at the middle value: if what you want is smaller, take the left half; if larger, the right half. Then repeat.

But it is not free. To use it, the data must be in ascending (or descending) order. Unsorted, "smaller means left" does not hold. That is the decisive difference from linear search, and the exam always asks about the precondition.

What about the effort? Each comparison halves the range, so how many times you can halve n before reaching 1 is the number of comparisons. The expression for that is log2 n. Even at a million, 2 to the 20 is about 1.04 million, so about twenty comparisons finishes it.

The third way does not search at all: it produces the location by calculation. Put the key through a hash function and use the value that comes out directly as the location (the index). That is the hash search.

A common one is "the remainder after dividing by some number" — say, add up the digits of the key and take the remainder modulo 13 as the location.

The good part is that the effort is the same however many items there are. One pass through a function gives the location, whether there are ten or a million. Not growing at all, the effort is written as 1.

But different keys can produce the same location. That is a collision. The more collisions, the more effort goes into hunting for a free place afterwards and the slower it gets. So the ideal is for hash values to scatter across every location with equal probability — that is, to be close to a uniform distribution. A skewed distribution keeps hitting the same places.

The effort of the three searches came out as n, log2 n and 1. The notation that keeps only how it grows as the data grows is order notation, written like O(n).

The knack is not to fuss over the details. Effort of 3n + 5 is still written O(n). The constant factor 3 and the extra 5 stop mattering once n is large. Order looks only at the shape.

Five of them come up often.

• O(1) … unchanged as the data grows (hash search)
• O(log n) … grows very slowly (binary search)
• O(n) … grows in proportion (linear search)
• O(n log n) … a little steeper than proportional (the fast sorts)
• O(n^2) … grows sharply (the naive sorts)

This list is fastest at the top. Hold on to that order alone and most combination questions in the exam fall to elimination.

The difference in order starts to bite as the data grows. Numbers make it plain.

An O(n) approach takes ten times as long for ten times the data. Straightforward enough.

O(n^2) takes a hundred times for ten times the data. Something that took a second now takes a minute and forty seconds. Ten times more again and it is ten thousand times, which is past waiting for.

O(log n), by contrast, barely grows. Going from a thousand records to a million takes the comparisons from ten to twenty.

What to hold on to is that a slow approach is invisible on small data. Your ten records finish instantly, and it only shows up once the data grows in production. Estimating the order as you write is the habit that catches it.

Now for sorting. Start with three whose ideas are plain. All take O(n^2) effort and take the shape of two nested loops.

Bubble sort compares neighbours and swaps them if they are the wrong way round. Repeat that to the end and small values rise to one end like bubbles.

Selection sort picks the smallest of what is left and puts it at the front. Then it picks the smallest of what remains after that, and so on.

Insertion sort slides the next item into its correct place in the already sorted run. It is exactly how you arrange cards in your hand.

To tell the three apart: compare with the neighbour is bubble, pick the smallest is selection, slide into the right place is insertion. In the exam those phrasings appear almost verbatim among the choices.

There are also sorts faster than O(n^2), at O(n log n). What they share is not comparing everything with everything, but dividing things up or using a structure.

Quicksort picks one pivot and partitions the data into a group smaller than it and a group larger. Within each group it picks a pivot and partitions again. That repetition alone sorts it. This is the one the exam asks about most.

Merge sort splits in half, sorts each half, then merges them back. The point is that merging only needs comparing the fronts of the two and taking the smaller.

Heap sort uses the heap from the previous lesson. Since the root always holds the largest value, you repeatedly take the root and restore the shape.

Shell sort is an improved insertion sort. It sorts elements that are far apart first and then narrows the gap. Roughing it out before refining reduces the weakness of insertion sort.

Sorting has another property besides speed: whether it is stable.

A stable sort is one where items with equal values keep their original relative order.

Suppose you sort a register by name first, then sort it by score. With a stable sort, people with the same score stay in name order. With an unstable sort, the order within a score may get shuffled.

The stable ones are bubble, insertion and merge sort. Quicksort and heap sort swap with distant positions, so they are not stable.

A fast sort is not necessarily stable. That is the thing to remember.

Quicksort and merge sort both went "divide, then do the same thing inside". Write that plainly and you get a function that calls itself from within itself. That is a recursive call.

The definition is just that: carrying out processing that uses the function itself inside the function.

What matters is always giving it a stopping condition. If f(n) calls f(n-1), then at some point n reaches 1 and a value is returned without calling itself. Without that dead end it calls forever.

The knack for following the calculation is to think of it as going all the way down, then coming back up in order. The states of the calls in progress are piled on the stack from the previous lesson and taken off in reverse on the way back.

Last, sort out the terms the exam always lines up together. They merely look like recursive; inside they are entirely different.

• Recursive … it can call itself
• Reentrant … it works correctly even if called from elsewhere before the processing has finished
• Reusable … after being used once, it can be run again without being loaded afresh
• Relocatable … it works wherever in main memory it is placed

The key is what is being asked. "Calls itself" is recursive; "safe when called at the same time" is reentrant; "run again without reloading" is reusable; "does not mind where it is placed" is relocatable.

All four start with "re-", so having all four among the choices is where hesitation begins. Split them on what comes after.