1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
1
00:00:00,000 --> 00:00:03,360
>> [Грає музика]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
ДАГ Lloyd: Гаразд,
бульбашкового сортування є алгоритм

4
00:00:06,730 --> 00:00:08,730
Ви можете використовувати для сортування набору елементів.

5
00:00:08,730 --> 00:00:10,850
Давайте поглянемо на те, як це працює.

6
00:00:10,850 --> 00:00:13,240
>> Таким чином, основна ідея
бульбашкового сортування полягає в наступному.

7
00:00:13,240 --> 00:00:17,340
Як правило, ми хочемо, щоб рухатися вище
значення елементів, як правило вправо,

8
00:00:17,340 --> 00:00:20,340
і знизити суму елементів, як правило
ліворуч, як і слід було очікувати.

9
00:00:20,340 --> 00:00:23,256
Ми хочемо, щоб нижні речі, щоб бути в
початок, і більш високі речі

10
00:00:23,256 --> 00:00:24,970
щоб бути в кінці.

11
00:00:24,970 --> 00:00:26,130
>> Як ми це робимо?

12
00:00:26,130 --> 00:00:28,040
Ну в псевдокоду коду,
ми могли б сказати, давайте

13
00:00:28,040 --> 00:00:30,320
встановити лічильник на своп НЕ-нульове значення.

14
00:00:30,320 --> 00:00:32,570
Ми побачимо, чому ми робимо, що в секунду.

15
00:00:32,570 --> 00:00:36,090
А потім ми повторюємо наступні
Процес поки лічильник не підкачки дорівнює 0,

16
00:00:36,090 --> 00:00:39,910
або поки ми не робимо ніяких свопи на всіх.

17
00:00:39,910 --> 00:00:43,170
>> Скидання підкачки лічильник
0, якщо це не вже 0.

18
00:00:43,170 --> 00:00:46,420
Тоді подивіться на кожен
сусідній парою елементів.

19
00:00:46,420 --> 00:00:49,550
Якщо ці два елементи
не в порядку, поміняти їх місцями,

20
00:00:49,550 --> 00:00:51,620
і додати 1 до прилавка підкачки.

21
00:00:51,620 --> 00:00:53,870
Якщо ви думаєте про
це, перш ніж візуалізувати його,

22
00:00:53,870 --> 00:00:57,471
зауважити, що це буде рухатися нижче
значення елементів зліва

23
00:00:57,471 --> 00:01:00,720
і вище цінується елементи права,
ефективно робити те, що ми хочемо зробити,

24
00:01:00,720 --> 00:01:03,940
що рухатися ті групи
елементів таким чином.

25
00:01:03,940 --> 00:01:07,035
Давайте собі, як це
може виглядати за допомогою нашого масиву

26
00:01:07,035 --> 00:01:10,504
що ми використовували для тестування
з цих алгоритмів.

27
00:01:10,504 --> 00:01:13,420
У нас є несортоване масив тут,
вказує всі елементи

28
00:01:13,420 --> 00:01:14,840
перебуваючи в червоний колір.

29
00:01:14,840 --> 00:01:17,970
І я можу встановити лічильник підкачки
в ненульове значення.

30
00:01:17,970 --> 00:01:20,610
Я вибрав довільно
негативне 1-- це не 0.

31
00:01:20,610 --> 00:01:23,840
Ми хочемо, щоб повторити цей процес
до лічильника підкачки не дорівнює 0.

32
00:01:23,840 --> 00:01:26,540
Ось чому я можу встановити своп
врозріз з якоюсь ненульове значення,

33
00:01:26,540 --> 00:01:29,400
оскільки в іншому випадку
Лічильник підкачки буде 0.

34
00:01:29,400 --> 00:01:31,610
Ми навіть не почати
Процес алгоритму.

35
00:01:31,610 --> 00:01:33,610
Отже, ще раз, кроки are--
скинути лічильник підкачки

36
00:01:33,610 --> 00:01:37,900
0, а потім подивитися на кожен поруч
пара, і якщо вони не в порядку,

37
00:01:37,900 --> 00:01:40,514
обміняти їх, і додати 1
до прилавка підкачки.

38
00:01:40,514 --> 00:01:41,680
Отже, давайте почнемо цей процес.

39
00:01:41,680 --> 00:01:44,430
Тому перше, що ми робимо, це
ми встановлюємо лічильник підкачки на 0,

40
00:01:44,430 --> 00:01:46,660
і тоді ми починаємо дивлячись
на кожній суміжній пари.

41
00:01:46,660 --> 00:01:49,140
>> Так ми вперше почати дивитися на 5 і 2.

42
00:01:49,140 --> 00:01:52,410
Ми бачимо, що вони знаходяться поза
замовити і тому ми поміняти їх місцями.

43
00:01:52,410 --> 00:01:53,830
І ми додаємо 1 до прилавка підкачки.

44
00:01:53,830 --> 00:01:57,860
Так що тепер наша підкачки лічильник 1,
і 2 і 5 були включені.

