1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [मर्ज क्रमबद्ध करें]

2
00:00:02,000 --> 00:00:04,000
[रोब Bowden - हार्वर्ड विश्वविद्यालय]

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 के छोटे हमारे गई सूची के 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 और 23, 15 की तुलना छोटे और इसलिए है कि हमारे 3 तत्व है.

39
00:02:21,000 --> 00:02:23,910
अब 16 की तुलना और 23, 16 छोटे है.

40
00:02:23,910 --> 00:02:26,820
तो यह है कि 4 तत्व है.

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 सूचियों का 1 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
1 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
तो अब हम सिर्फ 2 से 4 आकार की सूची है, जिनमें से प्रत्येक का हल है.

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
जबकि बुलबुला तरह सम्मिलन तरह है, और चयन छंटाई के सभी हे (एन ²).

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
>> मेरा नाम रोब Bowden है, और इस 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
[हंसते हुए]

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
[हंसते हुए]

115
00:07:41,190 --> 00:07:44,190
मैं नहीं जानता कि क्या -