[Powered by Google Translate] [निवेशन क्रमबद्ध करें]
[टॉमी MacWilliam] [हार्वर्ड विश्वविद्यालय]
[इस CS50.TV]
चलो प्रविष्टि प्रकार पर एक नज़र, संख्याओं की एक सूची ले रही है और उन्हें छँटाई के लिए एक एल्गोरिथ्म ले.
एक एल्गोरिथ्म, याद है, बस एक कार्य को पूरा करने के लिए एक कदम दर कदम प्रक्रिया है.
सम्मिलन तरह पीछे मूल विचार, दो भागों में हमारी सूची में विभाजित है,
एक क्रमबद्ध भाग और एक unsorted भाग.
>> एल्गोरिथ्म के हर कदम पर ले जाया जाता है, एक संख्या
unsorted भाग से हल भाग
अंततः जब तक पूरे सूची हल है.
23, 42, 4, 16, 8, और 15 - यहाँ छह unsorted संख्या की सूची है.
चूंकि ये संख्याएं सब आरोही क्रम में नहीं हैं, वे unsorted कर रहे हैं.
चूंकि हम अभी तक छँटाई शुरू नहीं किया है, हम सभी छह तत्व हमारी unsorted भाग पर विचार करेंगे.
>> एक बार जब हम छँटाई शुरू करते हैं, हम इन क्रमबद्ध संख्या इनमें से बाईं ओर डाल देता हूँ.
तो चलो, 23, हमारी सूची में पहला तत्व के साथ शुरू करते हैं.
हम हमारे क्रमबद्ध हिस्से में अभी तक किसी भी तत्व नहीं है,
तो चलो बस 23 पर विचार करने के लिए और हमारे क्रमबद्ध हिस्से के शुरू और अंत हो.
अब, हमारे क्रमबद्ध भाग संख्या एक, 23 है,
और हमारे unsorted हिस्सा इन पांच नंबर है.
चलो अब हमारे unsorted भाग, 42, में क्रमबद्ध भाग में अगले नंबर डालने.
>> ऐसा करने के लिए, हम से 23 से 42 की तुलना करने की आवश्यकता होगी - हमारे क्रमबद्ध हिस्से में केवल तत्व इतनी दूर है.
बयालीस 23 से भी बड़ा है, तो हम बस को समाप्त करने के लिए 42 संलग्न कर सकते हैं
सूची के अनुसार क्रमबद्ध भाग की. महान!
अब हमारे क्रमबद्ध भाग दो तत्व है, और हमारे unsorted भाग चार तत्व है.
तो, चलो अब 4 के लिए ले जाने के लिए, unsorted भाग में अगले तत्व.
तो, जहाँ इस क्रमबद्ध भाग में रखा जाना चाहिए?
>> याद है, हम क्रमबद्ध क्रम में इस संख्या को जगह करना चाहते हैं
तो हमारे क्रमबद्ध भाग सही ढंग से हर समय पर हल बनी हुई है.
अगर हम सही करने के लिए 42 के 4 जगह है, तो हमारी सूची के आदेश से बाहर हो जाएगा.
तो, चलो हमारी तरह भाग में दाएँ - से - बाएँ बढ़ जारी रखने के.
जैसा कि हम चाल, चलो एक जगह नीचे प्रत्येक संख्या में शिफ्ट करने के लिए नए नंबर के लिए कमरे बनाने के.
ठीक है, 4 भी कम से कम 23 है, तो हम इसे यहाँ जगह नहीं भी कर सकते हैं.
चलो 23 सही जगह एक कदम.
>> इसका मतलब है कि हम क्रमबद्ध हिस्से में 1 स्लॉट में 4 जगह करना चाहते हैं.
सूचना कैसे सूची में इस जगह पहले से ही खाली था,
क्योंकि हम क्रमबद्ध तत्वों रहा है नीचे के रूप में हम उन्हें सामना करना पड़ा है.
सही सभी. तो, हम आधे रास्ते वहाँ रहे.
चलो क्रमबद्ध भाग में 16 डालने से हमारे एल्गोरिथ्म जारी है.
सोलह है 42 से कम है, तो हम सही करने के लिए 42 शिफ्ट करने के लिए.
सोलह भी 23 की तुलना में कम है, तो हम भी उस तत्व बदलाव.
>> अब, 16 4 से अधिक है. इसलिए, यह लग रहा है जैसे हम 4 और 23 के बीच 16 डालने करना चाहते हैं.
जबकि सूची के अनुसार क्रमबद्ध भाग के माध्यम से दाईं से बाईं ओर चलती है,
4 1 संख्या हमने देखा है कि संख्या से कम है
हम सम्मिलित करने के लिए कोशिश कर रहे हैं.
तो, अब हम इस खाली स्लॉट में 16 सम्मिलित कर सकते हैं,
जो याद है, हम आगे बढ़ तत्वों द्वारा सॉर्ट हिस्से में बनाया है
के रूप में हम उन्हें सामना करना पड़ा है.
>> सही सभी. अब, हम चार क्रमबद्ध तत्वों और दो unsorted तत्वों है.
तो, चलो क्रमबद्ध भाग में स्थानांतरित करने के लिए 8.
आठ कम से कम 42 है.
आठ कम से कम 23 है.
और 8 कम से कम 16 है.
लेकिन 8 4 से अधिक है.
तो, हम 4 और 16 के बीच 8 डालने करना चाहते हैं.
15 - और अब हम सिर्फ एक और अधिक छोड़ दिया तत्व सॉर्ट है.
पंद्रह कम से कम 42 है,
पंद्रह कम से कम 23 है.
और 15 कम से कम 16 है.
लेकिन 15 8 से अधिक है.
>> तो, यहाँ है जहां हम हमारे अंतिम प्रविष्टि बनाना चाहते हैं.
और हम कर रहे हैं.
हम unsorted भाग में कोई अधिक तत्व है,
और हमारे क्रमबद्ध हिस्से को सही क्रम में है.
संख्या से छोटी सबसे बड़ा करने के आदेश दिए हैं.
तो, चलो कुछ pseudocode है कि कदम हम सिर्फ प्रदर्शन का वर्णन पर एक नज़र रखना.
>> लाइन 1 में, हम देख सकते हैं कि हम पर सूची में प्रत्येक तत्व पुनरावृति करने की आवश्यकता होगी
1 को छोड़कर, unsorted भाग में पहला तत्व के बाद से बस हो जाएगा
क्रमबद्ध भाग में पहला तत्व.
लाइनों 2 और 3 में, हम हमारे unsorted हिस्से में वर्तमान जगह का ट्रैक रख रहे हैं.
तत्व संख्या का प्रतिनिधित्व करता है हम वर्तमान में क्रमबद्ध भाग में बढ़ रहे हैं,
और जम्मू unsorted भाग में हमारे सूचकांक का प्रतिनिधित्व करता है.
>> 4 लाइन पर, हम क्रमबद्ध दाईं से बाईं ओर भाग के माध्यम से iterating रहे हैं.
हम हमारे वर्तमान स्थिति की बाईं तत्व एक बार फिर शुरू होने से रोका चाहते हैं
हम तत्व सम्मिलित करने के लिए कोशिश कर रहे हैं की तुलना में कम है.
आन लाइन 5, हम प्रत्येक तत्व हम सही करने के लिए एक अंतरिक्ष मुठभेड़ जा रहे हैं.
इस तरह, हम एक स्पष्ट करने के लिए अंतरिक्ष में डालने के लिए है, जब हम पहली तत्व मिल जाएगा
तत्व हम आगे बढ़ रहे हैं, की तुलना में कम है.
6 लाइन पर, हम हमारे काउंटर अद्यतन कर रहे हैं क्रमबद्ध भाग के माध्यम से छोड़ दिया जाना जारी है.
अंत में, 7 लाइन पर, हम सूची के अनुसार क्रमबद्ध भाग में तत्व डालने रहे हैं.
>> हम जानते हैं कि यह स्थिति जम्मू में डालने के लिए ठीक है,
क्योंकि हम पहले से ही तत्व है कि वहाँ सही करने के लिए एक अंतरिक्ष इस्तेमाल किया जा स्थानांतरित किया है.
याद है, हम सही से क्रमबद्ध भाग के माध्यम से छोड़ दिया करने के लिए जा रहे हैं,
लेकिन हम बाएं से दाएं unsorted भाग के माध्यम से आगे बढ़ रहे हैं.
सही सभी. चलो अब कितनी देर तक चल रहा है कि एल्गोरिथ्म ले लिया पर एक नज़र रखना.
हम पहला सवाल पूछते हैं कि यह कैसे समय के लिए इस एल्गोरिथ्म सबसे खराब स्थिति में चलाने के लिए ले करता हूँ.
याद है कि हम बड़ी हे संकेतन के साथ इस समय चल रहा है का प्रतिनिधित्व करते हैं.
आदेश में हमारी सूची को सॉर्ट करने के लिए, हम unsorted भाग में तत्वों पर पुनरावृति था,
और उन तत्वों के संभावित क्रमबद्ध भाग में सभी तत्वों पर, प्रत्येक के लिए.
Intuitively, एक हे आपरेशन (n ^ 2) की तरह लग रहा है.
>> हमारे pseudocode को देखते हुए, हम एक दूसरे पाश अंदर नेस्टेड पाश है,
जो, वास्तव में, एक हे आपरेशन (n ^ 2) की तरह लगता है.
हालांकि, सूची के अनुसार क्रमबद्ध भाग बहुत अंत तक पूरे सूची में शामिल नहीं किया था.
फिर भी, हम संभावित क्रमबद्ध हिस्से के बहुत शुरुआत में एक नए तत्व डालने के सकता है
एल्गोरिथ्म के हर यात्रा पर,
जिसका अर्थ है कि हम प्रत्येक तत्व पर क्रमबद्ध भाग में वर्तमान में लग रही है चाहते हैं.
तो, इसका मतलब है कि हम संभवतः दूसरा तत्व के लिए एक तुलना कर सकता है,
3 तत्व के लिए दो तुलना, और इतने पर.
तो, कदम की कुल संख्या 1 से 1 शून्य सूची की लंबाई पूर्णांकों का योग है.
हम एक संकलन के साथ इस का प्रतिनिधित्व कर सकते हैं.
>> हम summations में यहाँ नहीं जाना है, लेकिन यह पता चला है कि इस समेशन के बराबर है
2 से अधिक है, जो बराबर 2 ^ 2 / n है - (1 एन) n / 2 n.
जब asymptotic क्रम के बारे में बात कर रही है,
इस n ^ 2 शब्द इस n शब्द हावी हो रहा है.
इसलिए, प्रविष्टि प्रकार बड़ी हे (n ^ 2) है.
क्या होगा अगर हम पहले से ही एक क्रमबद्ध सूची पर अंतरवेशन शॉटन भागा.
उस मामले में, हम बस क्रमबद्ध बाएँ से दाएँ भाग का निर्माण चाहते हैं.
तो, हम केवल n चरणों का के आदेश पर की आवश्यकता होगी.
>> इसका मतलब है कि सम्मिलन तरह n के एक प्रदर्शन सबसे अच्छा मामले,
जो हम Ω (एन) के साथ प्रतिनिधित्व.
और कहा कि यह प्रविष्टि प्रकार के लिए है,
सिर्फ एक कई एल्गोरिदम के हम एक सूची को सॉर्ट करने के लिए उपयोग कर सकते हैं.
मेरा नाम टॉमी है, और इस CS50 है.
[CS50.TV]
ओह, आप बस को रोक नहीं सकते हैं कि एक बार यह शुरू होता है.
ओह, हम किया है कि - >> बूम!