# Sorting Algorithms

## What's an Algorithm?

A key feature of the National Curriculum for KS3 *Computing*
is algorithms. An understanding of specific algorithms is also required for some GCSE and A level Computer Science courses. The word *algorithm* is used to describe the sequence of steps we take to complete a task - it's really just a method
for, or way of, doing something, like a recipe.

Sometimes the order of steps doesn't matter, but sometimes swapping two steps
will cause problems. For example, it doesn't much matter if you add the milk or the sugar first when making
a cup of tea, but it does matter if you pour the water into the cup before you
turn the kettle on. Sometimes one way of doing things might be more *efficient* than another. For example, if you want to visit
the neighbour to your right, you could turn left, left, left and left again (i.e. go
around the block), but it's quicker to turn right.

Sometimes making changes to the algorithm used can make a big difference to how a program runs. Have a look at my video on programming efficiency to see how changing the way a program draws a circle can make it run more than twenty times as fast.

## Sorting

This page allows you to compare the performance of different sorting algorithms. You can also play the interactive sorting game to practise your sorting skills, or look at programmed examples.

Unlike some other pages, which just use videos or animations, this page lets
you sort your own
numbers - you can then see what impact the initial order (i.e. almost sorted,
reverse order, random) has on the number of steps required. You can choose a sorting *algorithm*, and
use the slider to determine how quickly it runs. On the slowest setting, the sort is advanced using the *Next* button. The box on the right explains each step, and the algorithm is described at the bottom of the page.

Some GCSE Computer Science courses also require you to know about merge sort, which is difficult to show "in place", so I've coded a version of merge sort in Python to demonstrate the process.

You can click *Go* again to try a different algorithm with the same numbers, and see how they compare. The algorithms can be more or less efficient, depending on whether the numbers
are nearly in order, random, or completely reversed, so try the algorithms again with a different set of numbers.

### Inputs

### Demonstration

### Bubble Sort

In a *bubble sort*, adjacent pairs of numbers are compared, and if they are the wrong way round, then they are swapped. This makes the highest number "bubble" to the end of the list.

When the end of the list is reached, the process begins again at the start of the list, and is repeated until there are no swaps made - the list is then sorted.

Unless the list is almost in order to begin with, this results in a large number of comparisons, and so this simple sort is not very efficient for large lists.

### Optimised Bubble Sort

In a *bubble sort*, adjacent pairs of numbers are compared, and if they are the wrong way round, then they are swapped. This makes the highest number "bubble" to the end of the list.

When the end of the list is reached, the process begins again at the start of the list, and is repeated until there are no swaps made - the list is then sorted.

The difference between this version and the standard bubble sort is it takes advantage of the fact that the largest remaining value gets bubbled to the end of the list in each pass, so can reduce the number of comparisons on each pass. For example, after one pass, the highest value is at the end of the list, so only the first nine numbers need to be compared in the second pass. Then the last two numbers are in the right place, so only the first eight need be compared, etc.

### Selection Sort

In a *selection sort*, the first number in the list is compared with each of the subsequent numbers in turn, and if the first number in the list is higher, the numbers are swapped. This means that after one pass, the lowest number is at the start of the list.

The second number in the list is then compared with each of the subsequent numbers in turn, so that it becomes the lowest of the remaining numbers. This process is completed starting with the third, fourth, etc., number in the list, until the whole list is sorted.

This can result in a lot fewer comparisons than with a *bubble sort*, and so it is generally considered to be more efficient.

### Insertion Sort

In an *insertion sort*, adjacent pairs of values are compared, as they are in the *bubble sort*, but the difference is that out-of-order pairs are not swapped.

If the pair is out-of-order - i.e. the second value is lower than the first - the algorithm then works backwards through the list to put the lower number in the right place. The number of *swaps* given in the commentary on the right, therefore, is really the number of *insertions*.

The coding for this algorithm is a bit more complex than for the *bubble* and *selection* sorts, but can be more efficient, and is also used as part of other algorithms, such as the *shell sort*.

### Quicksort

In the *quicksort*, a *pivot value* is chosen from the list of numbers. In simple versions, the *pivot* is the last or the middle value in the list, but for large lists efficiency can be improved by choosing a *pivot* that's close to the median value. In this version, the *pivot* is in the middle and is coloured red. The italicised numbers form the sub-list that is currently being sorted.

The algorithm then shifts all values that are less than or equal to the pivot value to the left of the *pivot*, and larger values to the right. Using *recursion*, the lists to the left and right of the pivot are sorted again. This process continues until the number of elements in the list is 0 or 1.

The *quicksort* is a bit more difficult to animate and compare because its efficiency depends upon the implementation. In this demonstration, as an *in-place sort*, the steps required to shuffle the values along are not counted as they would not be required if the values were not kept in the boxes.

Do you think that you can apply these techniques to sort some numbers? If so, why not try the interactive sorting game? Also, why not practice your programming skills by creating a program that uses these techniques? *Bubble Sort* and *Selection Sort *are particularly straightforward to program - the *Quicksort* algorithm requires recursion. Click here to download some curriculum programming examples.

There is also a similar page that allows you to compare searching algorithms.