Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
1
00:00:05,210 --> 00:00:06,280
So we're going to kick off
2
2
00:00:06,280 --> 00:00:10,000
our look at sort algorithms by starting with bubble sort.
3
3
00:00:10,000 --> 00:00:12,044
I want to say right up front that this
4
4
00:00:12,044 --> 00:00:14,770
algorithm's performance degrades quickly
5
5
00:00:14,770 --> 00:00:17,850
as the number of items you need to sort grows,
6
6
00:00:17,850 --> 00:00:20,330
but it's a commonly taught algorithm
7
7
00:00:20,330 --> 00:00:23,170
and you might hear about it so will take a look at it
8
8
00:00:23,170 --> 00:00:25,860
and it will get us warmed up for the rest of this section.
9
9
00:00:25,860 --> 00:00:27,610
So I'm going to start out by explaining
10
10
00:00:27,610 --> 00:00:29,570
how the algorithm works.
11
11
00:00:29,570 --> 00:00:31,580
So I have an array on this screen,
12
12
00:00:31,580 --> 00:00:34,140
it's an array of length seven
13
13
00:00:34,140 --> 00:00:36,710
so we can store seven integers.
14
14
00:00:36,710 --> 00:00:41,710
At index 0 we have 20, at index 1 35, at index 2 -15.
15
15
00:00:42,580 --> 00:00:44,610
You can see the rest of the array there
16
16
00:00:44,610 --> 00:00:47,800
and we want to use bubble sort to sort this array.
17
17
00:00:47,800 --> 00:00:49,640
Now the way that bubble sort works
18
18
00:00:49,640 --> 00:00:51,090
and you're going to see that this is
19
19
00:00:51,090 --> 00:00:53,960
pretty common with sort algorithms is
20
20
00:00:53,960 --> 00:00:56,470
as the algorithm progresses,
21
21
00:00:56,470 --> 00:01:00,760
it partitions the array into a sorted partition
22
22
00:01:00,760 --> 00:01:03,200
and an unsorted partition
23
23
00:01:03,200 --> 00:01:06,010
and this is a logical partitioning so
24
24
00:01:06,010 --> 00:01:09,840
we don't create completely separate array instances
25
25
00:01:09,840 --> 00:01:12,110
and we an array instance that contains
26
26
00:01:12,110 --> 00:01:13,970
what we've sorted so far and another
27
27
00:01:13,970 --> 00:01:16,350
array instance that contains unsorted numbers.
28
28
00:01:16,350 --> 00:01:19,810
No, everything is done when it comes to bubble sort
29
29
00:01:19,810 --> 00:01:22,350
using the array that we're sorting
30
30
00:01:22,350 --> 00:01:24,850
and we partition the array logically
31
31
00:01:24,850 --> 00:01:25,770
and you're going to see this when
32
32
00:01:25,770 --> 00:01:27,890
we go through the algorithm in just a minute.
33
33
00:01:27,890 --> 00:01:31,780
So when we start the algorithm for this array,
34
34
00:01:31,780 --> 00:01:34,610
we're going to have a field that
35
35
00:01:34,610 --> 00:01:37,360
we're going to call unsorted partition index
36
36
00:01:37,360 --> 00:01:41,340
and when we start this will be 6
37
37
00:01:41,340 --> 00:01:44,730
because the entire array is the
38
38
00:01:44,730 --> 00:01:47,210
unsorted partition when we start out
39
39
00:01:47,210 --> 00:01:49,100
because we haven't sorted anything yet.
40
40
00:01:49,100 --> 00:01:53,660
So 6, it will be the last index of the unsorted partition.
41
41
00:01:53,660 --> 00:01:56,290
Alright, so the implementation that I'm going to show you
42
42
00:01:56,290 --> 00:01:58,990
starts at the left of the array, or at index 0,
43
43
00:01:58,990 --> 00:02:02,110
so that's what I is and what we do
44
44
00:02:02,110 --> 00:02:04,980
is we compare the elemented index 0
45
45
00:02:04,980 --> 00:02:06,280
with the elemented index 1
46
46
00:02:07,330 --> 00:02:10,090
and if the elemented index 0 is greater
47
47
00:02:10,090 --> 00:02:14,510
than the elemented index 1, we swap the elements.
48
48
00:02:14,510 --> 00:02:16,350
If it's less we don't do anything
49
49
00:02:16,350 --> 00:02:19,230
because of course we want to move larger elements
50
50
00:02:19,230 --> 00:02:22,270
towards the end of the array or towards the right
51
51
00:02:22,270 --> 00:02:24,560
because we're sorting in ascending order.
52
52
00:02:24,560 --> 00:02:29,050
So in this case 20 is less than 35
53
53
00:02:29,050 --> 00:02:31,430
so we don't do any swapping
54
54
00:02:31,430 --> 00:02:34,630
and then what we're going to do is increment I to 1.
55
55
00:02:34,630 --> 00:02:37,070
So now we're going to look at
56
56
00:02:37,070 --> 00:02:38,780
the element at position 1
57
57
00:02:38,780 --> 00:02:42,030
and compare it with the element at position 2
58
58
00:02:42,030 --> 00:02:45,543
and in this case 35 is greater than -15,
59
59
00:02:46,510 --> 00:02:47,863
so we swap them.
60
60
00:02:48,740 --> 00:02:51,350
So now -15 will be at position 1
61
61
00:02:51,350 --> 00:02:53,620
and 35 will be at position 2
62
62
00:02:53,620 --> 00:02:55,760
and we increment I to 2.
63
63
00:02:55,760 --> 00:02:57,430
So now we're going to compare the
64
64
00:02:57,430 --> 00:03:01,420
element at index 2 with the elemented index 3.
65
65
00:03:01,420 --> 00:03:05,710
35 is greater than 7 so we swap them
66
66
00:03:05,710 --> 00:03:08,350
and we increment I to 3.
67
67
00:03:08,350 --> 00:03:11,100
So now we're going to compare the elemented index 3
68
68
00:03:11,100 --> 00:03:13,530
with the elemented index 4.
69
69
00:03:13,530 --> 00:03:16,630
35 is less than 55 so we don't do anything
70
70
00:03:16,630 --> 00:03:19,320
we just increment I to 4
71
71
00:03:19,320 --> 00:03:22,000
and then we compare 55 to 1,
72
72
00:03:22,000 --> 00:03:23,700
that's the elemented position 4
73
73
00:03:23,700 --> 00:03:26,010
with the elemented position 5.
74
74
00:03:26,010 --> 00:03:28,960
55 is greater than 1 so we swap them
75
75
00:03:29,800 --> 00:03:32,420
and we increment I to 5
76
76
00:03:32,420 --> 00:03:36,380
and finally we compare 55 to -22
77
77
00:03:36,380 --> 00:03:41,380
and of course 55 is greater than -22 so we swap them
78
78
00:03:42,060 --> 00:03:44,910
and at this point I is equal to
79
79
00:03:44,910 --> 00:03:49,100
the last unsorted partition index so we stop.
80
80
00:03:49,100 --> 00:03:53,610
We have completed the first traversal of the array
81
81
00:03:53,610 --> 00:03:56,210
and at the end of that traversal,
82
82
00:03:56,210 --> 00:04:00,800
the last element in the array is in its correct position
83
83
00:04:00,800 --> 00:04:03,830
and so at this point the greatest element in the array
84
84
00:04:03,830 --> 00:04:07,850
will be at index array length minus one
85
85
00:04:10,080 --> 00:04:13,000
and for our array length minus one is 6.
86
86
00:04:13,000 --> 00:04:16,230
So at this point what we're going to do is
87
87
00:04:16,230 --> 00:04:21,150
we're going to set the unsorted partition index to 5
88
88
00:04:21,150 --> 00:04:24,910
because we now consider position 6 to be sorted
89
89
00:04:24,910 --> 00:04:29,070
and so the logical partition is going to be between
90
90
00:04:29,070 --> 00:04:32,350
the elemented index 5 and the elemented index 6.
91
91
00:04:32,350 --> 00:04:35,520
Everything from index 5 down to the front
92
92
00:04:35,520 --> 00:04:38,050
of the array is in the unsorted partition
93
93
00:04:38,050 --> 00:04:42,160
and everything at array index 6 and to the right,
94
94
00:04:42,160 --> 00:04:44,110
and in this case there isn't anything to the right,
95
95
00:04:44,110 --> 00:04:46,830
everything there is in the sorted partition.
96
96
00:04:46,830 --> 00:04:48,890
So on the next traversal,
97
97
00:04:48,890 --> 00:04:53,630
we can see that 55 is now in the sorted partition
98
98
00:04:53,630 --> 00:04:56,080
and we set I back to zero
99
99
00:04:56,080 --> 00:04:59,290
because we want to repeat the process we just did
100
100
00:04:59,290 --> 00:05:02,400
and the unsorted partition index is now 5.
101
101
00:05:02,400 --> 00:05:05,860
So we start all over again we go OK
102
102
00:05:05,860 --> 00:05:09,040
the element at array index 0
103
103
00:05:09,040 --> 00:05:12,080
is it greater than the element array index 1
104
104
00:05:12,080 --> 00:05:14,870
and it is and so we swap them
105
105
00:05:14,870 --> 00:05:16,820
and we increment I to 1
106
106
00:05:16,820 --> 00:05:17,840
and then we say
107
107
00:05:17,840 --> 00:05:20,710
is the array element at index 1
108
108
00:05:20,710 --> 00:05:22,930
greater than the array element at index 2?
109
109
00:05:22,930 --> 00:05:27,220
Yes it is so we swap them and we increment I to 2.
110
110
00:05:27,220 --> 00:05:29,470
We say is the element at index 2
111
111
00:05:29,470 --> 00:05:31,210
greater than the elemented index 3?
112
112
00:05:31,210 --> 00:05:35,090
No it isn't so we just increment I to 3.
113
113
00:05:35,090 --> 00:05:37,480
Then we compare the elemented index 3
114
114
00:05:37,480 --> 00:05:39,630
to the elemented index 4.
115
115
00:05:39,630 --> 00:05:42,730
35 is greater than one so we swap them,
116
116
00:05:42,730 --> 00:05:44,700
I get incremented to 4 .
117
117
00:05:44,700 --> 00:05:48,860
35 is greater than -22 so we swap them.
118
118
00:05:48,860 --> 00:05:52,150
I gets incremented to 5 and now I equals
119
119
00:05:52,150 --> 00:05:55,200
the unsorted partition index so we stop.
120
120
00:05:55,200 --> 00:06:00,120
And at this point, 35 and 55 are in their correct positions
121
121
00:06:00,120 --> 00:06:04,610
and we set the unsorted partition index to 4.
122
122
00:06:04,610 --> 00:06:07,610
So now everything in array index 0
123
123
00:06:07,610 --> 00:06:11,430
to array index 4 is in the unsorted partition
124
124
00:06:11,430 --> 00:06:14,650
and everything from array index 5
125
125
00:06:14,650 --> 00:06:17,950
up to the end of the array is in the sorted partition
126
126
00:06:17,950 --> 00:06:19,720
and we've set I back to zero
127
127
00:06:19,720 --> 00:06:21,600
because we're now going to repeat the process.
128
128
00:06:21,600 --> 00:06:24,040
Now I'm not going to go through the other traversals,
129
129
00:06:24,040 --> 00:06:26,630
they'll operate the exact same way.
130
130
00:06:26,630 --> 00:06:28,370
We're gonna to keep incrementing I and
131
131
00:06:28,370 --> 00:06:31,220
we're gonna keep comparing the elemented I
132
132
00:06:31,220 --> 00:06:33,640
with its neighbour and swap the elements
133
133
00:06:33,640 --> 00:06:37,210
if its neighbour is less than the elemented I
134
134
00:06:37,210 --> 00:06:40,900
until the sorted partition is the entire array
135
135
00:06:40,900 --> 00:06:41,990
and then we're done.
136
136
00:06:41,990 --> 00:06:44,780
Now this is called a bubble sort because depending on
137
137
00:06:44,780 --> 00:06:47,930
which way you're sorting, in our case the larger
138
138
00:06:47,930 --> 00:06:50,870
values in the array will bubble up to the end of the array
139
139
00:06:50,870 --> 00:06:52,840
and another way of looking at it is to flip
140
140
00:06:52,840 --> 00:06:55,460
the array vertically so we take the array
141
141
00:06:55,460 --> 00:06:58,310
and we flip it counterclockwise so that
142
142
00:06:58,310 --> 00:07:00,610
array element zero is at the bottom and
143
143
00:07:00,610 --> 00:07:02,640
array element 6 is at the top
144
144
00:07:02,640 --> 00:07:03,930
and another way of looking at it
145
145
00:07:03,930 --> 00:07:05,480
is saying that the larger values are
146
146
00:07:05,480 --> 00:07:07,190
bubbling up to the top of the array.
147
147
00:07:07,190 --> 00:07:09,050
Now as I said there are some variations
148
148
00:07:09,050 --> 00:07:11,870
where the array is sorted from right to left
149
149
00:07:11,870 --> 00:07:14,290
so the traversal goes from right to left
150
150
00:07:14,290 --> 00:07:16,570
and sometimes the smaller elements are bubbled
151
151
00:07:16,570 --> 00:07:17,720
to the front of the array
152
152
00:07:17,720 --> 00:07:19,090
rather than the larger elements
153
153
00:07:19,090 --> 00:07:20,870
being bubbled to the back of the array
154
154
00:07:20,870 --> 00:07:22,820
but the same steps are used,
155
155
00:07:22,820 --> 00:07:24,360
it's the same algorithm.
156
156
00:07:24,360 --> 00:07:27,170
So that's bubble sort and so now let's take a look at
157
157
00:07:27,170 --> 00:07:29,290
how this algorithm performs.
158
158
00:07:29,290 --> 00:07:32,120
First of all, it's an in-place algorithm.
159
159
00:07:32,120 --> 00:07:33,500
Now what do I mean by that?
160
160
00:07:33,500 --> 00:07:37,010
Well as I said we're logically partitioning the array.
161
161
00:07:37,010 --> 00:07:39,790
We don't have to create another array
162
162
00:07:39,790 --> 00:07:41,580
in order to perform this sort
163
163
00:07:41,580 --> 00:07:43,160
and so when it comes to memory,
164
164
00:07:43,160 --> 00:07:45,410
this is an in-place algorithm.
165
165
00:07:45,410 --> 00:07:49,240
Now we do, as you see when we look at the implementation,
166
166
00:07:49,240 --> 00:07:52,470
we do create some local variables but that's OK.
167
167
00:07:52,470 --> 00:07:53,990
It's an in-place algorithm.
168
168
00:07:53,990 --> 00:07:56,190
If the extra memory that you need
169
169
00:07:56,190 --> 00:07:59,110
doesn't depend on the number of items you're sorting.
170
170
00:07:59,110 --> 00:08:02,230
So we're going to create a few local variables, for example,
171
171
00:08:02,230 --> 00:08:04,600
to store the last sorted partition
172
172
00:08:04,600 --> 00:08:07,280
and to store I, for example, but
173
173
00:08:07,280 --> 00:08:09,870
that doesn't mean it's not an in-place algorithm.
174
174
00:08:09,870 --> 00:08:12,390
If the extra memory you're using
175
175
00:08:12,390 --> 00:08:14,050
doesn't increase as the number
176
176
00:08:14,050 --> 00:08:16,330
of items in the array increases,
177
177
00:08:16,330 --> 00:08:18,640
then it's still an in-place algorithm.
178
178
00:08:18,640 --> 00:08:21,060
It's OK to use a few extra variables.
179
179
00:08:21,060 --> 00:08:24,530
Now this algorithm has O to the n square time complexity.
180
180
00:08:24,530 --> 00:08:26,680
It's a quadratic algorithm
181
181
00:08:26,680 --> 00:08:31,280
so that means that it will take 100 steps to sort 10 items,
182
182
00:08:31,280 --> 00:08:34,260
10,000 steps to sort 100 items,
183
183
00:08:34,260 --> 00:08:37,690
1,000,000 steps to sort 1,000 items.
184
184
00:08:37,690 --> 00:08:41,030
So as you can see this algorithm really degrades quickly.
185
185
00:08:41,030 --> 00:08:43,510
Now how do we get O to the n squared?
186
186
00:08:43,510 --> 00:08:45,490
Well, we'll talk about this a little more
187
187
00:08:45,490 --> 00:08:46,760
in the next video when we take
188
188
00:08:46,760 --> 00:08:48,450
a look at the implementation.
189
189
00:08:48,450 --> 00:08:49,653
So I'll see you there.
16368
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.