1
00:00:00,000 --> 00:00:03,220


2
00:00:03,220 --> 00:00:06,053
DAVID: Let's see this maybe in more
slow motion, if you will, Brian,

3
00:00:06,053 --> 00:00:07,803
and if you could be a
little more pedantic

4
00:00:07,803 --> 00:00:09,440
and explain exactly what you're doing.

5
00:00:09,440 --> 00:00:13,910
I see you've already reset the numbers
to their original, unsorted order.

6
00:00:13,910 --> 00:00:16,840
Why don't we go ahead and start
a little more methodically.

7
00:00:16,840 --> 00:00:19,390
And could you go ahead and,
for us, more slowly this time,

8
00:00:19,390 --> 00:00:21,670
select the smallest value?

9
00:00:21,670 --> 00:00:23,500
Because I do think,
per Peter, it's going

10
00:00:23,500 --> 00:00:25,690
to need to end up at the far left.

11
00:00:25,690 --> 00:00:26,440
BRIAN: Yeah, sure.

12
00:00:26,440 --> 00:00:27,690
So I'm looking at the numbers.

13
00:00:27,690 --> 00:00:28,910
And the 1 is the smallest.

14
00:00:28,910 --> 00:00:30,498
So I now have the smallest value.

15
00:00:30,498 --> 00:00:32,540
DAVID: All right, so you
did that really quickly.

16
00:00:32,540 --> 00:00:35,800
But I feel like you took the liberty
of being a human who can have this

17
00:00:35,800 --> 00:00:37,600
bird's-eye view of
everything all at once.

18
00:00:37,600 --> 00:00:39,610
But be a little more
computer-like if you could.

19
00:00:39,610 --> 00:00:41,360
And if these eight
numbers are technically

20
00:00:41,360 --> 00:00:44,290
an array, kind of like my
seven doors out here, such

21
00:00:44,290 --> 00:00:48,310
that you can only look at one number at
a time, can you be even more methodical

22
00:00:48,310 --> 00:00:51,640
and deliberate this time in telling
us how you found the smallest

23
00:00:51,640 --> 00:00:53,360
number to put into place?

24
00:00:53,360 --> 00:00:53,860
BRIAN: Sure.

25
00:00:53,860 --> 00:00:56,710
I guess, since the computer can
only look at one number at a time,

26
00:00:56,710 --> 00:00:58,600
I would start at the
left side of this array

27
00:00:58,600 --> 00:01:01,940
and work my way through the right,
looking at each number one at a time.

28
00:01:01,940 --> 00:01:04,540
So I might start with the 6
and say, OK, this right now

29
00:01:04,540 --> 00:01:06,712
is the smallest number
I've looked at so far.

30
00:01:06,712 --> 00:01:08,170
But then I look at the next number.

31
00:01:08,170 --> 00:01:08,780
And it's a 3.

32
00:01:08,780 --> 00:01:10,030
And that's smaller than the 6.

33
00:01:10,030 --> 00:01:13,250
So now the 3, that's the smallest
number I've found so far.

34
00:01:13,250 --> 00:01:14,950
So I'll remember that and keep looking.

35
00:01:14,950 --> 00:01:16,242
The 8 is bigger than the three.

36
00:01:16,242 --> 00:01:17,742
So I don't need to worry about that.

37
00:01:17,742 --> 00:01:19,030
The 5 is bigger than the 3.

38
00:01:19,030 --> 00:01:20,590
The 2 is smaller than the 3.

39
00:01:20,590 --> 00:01:23,405
So that now is the smallest
number I found so far.

40
00:01:23,405 --> 00:01:24,280
But I'm not done yet.

41
00:01:24,280 --> 00:01:25,155
So I'll keep looking.

42
00:01:25,155 --> 00:01:26,500
The 7 is bigger than the 2.

43
00:01:26,500 --> 00:01:28,000
The 4 is bigger than the 2.

44
00:01:28,000 --> 00:01:29,620
But the 1 is smaller than the 2.

45
00:01:29,620 --> 00:01:32,290
So now I've made my way all the
way to the end of the array.

46
00:01:32,290 --> 00:01:34,990
And 1, I can say, is the
smallest number that I've found.

47
00:01:34,990 --> 00:01:38,198
DAVID: OK, so what I'm hearing is you're
doing all of these comparisons, also

48
00:01:38,198 --> 00:01:39,640
similar to what Peter implied.

49
00:01:39,640 --> 00:01:41,433
And you keep checking, is this smaller?

50
00:01:41,433 --> 00:01:42,100
Is this smaller?

51
00:01:42,100 --> 00:01:42,580
Is the smaller?

52
00:01:42,580 --> 00:01:45,580
And you're keeping track of the
currently smallest number you've seen.

53
00:01:45,580 --> 00:01:45,970
BRIAN: Yeah.

54
00:01:45,970 --> 00:01:46,690
That sounds about right.

55
00:01:46,690 --> 00:01:47,860
DAVID: All right, so you found it.

56
00:01:47,860 --> 00:01:49,550
And I think it belongs at the beginning.

