Sorting Secret - Computerphile

Key Takeaways

Today we're going to talk about sorting and in particular we're going to talk about two very well-known sorting methods. One is called selection sort. The other one is called insertion sort. And when people learn about sorting methods, they usually learn about these as being two completely different ideas. You have selection sort on the one hand and insertion sort on the other hand. And what I'm going to show you today is that these are actually the same. You can regard them as being equal. And the trick is that you just draw pictures on them. You don't need any coding to see this. You don't need to know any fancy stuff. In fact, you don't need to know anything about computer science at all. If you just draw a picture of selection sort in the right way and a picture of insertion sort in the right way, you see that they're actually the same thing. And this is kind of a secret about sorting methods that even people like me who've been doing computer science for many years, most people or hardly anybody actually knows this little trick. We'll start off by kind of refreshing ourselves with pictures about what sorting actually is. So let me draw a box. What we're going to do is put some numbers into this box. Doesn't matter how many numbers. Everything which I'm going to show you is completely general, but we'll do it with five. So suppose we do a five and a two and a three and a one and a four. These are the first five numbers in in some kind of random order here. But the key thing is they're not sorted. They're not in ascending order. And what we'd like our sorting box to do is give us the same numbers out but in sorted order. So we'd like to have 1 2 3 4 and five coming out. Let's start to think about how we might construct a little program which implemented this kind of sorting procedure here. The most basic building block which you can think of is just a little box with four sides. What this box is going to do is on the left hand side and on the top side you're going to have two numbers come in and then at the bottom the smallest number is going to pop out and on the right hand side the largest number is going to pop out. So you can think of this as being like a little sorting box for only two numbers. So for example, if we put the number one in on the left hand side and the number two in on the top, then what our little sorting box would do is give us the smallest one out the bottom and it would give us the biggest one out the right hand side. So this is a sorting box for two numbers. And it doesn't matter the order in which the two numbers come in. So if I swap this around and if I had a two coming in here and a one coming in here, it doesn't make any difference. The smallest one is going to pop out the bottom and the biggest one is going to pop out the right hand side. So the game here is we've got this basic building block and we want to kind of plug these together in just with pictures and see how you could build a little sorting program. The trick is that you just build a little triangle of these boxes. So let's put a bunch of these things together. There's a little triangle of these boxes and we're going to just wire them together in a very straightforward way. We'll just draw the obvious little links between them. And each of these boxes just sorts two numbers like we saw a few moments ago. So let's take our little example and just push it through this little uh sorting network and actually see what happens. So I think the numbers we had were five 2 3 1 and four. So out the bottom we hope to get 1 2 3 4 5. So let's see what happens. So we're going to treat the first column first of all and we'll see what happens. So it's really simple. So you've got the two and the five coming into the first box. So the smallest number pops out the bottom. So that's the two. And the biggest number comes out the right hand side. So that's the five. And then we do the same with the second box in the column. So we've got a two coming in and a three coming in. So the smallest number pops out the bottom. And the biggest number comes out the right hand side. And we just do the same again. Then we've got a one and a two. So the one comes out the bottom and the two comes out the right hand side. And then we've got a four and a one. So the one pops out the bottom and the four comes out the right hand side. So what you see is that the smallest number which in this case has one has kind of rippled its way down to the bottom. So what's happened is this first column has selected the smallest number. Okay? And it's quite easy to see that that's the case because the top box selects the smallest from the two numbers it's given and then the second box selects the smallest numbers from the two numbers it's given and so on and so on. So kind of the the smallest number is going to ripple its way down to the bottom. So it's selecting the smallest one. Then we do the same with the with the remaining columns. And we won't be surprised with what happens. So we've got a three coming in and a five coming in. So the three will pop out and the five will pop out here. Then we've got a two and a three. So the two is smaller. So it pops out and the three comes out here. And then we've got a two and a four and the two is the smallest. And then the four pops out the other side. And you see what's happened again from the remaining numbers five 3 2 and four. The second column has selected the smallest one. And then if I just complete this, it's obvious what's going to happen. We get a three here and a five here. Three, four, four, five. So what you see is that our little sorting grid has taken five numbers in a mixed up order and just by pushing them through one column at a time, we've ended up with the numbers in the correct order. And this is known as selection sort because each column just selects the smallest number from what is left. Okay? So nice and easy. You don't need to know anything about computer science, anything about algorithms. Anyone can understand what's going on with selection sort here. But you can actually view this picture in another way. So let me redraw the same picture. Okay. So I just wire it up in exactly the same way as before and we'll push exactly the same five numbers through. So we started off with a five, two, three, one, and a four. So what we did last time is we treated it in terms of the columns. But actually you can do exactly the same thing in terms of the rows. So we'll do one row at a time and actually see what happens. So if we consider the first row, it's the same as before. We get the two and the five coming in and the two pops out here and the five pops out on the right hand side because the two is the smallest one. So we'll do the second row. So what happens? So we've got a two and a three coming in. So the two is the smallest. It will come out at the bottom and the three is the biggest. So it comes out on the right hand side. And then we go over to this box in the row. We've got a three and a five. So the three comes out the bottom and the five comes out the right hand side. So what's actually happened is the second row has taken the two and the five which are already in the right order because the first box did that for us and it's taken the three and it's put the three into the correct place. So maybe if I use a different color here. You can see this. So I've got a two and a five here. And then I've got a three coming in on the left hand side. And what the second row does is it puts the three into the right place. So at the bottom you get two, three, and five. So what the second row has done is inserted this number into the right place. And let's see what happens with the next row. So then we've got a one and a two coming in. So the one comes out the bottom cuz it's the smallest. And then the two comes out here. And we've got a two and a three. So we get the two and the three. And then we've got a three and a five. And the three is the smallest. So it comes out here. What you see is exactly the same thing has happened again. We had a one here. And then we had two, three, and five, which has already been sorted by the grid above us. And then this row here is just going to put the one into the right place. What's popped out the bottom of this grid is 1 2 3 and five. So if we just complete the picture, we'll get the expected result. So we've got a one and a four. So the one is the smallest, so it pops out at the bottom. And the four goes around here. Then we've got a two and a four. So the two pops out and the four and the three and the four. So three is smallest. And then we get the four and the five. This sorting method when you think about the rows rather than the columns is called insertion sort. And it's called insertion sort because each of these rows just inserts a number into the correct position in a sorted sequence. So for example, if we look at the bottom row here, the input on the top is a sorted sequence. 1 2 3 and five. Those are in the right order. And all the bottom row is doing is putting this four into the correct position so that we get one two three four and five. Previously we had exactly the same picture and we said that's selection sort. If you view it in terms of the columns and if you take the same picture now and view it in terms of the rows this way around then we get insertion sort. So for me this is a bit of magic. Uh I've been doing computer science for a long long time. uh I was thinking about how to teach sorting algorithms to my students a few years ago and I came up with this pictorial uh idea and I didn't realize until then that insertion sort and selection sort are exactly the same thing but you only see this if you look at it in the right way using the pictures basically it's all comes all down to perspective right yes exactly it's it's this if you look at stuff in the right way then you can see things that you couldn't see before so if you write programs to do insertion sort or selection sort the kind of structure here which is the same is being is being kind of hidden from you. But if you just draw some simple pictures and forget all your fancy computing, then you end up with an observation which is quite interesting. Have you come across anything else that that is kind of a similar? Have you have you gone through other sort of algorithms and thought thought about them this way? Yeah. So a colleague of mine from Oxford a few years ago, we I was showing him this to him and and he said, "Oh, we we can write a paper about this." So we we tried to look at like quick sort and merge sort and see if they were had the same kind of duality, but it didn't quite work out at the time. and and we kind of gave up writing the paper about it. But um I think this is just a simple observation in its own right here. It's very difficult for a firewall or something to notice this because these are valid HTTP requests. They're just super slow. And um you know, maybe I've just got a really bad internet connection. Maybe.