[Powered by Google Translate] [मर्ज क्रमबद्ध करें] [रोब Bowden - हार्वर्ड विश्वविद्यालय] [यह CS50 है. - CS50.TV] चलो मर्ज प्रकार के बारे में बात करते हैं. अब तक आप बुलबुला तरह सम्मिलन तरह है, और चयन छंटाई देखा है. हालांकि मैं हूँ कि मैं क्या मतलब है बेहतर में मेरा हाथ की लहर की तरह, मर्ज तरह आम तौर पर इन 3 प्रकार के किसी भी की तुलना में बेहतर प्रदर्शन करती है. 

लेकिन मर्ज प्रकार के बारे में बात करने से पहले, 2 क्रमबद्ध सूचियों विलय के बारे में बात करते हैं. हम इन तरह 2 क्रमबद्ध सूचियों लेने की प्रक्रिया, फोन करता हूँ, और उनमें से एक भी क्रमबद्ध सूची से बाहर कर सूचियों विलय. हम यह कैसे कर सकते हैं? खैर, एक विचार करने के लिए सिर्फ दूसरी सूची के अंत पर एक सूची छड़ी और फिर जिसके परिणामस्वरूप सूची को सॉर्ट. 

हालांकि यह काम करता है, यह अनावश्यक काम का एक बहुत कुछ है. हम इसे सिर्फ छँटाई की तुलना में तेजी से कर सकते हैं. सूचना है कि एक गलत विचार करने के लिए बस एक सूची से बारी कप ले रहा है. जब तक कि वह काम करता है पहले की तरह लग सकता है, कर रही है कि हम 4, 8, 15, 23, 16 के साथ अंत - सूचना है कि 16 और 23 जगह से बाहर हैं. इसका कारण यह है 2 तत्वों है कि मर्ज किए गए सूची में लगातार दिखाई चाहिए एक ही प्रारंभिक सूची में हैं. दोनों 15 और 16 के बाईं ओर की सूची में हैं. चाल के लिए तथ्य यह है कि दोनों सूचियों को पहले से ही हल कर रहे हैं का लाभ ले रहा है. इसका मतलब यह है कि अगर हम दोनों सूचियों का पहला तत्व पर देखो - यहाँ, 4 और 8 - उनमें से एक भी मर्ज की गई सूची के पहले तत्व होना चाहिए. खैर, ऐसा क्यों है? इन सूचियों के दोनों पहले से ही हल कर रहे हैं, और इसलिए या तो 4 या 8 छोटी तत्व हो सकता है जब हम 2 सूचियों गठबंधन करना चाहिए. इस मामले में, छोटी 4 है, तो हम 4 से बाहर ले सकते हैं और यह हमारे की गई सूची के पहला तत्व है. अब हम पहली सूची की शेष 3 तत्वों विलय जारी और दूसरी सूची के 4 तत्वों. 

एक बार फिर, हम केवल दोनों सूचियों के पहले तत्व को देखने की जरूरत है. 2 के छोटे हमारे गई सूची के 2 तत्व होना चाहिए. इस बार, 8 और 15 के बीच छोटी 8 है, और इसलिए हम डालने के कि हमारे सॉर्ट की गई सूची के दूसरे तत्व के रूप में. हम दोनों सूचियों का पहला तत्व की तुलना करने के लिए जारी कर सकते हैं और 2 के छोटे को हटाने. 15 और 23, 15 की तुलना छोटे और इसलिए है कि हमारे 3 तत्व है. अब 16 की तुलना और 23, 16 छोटे है. तो यह है कि 4 तत्व है. 

सूचना है कि 2 तत्वों को एक पंक्ति में एक ही सूची से आया. यह है क्यों मर्ज किए गए सूची सिर्फ 2 सूचियों से वैकल्पिक तत्वों नहीं कर सकते. 50 और 23, 23 की तुलना में छोटे है, इसलिए हम चुनें कि. 50 और 42 के बीच, 42 छोटी है. 50 और 108 के बीच, 50 छोटी है. और अंत में, हम सिर्फ 108 है, तो यह हमारी सूची के अंत पर जाना चाहिए. सूचना है कि हम एक अच्छा हल सूची है. हर बार हम 2 सूचियों का 1 2 तत्वों की तुलना में हम मर्ज की गई सूची के अगले तत्व निर्धारित करने में सक्षम थे. इसका मतलब यह है कि अगर अंतिम सूची n संख्या है, जहाँ n यहाँ 8, तो हम सबसे n तुलना में सही जगह में उन लोगों की संख्या के सभी मिल की जरूरत है. इस तरह के एक एल्गोरिथ्म रैखिक समय में चलाने के लिए कहा जाता है, लेकिन यह है कि यहाँ के बारे में चिंता मत करो. 

