Numbers index

  5,2,9,1,4   Sorting data   1,2,4,5,9  


Handling data --- Data --- Pictograms --- Graphs --- Mean, median, mode --- Sorting

One thing that you can do with a set of numbers is sort it into order. Either you can do this by hand, or you can get a computer to do it for you. However, in case you're interested, here is how a computer can do it.


Insertion sort

This type of sort starts from one end. It makes sure that all numbers up to one point are sorted. Then it takes the next number, and compares it to the numbers to the left. If it's out of order, it swaps places with the number to its left, and carries on until it's in the right place. That means that we have sorted one more number.

Click on Get unsorted numbers. Then, every time you click on Sort a number, it will sort one number. Watch it moving to its correct position. Obviously to sort all numbers, you will need to click on the button several times, but wait until one number is finished before clicking on the button for the next number. This is quick at the start, then slows down.

 

   

The problem with this sort is that it takes longer and longer the more numbers you have. This is true of all sorts, but this one is worse than most.


Tree sort

The problem with the insertion sort is that you need to compare each new number with every single number you've already sorted which is greater than it. It's more efficient to break down the numbers you've already sorted, so you can position the new number quicker. One way is to put the numbers into a tree. You put the first number at the top of the tree. The next number goes either to the left or the right depending whether it's bigger or smaller. Now each new number need only trace a path down one branch of the tree.

Click on Get unsorted numbers. Then, every time you click on Put red number in tree, it will put one number in the tree. Watch it moving to its correct position. Obviously to sort all numbers, you will need to click on the button several times, but wait until one number is finished before clicking on the button for the next number. At the end, it will give you all numbers sorted in order. This sort is quick at the start, then slows down, but it doesn't end up as slow as the previous sort.

 

   

 

This sort is quite efficient, but you need to work out the tree, which takes time.


Quicksort

Quicksort works in an entirely different way. It takes one number in the set. In these examples, I've chosen the first, but it could be any of the numbers. This is called the pivot. Now it rearranges all the numbers so numbers lower than the pivot are to the left of it, and numbers higher than the pivot are to the right. These numbers are not in the correct order themselves, necessarily. All we've done is to make sure that the pivot is in its correct final place. For the next pass, we choose a new pivot from the numbers on the left, and position that correctly within the left-hand numbers in the same way. Then we do the same to the right. Gradually, we find pivots in the smaller and smaller sets of numbers, until finally all is in order.

Click on Get unsorted numbers. Then every time you click on Position a number, it selects a pivot (red), and position it in the correct place, by comparing it to each number in turn (which is pink). It places in front of it lower numbers (pale blue) and above it higher numbers (darker blue). It stops when it meets a previously sorted pivot. Any previous pivots are changed to green, and you can see that they don't move. Obviously to sort all numbers, you will need to click on the button several times, but wait until one number is in the correct position before clicking on the button for the next number. The first pass is slow, then it gets faster.

 

   

This sort is faster than the insertion sort, especially for large collections of numbers (which we don't have here). This is because we break down the set into smaller and smaller sets, and sort those. Sorting small sets is far faster than sorting larger ones, so this is more efficient. It is better than the tree sort as you can sort the numbers in place. However, for small sets of numbers like these, it can be frustrating when the pivot keeps being too close to one end!