45
00:01:57,860 --> 00:01:59,370
Тепер ми повторюємо цей процес знову.

46
00:01:59,370 --> 00:02:03,540
>> Ми дивимося на наступній суміжній пари,
5 і 1-- вони також вийшли з ладу,

47
00:02:03,540 --> 00:02:06,960
таким чином, ми поміняти їх і додати
1 до прилавка підкачки.

48
00:02:06,960 --> 00:02:08,900
Потім ми розглянемо 5 і 3.

49
00:02:08,900 --> 00:02:13,830
Вони вийшли з ладу, тому ми переставляємо
їх і додати 1 до прилавка підкачки.

50
00:02:13,830 --> 00:02:15,550
Потім ми розглянемо 5 і 6.

51
00:02:15,550 --> 00:02:18,630
Вони в порядку, так що ми насправді не
потрібно поміняти що-небудь в цей раз.

52
00:02:18,630 --> 00:02:20,250
Потім ми розглянемо 6 і 4.

53
00:02:20,250 --> 00:02:24,920
Вони також не в порядку, таким чином, ми поміняти
їх і додати 1 до прилавка підкачки.

54
00:02:24,920 --> 00:02:26,230
>> Тепер зверніть увагу, що сталося.

55
00:02:26,230 --> 00:02:29,514
Ми переїхали 6 весь шлях до кінця.

56
00:02:29,514 --> 00:02:32,180
Таким чином, у виборі роду, якщо у Вас є
видно, що відео, те, що ми робили, було

57
00:02:32,180 --> 00:02:35,290
ми закінчили переміщення
маленькі елементи будівлі

58
00:02:35,290 --> 00:02:39,640
відсортований масив по суті з
зліва направо, від меншого до більшого.

59
00:02:39,640 --> 00:02:43,200
У разі бульбашкового сортування, якщо ми
після цього конкретного алгоритму,

60
00:02:43,200 --> 00:02:46,720
ми насправді збираєтеся будувати
відсортований масив праворуч

61
00:02:46,720 --> 00:02:49,100
наліво, від більшого до меншого.

62
00:02:49,100 --> 00:02:53,840
Ми ефективно пропускають 6,
Найбільше значення, весь шлях до кінця.

63
00:02:53,840 --> 00:02:56,165
>> І таким чином ми можемо оголосити сьогодні
що це сортується,

64
00:02:56,165 --> 00:02:59,130
і в майбутньому iterations--
переживає масиву again--

65
00:02:59,130 --> 00:03:01,280
ми не повинні розглядати 6 більше.

66
00:03:01,280 --> 00:03:03,850
У нас є тільки розглянути
невідсортоване елементи

67
00:03:03,850 --> 00:03:06,299
коли ми дивимося на сусідніх пар.

68
00:03:06,299 --> 00:03:08,340
Таким чином, ми закінчили одне
пройти через бульбашкового сортування.

69
00:03:08,340 --> 00:03:11,941
Так що тепер ми повернемося до питання,
повторювати, поки лічильник заміни не дорівнює 0.

70
00:03:11,941 --> 00:03:13,690
Ну лічильник підкачки
4, так що ми збираємося

71
00:03:13,690 --> 00:03:15,410
щоб повторювати цей процес знову.

72
00:03:15,410 --> 00:03:19,180
>> Ми збираємося, щоб скинути лічильник підкачки
0, і дивитися на кожній суміжній пари.

73
00:03:19,180 --> 00:03:21,890
Отже, ми починаємо з 2 і 1-- вони
в порядку, так що ми обміняти їх

74
00:03:21,890 --> 00:03:23,620
і ми додаємо 1 до прилавка підкачки.

75
00:03:23,620 --> 00:03:25,490
2 і 3, вони в порядку.

76
00:03:25,490 --> 00:03:27,060
Нам не потрібно нічого робити.

77
00:03:27,060 --> 00:03:28,420
3 і 5 в порядку.

78
00:03:28,420 --> 00:03:30,150
Нам не потрібно, щоб зробити що-небудь там.

79
00:03:30,150 --> 00:03:32,515
>> 5 і 4, вони знаходяться поза
порядку, і тому ми

80
00:03:32,515 --> 00:03:35,130
потрібно поміняти їх і додати
1 до прилавка підкачки.

81
00:03:35,130 --> 00:03:38,880
А тепер ми переїхали 5,
другий за величиною елемент,

82
00:03:38,880 --> 00:03:40,920
до кінця несортованих частини.

83
00:03:40,920 --> 00:03:44,360
Так що тепер ми можемо назвати, що
частина відсортованої частини.

84
00:03:44,360 --> 00:03:47,180
>> Тепер ви дивлячись на
Екран і, ймовірно, може сказати,

85
00:03:47,180 --> 00:03:50,130
а я можу, що масив
відсортовано прямо зараз.

86
00:03:50,130 --> 00:03:51,820
Але ми не можемо довести, що ще.

87
00:03:51,820 --> 00:03:54,359
Ми не маємо гарантію
що це сортується.

