Molly Roberts

Finally! You’ve packed your bags and are ready to put everything in the car and get going. Off to sunny Spain, perhaps, snowy Canada, or, well… Rainy England. Nevertheless, you are excited, you are free, you don’t have to use your brain for a week, nothing can get you down.

Except possibly the huge, enormous, supremely disorganised pile of luggage waiting at the door for you to put in the car.

But never fear! Again, maths is here to save the day. What’s the golden rule of packing? Put the biggest things in first, followed by the smallest. But you are stressed. The bags are heavy. The idea of carrying them all around your house in order to sort them into decreasing order of size is a nightmare. And so we will use an algorithm.

As in part 1 of this series, we will be making a few assumptions before we begin in order to make our lives easier.

1. The bags are initially ordered. Doesn’t matter what order, just so long as they each have a unique position in the line.
2. The way we will measure size is, as in part 1, by volume. This is by no means the only, or even the best, way of doing this, but it is the most convenient for now.

With these assumptions in place, let’s go ahead and look at a couple of the algorithms we could use to sort the bags into descending order.

Bubble Sort

As the name suggests, you might imagine the smaller suitcases bubbling up to the end of the line, whilst the larger suitcases remain nearer the door. The algorithm is carried out in a series of passes, each one beginning with the bag nearest the door. Here’s how it works:

Pass 1

Step 1: Compare the volume of the first and second bags. If the first bag does not have a smaller volume than the second, go to step 2. Otherwise, switch the positions of the bags, and go to step 2.

Step 2: Compare the volume of the second and third bags. If the second bag does not have a smaller volume than the third, go to step 3. Otherwise, switch the positions of the bags, and go to step 3.

.

.

.

(Continue comparing volumes in the same way, switching only if the first value in the pair is smaller than the second)

.

.

.

Final Step: Compare the volume of the penultimate and ultimate bags. If the penultimate bag does not have a smaller volume than the ultimate, stop. Otherwise, switch the positions of the bags and stop.

At the end of this pass, the bag with the smallest volume will be in the position farthest from the door, as it is always smaller than any bag it is compared with, and so will always switch. The second pass imitates the first pass, except that you need to carry out one less step since the last bag is in the correct position and need not be compared with anything. Continue with this until a pass contains no switches, and then the bags will all be in order.

This algorithm is one of those things in maths which is a lot easier to understand when you have an example. So let’s try it. We will begin with four bags of volumes 100, 200, 400, and 300 litres respectively (if you actually know how big bags are, these values seem ridiculous, but I wanted to pick simple numbers). Here are how the bags start:

Pass 1

Step 1: Compare 100 and 200. 100 is smaller than 200 so they swap. The order is now 200, 100, 400, 300.

Step 2: Compare 100 and 400. 100 is smaller than 400 so they swap. The order is now 200, 400, 100, 300.

Step 3: Compare 100 and 300. 100 is smaller than 300 so they swap. The order is now 200, 400, 300, 100.

As you can see, at the end of the first pass, 100 – the smallest – is in the correct position.

Pass 2

Step 1: Compare 200 and 400. 200 is smaller than 400 so they swap. The order is now 400, 200, 300, 100.

Step 2: Compare 200 and 300. 200 is smaller than 300 so they swap. The order is now 400, 300, 200, 100.

Now, as you can see, 200 is also in the correct position after the second pass. In fact, all of the bags are in the correct positions, but in order for the algorithm to finish, we would need to carry out a third pass to ensure that there are no more swaps in the next pass. This is because algorithms are often carried out by computers, and unlike humans, computers are unable to just look at all the bags at once and say ‘yeah, I’m done’. For convenience, I won’t include the third pass here, but it would just involve comparing 400 and 300, and realising they don’t need to be swapped.

For only four bags, this was a fairly quick process. The most number of comparisons we would have to do would be 6 (3 in the first pass, 2 in the second, and 1 in the third). However, for a large number of bags, this could be an awful lot higher. Not to mention the constant running back to the door every time you reach the other end of your luggage.