विलय के लिए हमारे एल्गोरिथ्म का उपयोग करना, हम एक तेजी से मर्ज सॉर्ट एल्गोरिथ्म बनाने कर सकते हैं. तो, चलो हमारी सूची रीसेट. मर्ज तरह की प्रक्रिया में 2 बड़े कदम उठाए हैं. सबसे पहले, लगातार हिस्सों में कप की सूची में विभाजित जब तक हम सिर्फ उन में 1 कप के साथ सूचियों का एक गुच्छा है. चिंता मत करो अगर एक सूची में एक विषम संख्या है और आप उन दोनों के बीच एक पूरी तरह से साफ कटौती नहीं कर सकते हैं. बस मनमाने ढंग से लेने की सूची है जो अतिरिक्त कप अंदर शामिल करने के लिए तो, चलो इन सूचियों को विभाजित. अब हम 2 सूची है. अब हम 4 सूची है. 

और अब हम प्रत्येक सूची में एक कप के साथ 8 सूची है. तो यह है कि चरण 1 के लिए है. चरण 2 के लिए, हम बार बार मर्ज एल्गोरिथ्म हम पहले सीखा का उपयोग सूचियों के जोड़े को मर्ज. 108 और 15 मर्ज करना, हम सूची 15, 108 के साथ खत्म होता है. 50 और 4 मर्ज करना, हम 50 4 के साथ खत्म होता है. 8 और 42 मर्ज करना, हम 8 के साथ खत्म होता है, 42. और विलय 23 और 16, हम 16 के साथ खत्म होता है, 23. अब हमारे सभी सूचियों 2 आकार की हैं. ध्यान दें कि 4 सूचियों का प्रत्येक सॉर्ट किया जाता है. 

तो हम फिर सूचियों के जोड़े विलय शुरू कर सकते हैं. 15 और 108 और 4 और 50 मर्ज करना 1 4 ले, फिर 15, फिर 50, फिर 108. 8, 42 और 16, 23, विलय, हम पहली बार 8, तो 16, फिर 23, फिर 42 ले लो. तो अब हम सिर्फ 2 से 4 आकार की सूची है, जिनमें से प्रत्येक का हल है. तो अब हम इन 2 सूचियों विलय. पहले हम 4 ले लो. फिर हम 8 ले. फिर हम 15 और 16, फिर 23, फिर 42, फिर 50, फिर 108. और हम कर रहे हैं. अब हम एक क्रमबद्ध सूची है. तो कितनी तेजी से यह ठीक था? तकनीकी शब्दों में, मर्ज प्रकार हे (n लॉग एन) है, जबकि बुलबुला तरह सम्मिलन तरह है, और चयन छंटाई के सभी हे (एन ²). वास्तव में, के रूप में आप जल्द ही सीख जाओगे, तो आप एक तरह के साथ आने के लिए सक्षम नहीं होगा कि मामले में सामान्य हे (n लॉग एन) की तुलना में बेहतर प्रदर्शन. फिर, इस बड़ी हे संकेतन के बारे में चिंता नहीं है अगर आप अभी तक नहीं देखा है. 

सिर्फ इतना पता है कि इसका मतलब है कि अगर हम एक बहुत बड़ी सूची तरह करना चाहता था बुलबुला तरह सम्मिलन तरह है, और चयन छंटाई संभावित ले सकता है छंटाई संविलय की तुलना में काफी लंबे समय तक. इसका मतलब यह नहीं है कि मर्ज तरह सभी सूचियों के लिए तेजी से हो जाएगा या यहां तक ​​कि एक निश्चित आकार के तहत किसी भी एकल सूची के लिए. उदाहरण के लिए, सम्मिलन तरह सभी 5 तत्वों की तुलना में छोटे सूचियों के लिए सबसे तेजी से तरह हो सकता है. अभ्यास में, मर्ज तरह 50 तत्व के रूप में छोटे रूप में सूची के लिए आम तौर पर तेजी है. 

लेकिन इस अतिरिक्त गति एक मूल्य के बिना नहीं आया है. हमारे अन्य प्रकार के विपरीत है, जो एक सूची लेने के लिए और जगह में सूची को संशोधित जब तक हम एक क्रमबद्ध सूची, मर्ज तरह कुछ अतिरिक्त जगह की जरूरत है 2 सूची एक साथ विलय. हम तुरंत सूची है कि विलय किया जा रहा है नहीं मर्ज की गई सूची का उपयोग करने के लिए स्टोर कर सकते हैं के बाद से हम तत्व है कि अभी तक विलय करने की आवश्यकता है को पार कर सकता है. इस अंतरिक्ष में एक मूल्य के एक सा है, लेकिन यह आम तौर पर अनुचित नहीं है. और कहा कि यह मर्ज प्रकार के लिए है. 

मेरा नाम रोब Bowden है, और इस CS50 है. [CS50.TV] - और तरह का चयन. [हंसते हुए] ओह, कि बाहर भी ले क्योंकि मैं बदल कैसे मैं इसे पेश किया गया है. बाईं तरफ सूची. कि एक टाइपो था. [Misspoke] मैं बँधा हुआ - [हंसते हुए] मैं नहीं जानता कि क्या -