1
00:00:00,000 --> 00:00:00,180


2
00:00:00,180 --> 00:00:03,460
SPEAKER 1: Let's take a look at how
you might have solved the sort problem.

3
00:00:03,460 --> 00:00:05,880
In this problem, we gave
you three different programs

4
00:00:05,880 --> 00:00:09,650
that used three different sorting
algorithms, selection sort, bubble

5
00:00:09,650 --> 00:00:11,050
sort, and merge sort.

6
00:00:11,050 --> 00:00:12,990
But we didn't tell you which was which.

7
00:00:12,990 --> 00:00:15,930
And your job was to figure it
out by timing these programs

8
00:00:15,930 --> 00:00:17,820
on various different inputs.

9
00:00:17,820 --> 00:00:21,362
For example, we gave you
this file random10000.txt

10
00:00:21,362 --> 00:00:25,560
with 10,000 numbers in random
order, potentially sort.

11
00:00:25,560 --> 00:00:28,140
And one thing you might
have tried is recognizing

12
00:00:28,140 --> 00:00:31,859
that both bubble sort and
selection sort have a Big O running

13
00:00:31,859 --> 00:00:33,990
time of Big O of n squared.

14
00:00:33,990 --> 00:00:37,560
Whereas merge sort has a Big
O running time of n log n.

15
00:00:37,560 --> 00:00:41,970
Then, for large random inputs, you
should probably expect that merge sort

16
00:00:41,970 --> 00:00:46,980
is going to be significantly faster than
both bubble sort and selection sort.

17
00:00:46,980 --> 00:00:50,730
So if we try these three programs
on a file like random10000,

18
00:00:50,730 --> 00:00:54,570
but you might try it on some others,
too, you would expect that merge sort

19
00:00:54,570 --> 00:00:56,100
should be the fastest.

20
00:00:56,100 --> 00:00:57,510
Let's try it out.

21
00:00:57,510 --> 00:01:04,019
Let's time ./sort1 on random10000.txt
and see how long it takes to run

22
00:01:04,019 --> 00:01:07,260
./sort1 on these 10,000 numbers.

23
00:01:07,260 --> 00:01:14,010
Here we see that it took 0.505 seconds
for ./sort1, so about half a second.

24
00:01:14,010 --> 00:01:17,520
Let's try it again for ./sort2, and
see how long it takes ./sort2 to do

25
00:01:17,520 --> 00:01:20,030
the same thing with the same file.

26
00:01:20,030 --> 00:01:20,700
OK.

27
00:01:20,700 --> 00:01:26,970
It took, in real terms, 0.038 seconds,
significantly faster than the nearly

28
00:01:26,970 --> 00:01:29,400
half a second it took for ./sort1.

29
00:01:29,400 --> 00:01:32,230
But just for good measure,
let's try ./sort3 as well.

30
00:01:32,230 --> 00:01:36,120
And compare ./sort3 against the other
two sorting algorithms in terms of how

31
00:01:36,120 --> 00:01:37,230
long it takes.

32
00:01:37,230 --> 00:01:41,310
And it looks like this one also
takes a little over half a second

33
00:01:41,310 --> 00:01:44,430
to be able to sort these 10,000 numbers.

34
00:01:44,430 --> 00:01:48,630
So based on that information, it seems
pretty reasonable to conclude that

35
00:01:48,630 --> 00:01:52,890
./sort2, the one which was the fastest
on dealing with these random inputs,

36
00:01:52,890 --> 00:01:54,880
is probably merge sort.

37
00:01:54,880 --> 00:01:57,630
Between the other two, whether
it's selection sort or bubble sort,

38
00:01:57,630 --> 00:01:59,460
we really don't know for sure just yet.

39
00:01:59,460 --> 00:02:03,450
But it's probably a pretty good guess
that ./sort2 is going to be merge sort.

40
00:02:03,450 --> 00:02:06,960
And you could verify that for yourself
by testing it on some other inputs

41
00:02:06,960 --> 00:02:08,160
as well.

42
00:02:08,160 --> 00:02:12,960
But now we need to figure out some way
of distinguishing ./sort1 from ./sort3.

43
00:02:12,960 --> 00:02:16,430
Which one is bubble sort and
which one is selection sort?

44
00:02:16,430 --> 00:02:19,440
And to do that, we can take
advantage of what we know about each

45
00:02:19,440 --> 00:02:21,810
of their big omega running times.

46
00:02:21,810 --> 00:02:25,710
Bubble sort, we know, has a
big omega of n running time.