57
00:01:49,550 --> 00:01:51,190
So how do we, put, this into place now?

58
00:01:51,190 --> 00:01:52,840
BRIAN: Yeah, so I want to
put it at the beginning.

59
00:01:52,840 --> 00:01:54,173
There's not really space for it.

60
00:01:54,173 --> 00:01:57,113
So I could make space for it just
by shifting these numbers over.

61
00:01:57,113 --> 00:01:58,030
DAVID: OK, wait, wait.

62
00:01:58,030 --> 00:02:01,450
But I feel like you're just-- now
you're doubling the amount of work.

63
00:02:01,450 --> 00:02:02,200
Don't do all that.

64
00:02:02,200 --> 00:02:04,658
That feels like you're going
to do more steps than we need.

65
00:02:04,658 --> 00:02:06,010
What else could we do here?

66
00:02:06,010 --> 00:02:09,073
BRIAN: OK, so the other option
is it needs to go in this spot,

67
00:02:09,073 --> 00:02:10,490
like this first spot in the array.

68
00:02:10,490 --> 00:02:11,840
So I could just put it there.

69
00:02:11,840 --> 00:02:15,080
But if I do that, I'm going to have to
take the 6, which is there right now,

70
00:02:15,080 --> 00:02:16,510
and pull the 6 out.

71
00:02:16,510 --> 00:02:17,750
The 1's in the right place.

72
00:02:17,750 --> 00:02:18,470
But the 6 isn't.

73
00:02:18,470 --> 00:02:18,970
DAVID: Yeah.

74
00:02:18,970 --> 00:02:19,270
I agree.

75
00:02:19,270 --> 00:02:20,478
But I think that's OK, right?

76
00:02:20,478 --> 00:02:22,640
Because these numbers started randomly.

77
00:02:22,640 --> 00:02:24,612
And so the 6 is in the
wrong place anyway.

78
00:02:24,612 --> 00:02:27,820
I don't think we're making the problem
any worse by just moving it elsewhere.

79
00:02:27,820 --> 00:02:29,695
And indeed, it's a lot
faster, I would think,

80
00:02:29,695 --> 00:02:32,890
to just swap two numbers, move
one to the other and vise versa,

81
00:02:32,890 --> 00:02:35,600
that shift all of those
numbers in between.

82
00:02:35,600 --> 00:02:36,100
BRIAN: Yeah.

83
00:02:36,100 --> 00:02:39,078
So I took the 1 out of the position
at the very end of the array all

84
00:02:39,078 --> 00:02:40,370
the way on the right-hand side.

85
00:02:40,370 --> 00:02:42,850
So I guess I could take
the 6 and just put it there

86
00:02:42,850 --> 00:02:45,480
because that's where there's an
open space to put the number.

87
00:02:45,480 --> 00:02:45,980
DAVID: Yeah.

88
00:02:45,980 --> 00:02:47,690
It's not exactly in the right space.

89
00:02:47,690 --> 00:02:48,710
But, again, it's no worse off.

90
00:02:48,710 --> 00:02:49,210
So I like that.

91
00:02:49,210 --> 00:02:51,490
All right, but now the fact
that the 1 is in the right place

92
00:02:51,490 --> 00:02:53,860
and, indeed, you've illuminated
it to indicate as much,

93
00:02:53,860 --> 00:02:56,110
I feel like we can pretty
much ignore the 1 henceforth

94
00:02:56,110 --> 00:02:58,280
and now just select the
next smallest element.

95
00:02:58,280 --> 00:02:59,660
So can you walk us through that?

96
00:02:59,660 --> 00:02:59,920
BRIAN: Yeah.

97
00:02:59,920 --> 00:03:01,545
So I guess I'd repeat the same process.

98
00:03:01,545 --> 00:03:02,470
I start with the 3.

99
00:03:02,470 --> 00:03:04,475
That's the smallest
number I found so far.

100
00:03:04,475 --> 00:03:05,350
And I'd keep looking.

101
00:03:05,350 --> 00:03:06,700
The 8 is bigger than the 3.

102
00:03:06,700 --> 00:03:08,230
The 5 is bigger than the 3.

103
00:03:08,230 --> 00:03:09,610
The 2 is smaller than the 3.

104
00:03:09,610 --> 00:03:10,660
So I'll remember that 2.

105
00:03:10,660 --> 00:03:12,460
That's the smallest
thing I've seen so far.

106
00:03:12,460 --> 00:03:15,640
And then I just need to check to see
if there's anything smaller than the 2.

107
00:03:15,640 --> 00:03:18,148
And I look at the 7, the 4, and the 6.

108
00:03:18,148 --> 00:03:19,690
None of those are smaller than the 2.

109
00:03:19,690 --> 00:03:23,390
So the 2, I can say, is the next
smallest number for the array.

110
00:03:23,390 --> 00:03:23,890
DAVID: OK.

111
00:03:23,890 --> 00:03:25,360
And where would you put that then?

112
00:03:25,360 --> 00:03:27,152
BRIAN: That needs to
go in the second spot.

113
00:03:27,152 --> 00:03:28,540
So I'll need to pull the 3 out.

