2.1 – Algorithms

🎇2.1.3 Searching and sorting algorithms

This section covers:

Standard searching algorithms:
- Binary search
- Linear search
Standard sorting algorithms:
- Bubble sort
- Merge sort
- Insertion sort

🏠 Click here to go back to the main page.

Searching

Computers can hold a lot of information, but that information is only useful if we can find it easily. There are many ways that a computer can search for information, and for your GCSE you need to know about two of the most popular methods. Watch the Searching Algorithms Video (opposite) which explains about searching.

Searching Algorithms Video

Searching.mp4

Linear Search

The first search algorithm that we need to know about is called a linear search. This is the most common way that humans would search for something, we start at the beginning and check each item until we have either found what we are looking for, or reached the end.

The list of items does not need to be in order. Below, you can see a pseudocode algorithm for a linear search, along with a version written in Python.

Pseudocode for a linear search

Python code for the same linear search

Binary Search

Obviously, there are faster and more efficient ways of searching than just starting at the beginning and checking every item until you find it (as in the linear search above)

If the list of items to be found are in order, then we could start by checking the item right in the middle of the list. You may be lucky, and find what you are looking for straight away, but it is unlikely. If the item that you check is bigger than what you are looking for, then you can continue searching using only the cards which are smaller. This gives you a list of items that are half as big, so you can continue - checking the middle item, removing half the items etc. until you have found what you are looking for.

This search is called a binary search because we split the list in two each time. It is usually much faster than a linear search (see below)

Pseudocode for a binary search

Python code for the same binary search. three variables are used to remember the positions of the midpoint, a point on the left and a point on the right.

When we use a linear search, we will probably have to check a large number of items before we find what we are looking for (on average, if we search 1000 items, it will take 500 searches)

A binary search removes half the list every time one check is carried out, which means that we have to check far fewer items, so a binary search is far quicker (unless the item you are searching for is at the beginning of the list of items). Using a binary search on 1000 items will take a maximum of 10 searches.

Sorting

Bubble Sort

As well as searching for an item in a list, it is very common for us to be able to sort a list of items into a particular order. One of the simplest ways to do this is the bubble sort.

To perform a bubble sort on a list of items, a number of comparisons are made. This involves comparing the value of one item with another, and taking an appropriate action. With a bubble sort, the first and second item are checked, and swapped if the first item is greater than the second. Next, the second and third item are checked, and swapped if the second is greater than the first. In this way, a "large" item will "bubble" up the list of items. The process is continued right to the end of the list, and then it is done again until the full list has been gone through and no items have had to be swapped (i.e., it is in order)

Bubble Sort Video

You will find lots of videos on Youtube about the different sorting algorithms, but I thought this one from Cambridge University Press was easy to understand and made good sense.

Bubble Sort.mp4

Merge Sort

With a merge sort, the list of items is broken down into smaller lists, with just two items in each. The small, two item lists are arranged into the correct order. It is very easy to merge two of these lists together so that all the items are in the correct order. This will be repeated until all of the two item lists have been merged into four item lists. The four item lists can then be merged into eight item ones etc.

The process of merging two lists is easier, as both the lists are in order. The smallest item in both lists is compared and the smallest one inserted into the new list. This is repeated until all the items are inserted.

Insertion Sort

This is the final sorting algorithm that we need to understand for GCSE Computing.

To carry out an insertion sort, a completely new list is made. The original set of data is then added to it, one item at a time. As it is added, it is placed in the correctly sorted position. This is a very quick way of sorting data.