DAVID: Let's see this maybe in more slow motion, if you will, Brian,
and if you could be a little more pedantic
and explain exactly what you're doing.
I see you've already reset the numbers to their original, unsorted order.
Why don't we go ahead and start a little more methodically.
And could you go ahead and, for us, more slowly this time,
select the smallest value?
Because I do think, per Peter, it's going
to need to end up at the far left.
BRIAN: Yeah, sure.
So I'm looking at the numbers.
And the 1 is the smallest.
So I now have the smallest value.
DAVID: All right, so you did that really quickly.
But I feel like you took the liberty of being a human who can have this
bird's-eye view of everything all at once.
But be a little more computer-like if you could.
And if these eight numbers are technically
an array, kind of like my seven doors out here, such
that you can only look at one number at a time, can you be even more methodical
and deliberate this time in telling us how you found the smallest
number to put into place?
BRIAN: Sure.
I guess, since the computer can only look at one number at a time,
I would start at the left side of this array
and work my way through the right, looking at each number one at a time.
So I might start with the 6 and say, OK, this right now
is the smallest number I've looked at so far.
But then I look at the next number.
And it's a 3.
And that's smaller than the 6.
So now the 3, that's the smallest number I've found so far.
So I'll remember that and keep looking.
The 8 is bigger than the three.
So I don't need to worry about that.
The 5 is bigger than the 3.
The 2 is smaller than the 3.
So that now is the smallest number I found so far.
But I'm not done yet.
So I'll keep looking.
The 7 is bigger than the 2.
The 4 is bigger than the 2.
But the 1 is smaller than the 2.
So now I've made my way all the way to the end of the array.
And 1, I can say, is the smallest number that I've found.
DAVID: OK, so what I'm hearing is you're doing all of these comparisons, also
similar to what Peter implied.
And you keep checking, is this smaller?
Is this smaller?
Is the smaller?
And you're keeping track of the currently smallest number you've seen.
BRIAN: Yeah.
That sounds about right.
DAVID: All right, so you found it.
And I think it belongs at the beginning.
So how do we, put, this into place now?
BRIAN: Yeah, so I want to put it at the beginning.
There's not really space for it.
So I could make space for it just by shifting these numbers over.
DAVID: OK, wait, wait.
But I feel like you're just-- now you're doubling the amount of work.
Don't do all that.
That feels like you're going to do more steps than we need.
What else could we do here?
BRIAN: OK, so the other option is it needs to go in this spot,
like this first spot in the array.
So I could just put it there.
But if I do that, I'm going to have to take the 6, which is there right now,
and pull the 6 out.
The 1's in the right place.
But the 6 isn't.
DAVID: Yeah.
I agree.
But I think that's OK, right?
Because these numbers started randomly.
And so the 6 is in the wrong place anyway.
I don't think we're making the problem any worse by just moving it elsewhere.
And indeed, it's a lot faster, I would think,
to just swap two numbers, move one to the other and vise versa,
that shift all of those numbers in between.
BRIAN: Yeah.
So I took the 1 out of the position at the very end of the array all
the way on the right-hand side.
So I guess I could take the 6 and just put it there
because that's where there's an open space to put the number.
DAVID: Yeah.
It's not exactly in the right space.
But, again, it's no worse off.
So I like that.
All right, but now the fact that the 1 is in the right place
and, indeed, you've illuminated it to indicate as much,
I feel like we can pretty much ignore the 1 henceforth
and now just select the next smallest element.
So can you walk us through that?
BRIAN: Yeah.
So I guess I'd repeat the same process.
I start with the 3.
That's the smallest number I found so far.
And I'd keep looking.
The 8 is bigger than the 3.
The 5 is bigger than the 3.
The 2 is smaller than the 3.
So I'll remember that 2.
That's the smallest thing I've seen so far.
And then I just need to check to see if there's anything smaller than the 2.
And I look at the 7, the 4, and the 6.
None of those are smaller than the 2.
So the 2, I can say, is the next smallest number for the array.
DAVID: OK.
And where would you put that then?
BRIAN: That needs to go in the second spot.
So I'll need to pull the 3 out.
And I guess I can take the 3 and just put it into this open spot
where there's available space.
DAVID: Yeah.
And I feel like it's starting to become clear
that we're inside some kind of loop because you
pretty much told the same story again, but with a different number.
Do you mind just continuing the algorithm to the end
and select the next smallest, next smallest, next smallest
and get this sorted?
BRIAN: Sure.
So we got the 8.
5 is smaller than that.
3 is smaller than that.
And then the rest of the numbers, 7, 4, 6, those are all bigger.
So the 3, that's going to go into sorted position here.
And I'll take the 8 and swap it.
Now I'm going to look at the 5.
8 and 7 are both bigger.
The 4 is smaller than the 5.
But the 6 is bigger.
So the 4, that's the smallest number I've seen so far.
So the 4, that's going to go into place.
And I'll swap it with the 5.
And now I've got the 8.
The 7 is smaller than the 8.
So I'll remember that.
5 is smaller than that.
But the 6 is bigger.
So the 5, that's going to be the next number.
And now I'm left with 7.
8 is bigger.
So 7 is still the smallest I've seen.
But 6 is smaller.
So 6 goes next.
And now I'm down to the last two.
And between the last two, the 8 and the 7, the 7 is smaller.
So the 7 is going to go in this spot.
And at this point, I've only got one number left.
So that number must be in sorted position.
And now I would say that this is a sorted array of numbers.
DAVID: Nice.
So it definitely seems to be correct.
It felt a little slow.
But, of course, a computer could do this much faster
than we, using an actual array.
And if you don't mind my making an observation,
it looks like if we have eight numbers to begin with, or n more generally.
It looks like you essentially did n minus 1 comparisons
because you kept comparing numbers again.
Actually, you did n comparisons.
You looked at the first number and then you compared it again
and again and again at all of the other possible values
in order to find the smallest elements.
BRIAN: Yeah because for each of the numbers in the array,
I had to do a comparison to see, is it smaller than the smallest thing
that I've seen so far?