Sorting is another very important area of algorithms.
Computers often have to sort large amounts of data into order based on some attribute of that data, such as sorting a list of files by their name or size, or emails by the date they were received, or a customer list according to people's names.
Most of the time this is done to make searching easier.
For example you might have a large amount of data and each piece of data could be someone's name and their phone number.
If you want to search for someone by name it would help to first have the data sorted alphabetically according to everyones names, but if you then wanted to search for a phone number it would be more useful to have the data sorted according to people's phone numbers.
Like searching there are many different sorting algorithms, but some take much longer than others.
In this section you will be introduced to two slower algorithms and one much better one.
Throughout this section you can use the sorting interactive to test out the algorithms we talk about.
When you're using it make sure you take note of the comparisons at the bottom of the screen, each time you compare two boxes the algorithm is making 'one comparison' so the total number of comparisons you have to make with each algorithm is the cost of that algorithm for the 8 boxes.
Use the scales to compare the boxes (you can only compare two boxes at a time) and then arrange them along the bottom of the screen.
Arrange them so that the lightest box is on the far left and the heaviest is on the far right.
Once you think they are in order click 'Test order'.
If the interactive does not run properly on your computer you can use a set of physical balance scales instead; just make sure you can only tell if one box is heavier than the other, not their exact weight (so not digital scales that show the exact weight).
One of the most intuitive ways to sort a group of boxes into order, from lightest to heaviest, is to start by first finding the lightest (or the heaviest) box and placing that to the side.
Try this with the scales interactive.
After finding the lightest box simply repeat the process again with the remaining boxes until you find the second lightest, now place that to the side alongside the lightest box.
If you keep repeating this process you will eventually find you have placed each box into order.
Try sorting the whole group of boxes in the scales interactive into order using this method and count how many comparisons you have to make.
Tip: Start by moving all the boxes to the right of the screen and then once you have found the lightest box place it to the far right (if you want to find the heaviest first instead then move them all to the left).
If you record how many comparisons you had to make each time to find the next lightest box you might notice a pattern (hint: finding the lightest should take 7 comparisons, and then finding the second lightest should take 6 comparisons…).
If you can see the pattern then how many comparisons do you think it would take to then sort 9 boxes into order?
What about 20? If you knew how many comparisons it would take to sort 1000 boxes, then how many more comparisons would it take to sort 1001 instead?
This algorithm is called selection sort, because each time you look through the list you are 'selecting' the next lightest box and putting it into the correct position.
If you go back to the algorithms racing interactive at the top of the page you might now be able to watch the selection sort list and understand what it is doing at each step.
The selection sort algorithm can be described as follows:
Find the smallest item in the list and place it to one side. This will be your sorted list.
Next find the smallest item in the remaining list, remove it and place it into your sorted list beside the item you previously put to the side.
Repeat this process until all items have been selected and moved into their correct position in the sorted list.
You can swap the word 'smallest' for 'largest' and the algorithm will still work, as long as you are consistent it doesn't matter if you are looking for the smallest or the largest item each time.
This algorithm works by removing each box from the original group of boxes and inserting it into its correct position in a new sorted list.
Like selection sort, it is very intuitive and people often perform it when they are sorting objects themselves, like cards in their hands.
Try this with the scales interactive.
Start by moving all the boxes to one side of the screen, this is your original, and unsorted, group.
Now choose a box at random and place that on the other side of the screen, this is the start of your sorted group.
To insert another box into the sorted group, compare it to the box that is already in the sorted group and then arrange these two boxes in the correct order.
Then to add the next box compare it to these boxes (depending on the weight of the box you might only have to compare it to one!) and then arrange these three boxes in the correct order.
Continue inserting boxes until the sorted list is complete.
Don't forget to count how many comparisons you had to make!
This algorithm is called insertion sort.
If you're not quite sure if you've got the idea of the algorithm yet then have a look at this animation from Wikipedia.
Insertion sort can be described with informal instructions as follows:
Take an item from your unsorted list and place it to the side, this will be your sorted list.
One by one, take each item from the unsorted list and insert it into the correct position in the sorted list.
Do this until all items have been sorted.
People often perform this when they physically sort items.
It can also be a very useful algorithm to use if you already have a sorted set of data and want to add a new piece of data into the set.
For example if you owned a library and purchased a new book you wouldn't do a selection sort on the entire library just to place this new book, you would simply insert the new book in its correct place.
Insertion and selection sort may seem like logical ways to sort things into order, but they both take far too many comparisons when they are used for large amounts of data.
Remember computers often have to search through HUGE amounts of data, so even if they use a good searching algorithm like binary search to look through their data, if they use a bad sorting algorithm to first sort that data into order then finding anything will take far too long!
A much better sorting algorithm is quicksort! (the name is a bit of a giveaway)
This algorithm is a little more complicated, but very powerful.
To do this algorithm with the sorting interactive, start by randomly choosing a box and placing it on the scales.
Now compare every other box to the one you selected; heavier boxes should be put on the right of the second row and lighter boxes are put on the left.
When you are done, place the box you were comparing everything else to between these two groups, but to help you keep track of things, put it in the row below.
The following example shows how it might look after this step.
Note that the selected block is in the right place for the final sorted order, and everything on either side will remain on the side that it is on.
Now apply this process to each of the two groups of boxes (the lighter ones, then the heavier ones).
Keep on doing this until they are all sorted. The boxes should then be in sorted order!
It might be worth trying this algorithm out a few times and counting the number of comparisons you perform each time.
This is because sometimes you might be unlucky and happen to pick the heaviest, or the lightest box first.
On the other hand you might be very lucky and choose the middle box to compare everything to first.
Depending on this the number of comparisons you perform will change.
Quicksort can be described in the following way:
Choose an item from the list and compare every other item in the list to this (this item is often called the pivot).
Place all the items that are greater than it into one subgroup and all the items that are smaller into another subgroup.
Place the pivot item in between these two subgroups.
Choose a subgroup and repeat this process.
Eventually each subgroup will contain only one item and at this stage the items will be in sorted order.
Code to run selection sort and quicksort for yourself
Project
The following files will run selection sort and quicksort in various languages; you can use them to generate random lists of values and measure how long they take to be sorted.
Note how long these take for various amounts of input (n), and show it in a table or graph.
You should notice that the time taken by quicksort is quite different to that taken by selection sort.
A Scratch implementation of selection sort and quicksort can be downloaded below.
There are dozens of sorting algorithms that have been invented; most of the ones that are used in practice are based on quicksort and/or mergesort.
These, and many others, can be seen in this intriguing animated video.