88
00:03:54,359 --> 00:03:56,900
Але це, де своп
Лічильник збирається вступити в гру.

89
00:03:56,900 --> 00:03:59,060
>> Таким чином, ми завершили прохід.

90
00:03:59,060 --> 00:04:00,357
Лічильник своп 2.

91
00:04:00,357 --> 00:04:02,190
Так що ми збираємося повторити
цей процес знову,

92
00:04:02,190 --> 00:04:04,290
повторювати, поки лічильник заміни не дорівнює 0.

93
00:04:04,290 --> 00:04:05,550
Скидання лічильника підкачки 0.

94
00:04:05,550 --> 00:04:06,820
Таким чином, ми скинути його.

95
00:04:06,820 --> 00:04:09,810
>> Тепер подивимося на кожній суміжній пари.

96
00:04:09,810 --> 00:04:11,880
Це в порядку, 1 і 2.

97
00:04:11,880 --> 00:04:13,590
2 і 3 в порядку.

98
00:04:13,590 --> 00:04:15,010
3 і 4 знаходяться в порядку.

99
00:04:15,010 --> 00:04:19,250
Таким чином, на даний момент, зверніть увагу, ми завершили
дивлячись на кожного сусідній пари,

100
00:04:19,250 --> 00:04:22,530
але лічильник своп раніше 0.

101
00:04:22,530 --> 00:04:25,520
>> Якщо ми не доведеться перемикатися
будь-які елементи, то вони

102
00:04:25,520 --> 00:04:28,340
повинні бути в порядку, від
Гідність цього процесу.

103
00:04:28,340 --> 00:04:32,000
І так що ефективність сортів,
що ми любимо комп'ютерні вчені,

104
00:04:32,000 --> 00:04:35,560
Тепер ми можемо оголосити
весь масив повинен

105
00:04:35,560 --> 00:04:38,160
бути розсортовані, тому що ми не зробили
є, щоб поміняти будь-які елементи.

106
00:04:38,160 --> 00:04:40,380
Це дуже приємно.

107
00:04:40,380 --> 00:04:43,260
>> Так що в гіршому випадку
Сценарій з бульбашкового сортування?

108
00:04:43,260 --> 00:04:46,240
У гіршому випадку масив
У повністю зворотному порядку,

109
00:04:46,240 --> 00:04:49,870
і тому ми повинні один міхура
великих елементів всього

110
00:04:49,870 --> 00:04:51,780
шлях через масив.

111
00:04:51,780 --> 00:04:55,350
І ми ефективно також повинні
міхур всі маленькі елементи назад

112
00:04:55,350 --> 00:04:57,050
весь шлях через масив, теж.

113
00:04:57,050 --> 00:05:01,950
Таким чином, кожен з п елементів повинен рухатися
за всіма іншими п елементів.

114
00:05:01,950 --> 00:05:04,102
Так що це найгірший сценарій.

115
00:05:04,102 --> 00:05:05,810
У кращому випадку
сценарій, хоча це

116
00:05:05,810 --> 00:05:07,880
трохи відрізняється від вибору роду.

117
00:05:07,880 --> 00:05:10,040
Масив вже
відсортовано коли ми йдемо в.

118
00:05:10,040 --> 00:05:12,550
Ми не повинні робити які-небудь
свопи на першому проході.

119
00:05:12,550 --> 00:05:14,940
Таким чином, ми, можливо, доведеться шукати
в меншій кількості елементів, правильно?

120
00:05:14,940 --> 00:05:18,580
Ми не повинні повторити це
обробляти кілька разів.

121
00:05:18,580 --> 00:05:19,540
>> Отже, що ж це означає?

122
00:05:19,540 --> 00:05:22,390
Так що в гіршому випадку
для бульбашкового сортування, і те, що

123
00:05:22,390 --> 00:05:25,330
кращий сценарій для бульбашкового сортування?

124
00:05:25,330 --> 00:05:27,770
Ви здогадалися це?

125
00:05:27,770 --> 00:05:32,420
У гіршому випадку вам доведеться повторювати
по всіх п елементів п раз.

126
00:05:32,420 --> 00:05:34,220
Таким чином, в гіршому випадку буде н в квадраті.

127
00:05:34,220 --> 00:05:36,550
>> Якщо масив прекрасно
відсортований хоча, ви тільки

128
00:05:36,550 --> 00:05:38,580
повинні дивитися один на
елементів відразу.

129
00:05:38,580 --> 00:05:42,670
І якщо лічильник своп раніше 0,
Ви можете сказати, що це масив відсортований.

130
00:05:42,670 --> 00:05:45,780
І так, в кращому випадку, це
насправді краще, ніж вибір

131
00:05:45,780 --> 00:05:49,230
sort-- це омега п.

132
00:05:49,230 --> 00:05:50,270
>> Я Дуг Ллойд.

133
00:05:50,270 --> 00:05:52,140
Це CS50.

134
00:05:52,140 --> 00:05:54,382