Sorting Algorithms

One of the most important new sections in the National Curriculum for KS3 Computing is about algorithms. An understanding of certain 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, or way, or doing something.

Sometimes the order of the steps doesn't matter too much, but sometimes if you swap two of the steps around, things don't work properly - e.g. if you pour the water into the cup before you boil the kettle when you're making a cup of tea. Sometimes, one way of doing things might be more efficient than another. For example, if you want to visit the house next door, would you turn the opposite way and walk around the block to get there, or would you just go there directly?

Changes to an algorithm can make a big difference to how a program runs.  You can use this page to compare sorting algorithms.  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.  You can also play my interactive sorting game or look at my programmed examples in BASIC or Python

This page animates the sorting of your own numbers using different algorithms. You can enter ten numbers in the Inputs section below, or you can use the Random button to generate ten random numbers.   You can then select a sorting algorithm, and how quick 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.

You can click Start 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. Click here to download some curriculum programming examples.

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