Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
1
00:00:00,295 --> 00:00:03,545
(bright ambient music)
2
2
00:00:05,310 --> 00:00:06,910
Alright, so the challenge
3
3
00:00:06,910 --> 00:00:10,380
was to modify the implementation of Merge Sort
4
4
00:00:10,380 --> 00:00:13,540
so that it sorts the integers in descending order
5
5
00:00:13,540 --> 00:00:15,630
and this is the start project
6
6
00:00:15,630 --> 00:00:17,810
that was in the resources section.
7
7
00:00:17,810 --> 00:00:20,313
So if we just go ahead and run right now,
8
8
00:00:22,230 --> 00:00:24,600
we'll see that the Merge Sort is sorting
9
9
00:00:24,600 --> 00:00:27,800
in ascending order because this is essentially the code
10
10
00:00:27,800 --> 00:00:29,610
that we did in the Merge Sort video.
11
11
00:00:29,610 --> 00:00:32,170
We want descending order, so let's go ahead
12
12
00:00:32,170 --> 00:00:33,130
and look at the code.
13
13
00:00:33,130 --> 00:00:35,660
Now, the splitting phase doesn't have to change,
14
14
00:00:35,660 --> 00:00:37,270
I mean all the splitting phase does
15
15
00:00:37,270 --> 00:00:39,310
is keeps dividing the array into two.
16
16
00:00:39,310 --> 00:00:41,320
It doesn't care whether you're sorting
17
17
00:00:41,320 --> 00:00:43,510
in ascending or descending order.
18
18
00:00:43,510 --> 00:00:46,800
So we don't need to change the Merge Sort method at all.
19
19
00:00:46,800 --> 00:00:50,210
What we have to change, is the merge step,
20
20
00:00:50,210 --> 00:00:52,820
because that's the step when we're comparing elements
21
21
00:00:52,820 --> 00:00:55,460
in the right and left arrays against each other
22
22
00:00:55,460 --> 00:00:58,630
and writing them in sorted order to a temporary array.
23
23
00:00:58,630 --> 00:00:59,690
So when we're doing that,
24
24
00:00:59,690 --> 00:01:02,410
instead of sorting them into ascending order,
25
25
00:01:02,410 --> 00:01:05,070
we want to sort them into descending order.
26
26
00:01:05,070 --> 00:01:07,800
So there are two places that we have to change
27
27
00:01:07,800 --> 00:01:08,830
in this merge method.
28
28
00:01:08,830 --> 00:01:11,500
The first place is this optimization.
29
29
00:01:11,500 --> 00:01:13,710
In the Merge Sort video, we went through
30
30
00:01:13,710 --> 00:01:15,710
what this optimization is doing.
31
31
00:01:15,710 --> 00:01:18,590
It's essentially checking to see whether you actually
32
32
00:01:18,590 --> 00:01:21,700
have to do any merging because if this condition
33
33
00:01:21,700 --> 00:01:24,750
is true when we're sorting in ascending order,
34
34
00:01:24,750 --> 00:01:27,130
then it means that all the elements in the left array
35
35
00:01:27,130 --> 00:01:29,500
are less than all the elements in the right array.
36
36
00:01:29,500 --> 00:01:31,160
And because the left array and right array
37
37
00:01:31,160 --> 00:01:33,170
are in sorted order, it would mean that
38
38
00:01:33,170 --> 00:01:34,943
if we copied them to a temporary array,
39
39
00:01:34,943 --> 00:01:38,600
we'd just end up copying the temporary array
40
40
00:01:38,600 --> 00:01:41,730
back into the input array and none of the elements,
41
41
00:01:41,730 --> 00:01:44,940
the positions of none of the elements would change.
42
42
00:01:44,940 --> 00:01:47,440
This optimization avoids needless work,
43
43
00:01:47,440 --> 00:01:49,810
but if we're sorting in descending order,
44
44
00:01:49,810 --> 00:01:51,650
this no longer makes sense.
45
45
00:01:51,650 --> 00:01:54,960
What we wanna know now, is whether all of the elements
46
46
00:01:54,960 --> 00:01:58,340
in the left array are greater or equal
47
47
00:01:58,340 --> 00:02:00,630
to all of the elements in the right array.
48
48
00:02:00,630 --> 00:02:01,980
Because if that's the case,
49
49
00:02:01,980 --> 00:02:03,460
then we don't have to do any work.
50
50
00:02:03,460 --> 00:02:05,110
So our first change here
51
51
00:02:05,110 --> 00:02:08,750
is going to be greater than or equal.
52
52
00:02:08,750 --> 00:02:10,780
If all the elements in the left array
53
53
00:02:10,780 --> 00:02:13,070
are greater than or equal, then all of the elements
54
54
00:02:13,070 --> 00:02:14,740
in the right array, we don't actually
55
55
00:02:14,740 --> 00:02:16,140
have to do any merging.
56
56
00:02:16,140 --> 00:02:18,600
If we were to merge them, we'd just end up
57
57
00:02:18,600 --> 00:02:21,660
sticking the right array onto the end of the left array
58
58
00:02:21,660 --> 00:02:25,350
and then we'd have that entire range of elements
59
59
00:02:25,350 --> 00:02:27,600
sorted in descending order.
60
60
00:02:27,600 --> 00:02:29,240
Now the second place we have to change
61
61
00:02:29,240 --> 00:02:31,410
is when we're actually doing a merge,
62
62
00:02:31,410 --> 00:02:34,460
and we're traversing the left and right partitions
63
63
00:02:34,460 --> 00:02:36,650
and we're comparing elements in the left array
64
64
00:02:36,650 --> 00:02:38,930
against elements in the right array.
65
65
00:02:38,930 --> 00:02:42,870
So here, we're saying that if the element in the left array
66
66
00:02:42,870 --> 00:02:45,380
is less than or equal to the element in the right array,
67
67
00:02:45,380 --> 00:02:47,870
then we write the element in the left array
68
68
00:02:47,870 --> 00:02:49,480
to the temp array.
69
69
00:02:49,480 --> 00:02:52,400
Obviously, if we're gonna be sorting in descending order,
70
70
00:02:52,400 --> 00:02:55,580
we want to write the larger of the two elements
71
71
00:02:55,580 --> 00:02:57,820
into the temp array first,
72
72
00:02:57,820 --> 00:03:00,170
not the smaller of the two elements.
73
73
00:03:00,170 --> 00:03:01,690
Once again, we're gonna change
74
74
00:03:01,690 --> 00:03:03,380
that to greater and equal to.
75
75
00:03:03,380 --> 00:03:06,960
Now, keeping this equals is extremely important
76
76
00:03:06,960 --> 00:03:09,823
because Merge Sort is supposed to be a stable sort.
77
77
00:03:10,770 --> 00:03:14,580
If we have the situation where the element in the left array
78
78
00:03:14,580 --> 00:03:17,420
is equal to five and the element in the right array
79
79
00:03:17,420 --> 00:03:20,120
is equal to five, we want the one in the left array
80
80
00:03:20,120 --> 00:03:22,680
to be written first, because that will preserve
81
81
00:03:22,680 --> 00:03:26,270
the relative ordering of the duplicates.
82
82
00:03:26,270 --> 00:03:30,070
We want an equals here, if this was just greater than,
83
83
00:03:30,070 --> 00:03:32,140
it would result in the element in the right array
84
84
00:03:32,140 --> 00:03:34,140
being written before the one in the left array
85
85
00:03:34,140 --> 00:03:37,450
and that would turn Merge Sort into an unstable sort
86
86
00:03:37,450 --> 00:03:38,760
and we don't want that.
87
87
00:03:38,760 --> 00:03:40,350
That's it, that's all we have to do
88
88
00:03:40,350 --> 00:03:44,330
to change this implementation to sort the integers
89
89
00:03:44,330 --> 00:03:45,270
in descending order.
90
90
00:03:45,270 --> 00:03:49,540
So let's run, and there you go,
91
91
00:03:49,540 --> 00:03:54,180
55, 35, 20, seven, one,
92
92
00:03:54,180 --> 00:03:56,530
15, and -22.
93
93
00:03:56,530 --> 00:03:58,230
So that was a rather easy one,
94
94
00:03:58,230 --> 00:03:59,750
just to get us warmed up.
95
95
00:03:59,750 --> 00:04:03,193
Alright, so let's move on to challenge number two.
8299
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.