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

Algorithm:

Step interval :

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.