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