All language subtitles for 2. Bubble Sort (Theory)

af Afrikaans
ak Akan
sq Albanian
am Amharic
ar Arabic Download
hy Armenian
az Azerbaijani
eu Basque
be Belarusian
bem Bemba
bn Bengali
bh Bihari
bs Bosnian
br Breton
bg Bulgarian
km Cambodian
ca Catalan
chr Cherokee
ny Chichewa
zh-CN Chinese (Simplified)
zh-TW Chinese (Traditional)
co Corsican
hr Croatian
cs Czech
da Danish
nl Dutch
en English
eo Esperanto
et Estonian
ee Ewe
fo Faroese
tl Filipino
fi Finnish
fr French
fy Frisian
gaa Ga
gl Galician
ka Georgian
de German
el Greek
gn Guarani
gu Gujarati
ht Haitian Creole
ha Hausa
haw Hawaiian
iw Hebrew
hi Hindi
hu Hungarian
is Icelandic
ig Igbo
id Indonesian
ia Interlingua
ga Irish
it Italian
ja Japanese
jw Javanese
kn Kannada
kk Kazakh
rw Kinyarwanda
rn Kirundi
kg Kongo
ko Korean
kri Krio (Sierra Leone)
ku Kurdish
ckb Kurdish (Soranî)
ky Kyrgyz
lo Laothian
la Latin
lv Latvian
ln Lingala
lt Lithuanian
loz Lozi
lg Luganda
ach Luo
mk Macedonian
mg Malagasy
ms Malay
ml Malayalam
mt Maltese
mi Maori
mr Marathi
mfe Mauritian Creole
mo Moldavian
mn Mongolian
sr-ME Montenegrin
ne Nepali
pcm Nigerian Pidgin
nso Northern Sotho
no Norwegian
nn Norwegian (Nynorsk)
oc Occitan
or Oriya
om Oromo
ps Pashto
fa Persian
pl Polish
pt-BR Portuguese (Brazil)
pt-PT Portuguese (Portugal)
pa Punjabi
qu Quechua
ro Romanian
rm Romansh
nyn Runyakitara
ru Russian
gd Scots Gaelic
sr Serbian
sh Serbo-Croatian
st Sesotho
tn Setswana
crs Seychellois Creole
sn Shona
sd Sindhi
si Sinhalese
sk Slovak
sl Slovenian
so Somali
es Spanish
es-419 Spanish (Latin American)
su Sundanese
sw Swahili
sv Swedish
tg Tajik
ta Tamil
tt Tatar
te Telugu
th Thai
ti Tigrinya
to Tonga
lua Tshiluba
tum Tumbuka
tr Turkish
tk Turkmen
tw Twi
ug Uighur
uk Ukrainian
ur Urdu
uz Uzbek
vi Vietnamese
cy Welsh
wo Wolof
xh Xhosa
yi Yiddish
yo Yoruba
zu Zulu
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.