Algorithms

5.1 What is an algorithm?

An algorithm means a precise, step-by-step set of instructions for solving some problem. It is not a concept unique to computers: a kitchen recipe and a set of directions are algorithms too. Precise steps, a precise order, a precise result.

In programming, one task can often be carried out by several different algorithms. For example, finding a name in a phone book. You can flip from the first page to the last, or you can open the book in the middle and work out which half it is in. Both give the correct result, but one is much faster.

This is exactly where efficiency matters: how many steps an algorithm needs to finish the job. On small data the difference is not noticeable, but on a list of a million elements a slow algorithm can take hours while a fast one runs in seconds.

5.2 Linear search

Linear search is the simplest method: starting from the beginning of the array, we check each element one after another until we find the value we are looking for or reach the end. Walking along an array with a loop, like last week, is exactly this.

Below, change the number being searched for and watch each check with Next step. The yellow cell is the element being checked right now, and the green cell is where it was found:

In the worst case (the value is at the end or not present at all) we check every element. So 100 elements may need 100 steps, and a million elements may need a million steps. This is slow, but it also works on an unsorted array, which is convenient.

5.3 Binary search

If the array is sorted (ordered from smallest to largest), there is a much smarter method: binary search. The idea is like the phone book: we open the middle. If the value being searched for is greater than the middle one, we do not look at the left half at all; if it is smaller, we do not look at the right half. At each step the remaining range shrinks by half.

Below is a sorted array. Choose a value and watch: the light cell is the range still being examined, the yellow cell is the middle, and the green cell is where it was found:

Here is the magic: binary search examines an 8-element array in at most 3 steps, because we throw away half each time (8 → 4 → 2 → 1). And for a million elements only 20 steps are enough! But there is one condition: the array must be sorted in advance.

Make a prediction

5.4 Efficiency: Big-O

To compare the speed of algorithms, programmers use Big-O notation. It does not show the exact time, but rather how the number of steps grows as the data size (n) increases. The most common ones are:

• O(1) constant: no matter the size, the same number of steps. The fastest
• O(log n) logarithmic: if the size doubles, only one step is added. Binary search is like this
• O(n) linear: equal to the size. Linear search is like this
• O(n^2) quadratic: the square of the size. Simple sorts are like this, slow

Below, choose n and compare how many steps each speed type requires:

5.5 What is sorting and why is it needed?

Sorting means placing the elements of an array in some order, for example from smallest to largest. Phone contacts by alphabet, store products by price, exam results by score: all of these are sorting.

Sorting is important for one more reason: it speeds up other algorithms. Recall that binary search worked only on a sorted array. So if we sort once, we can then search quickly thousands of times.

There are many sorting methods. We will look at two that are simple but excellent for learning: bubble sort and selection sort. We watch both live as a bar chart, where the height represents the value.

5.6 Bubble sort

Bubble sort is the easiest method to understand. The idea: we compare two neighboring elements, and if the left one is larger, we swap their places. We walk along the array like this, then start again from the beginning, until no swap is needed any more. On each pass the largest element "rises" to its final place like a bubble.

Watch each comparison and swap with Next step. The yellow bars are the ones being compared right now, the orange ones are being swapped, and the green bars have found their place:

Bubble sort is simple but slow: because it compares each pair over and over, its efficiency is O(n^2). That is, about 10,000 operations for 100 elements. Good for small arrays, but not suitable for large ones.

5.7 Selection sort

Selection sort uses a different strategy: each time we find the smallest element in the remaining unsorted part and put it at the front. On the first pass we find the smallest in the whole array and place it at position 0, on the second the smallest of the rest at position 1, and so on.

Watch below: the yellow bar is the element being checked right now, the orange one is the smallest candidate found so far, and the green bars have found their place:

Selection sort is also O(n^2): it too looks through the rest for each element. But it makes fewer swaps (only one per pass), so in some cases it is more practical than bubble sort.

5.8 Comparing the algorithms

Now we compare what we have seen in a single table. Note: speed depends not only on the algorithm but also on the condition (for example, binary search requires a sorted array).

There are faster sorting methods too (for example, merge sort, O(n log n)), which we will look at below and in the coming weeks. For now the main takeaway: O(log n) is very fast, O(n) is moderate, and O(n^2) is slow at large sizes.

5.9 Practical: which algorithm to choose?

There is no such thing as a single best algorithm; it is chosen depending on the situation. Here are some simple rules:

• If the array is small or you search only once: linear search is enough, and simpler
• If you search the same array many times: sort it once first, then use binary search
• If the data is unsorted and large: choose a faster method (O(n log n)), not the simple sorts
• For learning or a small task: bubble sort and selection sort are perfect, with short code

5.10 Going deeper advanced

You have seen the core algorithms. Now we take a brief look at two more ideas, which we will study in more depth in the coming weeks.

Divide and conquer

The fastest sorts (for example, merge sort) work differently: they split the array into two equal halves, sort each half separately, then merge the two sorted halves. This approach gives O(n log n) speed, much better than O(n^2). It is called "divide and conquer".

Recursion

The "sort each half separately" step above is interesting: the function calls itself on a smaller part. This is called recursion, a function calling itself. We will study this powerful but delicate concept fully in week 8.

Glossary of terms

5.11 Knowledge quiz

16 questions. To complete the week, answer at least 11 of them correctly.