114
00:03:28,540 --> 00:03:31,930
And I guess I can take the 3 and
just put it into this open spot

115
00:03:31,930 --> 00:03:33,620
where there's available space.

116
00:03:33,620 --> 00:03:34,120
DAVID: Yeah.

117
00:03:34,120 --> 00:03:36,280
And I feel like it's
starting to become clear

118
00:03:36,280 --> 00:03:37,930
that we're inside some
kind of loop because you

119
00:03:37,930 --> 00:03:40,300
pretty much told the same story
again, but with a different number.

120
00:03:40,300 --> 00:03:42,310
Do you mind just continuing
the algorithm to the end

121
00:03:42,310 --> 00:03:44,590
and select the next smallest,
next smallest, next smallest

122
00:03:44,590 --> 00:03:45,470
and get this sorted?

123
00:03:45,470 --> 00:03:45,970
BRIAN: Sure.

124
00:03:45,970 --> 00:03:46,900
So we got the 8.

125
00:03:46,900 --> 00:03:48,130
5 is smaller than that.

126
00:03:48,130 --> 00:03:49,460
3 is smaller than that.

127
00:03:49,460 --> 00:03:52,210
And then the rest of the numbers,
7, 4, 6, those are all bigger.

128
00:03:52,210 --> 00:03:55,450
So the 3, that's going to go
into sorted position here.

129
00:03:55,450 --> 00:03:57,610
And I'll take the 8 and swap it.

130
00:03:57,610 --> 00:03:59,010
Now I'm going to look at the 5.

131
00:03:59,010 --> 00:04:00,490
8 and 7 are both bigger.

132
00:04:00,490 --> 00:04:02,110
The 4 is smaller than the 5.

133
00:04:02,110 --> 00:04:03,280
But the 6 is bigger.

134
00:04:03,280 --> 00:04:05,990
So the 4, that's the smallest
number I've seen so far.

135
00:04:05,990 --> 00:04:07,960
So the 4, that's going to go into place.

136
00:04:07,960 --> 00:04:09,610
And I'll swap it with the 5.

137
00:04:09,610 --> 00:04:11,170
And now I've got the 8.

138
00:04:11,170 --> 00:04:12,460
The 7 is smaller than the 8.

139
00:04:12,460 --> 00:04:13,377
So I'll remember that.

140
00:04:13,377 --> 00:04:14,560
5 is smaller than that.

141
00:04:14,560 --> 00:04:16,000
But the 6 is bigger.

142
00:04:16,000 --> 00:04:18,610
So the 5, that's going
to be the next number.

143
00:04:18,610 --> 00:04:21,370
And now I'm left with 7.

144
00:04:21,370 --> 00:04:22,048
8 is bigger.

145
00:04:22,048 --> 00:04:23,590
So 7 is still the smallest I've seen.

146
00:04:23,590 --> 00:04:25,000
But 6 is smaller.

147
00:04:25,000 --> 00:04:26,770
So 6 goes next.

148
00:04:26,770 --> 00:04:29,020
And now I'm down to the last two.

149
00:04:29,020 --> 00:04:32,450
And between the last two, the
8 and the 7, the 7 is smaller.

150
00:04:32,450 --> 00:04:35,050
So the 7 is going to go in this spot.

151
00:04:35,050 --> 00:04:37,150
And at this point, I've
only got one number left.

152
00:04:37,150 --> 00:04:39,880
So that number must
be in sorted position.

153
00:04:39,880 --> 00:04:42,740
And now I would say that this
is a sorted array of numbers.

154
00:04:42,740 --> 00:04:43,240
DAVID: Nice.

155
00:04:43,240 --> 00:04:45,850
So it definitely seems to be correct.

156
00:04:45,850 --> 00:04:46,773
It felt a little slow.

157
00:04:46,773 --> 00:04:48,940
But, of course, a computer
could do this much faster

158
00:04:48,940 --> 00:04:50,720
than we, using an actual array.

159
00:04:50,720 --> 00:04:52,720
And if you don't mind my
making an observation,

160
00:04:52,720 --> 00:04:57,320
it looks like if we have eight numbers
to begin with, or n more generally.

161
00:04:57,320 --> 00:05:01,720
It looks like you essentially
did n minus 1 comparisons

162
00:05:01,720 --> 00:05:04,370
because you kept
comparing numbers again.

163
00:05:04,370 --> 00:05:05,703
Actually, you did n comparisons.

164
00:05:05,703 --> 00:05:08,245
You looked at the first number
and then you compared it again

165
00:05:08,245 --> 00:05:10,610
and again and again at all
of the other possible values

166
00:05:10,610 --> 00:05:12,845
in order to find the smallest elements.

167
00:05:12,845 --> 00:05:15,220
BRIAN: Yeah because for each
of the numbers in the array,

168
00:05:15,220 --> 00:05:18,890
I had to do a comparison to see, is
it smaller than the smallest thing

169
00:05:18,890 --> 00:05:21,010
that I've seen so far?

170
00:05:21,010 --> 00:05:22,000