1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [બબલ સોર્ટ]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP હાર્વર્ડ યુનિવર્સિટી]

3
00:00:04,560 --> 00:00:07,500
[આ CS50 છે. CS50TV]

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
પછી તેને પસાર-throughs સંખ્યાબંધ નંબર સમાન લે છે

46
00:02:17,840 --> 00:02:19,730
n-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 iterations લાગી રહ્યું છે.

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
n-1 વખત, કે જ્યાં n એરે માં સંખ્યાબંધ તત્વો છે તે કરતાં વધુ.

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
>> સમગ્ર એરે મારફતે મીટર iterations પછી,

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, 2, 3], [6, 5, 9, 2, 3], [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 એ 'bubbled અપ' માટે હશે

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
પ્રથમ બે પાસ-throughs પછી.

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
બે iterations પછી, અમે ખાતરી જમણીબાજુનીસ્થિતિ બે ઘટકો તેની જગ્યાએ છે જાણી.

76
00:03:43,050 --> 00:03:48,260
તેથી, સામાન્ય રીતે, પૂર્ણ એરે મારફતે k iterations પછી,

77
00:03:48,260 --> 00:03:51,550
છેલ્લા k તત્વો ચકાસણી રીડન્ડન્ટ છે કારણ આપણે જાણીએ છીએ

78
00:03:51,550 --> 00:03:52,360
તેઓ યોગ્ય સ્થાન પહેલાથી જ છો.

79
00:03:52,360 --> 00:03:54,870
>> તેથી જો તમે n તત્વોના ઝાકઝમાળ સૉર્ટ કરી રહ્યા છો,

80
00:03:54,870 --> 00:03:57,870
પ્રથમ પુનરાવૃત્તિ પર - you'll માટે બધા તત્વો સૉર્ટ હોય - પ્રથમ-n 0.

81
00:03:57,870 --> 00:04:04,170
બીજા પુનરાવૃત્તિ પર, તમે આ બધા તત્વો પરંતુ છેલ્લા જોવા મળશે -

82
00:04:04,170 --> 00:04:07,090
આ n-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
જો તે પહેલાથી જ છટણી છે, અમે કોઇપણ વધુ iterations બનાવવા જરૂર નથી

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
કોઈપણ ઘટકો છે કે જે એક ઓર્ડર પદ્ધતિ હોય કામ tweaked.

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
તેના રનટાઈમ સૌથી ખરાબ કેસ n ના મોટા ઓ છે ચોરસ

108
00:05:12,370 --> 00:05:14,810
કારણ કે તમે યાદી મારફતે n iterations બનાવવા હોય

109
00:05:14,810 --> 00:05:18,430
તમામ n તત્વોના ચકાસણી દરેક પાસ થ્રુ, nxn = n ધરાવે છે.

110
00:05:18,430 --> 00:05:22,730
આ સ્કોર સમય અર્થ એ છે કે સંખ્યાબંધ તત્વો તરીકે તમે વધારો સૉર્ટ કરી રહ્યા છો,

111
00:05:22,730 --> 00:05:24,330
આ સમય રન quadratically વધારે છે.

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
CS50.TV