1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [БУББЛЕ СОРТ]

2
00:00:02,840 --> 00:00:04,560
[ЈАЦКСОН СТЕИНКАМП Универзитет Харвард]

3
00:00:04,560 --> 00:00:07,500
[Ово је ЦС50. ЦС50ТВ]

4
00:00:08,000 --> 00:00:11,730
Буббле Сортирај је пример сортирање алгоритмом -

5
00:00:11,730 --> 00:00:14,460
то јест, поступак за сортирање низа елемената у

6
00:00:14,460 --> 00:00:15,840
растућем или опадајућем редоследу.

7
00:00:15,840 --> 00:00:18,710
На пример, ако сте желели да сортирате низ састоји од бројева

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], коректна имплементација Буббле Сортирај би да врати

9
00:00:23,060 --> 00:00:26,260
сортирају низ [2, 3, 5, 9] у растућем редоследу.

10
00:00:26,260 --> 00:00:28,850
Сада ћу да објасним у Псеудокод како алгоритам ради.

11
00:00:28,850 --> 00:00:34,000
>> Рецимо да смо сортирање листу од 5 бројева - 3, 2, 9, 6 и 5.

12
00:00:34,000 --> 00:00:37,650
Алгоритам почиње гледајући прва два елемента, 3 и 2,

13
00:00:37,650 --> 00:00:40,850
и провере да ли су они из реда у односу на другог.

14
00:00:40,850 --> 00:00:43,150
Они су - 3 је већа од 2.

15
00:00:43,150 --> 00:00:45,190
Да буде у растућем редоследу, они би требало да буде обрнуто.

16
00:00:45,190 --> 00:00:46,610
Дакле, ми смо их замене.

17
00:00:46,610 --> 00:00:49,760
Сада је списак изгледа овако: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Даље, гледамо друге и треће елемената, 3 и 9.

19
00:00:52,450 --> 00:00:55,770
Они су у исправном редоследу у односу на другог.

20
00:00:55,770 --> 00:00:58,800
То је, 3 је мање од 9 па алгоритам их не замене.

21
00:00:58,800 --> 00:01:01,900
Даље, ми гледамо у 9 и 6. Они су у квару.

22
00:01:01,900 --> 00:01:04,260
>> Дакле, морамо да их замене јер 9 је већи од 6 година.

23
00:01:04,260 --> 00:01:08,840
На крају, ми погледамо последња два цела броја, 9 и 5.

24
00:01:08,840 --> 00:01:10,850
Они су у реду, тако да они морају бити замењени.

25
00:01:10,850 --> 00:01:13,360
После првог комплетног пролазе кроз листе,

26
00:01:13,360 --> 00:01:17,140
изгледа овако: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Није лоше. То је скоро сортирају.

28
00:01:19,690 --> 00:01:22,450
Али ми треба да пролазе кроз листу да бисте добили потпуно сортирају.

29
00:01:22,450 --> 00:01:29,250
Два мања од 3, тако да их не замене.

30
00:01:29,250 --> 00:01:31,700
>> Три мање од 6 година, тако да их не замене.

31
00:01:31,700 --> 00:01:35,500
Шест је већа од 5. Ми замењивати.

32
00:01:35,500 --> 00:01:38,460
Шест је мање од 9. Ми не мењате.

33
00:01:38,460 --> 00:01:42,170
После другог пролазе кроз то изгледа овако: [2, 3, 5, 6, 9]. Савршено.

34
00:01:42,170 --> 00:01:44,680
Сада, хајде да напишемо је у Псеудокод.

35
00:01:44,680 --> 00:01:48,450
У основи, за сваки елемент у листи, потребно је да погледате

36
00:01:48,450 --> 00:01:50,060
и елеменат директно свог права.

37
00:01:50,060 --> 00:01:53,420
Ако су из реда у односу на другу - то јест, ако је елемент на левој

38
00:01:53,420 --> 00:01:56,810
је већа од оне на десној - ми треба да замените два елемента.

