# Sorting Algorithms

This interactive and animated page allows you to compare sorting algorithms and their performance. Elsewhere on the site you
can also play an interactive sorting game to practise your sorting skills, or look at programmed
examples to see how to implement the algorithms in *Python* or *BASIC*.

## 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

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 and show the steps as you'd be expected to write them in the answer to an exam question. I've done the same thing for Bubble Sort and Insertion Sort and you can also test your knowledge of the steps required using interactive Bubble Sort, Merge Sort and Insertion Sort games.

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.
There are also coded examples of sorts on the Python examples page.

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