47
00:02:25,710 --> 00:02:29,310
In an ideal case where all of
the numbers are already sorted,

48
00:02:29,310 --> 00:02:31,260
bubble sort can sort
the numbers very easily.

49
00:02:31,260 --> 00:02:34,530
It'll go through each of the
numbers, one pair at a time,

50
00:02:34,530 --> 00:02:37,110
and realize that there
are no swaps necessary,

51
00:02:37,110 --> 00:02:41,370
and then just declare that the numbers
are already sorted in linear time

52
00:02:41,370 --> 00:02:45,870
without needing to make multiple passes
through the array again and again.

53
00:02:45,870 --> 00:02:49,860
So we should expect that even though
these two sorting algorithms had

54
00:02:49,860 --> 00:02:52,710
a very similar running
time on a random file,

55
00:02:52,710 --> 00:02:56,280
if we gave them a big file that
was already in sorted order,

56
00:02:56,280 --> 00:03:00,460
bubble sort should be much
faster than selection sort.

57
00:03:00,460 --> 00:03:01,890
So let's try it out.

58
00:03:01,890 --> 00:03:04,620
The biggest file that's
all in sorted order we have

59
00:03:04,620 --> 00:03:10,330
is sorted50000.txt, with 50,000 numbers,
each of which is in sorted order.

60
00:03:10,330 --> 00:03:16,170
And let's try timing ./sort1
on that sorted50000.txt file,

61
00:03:16,170 --> 00:03:19,890
and see how long it takes in order to
sort all of those numbers and print

62
00:03:19,890 --> 00:03:21,340
them out as well.

63
00:03:21,340 --> 00:03:25,320
It looks like it took a little over
three seconds for ./sort1 to be able

64
00:03:25,320 --> 00:03:27,420
to sort and then print,
all of those numbers,

65
00:03:27,420 --> 00:03:31,350
recognizing that it's going to take
some time to print 50,000 numbers

66
00:03:31,350 --> 00:03:33,010
to the terminal as well.

67
00:03:33,010 --> 00:03:39,120
But let's compare that then to ./sort3
on that same input, sorted50000,

68
00:03:39,120 --> 00:03:42,750
and see how much time it takes
for ./sort3 to do the same thing,

69
00:03:42,750 --> 00:03:47,730
sort these 50,000 numbers that are
already in sorted order themselves.

70
00:03:47,730 --> 00:03:50,220
Whereas ./sort1 took
about three seconds,

71
00:03:50,220 --> 00:03:53,580
it looks like this algorithm
is taking closer to 7 seconds,

72
00:03:53,580 --> 00:03:56,448
more than double the
amount of time required.

73
00:03:56,448 --> 00:03:59,490
And so based on that, and you could
do some additional experiments, maybe

74
00:03:59,490 --> 00:04:01,750
testing these multiple times as well.

75
00:04:01,750 --> 00:04:07,110
But for sorted numbers, it seems that
./sort1 is outperforming ./sort3,

76
00:04:07,110 --> 00:04:10,680
whereas for numbers in random order,
they're behaving pretty similarly.

77
00:04:10,680 --> 00:04:15,480
And that, then, is a pretty good sign
that ./sort1 is probably bubble sort

78
00:04:15,480 --> 00:04:20,100
and ./sort3 is probably selection sort,
given that we know that bubble sort

79
00:04:20,100 --> 00:04:23,480
performs better when the numbers
are already in sorted order,

80
00:04:23,480 --> 00:04:26,970
whereas selection sort still needs
to go through that entire array,

81
00:04:26,970 --> 00:04:29,970
looking for the smallest
element every single time,

82
00:04:29,970 --> 00:04:32,220
making multiple passes
through the array,

83
00:04:32,220 --> 00:04:35,220
even if the array is
already in sorted order.

84
00:04:35,220 --> 00:04:38,160
And that then gives us our
answer for which algorithm

85
00:04:38,160 --> 00:04:40,540
is in use by each of these programs.

86
00:04:40,540 --> 00:04:42,780
./sort1 is using bubble sort.

87
00:04:42,780 --> 00:04:44,750
./sort2 is using merge sort.

88
00:04:44,750 --> 00:04:47,610
And ./sort3 is using selection sort.

89
00:04:47,610 --> 00:04:48,720
My name is Brian.

90
00:04:48,720 --> 00:04:51,050
And this was sort.

91
00:04:51,050 --> 00:04:52,000