1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [સૉર્ટ કરો મર્જ કરો]

2
00:00:02,000 --> 00:00:04,000
[રોબ બોડેન - હાર્વર્ડ યુનિવર્સિટી]

3
00:00:04,000 --> 00:00:07,000
[આ CS50 છે. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
ચાલો મર્જ સૉર્ટ વિશે વાત કરો.

5
00:00:09,000 --> 00:00:14,000
અત્યાર સુધી તમે બબલ સૉર્ટ કરો, નિવેશ સૉર્ટ કરો, અને પસંદગી સૉર્ટ જોઇ છે.

6
00:00:14,000 --> 00:00:17,000
જોકે હું પડશે હું શું વધુ સારી દ્વારા અર્થ મારા હાથ મોજું પ્રકારની,

7
00:00:17,000 --> 00:00:21,000
મર્જ સૉર્ટ સામાન્ય રીતે આ પ્રકારની 3 કોઈપણ કરતાં વધુ સારી કામગીરી બજાવે છે.

8
00:00:22,000 --> 00:00:27,000
>> પરંતુ મર્જ સૉર્ટ વિશે વાત કરતાં પહેલાં, ચાલો 2 છટણી યાદીઓ મર્જ વિશે વાત કરો.

9
00:00:27,000 --> 00:00:31,000
અમે આ જેવા 2 છટણી યાદીઓ લેવાની પ્રક્રિયા, કૉલ કરશો,

10
00:00:31,000 --> 00:00:35,000
અને તેમને એક જ છટણી યાદી બહાર બનાવે છે - યાદીઓ મર્જ.

11
00:00:35,000 --> 00:00:37,750
અમે આ કેવી રીતે કરી શકો છો?

12
00:00:37,750 --> 00:00:41,290
વેલ, એક વિચાર માત્ર બીજી યાદી ઓવરને પર એક યાદી વળગી છે

13
00:00:41,290 --> 00:00:43,830
અને પછી પરિણામી યાદીમાં સૉર્ટ.

14
00:00:43,830 --> 00:00:47,220
>> જ્યારે આ કામ કરે છે, તે બિનજરૂરી કામ ઘણું છે.

15
00:00:47,220 --> 00:00:49,900
અમે તે માત્ર સૉર્ટ કરતાં વધુ ઝડપથી કરી શકો છો.

16
00:00:49,900 --> 00:00:54,100
નોંધ કરો કે એક ખોટું વિચાર માત્ર દરેક યાદીમાંથી વૈકલ્પિક કપ લેવાનું હોય છે.

17
00:00:54,100 --> 00:00:56,460
જ્યારે કે જે કામો જેવા પ્રથમ લાગે,

18
00:00:56,460 --> 00:01:05,760
આમ કે અમે 4, 8, 15, 23, 16 સાથે અંત - સૂચના કે 16 અને 23 સ્થળ ગઈ છે.

19
00:01:05,760 --> 00:01:09,380
આ કારણ છે કે 2 તત્વો કે મર્જ યાદીમાં સતત દેખાવા જોઈએ

20
00:01:09,380 --> 00:01:11,720
એ જ પ્રારંભિક યાદી છે.

21
00:01:11,720 --> 00:01:14,850
15 અને 16 એમ બંને ડાબી બાજુ પર યાદી છે.

22
00:01:14,850 --> 00:01:19,810
આ યુક્તિ એ હકીકત છે કે બંને યાદીઓ પહેલાથી જ અલગ પાડવામાં આવે છે લાભ લેવા છે.

23
00:01:19,810 --> 00:01:23,320
આનો અર્થ એ થાય કે જો અમે માત્ર બંને યાદીઓ પ્રથમ તત્વો જોવા -

24
00:01:23,320 --> 00:01:29,580
અહીં, 4 અને 8 - તેમાંના એક પણ મર્જ યાદી પ્રથમ તત્વ હોવા જ જોઈએ.

25
00:01:29,580 --> 00:01:31,620
વેલ, તે શા માટે છે?

26
00:01:31,620 --> 00:01:33,520
આ યાદીઓ બંને પહેલેથી જ છટણી કરવામાં આવે છે,

27
00:01:33,520 --> 00:01:38,410
અને તેથી 4 અથવા 8 નાના તત્વ હોય ત્યારે અમે 2 યાદીઓ ભેગા જ જોઈએ.

28
00:01:38,410 --> 00:01:41,770
આ કિસ્સામાં, નાના 4 છે,

29
00:01:41,770 --> 00:01:46,370
તેથી અમે 4 લાગી શકે છે અને તે અમારા મર્જ યાદી પ્રથમ તત્વ બનાવે છે.

30
00:01:46,370 --> 00:01:50,710
હવે અમે પ્રથમ યાદી બાકીના 3 તત્વો ભળીને ચાલુ રાખવા

31
00:01:50,710 --> 00:01:52,920
અને બીજી યાદી 4 તત્વો છે.

32
00:01:52,920 --> 00:01:57,150
>> ફરી એકવાર, અમે માત્ર બંને યાદીઓ પ્રથમ તત્વ અંતે જોવાની જરૂર નથી.

33
00:01:57,150 --> 00:02:01,060
2 ની નાની અમારા મર્જ યાદી બીજા તત્વ હોવા જ જોઈએ.

34
00:02:01,060 --> 00:02:05,440
આ સમય, 8 અને 15 વચ્ચે નાના 8 છે, અને તેથી અમે દાખલ કરો કે જે

35
00:02:05,440 --> 00:02:09,240
અમારા છટણી યાદી બીજા તત્વ તરીકે.

36
00:02:09,240 --> 00:02:12,180
અમે બંને યાદીઓ પ્રથમ તત્વો સાથે સરખામણી ચાલુ રાખી શકો છો

37
00:02:12,180 --> 00:02:14,420
અને 2 ના નાના દૂર કરીને.

38
00:02:14,420 --> 00:02:19,460
15 અને 15 23, સરખામણી નાના અને જેથી અમારા ત્રીજા તત્વ છે.

39
00:02:21,000 --> 00:02:23,910
હવે 16 સરખામણી અને 23, 16 ઓછી છે.

40
00:02:23,910 --> 00:02:26,820
જેથી ચોથા તત્વ છે.

41
00:02:26,820 --> 00:02:30,390
>> નોંધ કરો કે 2 તત્વો પંક્તિ એ જ યાદી હતી.

42
00:02:30,390 --> 00:02:34,400
આ શા માટે થાય છે મર્જ યાદી 2 યાદી માત્ર વૈકલ્પિક તત્વો શકતો નથી.

43
00:02:34,400 --> 00:02:40,020
50 અને 23, 23 સરખામણી નાની હોય છે, તેથી અમે તે પસંદ કરો.

44
00:02:40,770 --> 00:02:44,070
50 અને 42 ની વચ્ચે, 42 ઓછી છે.

45
00:02:44,070 --> 00:02:48,290
50 અને 108 ની વચ્ચે, 50 ઓછી છે.

46
00:02:48,290 --> 00:02:52,330
અને, અંતે અમે માત્ર 108 છે, જેથી તે અમારી યાદી ઓવરને પર જવું આવશ્યક છે.

47
00:02:53,750 --> 00:02:56,180
નોંધ કરો કે અમે સરસ, સોર્ટ યાદી હોય છે.

48
00:02:56,180 --> 00:02:59,040
દર વખતે આપણે 2 યાદીઓ પ્રથમ 2 તત્વો સરખામણીમાં

49
00:02:59,040 --> 00:03:02,730
અમે મર્જ યાદી આગળના તત્વ નક્કી કરવા સમર્થ હતા.

50
00:03:02,730 --> 00:03:08,070
આનો અર્થ એ થાય કે જો અંતિમ યાદી n નંબરો, જ્યાં n અહીં 8 ધરાવે છે,

51
00:03:08,070 --> 00:03:12,610
તો પછી અમે સૌથી n સરખામણીઓ અંતે જરૂર યોગ્ય સ્થાન માં તે નંબરો તમામ મેળવો.

52
00:03:13,230 --> 00:03:16,230
આવી અલ્ગોરિધમનો લિનીઅર સમય ચાલે કહેવાય છે,

53
00:03:16,230 --> 00:03:18,090
પરંતુ તે વિશે અહીં ચિંતા કરશો નહિ.

54
00:03:18,570 --> 00:03:22,810
>> મર્જ માટે અમારા અલ્ગોરિધમનો ઉપયોગ કરીને, આપણે ઝડપી મર્જ સૉર્ટ અલ્ગોરિધમનો કરી શકો છો.

55
00:03:22,810 --> 00:03:25,170
તેથી, ચાલો અમારા યાદીઓ પર ફરીથી સેટ કરી.

56
00:03:35,210 --> 00:03:37,750
ત્યાં મર્જ પ્રકારની પ્રક્રિયા 2 મોટી પગલાંઓ છે.

57
00:03:37,750 --> 00:03:41,500
પ્રથમ, સતત છિદ્ર માં કપ યાદી વિભાજિત

58
00:03:41,500 --> 00:03:44,860
ત્યાં સુધી અમે તેમને 1 કપ સાથે યાદીઓ સમૂહ છે.

59
00:03:44,860 --> 00:03:47,350
ચિંતા કરશો નહીં, જો એક યાદી એક વિચિત્ર નંબર સમાવે છે

60
00:03:47,350 --> 00:03:49,880
અને તમે તેમની વચ્ચે એક સંપૂર્ણપણે સ્વચ્છ કટ કરી શકતા નથી.

61
00:03:49,880 --> 00:03:53,750
જસ્ટ આપખુદ બનાવ્યો યાદી છે કે જે વધારાના કપ સાઇન સમાવવા માટે

62
00:03:53,750 --> 00:03:56,240
તેથી, ચાલો આ યાદીઓ વિભાજિત.

63
00:03:58,140 --> 00:04:01,310
હવે અમે 2 યાદીઓ છે.

64
00:04:04,120 --> 00:04:06,570
હવે અમે 4 યાદીઓ છે.

65
00:04:10,350 --> 00:04:13,870
>> અને હવે અમે દરેક યાદી એક કપ સાથે 8 યાદીઓ છે.

66
00:04:13,870 --> 00:04:16,630
જેથી તે પગલું 1 માટે છે.

67
00:04:16,630 --> 00:04:22,230
પગલું 2 માટે, અમે વારંવાર મર્જ અલ્ગોરિધમનો અમે પહેલાં શીખ્યા મદદથી યાદીઓ જોડીઓ મર્જ.

68
00:04:22,230 --> 00:04:29,160
108 અને 15 મર્જ, અમે 15 યાદી, 108 સાથે અંત.

69
00:04:30,330 --> 00:04:36,250
50 અને 4 મર્જ, અમે 50 4, સાથે અંત.

70
00:04:36,960 --> 00:04:41,400
8 અને 42 મર્જ, અમે 8 સાથે અંત, 42.

71
00:04:42,790 --> 00:04:48,130
અને 23 અને 16 મર્જ, અમે 16 સાથે અંત, 23.

72
00:04:49,740 --> 00:04:52,450
હવે અમારી બધી યાદીઓમાં 2 કદના હોય છે.

73
00:04:53,020 --> 00:04:56,180
નોંધ કરો કે આ યાદીઓ 4 દરેક સૉર્ટ થાય છે.

74
00:04:56,180 --> 00:04:59,160
>> તેથી અમે યાદીઓ જોડીઓ ફરીથી મર્જ શરૂ કરી શકો છો.

75
00:04:59,160 --> 00:05:03,240
15 અને 108 અને 4 અને 50 મર્જ -

76
00:05:03,240 --> 00:05:11,170
પ્રથમ 4 લાગી, પછી 15 ના, તો પછી 50, 108 કે પછી.

77
00:05:11,170 --> 00:05:15,120
8, 42 અને 16, 23 મર્જ,

78
00:05:15,120 --> 00:05:22,440
અમે પ્રથમ 8 ના, તો પછી 16 ના, તો પછી 23 ના, તો પછી 42 ના લો.

79
00:05:22,440 --> 00:05:27,370
તેથી હવે અમે 4 કદ 2 માત્ર યાદીઓ હોય છે, જે પ્રત્યેક સૉર્ટ થાય છે.

80
00:05:27,370 --> 00:05:30,980
તેથી હવે અમે આ 2 યાદીઓ મર્જ.

81
00:05:30,980 --> 00:05:33,440
પ્રથમ અમે 4 લો.

82
00:05:33,440 --> 00:05:36,580
તો પછી અમે 8 ના લો.

83
00:05:36,580 --> 00:05:50,700
તો પછી અમે 15 અને 16, 23 પછી, પછી 42, પછી 50, પછી 108 લે છે.

84
00:05:50,700 --> 00:05:52,220
અને અમે પૂર્ણ કરી લીધું.

85
00:05:52,220 --> 00:05:54,900
હવે અમે એક છટણી યાદી હોય છે.

86
00:05:54,900 --> 00:05:57,890
જેથી ઝડપી આ કેવી રીતે બરાબર હતું?

87
00:05:57,890 --> 00:06:02,000
તકનિકી દ્રષ્ટિએ, મર્જ સૉર્ટ ઓ (n લોગ એન) છે,

88
00:06:02,000 --> 00:06:07,380
જ્યારે બબલ સૉર્ટ કરો, નિવેશ સૉર્ટ કરો, અને પસંદગી પ્રકારના તમામ ગુમાવનારા છે (n ²) હતું.

89
00:06:07,380 --> 00:06:11,120
હકીકત માં, તમે જલદી જાણવા મળશે, તો તમે એક પ્રકારના આંબવું કરી શકશે નહીં

90
00:06:11,120 --> 00:06:14,820
કે સામાન્ય કિસ્સામાં ઓ (n લોગ એન) કરતા વધુ સારી રીતે કરે છે.

91
00:06:14,820 --> 00:06:19,120
ફરીથી, આ મોટી ઓ નોટેશનમાં વિશે ચિંતા જો તમે તેને હજુ સુધી જોઇ ન હોય નથી.

92
00:06:19,120 --> 00:06:23,490
>> જસ્ટ ખબર છે કે આ અર્થ છે જો આપણે ખરેખર મોટી યાદી સૉર્ટ માગે છે

93
00:06:23,490 --> 00:06:26,820
બબલ સૉર્ટ કરો, નિવેશ સૉર્ટ કરો, અને પસંદગી સૉર્ટ સંભવિત સમય લાગી શકે છે

94
00:06:26,820 --> 00:06:29,500
લાંબા સમય સુધી નોંધપાત્ર કરતાં સૉર્ટ મર્જ.

95
00:06:29,500 --> 00:06:33,210
તેનો અર્થ એ નથી કે મર્જ સૉર્ટ તમામ યાદી ઝડપી થશે

96
00:06:33,210 --> 00:06:36,220
અથવા તો એક ચોક્કસ માપ હેઠળ કોઈ એક યાદી માટે.

97
00:06:36,220 --> 00:06:41,950
ઉદાહરણ તરીકે, નિવેશ સૉર્ટ તમામ 5 તત્વો કરતાં નાની યાદી સૌથી ઝડપી સૉર્ટ હોઈ શકે છે.

98
00:06:41,950 --> 00:06:47,360
વ્યવહારમાં, મર્જ સૉર્ટ 50 તત્વો તરીકે નાના તરીકે યાદી ઝડપી હોય છે.

99
00:06:47,360 --> 00:06:51,120
>> પરંતુ આ વધારે ઝડપ ભાવ વિના ન કરવામાં આવે તો.

100
00:06:51,120 --> 00:06:54,770
અમારા અન્ય પ્રકારની જેમ નહિં પણ, કે જે યાદી લઇ અને જગ્યામાં યાદી સુધારવા

101
00:06:54,770 --> 00:06:58,740
ત્યાં સુધી અમે એક છટણી યાદી મેળવવા માટે, મર્જ સૉર્ટ કેટલીક વધારાની જગ્યા જરૂર

102
00:06:58,740 --> 00:07:00,900
2 માટે યાદીઓ મળીને મર્જ.

103
00:07:00,900 --> 00:07:04,690
અમે તરત જ યાદીઓ તે મર્જ કરવામાં આવી રહી છે ને મર્જ યાદી સ્ટોર કરી શકો છો

104
00:07:04,690 --> 00:07:08,880
કારણ કે અમે તત્વો કે હજુ પણ મર્જ કરવાની જરૂર પર ફરીથી લખી શકે છે.

105
00:07:08,880 --> 00:07:13,540
આ જગ્યા કિંમત એક બીટ છે, પરંતુ તે સામાન્ય રીતે ગેરવાજબી નથી.

106
00:07:13,540 --> 00:07:15,330
અને તે મર્જ સૉર્ટ માટે છે.

107
00:07:15,330 --> 00:07:18,490
>> મારું નામ રોબ બોડેન છે, અને આ CS50 છે.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- અને સૉર્ટ પસંદગી.

110
00:07:24,000 --> 00:07:25,880
[Laughs]

111
00:07:25,880 --> 00:07:31,480
ઓહ, કે બહાર લઇ જવા માટે પણ કારણ કે હું સ્વિચ હું કેવી રીતે તે પ્રસ્તુત કરવામાં આવી હતી મળ્યો હતો.

112
00:07:31,480 --> 00:07:35,680
ડાબી બાજુ પર યાદી. કે લખતી વખતની ભૂલો હતી.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] હું ઘણું ખરાબ -

114
00:07:39,290 --> 00:07:41,190
[Laughs]

115
00:07:41,190 --> 00:07:44,190
મને ખબર નથી કે શું -