So is there perhaps another algorithm which might be better?

Cocktail Shaker Sort

Okay, I’m not going to lie. At least 90% of the reason I included this algorithm here was because it had a holiday-appropriate name. You could view carrying out this algorithm as the first cocktail of the holiday, and indeed you might feel pleasantly tipsy – or utterly bamboozled – once you have tried it.

The cocktail shaker sort is essentially a bidirectional version of the bubble sort. That is, once you’ve finished the first pass, instead of jogging resignedly back to your front door, you start sorting through your bags in the opposite direction. To see how it works in practice let’s try sorting out the bags from above using this algorithm.

Pass 1 would be exactly the same as pass 1 of bubble sort, and at the end you have the bags in the order 200, 400, 300, 100, with 100 in the correct (and now fixed) position. Pass 2 will start from 300, since 100 is now fixed, and we begin from the opposite end. At the end of pass 1, the bags were in the position:

Pass 2

Step 1: Compare 300 and 400. 300 is smaller than 400 so no swaps are made. The order remains the same.

Step 2: Compare 400 and 200. 200 is smaller than 400 so they swap. The order is now 400, 200, 300, 100.

At the end of this pass, 400 is now in its fixed position, since we have carried bubble sort out in the opposite direction – 400 is the biggest so it will switch with every other bag it is compared to. There is only one more pass necessary, because only two numbers aren’t fixed, and they will either stay the same or swap. To save time, let’s not write out the last pass. We know that 200 and 300 must switch.

Like bubble sort, this method can also be extended too much longer lines of luggage. The one big advantage it has is that it could potentially save you a lot of running back to the beginning. However, I think you would agree that it still seems like it would take far more time than you’ve got if you’re already late for your flight.

Luckily, there are plenty of other sorting algorithms which you could use to sort luggage into order. One which might catch your eye if you’re in a hurry is quicksort which – as the name suggests – tends to take less time to carry out, especially with a larger number of bags. However, I stick by the fact that bubble sort feels like the most intuitive sorting method, and being a nerd, I do enjoy carrying it out. Also, it has a strong advantage over sorting your bags out without an algorithm, which is that if you follow the instructions properly, there is no room for error. Why don’t you have a bit of fun and try carrying out bubble sort and cocktail shaker sort on a longer list of numbers? For example, try and sort into descending order the list: 1, 6, 7, 8, 3, 5, 9, 2, 4.

[Scroll down for the answers!]

.

.

.

.

.

.

.

.

.

.

.

.

Answers

Bubble sort:

• After pass 1: 6, 7, 8, 3, 5, 9, 2, 4, 1
• After pass 2: 7, 8, 6, 5, 9, 3, 4, 2, 1
• After pass 3: 8, 7, 6, 9, 5, 4, 3, 2, 1
• After pass 4: 8, 7, 9, 6, 5, 4, 3, 2, 1
• After pass 5: 8, 9, 7, 6, 5, 4, 3, 2, 1
• After pass 6: 9, 8, 7, 6, 5, 4, 3, 2, 1
• After pass 7: 9, 8, 7, 6, 5, 4, 3, 2, 1

Cocktail shaker sort:

• After pass 1: 6, 7, 8, 3, 5, 9, 2, 4, 1
• After pass 2: 9, 6, 7, 8, 3, 5, 4, 2, 1
• After pass 3: 9, 7, 8, 6, 5, 4, 3, 2, 1
• After pass 4: 9, 8, 7, 6, 5, 4, 3, 2, 1
• After pass 5: 9, 8, 7, 6, 5, 4, 3, 2, 1

If you enjoyed this article, and want to check out the other stages of the journey, you can find them at the links below.

Mathematical Holiday Part 1 – Packing The Bags

Mathematical Holiday Part 3 – Using The Sat Nav