>> [संगीत बजाना]
>> डौग लॉयड: तो प्रविष्टि तरह एक और है एल्गोरिथ्म हम एक सरणी से सुलझाने के लिए उपयोग कर सकते हैं।
इस एल्गोरिथ्म के पीछे विचार अपने सॉर्ट सरणी का निर्माण होता है
जगह में, से बाहर तत्वों के स्थानांतरण तुम जाओ के रूप में जिस तरह से, जगह बनाने के लिए।
यह थोड़ा अलग है चयन प्रकार या बुलबुला से
प्रकार, उदाहरण के लिए, जहां हम स्थानों समायोजित कर रहे हैं,
जहां हम स्वैप कर रहे हैं।
>> इस मामले में हम वास्तव में क्या कर रहे हैं कर रही रपट तत्व है
से अधिक है, जिस तरह से बाहर।
इस एल्गोरिथ्म कैसे करता है स्यूडोकोड में काम करते हैं?
खैर बस मनमाने ढंग से कहना है कि चलो सरणी के पहले तत्व हल है।
हम यह जगह में निर्माण कर रहे हैं।
>> हम लोग एक बार में एक ही तत्व जाना कर रहे हैं और इसे बनाने के लिए, और इसलिए पहली बात हम देखते हैं
एक एक तत्व सरणी है।
और परिभाषा के द्वारा, एक से एक तत्व सरणी हल है।
>> तो फिर हम इस प्रक्रिया को दोहराना होगा until-- हम निम्नलिखित प्रक्रिया दोहराता हूँ
तत्वों के सभी हल कर रहे हैं जब तक।
अगले अवर्गीकृत तत्व को देखो और सॉर्ट हिस्से में डालें,
अपेक्षित संख्या स्थानांतरण द्वारा जिस तरह से बाहर के तत्वों की।
उम्मीद है कि इस दृश्य आप है कि क्या वास्तव में देखने में मदद मिलेगी
प्रविष्टि प्रकार के साथ चल रहा है।
>> तो फिर, हमारे यहाँ है पूरे अवर्गीकृत सरणी,
तत्वों के सभी लाल रंग में संकेत दिया।
और चलो का पालन करते हैं हमारे स्यूडोकोड के कदम।
हम ऐसा पहली बात, हम कहते है सरणी के पहले तत्व, हल।
तो हम बस कहने वाला हो पांच, अब आप हल कर रहे हैं।
>> तो फिर हम अगले को देखो सरणी के अवर्गीकृत तत्व
और हम उस सम्मिलित करना चाहते हैं छाँटे गए हिस्से में,
तत्वों पर स्थानांतरण द्वारा।
तो अगले दो अवर्गीकृत है सरणी के तत्व।
जाहिर है कि यह पहले अंतर्गत आता है पांच, तो हम क्या करने वाले हैं
एक तरह से एक दूसरे के लिए एक तरफ दो पकड़ रहा है, पर पांच बदलाव, और उसके बाद दो डालें
पाँच से पहले, जहां जाना चाहिए।
और अब हम दो हल है कि कह सकते हैं।
>> आप देख सकते हैं तो, जैसा कि हम अब तक केवल है सरणी के दो तत्वों को देखा।
हम कम से देखा नहीं है पर सभी बाकी है, लेकिन हम है
उन दो तत्वों द्वारा हल मिल गया स्थानांतरण तंत्र का तरीका है।
>> तो हम फिर से इस प्रक्रिया को दोहराने।
अगले अवर्गीकृत को देखो तत्व, यह एक है।
, एक दूसरे के लिए है कि एक तरफ पकड़ चलो पर सब कुछ बदलाव, और एक डाल
जहां यह जाना चाहिए।
>> फिर, फिर भी, हम ही कभी किया है एक, दो, और पांच को देखा।
हम आ रहा है और क्या नहीं पता है, लेकिन हम उन तीन तत्वों हल है।
>> अगले अवर्गीकृत तत्व है तीन, इसलिए हम यह सेट अलग कर देंगे।
हम पर शिफ्ट करेंगे क्या हम है, जो इस समय की जरूरत है
पिछले के रूप में सब कुछ नहीं है दो मामलों में, यह सिर्फ पांच है।
और फिर हम में तीन रहना होगा, दो और पांच के बीच।
>> छह अवर्गीकृत बगल में है सरणी के लिए तत्व।
और वास्तव में छह इसलिए, पांच से अधिक है हम भी किसी से अदला-बदली करने की ज़रूरत नहीं है।
हम सिर्फ सही पर करने के लिए छह हमले कर सकते हैं छाँटे गए भाग के अंत।
>> अन्त में, चार है पिछले अवर्गीकृत तत्व।
इसलिए हम यह सेट अलग कर देंगे, के साथ बदलाव तत्वों हम, पर बदलाव की जरूरत
जहां यह है और फिर चार डाल दिया।
और अब, देखो हम प्रकार है सभी तत्वों की।
प्रविष्टि के साथ नोटिस तरह, हम नहीं था
आगे और पीछे सरणी पार जाने के लिए।
हम केवल सरणी पार चला गया एक समय है, और हम चीजों को स्थानांतरित कर दिया
हम पहले से ही क्रम में, का सामना करना पड़ा था कि नए तत्वों के लिए जगह बनाने के लिए।
>> तो क्या सबसे खराब मामला है प्रविष्टि प्रकार के साथ परिदृश्य?
सबसे खराब स्थिति में, सरणी रिवर्स क्रम में है।
आप n तत्वों की प्रत्येक पारी के लिए है n पदों के लिए, हर बार हम
एक प्रविष्टि बनाते हैं।
यही कारण है कि स्थानांतरण का एक बहुत कुछ है।
>> सबसे अच्छा मामले में, सरणी पूरी तरह से हल है।
और एक तरह से क्या हुआ जैसे उदाहरण में पांच और छह के साथ
हम सिर्फ यह पर हमले कर सकता है, जहां किसी भी स्थानांतरण करने के लिए बिना,
हम अनिवार्य है कि क्या करना चाहते हैं।
>> आप कल्पना करें कि अगर हमारे सरणी, छह के माध्यम से एक था
हम द्वारा बंद शुरू होगा एक घोषणा के हल है।
दो तो हम सिर्फ यह कर सकते हैं एक के बाद आता है एक और दो के अनुसार क्रमबद्ध हैं, ठीक है, ठीक है, कहते हैं।
तीन ठीक है, तो बाद दो आता है, एक और दो और तीन के अनुसार क्रमबद्ध हैं।
>> हम हम कर रहे हैं, किसी भी स्वैप नहीं बना रहे हैं सिर्फ इस मनमाना लाइन चलती
हम जाने के रूप में के बीच हल और अवर्गीकृत।
के रूप में प्रभावी रूप से हम उदाहरण में किया था, हम आगे बढ़ने के रूप में, नीले तत्वों बदल रहे हैं।
तो सबसे ज्यादा मामले क्रम तो, क्या बात है?
हम में से प्रत्येक के लिए शिफ्ट करने के लिए है, तो याद रखें n तत्वों संभवतः एन पदों,
उम्मीद है कि आप देता है सबसे खराब स्थिति है कि एक विचार
क्रम n के बड़ी हे चुकता है।
>> सरणी पूरी तरह से है हल, सब हमें क्या करना है
हर एक तत्व में लग रहा है एक बार, और फिर हम कर रहे हैं।
तो सबसे अच्छा मामले में, यह n के ओमेगा है।
>> मैं डौग लॉयड हूँ।
इस CS50 है।