डौग लॉयड: तो CS50 में हम के बारे में सीखा छंटाई और खोज की एक किस्म एल्गोरिदम। और कभी कभी यह हो सकता है रखने के लिए एक छोटी सी मुश्किल क्या एल्गोरिथ्म का ट्रैक क्या करता है। हम वास्तव में ही है , भी सतह स्किम्ड कई अन्य खोज कर रहे हैं और एल्गोरिदम छँटाई। तो इस वीडियो में चलो बस कुछ मिनट लग कोशिश करते हैं और प्रत्येक एल्गोरिथ्म गढ़ने के लिए इसके मूल तत्वों के नीचे इसलिए आप सबसे अधिक याद कर सकते हैं उनके बारे में महत्वपूर्ण जानकारी और स्पष्ट करने में सक्षम होना मतभेद, यदि आवश्यक है। 

पहले चयन तरह है। चयन प्रकार के पीछे मूल विचार छोटी से छोटी अवर्गीकृत तत्व मिल रहा है और एक सरणी में साथ यह स्वैप कि सरणी के पहले अवर्गीकृत तत्व। हम सबसे ज्यादा मामले ने कहा कि इस बात का चलाते समय n चुकता किया गया था। और तुम क्यों याद करना चाहते हैं, तो ले लो एक चयन तरह वीडियो को देखो। सबसे अच्छा मामले चलाने के लिए समय भी n चुकता है। 

बुलबुला तरह, कि पीछे विचार एक आसन्न जोड़े स्वैप करने के लिए है। तो यह है कि आप में मदद करता है कि कुंजी है यहाँ अंतर याद है। चयन तरह है, अब तक, smallest-- बुलबुला मिल तरह है आसन्न जोड़े स्वैप। हम आसन्न जोड़े स्वैप तत्वों की है कि वे यदि जो प्रभावी रूप से, क्रम से बाहर हैं सही करने के लिए बड़ा तत्व बुलबुले और एक ही समय में यह भी शुरू होता है बाईं ओर छोटे तत्वों को स्थानांतरित करने के लिए। सबसे ज्यादा मामले मामला चलाने के लिए समय बुलबुला तरह के n चुकता है। सबसे अच्छा मामले चलाने के लिए समय बुलबुले की तरह n है। क्योंकि उस स्थिति में हम actually-- नहीं है हम करने की जरूरत नहीं हो सकती है सब पर किसी भी अदला-बदली कर सकते हैं। हम केवल एक बनाने के लिए है सभी एन तत्वों भर से गुजरती हैं। 

प्रविष्टि प्रकार में, यहाँ मूल विचार जा रहा है। यही कारण है कि प्रविष्टि प्रकार के लिए कीवर्ड है। हम के माध्यम से एक बार कदम करने के लिए जा रहे हैं से सरणी सही करने के लिए छोड़ दिया है। हम करते हैं और, जैसा कि हम कर रहे हैं तत्वों बदलाव करने जा रहा हम पहले से ही के लिए जगह बनाने के लिए देखा है कहीं फिट करने की जरूरत है कि छोटे लोगों पीठ कि छाँटे गए हिस्से में। इसलिए हम सॉर्ट सरणी का निर्माण एक सही करने के लिए छोड़ दिया है एक समय में तत्व, और हम जगह बनाने के लिए चीजों को पाली। के सबसे ज्यादा मामले चलाने के लिए समय प्रविष्टि प्रकार n चुकता है। सबसे अच्छा मामले चलाने के समय n है। 

कीवर्ड sort-- मर्ज यहां विभाजित है और विलय है। हम, चाहे पूरी सरणी विभाजित यह छह तत्वों, आठ तत्वों है, 10,000 elements-- हम इसे विभाजित नीचे आधे से आधे से आधे से, हम सरणी के तहत जब तक n एक तत्व सरणियों की। N एक तत्व सरणियों का एक सेट। इसलिए हम एक साथ शुरू किया 1000-तत्व सरणी, और हम बात करने के लिए मिलता है, जहां हम 1000 एक तत्व सरणियों है। तो फिर हम उन उप सरणियों विलय करने के लिए शुरू वापस एक साथ सही क्रम में। इसलिए हम दोनों एक-तत्व सरणियों ले लो और एक दो तत्व सरणी बनाएँ। हम दो दो तत्व सरणियों ले लो और एक चार तत्व सरणी बनाने और इतने पर और इतने पर हम है जब तक फिर एक n तत्व सरणी पुनर्निर्माण किया। 

के सबसे ज्यादा मामले चलाने के लिए समय तरह है विलय n बार एन लॉग इन करें। हम n तत्व है, लेकिन इस recombining प्रक्रिया लॉग इन कर लेता एन कदम पाने के लिए एक पूरी सरणी के लिए वापस। समय चलाने सबसे अच्छा मामले भी n लॉग है n इस प्रक्रिया को वास्तव में नहीं है क्योंकि सरणी था कि क्या परवाह हल या नहीं के साथ शुरू करने के लिए। प्रक्रिया नहीं है, एक ही है शॉर्ट सर्किट बातें करने के लिए कोई रास्ता नहीं है। इसलिए n सबसे खराब स्थिति में लॉग n, एन सबसे अच्छा मामले में एन लॉग इन करें। 

हम दो के बारे में बात की थी एल्गोरिदम खोज। तो रैखिक खोज पुनरावृति के बारे में है। हम सरणी पार आगे बढ़ना एक बार, बाएं से दाएं, नंबर खोजने की कोशिश कि हम के लिए देख रहे हैं। सबसे ज्यादा मामले चलाने के समय n के बड़े हे है। यह पुनरावृति हमें ले सकता है हर एक तत्व के पार हम देख रहे हैं तत्व खोजने के लिए के लिए, या तो अंतिम स्थिति में, या बिल्कुल नहीं। लेकिन हम जब तक कि इस बात की पुष्टि नहीं कर सकते हम सब कुछ देखा है। सबसे अच्छा मामले हूँ, हम तुरंत लगता है। का सबसे अच्छा मामले चलाने के लिए समय रैखिक खोज 1 की ओमेगा है। 

अन्त में, द्विआधारी खोज, वहाँ था जो मिश्रित सरणी की आवश्यकता है। कि एक बहुत याद महत्वपूर्ण विचार द्विआधारी खोज के साथ काम कर रहे हैं। यह it-- का उपयोग करने के लिए एक शर्त है आप के माध्यम से देख रहे हैं कि सरणी हल किया जाना चाहिए। अन्यथा, कीवर्ड फूट डालो और राज है। आधे में सरणी विभाजित है और तत्वों का आधा खत्म हर बार जब आप के माध्यम से आगे बढ़ना है। इस वजह से फूट डालो और राज की और आधे दृष्टिकोण में बंटवारे बातें, सबसे ज्यादा मामले चलाने के लिए समय के द्विआधारी खोज है काफी हद तक है, जो लॉग n रैखिक खोज के एन से बेहतर है। सबसे अच्छा मामले चलाने के लिए अभी भी समय है। 

हम इसे तुरंत मिल सकता है पहली बार हम एक विभाजन बना है, लेकिन फिर, याद है कि द्विआधारी खोज है, हालांकि रैखिक खोज की तुलना में काफी बेहतर लॉग होने के आधार पर एन बनाम, आप काम के माध्यम से जाने के लिए हो सकता है पहले अपने सरणी छँटाई की जो निर्भर करता है कि यह कम प्रभावी बना सकता है छाँटे गए पुनरावृति के आकार पर। 

मैं डौग लॉयड हूँ, इस CS50 है।