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, bubbled છે
સૌથી મોટું મૂલ્ય, ઓવરને બધી રીતે.

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
તેથી અમે તેઓ 1-- 2 સાથે શરૂ કરો અને
હુકમ બહાર છે, તેથી અમે તેમને સ્વેપ

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
તેથી n તત્વોના દરેક ખસેડવા છે
અન્ય n તત્વોના બધી.

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
ખરાબમાં ખરાબ કિસ્સામાં તમે ફરી વળવું છે
બધા n તત્વોના n વખત સમગ્ર.

126
00:05:32,420 --> 00:05:34,220
તેથી ખરાબ કેસ સ્ક્વેર્ડ n છે.

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
સૉર્ટ તે n ના ઓમેગા છે.

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