39
00:01:56,810 --> 00:02:01,270
>> Ми ово радимо за сваки елемент листе, а ми смо направили један пролаз кроз.

40
00:02:01,270 --> 00:02:05,160
Сада само треба да урадите пасс-тхроугх довољно пута да обезбеди листу

41
00:02:05,160 --> 00:02:06,480
је у потпуности, правилно поредани.

42
00:02:06,480 --> 00:02:08,889
Али колико пута морамо проћи кроз листи

43
00:02:08,889 --> 00:02:10,400
гарантујем да смо урадили?

44
00:02:10,400 --> 00:02:14,730
Па, најгори сценарио је да ако имамо потпуно уназад листу.

45
00:02:14,730 --> 00:02:17,840
Затим је потребно неколико пасс-тхроугхс једнак броју

46
00:02:17,840 --> 00:02:19,730
елемената н-1.

47
00:02:19,730 --> 00:02:24,720
Ако ово нема смисла интуитивно, мислим једноставног случају - листа [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> То ће да траје један пролаз правилно сортирање.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Најгори случај је да са 3 елемената сортирани уназад,

50
00:02:33,060 --> 00:02:34,830
то ће узети 2 итерација до врсте.

51
00:02:34,830 --> 00:02:37,980
После једне итерације, то је [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Други приноси сортиран низ [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Дакле, ви знате да никада нећете морати да прође кроз низ, у принципу,

54
00:02:43,350 --> 00:02:46,790
више од н-1 пута, где је н број елемената у низу.

55
00:02:47,090 --> 00:02:50,470
То се зове Буббле Сортирај јер највећи елементи теже да се "мехур-уп '

56
00:02:50,470 --> 00:02:51,950
десно прилично брзо.

57
00:02:51,950 --> 00:02:53,980
У ствари, овај алгоритам има веома занимљиву понашање.

58
00:02:53,980 --> 00:02:57,410
>> Након м итерација кроз цео низ,

59
00:02:57,410 --> 00:02:59,000
крајње десне м елементи су гарантована

60
00:02:59,000 --> 00:03:01,000
бити сортирани у свом правом месту.

61
00:03:01,000 --> 00:03:02,280
Ако желите да видите ово за себе,

62
00:03:02,280 --> 00:03:05,500
можемо да пробамо на потпуно уназад листи [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Након једног пролазе кроз целу листу,

64
00:03:08,220 --> 00:03:09,220
[Звук писања]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
десна крајња елеменат 9 је у свом правом месту.

67
00:03:21,250 --> 00:03:24,760
После другог пролаз је 6 ће имати 'бубблед-уп' на

68
00:03:24,760 --> 00:03:26,220
Други десна крајња место.

69
00:03:26,220 --> 00:03:28,840
Два елемента на десној - 6 и 9 - ће бити у њиховим исправним местима

70
00:03:28,840 --> 00:03:30,580
после прва два пасс-тхроугхс.

71
00:03:30,580 --> 00:03:32,590
>> Дакле, како можемо искористити да би оптимизовали алгоритам?

72
00:03:32,590 --> 00:03:34,850
Па, после једне итерације кроз низ

73
00:03:34,850 --> 00:03:37,690
ми заправо не треба да проверите крајње десне елемент

74
00:03:37,690 --> 00:03:39,200
јер знамо да је сређено.

75
00:03:39,200 --> 00:03:43,050
Након два итерација, ми смо сигурни крајње десне два елемента су на месту.

76
00:03:43,050 --> 00:03:48,260
Дакле, у принципу, после к итерација кроз цео низ,

77
00:03:48,260 --> 00:03:51,550
провере последње к елемената је сувишна, јер знамо

78
00:03:51,550 --> 00:03:52,360
они су у исправном месту већ.

79
00:03:52,360 --> 00:03:54,870
>> Дакле, ако сте за сортирање низа од н елемената,

80
00:03:54,870 --> 00:03:57,870
на првој итерацији - иоу'лл да сортирате све елементе - први н-0.

81
00:03:57,870 --> 00:04:04,170
На другој итерацији, мораћете да погледате све елементе, али последњи -

82
00:04:04,170 --> 00:04:07,090
Први н-1.

83
00:04:07,090 --> 00:04:10,520
Други оптимизација може бити да проверите да ли је листа већ сортирана

84
00:04:10,520 --> 00:04:11,710
после сваке итерације.

85
00:04:11,710 --> 00:04:13,900
Ако је вец сортиран, ми не треба да се било више итерација

86
00:04:13,900 --> 00:04:15,310
кроз листу.

87
00:04:15,310 --> 00:04:16,220
Како можемо да урадимо ово?

88
00:04:16,220 --> 00:04:19,360
Па, ако ми не правимо никакве свопови на пролаз листе,

89
00:04:19,360 --> 00:04:22,350
јасно је да је листа сортирана већ зато што нисмо заменили ништа.

90
00:04:22,350 --> 00:04:24,160
Дакле, ми дефинитивно не морају поново да сортирате.

91
00:04:24,160 --> 00:04:27,960
>> Можда бисте могли да покрене променљиву заставе под називом "не сортира 'да

92
00:04:27,960 --> 00:04:30,990
лаж и промените га истина ако морате да мењате никакве елементе на

93
00:04:30,990 --> 00:04:32,290
једна итерација кроз низ.

94
00:04:32,290 --> 00:04:35,350
Или слично, направи контра да рачунају колико свопови правите

95
00:04:35,350 --> 00:04:37,040
на било ком итерације.

96
00:04:37,040 --> 00:04:40,040
На крају једне итерације, ако нисте заменили неки од елемената,

97
00:04:40,040 --> 00:04:41,780
знате листа већ сортира и готови сте.

98
00:04:41,780 --> 00:04:44,090
Буббле Сорт, као и друге сортирање алгоритама, могу бити

99
00:04:44,090 --> 00:04:46,960
намештена да ради за било елемената који имају којом методом.

100
00:04:46,960 --> 00:04:50,610
>> То је, с обзиром да су два елемента имају начин да кажу да ли први

101
00:04:50,610 --> 00:04:53,770
је већи него, једнако или мање од секунде.

102
00:04:53,770 --> 00:04:56,870
На пример, можете да сортирате слова алфабета говорећи

103
00:04:56,870 --> 00:05:00,520
да <б, б <ц, итд

104
00:05:00,520 --> 00:05:03,830
Или можете да сортирате дана у недељи у којој Недеља је мање од понедељка

105
00:05:03,830 --> 00:05:05,110
што је мање него у уторак.

106
00:05:05,110 --> 00:05:09,630
>> Буббле Сортирај никако веома ефикасно или брзо сортирање алгоритам.

107
00:05:09,630 --> 00:05:12,370
Његов најгори рунтиме је Велико О н ²

108
00:05:12,370 --> 00:05:14,810
јер морате да направите н итерација кроз листу

109
00:05:14,810 --> 00:05:18,430
провера н елемената сваки пролаз, нкн = н ².

110
00:05:18,430 --> 00:05:22,730
То води пут значи да се као број елемената сте сортирање расте

111
00:05:22,730 --> 00:05:24,330
рун тиме повећава куадратицалли.

112
00:05:24,330 --> 00:05:27,330
>> Али, ако ефикасност није главна брига вашег програма

113
00:05:27,330 --> 00:05:29,550
или ако ви само сортирање мали број елемената,

114
00:05:29,550 --> 00:05:31,660
можда пронађете Буббле Сорт користан јер

115
00:05:31,660 --> 00:05:33,360
то је један од најједноставнијих алгоритама за сортирање разумети

116
00:05:33,360 --> 00:05:34,250
и да кодира.

117
00:05:34,250 --> 00:05:37,270
То је такође одличан начин да стекнете искуство са превођењем теоријско

118
00:05:37,270 --> 00:05:40,220
Алгоритам у стварном функционалну код.

119
00:05:40,220 --> 00:05:43,000
Па, то је Буббле Сорт за тебе. Хвала за гледање.

120
00:05:43,000 --> 00:05:44,000
ЦС50.ТВ