[संगीत बजाना] 

ANDI PENG: खंड के 3 सप्ताह के लिए आपका स्वागत है। सभी आने के लिए धन्यवाद, तुम लोग, यह पहले शुरू करने का समय आज के लिए। हम एक अच्छा है, थोड़ा मिल गया है अंतरंग समूह आज। इसलिए उम्मीद है कि हम के लिए मिल जाएगा खत्म, शायद, जल्दी, एक छोटा सा आज जल्दी। तो जल्दी, सिर्फ कुछ एजेंडा आज के लिए घोषणाओं। हम शुरू करने से पहले, हम कर रहे हैं बस पर जाने के लिए जा कुछ संक्षिप्त सैन्य मुद्दों, pset सवाल, पूछताछ, इस तरह बातें। और फिर हम सही में गोता करेंगे। हम करने के लिए GDB नामक एक डिबगर इस्तेमाल करेंगे हमारे कोड, debunking शुरू दाऊद दूसरे दिन व्याख्यान में विस्तार से बताया। हम एक तरह की चार प्रकार पर जायेंगे। हम बहुत जल्दी से उन पर जाना होगा वे बहुत गहन रहे हैं के बाद। लेकिन सभी जानते हैं कि स्लाइड और स्रोत कोड ऑनलाइन हमेशा से रहे हैं। तो, आपके अवलोकन पर, बेझिझक वापस जाने के लिए और उस पर एक नज़र रखना। 

हम माध्यम से जाना होगा उपगामी संकेतन, जो सिर्फ एक अच्छा तरीका है कह "runtimes," हम बड़े हे है, जो जहां डेविड व्याख्यान में विस्तार से बताया। और हम भी ओमेगा, जो है कम बाध्य क्रम है। और हम थोड़ा और अधिक बात करेंगे में गहराई से कैसे उन काम के बारे में। और अंत में, हम, द्विआधारी खोज पर जायेंगे क्योंकि पहले से ही है, जो आप में एक बहुत अपने psets पर नजर शायद जानते हैं कि कि अपने pset में है कि एक सवाल है। तो आप सब खुश हो जाएगा हम आज यह है कि कवर। 

और अंत में, प्रति अपने खंड प्रतिक्रिया है, मैं वास्तव में पर लगभग 15 मिनट के लिए छोड़ दिया अंत में बस पर जाने के लिए pset3 की रसद, किसी भी सवाल, शायद मार्गदर्शन का एक सा है, अगर तुम जाएगा, हम प्रोग्रामिंग शुरू होने से पहले। तो चलो माध्यम से प्राप्त करने की कोशिश करते हैं बहुत जल्दी सामग्री। और फिर हम कुछ समय खर्च कर सकते हैं pset के लिए अधिक प्रश्नों ले रही है। ठीक। 

जल्दी है, तो बस कुछ हम पहले घोषणाओं आज शुरू करते हैं। सबसे पहले, बनाने के लिए स्वागत अपने psets के दो के माध्यम से यह। मैं your-- हाँ, चलो पर एक नज़र लिया कि एक के लिए प्रशंसा का एक दौर हो। असल में, मैं वास्तव में था वास्तव में प्रभावित। मैं आप लोगों के लिए पहली pset श्रेणीबद्ध पिछले हफ्ते और तुम लोगों को अविश्वसनीय था। 

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

वहाँ रहे हैं लेकिन एक कुछ पूछताछ सवाल मैं सिर्फ इतना है कि ऊपर जाने के लिए चाहते हैं दोनों मेरे जीवन बनाना होगा और अन्य का एक बहुत TAs 'थोड़ा आसान रहता है। सबसे पहले, मैंने देखा है यह अतीत आप में से कितने week-- पर check50 चल रहा है इससे पहले कि आप अपने कोड प्रस्तुत? ठीक। तो हर कोई check50 कर दिया जाना चाहिए, वास्तव में हम एक secret-- because-- हमारी शुद्धता के हिस्से के रूप में check50 चलाने अपने कोड के परीक्षण के लिए स्क्रिप्ट। अपने कोड में विफल रहा है तो अगर check50, सभी संभावना में, यह शायद करने के लिए जा रहा है के रूप में अच्छी तरह से हमारी जांच असफल। कभी-कभी आप लोग सही जवाब है। की तरह, लालची, कुछ अगर आप सही संख्या है, आप बस कुछ अतिरिक्त सामान बाहर प्रिंट। और कहा कि अतिरिक्त सामान वास्तव में जांच करने में विफल रहता है, कंप्यूटर नहीं करता है क्योंकि वास्तव में इसके लिए क्या देख रही है पता है। और तो यह सिर्फ माध्यम से चलेंगे अपने उत्पादन नहीं करता है कि वहाँ हम जवाब की उम्मीद क्या मैच हो सकता है, और यह गलत है चिह्नित करने के लिए। 

और मैं में हुआ पता है कि अपने मामलों में से कुछ इस सप्ताह। इसलिए मैं वापस और मैन्युअल चला गया हर किसी का कोड regraded। हालांकि भविष्य में, , कृपया सुनिश्चित करें कृपया आप चला रहे हैं कि अपने कोड पर 50 की जाँच करें। यह टीए के लिए एक दर्द की तरह है क्योंकि regrade मैन्युअल वापस जाने के लिए और करने के लिए हर एक के लिए हर एक pset एकल, छोटी सी चूक उदाहरण। तो मैं किसी भी अंक से नहीं लिया। मैंने सोचा कि मैं शायद दूर ले गया लगता है एक या डिजाइन के लिए दो। हालांकि भविष्य में, यदि आप check50 असफल रहे हैं अंक ले जाया जाएगा शुद्धता के लिए बंद। 

इसके अलावा, psets हैं दोपहर में शुक्रवार की वजह से। मैं एक सात मिनट लगता है कि वहाँ हम आपको दे कि देर से रियायती अवधि। हार्वर्ड समय के अनुसार, वे करने के लिए अनुमति दी हो सात मिनट देर से सब कुछ करने के लिए किया जाना है। यहाँ तो येल में, हम करेंगे साथ ही उस पर कायम रहें। लेकिन बहुत ज्यादा, 00:07 पर, अपने pset में नहीं है, यह रूप में देर के रूप में चिह्नित किया जा रहा है। इसलिए जब और यह चिह्नित है के रूप में देर से, TA-- मैं कर रहा हूँ अभी भी अपने psets ग्रेडिंग किया जा रहा है। तो आप अभी भी एक ग्रेड दिखाई देगा। हालांकि, कम से जानते हैं कि सेमेस्टर के अंत में, सब देर psets बस हो जाएगा स्वचालित रूप से कंप्यूटर द्वारा चुना। 

हम दो कारणों के लिए ऐसा करते हैं। एक, कभी कभी हम मिल डीन के बहाने की तरह, माफ़, बाद में उस पर मैं अभी तक के बारे में पता नहीं है। तो हम ग्रेडिंग रहे हैं सुनिश्चित करने के लिए की तरह बस के मामले में सब कुछ है, जैसे, मैं कर रहा हूँ एक डीन बहाना याद आ रही है। और दूसरी बात, में रखना मन, तुम अब भी कर सकते हैं एक pset कि ड्रॉप पूरी गुंजाइश अंक है। और इसलिए हम ग्रेड के लिए पसंद अपने psets के सभी बस अपने कार्यक्षेत्र के लिए सुनिश्चित करें कि करने के लिए वहाँ और आप उन्हें कोशिश कर रहे हैं। यह देर हो चुकी है, तो भी अगर आप अभी भी हूँ गुंजाइश अंक के लिए ऋण मिलता है, मुझे लगता है। 

कहानी है तो नैतिक, बनाना सुनिश्चित करें कि आपके psets पर समय में कर रहे हैं। और वे समय पर नहीं कर रहे हैं, यह बहुत अच्छा नहीं है कि पता है। हाँ, मुझे आगे बढ़ने से पहले, किसी को भी करता है pset प्रतिक्रिया के बारे में कोई सवाल? हाँ। 

दर्शकों: आप हम कहा था psets में से एक को छोड़ सकते हैं? 

ANDI PENG: हाँ। तो नौ psets समग्र वहाँ सेमेस्टर के पाठ्यक्रम पर। और अगर आप गुंजाइश है, तो points-- इतनी गुंजाइश है, बस है बहुत ज्यादा, आप प्रयास कर रहे हैं समस्या यह है कि आप समय में डाल रहे हैं क्या आप है कि दिखा रहे हैं प्रदर्शन आप कल्पना पढ़ा है। यह काफी गुंजाइश है। और अगर आप को पूरा कर रहे हैं, तो गुंजाइश अंक, हम सबसे कम ड्रॉप कर सकते हैं पूर्ण दायरे से बाहर है। तो यह है कि अपने लाभ में है को पूरा करने और हर pset प्रयास करें। 

यहाँ तक कि upload-- कोई नहीं करता है, तो उन्हें उन सब को अपलोड, काम करते हैं। और फिर हम उम्मीद कर सकेंगे आप उन बिंदुओं में से कुछ वापस दे। कूल। कोई ओर प्रश्न? अच्छा है। 

दूसरे, कार्यालय में कुछ hours-- कार्यालय समय के बारे में जल्दी नोट। तो पहले, शुरुआती सप्ताह में आते हैं। कोई भी कभी भी है सोमवार को कार्यालय समय। क्राइस्टाबेल के लिए आया था कार्यालय समय कल रात। हाँ, क्राइस्टाबेल। और हम ऑफिस पर क्या किया है घंटे कल रात, क्राइस्टाबेल? 

दर्शकों: हम आइसक्रीम था। 

ANDI PENG: तो यह सही है, हम था कार्यालय समय में आइसक्रीम कल रात। मुझे लगता है कि आप वादा नहीं कर सकते हम कार्यालय समय में आइसक्रीम होगा हर हफ्ते, मैं तुमसे वादा कर सकते हैं उल्लेखनीय है कि एक नहीं होगा कि है प्रादेशिक सेना के अनुपात को बेहतर छात्र। कानूनी तरह, यह 3-1 की तरह है। के साथ कि इसके विपरीत जबकि गुरुवार, आप के बारे में 150 मिल गया है वास्तव में बच्चों और कोई आइसक्रीम पर बल दिया। और यह सिर्फ किसी के लिए भी उपयोगी नहीं है। कहानी का तो नैतिक, जल्दी आ जाता है, कार्यालय समय और अच्छी बातें करने के लिए क्या होगा। 

इसके अलावा, सवाल पूछने के लिए तैयार आना। आपको पता है? भले ही क्या TAs की, मैं , कह दिया गया है लगता है, हम एक दो छात्रों को मिल रहा है 10:50, जैसे, पर गुरुवार को में आने वाले कल्पना पढ़ने वाले नहीं मेरी मदद की तरह किया जा रहा है, मेरी मदद करो। दुर्भाग्य से उस बिंदु पर, वहाँ है बहुत ज्यादा नहीं है हम आपकी मदद कर सकते हैं। इतनी जल्दी सप्ताह में आ कृपया। कार्यालय समय के लिए जल्दी आओ। सवाल पूछने के लिए तैयार आओ। के रूप में, यकीन है कि आपको लगता है कि बनाओ एक छात्र, जहां हैं तुम इतनी है कि होने की जरूरत Tas, साथ में मार्गदर्शन कर सकते हैं क्या कार्यालय समय है जो चाहिए के लिए आवंटित किया। 

दूसरी बात है, तो मैं प्रोफेसरों को पता है परीक्षण के साथ हमें आश्चर्य की तरह है। मैं एक प्रोफेसर उन था यो, तरह, जिस तरह से, कि मध्यावधि याद आप अगले सोमवार है। हाँ, मुझे लगता है कि मध्यावधि के बारे में पता नहीं था। इसलिए मुझे लगता है कि होने जा रहा हूँ टीए कि तुम सब है कि प्रश्नोत्तरी याद दिलाता है तुम्हें पता है, क्योंकि 0--, हम सीएस कर रहे हैं। अब हम किया सरणियों है कि आप मिलता है यह प्रश्नोत्तरी 0 क्यों है, एह एक प्रश्नोत्तरी नहीं? ठीक। ओह, मुझे लगता है कि एक पर कुछ दूसरे से टकराए मिला है। ठीक। 

तो प्रश्नोत्तरी 0 यदि 14 अक्टूबर होगी आप सोमवार से बुधवार खंड में हो और 15 अक्टूबर आप में कर रहे हैं मंगलवार गुरुवार अनुभाग। इस के लिए लागू नहीं होता हार्वर्ड में आप उन लोगों के मैं आप सभी को हो जाएगा लगता who-- 14 तारीख को अपने क्विज़ ले रही है। 

तो हाँ, अगले सप्ताह, यदि डेविड, व्याख्यान में चला जाता है, हाँ, उसके बारे में इतना प्रश्नोत्तरी अगले सप्ताह है, आप सभी क्योंकि हैरान नहीं की जाएगी आप अनुभाग के लिए आया था और आप जानते हैं कि आपके प्रश्नोत्तरी 0 दो हफ्तों में है। और हम समीक्षा करनी होगी सत्र और सब कुछ। के बारे में तो कोई चिंता नहीं उस के लिए डरा दिया जा रहा है। किसी भी सवाल का कोई प्रश्न के before-- सब के बारे में सैन्य मुद्दों पर, ग्रेडिंग, कार्यालय समय, वर्गों? हाँ। 

दर्शकों: प्रश्नोत्तरी है तो व्याख्यान के दौरान होने जा रहा? 

ANDI PENG: हाँ। प्रश्नोत्तरी तो, मुझे लगता है, 60 है उस समय स्लॉट में आवंटित मिनट आप बस ले लेंगे कि व्याख्यान कक्ष में। तो अगर आप में आने की जरूरत नहीं है एक यादृच्छिक 19:00, जैसे, पर। यह सब अच्छा है। हाँ। कूल। 

ठीक है। तो हम करने जा रहे हैं आप के लिए एक अवधारणा को लागू डेविड तरह पहले से ही है कि इस सप्ताह की यह पिछले सप्ताह व्याख्यान में पर छुआ। यह GDB कहा जाता है। और आप में से कितने, जबकि में अपने psets लिख ज़ाहिर है, कहते हैं कि एक बड़े बटन देखा है अपने आईडीई के शीर्ष पर "डिबग"? ठीक। तो अब हम वास्तव में पर्दाफाश करने के लिए मिल जाएगा क्या है कि बटन के रहस्य वास्तव में करता है। और मुझे लगता है कि यह एक है, आप की गारंटी सुंदर, सुंदर बात। 

अब तक, मुझे लगता है कि ऊपर तो वहाँ दो चीजें हो गया है छात्रों को आम तौर पर किया गया है psets जब debugging कर रही है। एक, वे या तो में जोड़ने printf () - तो हर कुछ लाइनों, वे एक printf () में जोड़ - ओह, यह चर क्या है? ओह, यह चर क्या है now-- और आप किस तरह की प्रगति देख अपने कोड की यह रन के रूप में। या बच्चों को क्या दूसरी विधि है वे अभी पूरी बात लिखने कि और फिर अंत में इस तरह चलते हैं। उम्मीद है कि यह काम करता है। मैं तुम्हें गारंटी, GDB बेहतर है उन तरीकों में से दोनों की तुलना में। हाँ। तो यह अपने नए सबसे अच्छा दोस्त हो जाएगा। यह एक खूबसूरत चीज है क्योंकि कि नेत्रहीन प्रदर्शित करता है दोनों क्या अपने कोड से कर रही है एक विशिष्ट बिंदु पर के रूप में अच्छी तरह से क्या सब के रूप में अपने चर ले जा रहे हैं, उनके मूल्यों को क्या कर रहे हैं जैसे, कि विशिष्ट बिंदु पर। और इस तरह से, तुम सच में कर सकते हैं अपने कोड में ब्रेकप्वाइंट निर्धारित किया है। आप लाइन से लाइन के माध्यम से चला सकते हैं। और GDB बस के लिए होगा आप, आप के लिए प्रदर्शित क्या अपने सभी चर की , वे क्या कर रहे हैं, क्या कोड में चल रहा है। और इस तरह से, यह है इतना आसान देखने के लिए क्या printf हैैं की बजाय क्या हो रहा है या अपने बयानों नीचे लिख। 

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

तो तुम लोग सब देख सकते हैं कि या मैं एक बिट में ज़ूम चाहिए? पीठ में, आप देख सकते हैं कि? मैं में ज़ूम चाहिए? बस थोड़ा सा? अच्छा ठीक है। हम वहाँ चलें। ठीक। 

इसलिए मुझे लगता है कि मेरे लिए, यहाँ है लालची के लिए कार्यान्वयन। और आप लोगों का एक बहुत कुछ लिखा है, जबकि कि form-- जबकि पाश में लालची ऐसा करने के लिए एक पूरी तरह से स्वीकार्य तरीका है यह बस के लिए है करने के लिए एक और रास्ता it-- सापेक्ष में विभाजित करते हैं। तो तुम हो सकता है क्योंकि आपके मूल्य और फिर अपने शेष है। और फिर तुम सिर्फ कर सकते हैं यह सब एक साथ जोड़ें। मैं क्या कर रहा हूँ के तर्क करता है यहां हर किसी को समझ कर, हम शुरू करने से पहले? एक प्रकार का? कूल। अच्छा है। यह एक बहुत सेक्सी टुकड़ा है कोड की है, मैं कहूँगा। जैसे मैंने दाऊद में कहा, एक समय के बाद, व्याख्यान, आप सभी कोड देखकर शुरू करेंगे सुंदर है कि कुछ के रूप में। और कभी कभी तुम सुंदर जब देखते हैं कोड, यह एक ऐसी अद्भुत लग रहा है। 

ताकि हालांकि, इस कोड को बहुत है, जबकि सुंदर, यह ठीक से काम नहीं करता है। तो चलो इस पर check50 चलाते हैं। 50 20-- OOP की जाँच करें। 2? कि pset2 है? हाँ। ओह, pset1। ठीक। इसलिए हम check50 चलाते हैं। 

और तुम लोग यहाँ देख सकते हैं, यह मामलों के एक जोड़े असफल साबित हुई है। और आप में से कुछ के लिए आपकी समस्या को सेट कर रही है, ज़ाहिर है, आह, क्यों यह काम नहीं कर रहा है, जैसे आप कर रहे हैं। ऐसा क्यों है कि कुछ के लिए काम कर रहा है मूल्यों लेकिन दूसरों के लिए नहीं? खैर, GDB आप आंकड़ा मदद करने के लिए जा रहा है बाहर क्यों उन सूचनाओं के काम नहीं कर रहे थे। 

ठीक। तो चलो, में से एक देखते हैं मैं check50 में असफल रहा था के चेक 0.41 के इनपुट मूल्य था। सही जवाब तो यह है कि आप हो जाना चाहिए एक 4 है। लेकिन इसके बजाय मैं बाहर मुद्रण रहा हूँ जो गलत है 3-एन, है। तो बस, चलो बस इस मैन्युअल चलाते हैं check50 काम कर रहा है कि सुनिश्चित करें। के ./greedy करते हैं। उफ़, मैं लालची बनाने के लिए है। हम वहाँ चलें। अब ./greedy। 

कितना बकाया है? के 0.41 करते हैं। और हां, हम यहाँ देखें यह 3 outputting है कि जब सही जवाब है, वास्तव में, 4 होना चाहिए। तो चलो GDB में प्रवेश करते हैं और हम देखते हैं कि कैसे इस समस्या को सुधारने के बारे में जाना जा सकता है। 

में पहला कदम तो हमेशा अपने कोड डिबगिंग एक breakpoint स्थापित करने के लिए है, या एक बिंदु है जिस पर आप कंप्यूटर या करना चाहते हैं डिबगर पर तलाश शुरू की। अगर आप ऐसा करेंगे तो वास्तव में नहीं है आपकी समस्या क्या है, आमतौर पर, ठेठ बात हम करना चाहते हैं ऐसा मुख्य हमारे breakpoint सेट करने के लिए है। तो तुम लोग यह देख सकते हैं सही वहाँ लाल बटन, हां, कि मुझे स्थापित किया गया एक मुख्य समारोह के लिए ब्रेकपाइंट। मुझे लगता है कि क्लिक करें। 

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

तो अगर आप सेंट, सिक्के, एन मिल गया है, सब अलग अलग बातें करने के लिए घोषित इस समय। कोई चिंता नहीं, क्योंकि हम वास्तव में नहीं है अभी तक किसी भी चर करने के लिए उन्हें initialized। आपके कंप्यूटर में तो अपने कंप्यूटर सिर्फ देख रहा है, ओह, 32767 पिछले इस्तेमाल समारोह था अपने कंप्यूटर में है कि स्मृति अंतरिक्ष की। सेंट वर्तमान में है, जहां और इतना है कि है। लेकिन कोई है कि एक बार आप कोड को चलाने यह initialized हो जाना चाहिए। 

तो चलो द्वारा, लाइन के माध्यम से चलते हैं लाइन, क्या हो रहा है यहाँ। ठीक। यहां तक ​​तो तीन हैं मैं सिर्फ समझाया कि बटन। आपको खेलने, या भागो समारोह है बटन, आप बटन पर कदम है और आप भी बटन में कदम है। और अनिवार्य रूप से, इन तीनों का उन्हें तो बस अपने कोड के माध्यम से जाना और अलग अलग बातें करते हैं। 

तो आम तौर पर, आप डिबगिंग कर रहे हैं, हम बस खेलते मारा नहीं करना चाहते हैं, प्ले सिर्फ चलेंगे क्योंकि यह अंत करने के लिए अपने कोड। और फिर आप वास्तव में नहीं होगा क्या पता है कि आपकी समस्या अगर आप कई breakpoints सेट जब तक है। अगर आप कई ब्रेकप्वाइंट सेट करते हैं, यह सिर्फ स्वचालित रूप से होगा एक ब्रेकप्वाइंट से चलाने के लिए, अगले करने के लिए अगले करने के लिए। लेकिन इस मामले में हम है सिर्फ एक है कि, क्योंकि हम हमारे रास्ते में काम करना चाहते हैं नीचे करने के लिए ऊपर से नीचे। तो हम उस बटन को अनदेखा करने के लिए जा रहे हैं अभी इस कार्यक्रम के उद्देश्यों के लिए। 

समारोह पर कदम तो बस हर एक लाइन पर कदम और आपको बताता है क्या कंप्यूटर से कर रही है। समारोह में कदम चला जाता है वास्तविक समारोह में कि कोड की अपनी लाइन पर है। तो उदाहरण के लिए, printf की तरह (), कि ठीक है, एक समारोह है? मैं शारीरिक रूप से कदम करना चाहता था printf () समारोह में, मैं वास्तव में के टुकड़े में जाना होगा printf () लिखा है और यह देखने गया था, जहां कोड वहाँ क्या हो रहा है। 

लेकिन आम तौर पर, हम मानते हैं कि हम आपको दे कि कोड काम करता है। हम () काम कर रहा है printf मान। हम GetInt () काम कर रहा है कि मान। तो कोई ज़रूरत नहीं करने के लिए भी नहीं है उन कार्यों में कदम। लेकिन कार्य है कि अगर वहाँ आप अपने आप को लिखने कि आप जाँच करना चाहते हैं पर क्या हो रहा है, आप कदम करने के लिए चाहते हो जाएगा उस समारोह में। 

इसलिए अभी हम सिर्फ जा रहे हैं कोड के इस टुकड़े पर कदम। तो चलो देखते हैं। ओह, प्रिंट, "ओह हाई, कैसे ज्यादा बदलाव बकाया है? " हम परवाह नहीं है। हम जानते हैं कि काम कर रहा है पता है, इसलिए हम इस पर कदम। 

इसलिए n, हमारी नाव है, जो कि हम initialized-- है या declared-- शीर्ष पर, अब हम कर रहे हैं GetFloat करने के लिए उस के बराबर ()। तो चलो कि पर कदम चलो। और हम पर देखना नीचे यहाँ, कार्यक्रम एक मूल्य के निवेश करने के लिए मुझे उत्साह है। तो इनपुट का हम चाहते हैं मूल्य देना 0.41 है, जो यहां का परीक्षण करने के लिए। अच्छा है। 

तो अब N-- तुम लोगों को देख कर यहाँ, bottom-- पर यह है stored-- क्योंकि हम अभी तक गोल नहीं किया है, यह है इस तरह की दिग्गज कंपनी में संग्रहीत ०.४०९९९९९९९६ है कि नाव, के काफी करीब है, जो हमारे उद्देश्यों, अभी, 0.41 तक। और फिर हम, पर बाद में के रूप में देखेंगे हम कार्यक्रम पर आगे बढ़ जारी है, यहां के बाद, एन बन गया है गोल और सेंट 41 हो गई है। अच्छा है। इसलिए हम अपने गोलाई का काम कर रहे हैं पता है। हम जानते हैं कि सेंट की सही संख्या, इसलिए हम चाहते हैं कि पता है कि नहीं वास्तव में समस्या। 

इसलिए हम घुसने के लिए जारी इस कार्यक्रम में पर। हम यहाँ जाना। और तो कोड की इस पंक्ति के बाद, हम हम कितने तिमाहियों पता होना चाहिए। हम पर कदम। और तुम हम, वास्तव में, एक है देखना तिमाही हम 25 घटाया गया है क्योंकि 41 के बारे में हमारी प्रारंभिक मूल्य से। और हम अपने पैसे के लिए 16 छोड़ दिया है। 

हर किसी को समझ में कैसे करता है कार्यक्रम के माध्यम से आगे बढ़ रहा है और क्यों सेंट अब 16 हो गई है और यही कारण है, अब, सिक्के 1 बन गया है? हर कोई उस तर्क पीछा कर रहा है? कूल। , इस बिंदु के रूप में तो कार्यक्रम के काम, है ना? हम इसे ठीक कर रहा है पता हम यह करने के लिए क्या चाहते हैं। और हम वास्तव में नहीं था ओह, बाहर मुद्रित करने के लिए है, क्या इस बिंदु पर सेंट है, इस बिंदु पर सिक्के क्या है। 

हम कार्यक्रम के माध्यम से जा रहे हैं। चहलकदमी। कूल। हम डाइम्स खत्म हो जाना। अच्छा है। हम इसे ले लिया है कि वहाँ एक पैसा के लिए 0.10 $ बंद। और अब हम दो सिक्के हैं। यह सही है। 

हम पैसे खत्म हो जाने और हम देखते हैं हम सेंट के ऊपर छोड़ दिया गया है। हम्म, यह अजीब है। यहां कार्यक्रम पर, मैं चाहिए था मेरे पैसे घटा दिए गए हैं। शायद मैं अभी नहीं था कि लाइन ठीक कर रहा। और अफसोस, आप देख सकते हैं यहाँ, क्योंकि हम जानते हैं हम कदम रख रहे हैं कि लाइनों के 32 और 33 के माध्यम से, कि जहां हमारे कार्यक्रम अनुचित तरीके से चर चला था। तो हम देखते हैं और ओह, देख सकते हैं, मैं यहाँ सेंट घटाकर रहा हूँ, लेकिन मैं वास्तव में नहीं हूँ मेरा सिक्का मूल्य को जोड़ने। मैं सेंट करने के लिए जोड़ रहा हूँ। और मैं करने के लिए जोड़ नहीं करना चाहते हैं सेंट, मैं सिक्कों को जोड़ना चाहते हैं। इसलिए हम सिक्के करने के लिए है कि बदलते हैं, हम काम कर रहे एक कार्यक्रम मिल गया है। मैं check50 चला सकते हैं। तुम बस GDB सही से बाहर निकलें कर सकते हैं यहाँ और उसके बाद फिर से check50 चलाते हैं। मैं सिर्फ यह कर सकता है। मैं लालची बनाने के लिए है। 0.41। और यहाँ, यह मुद्रण है सही जवाब बाहर। 

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

इसलिए मुझे लगता है के लिए जाँच करने के लिए भूल गया क्या होगा अगर मैं दो कमांड लाइन तर्क नहीं था। मैं सिर्फ इतना है कि जांच में नहीं डाली। मैं Debug-- चलाते हैं और इसलिए मैं सेट मेरी ब्रेकप्वाइंट वहाँ सही करने के लिए। मैं डिबग चलाते हैं। 

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

अगले समस्या में तो इस सप्ताह की स्थापना की, तुम लोग शायद का एक बहुत कुछ होगा चर खाक छानने। आपको यह सुनिश्चित होना नहीं जा रहे हैं क्या वे सभी एक निश्चित बिंदु पर मतलब है। तो GDB वास्तव में लगाना करने में मदद मिलेगी वे सब बराबर कर रहे हैं बाहर और नेत्रहीन कि देखने में सक्षम किया जा रहा है। किसी को कैसे पर उलझन में है उस के किसी भी काम कर रहा था? कूल। ठीक है। तो उसके बाद, हम कर रहे हैं सही गोता करने के लिए जा रहा में अलग-अलग चार हैं इस सप्ताह के लिए हर तरह के प्रकार। आप में से कितने, प्रथम सभी को, हम शुरू करने से पहले, pset3 के लिए पूरे कल्पना पढ़ा है? ठीक। मैं तुम लोगों पर गर्व है। उस वर्ग के आधे की तरह है, जो पिछली बार की तुलना में काफी अधिक है। 

तो यह है कि बहुत अच्छा है, क्योंकि जब हम सामग्री के बारे में बात करते हैं lecture-- या खेद में, section-- में मुझे पसंद है उस का एक बहुत से संबद्ध करने की वापस pset क्या है और आप चाहते हैं कि कैसे अपने pset में है कि लागू करने। आप कर आते हैं तो कल्पना पढ़ा, यह हूँ आप समझने के लिए एक बहुत आसान हो मैं जब मैं कहता हूँ के बारे में बात कर रहा हूँ, अरे ओह, यह एक सच में हो सकता है इस तरह लागू करने के लिए अच्छी जगह है। पढ़ा है जो आप उन लोगों के तो अपने pset के हिस्से के रूप में जानते हैं कि, कल्पना, आप के लिए करने जा रहे हैं तरह का एक प्रकार लिखें। तो यह बहुत उपयोगी हो सकता है आप में से बहुत आज के लिए। 

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

और यहाँ एक दृश्य विवरण है कि कैसे काम करेगा की। अगर हम थे तो उदाहरण के लिए, शुरू करने के लिए पांच तत्वों की एक सरणी, सूचकांक के साथ 0-4, के साथ 3, 5, 2, 6, और 4 मूल्यों इसलिए अभी array-- में रखा गया है, हम सिर्फ कल्पना करने के लिए जा रहे हैं वे सब अवर्गीकृत कर रहे हैं कि हम अन्यथा परीक्षण नहीं किया है क्योंकि। 

तो आप कैसे एक चयन तरह होगा काम है कि यह पहली बार होगा संपूर्णता के माध्यम से चलाने अवर्गीकृत सरणी की। यह छोटी मूल्य बाहर ले जाएगा। इस मामले में, 3 में, सही अब, सबसे छोटी है। यह 5 के लिए हो जाता है। नहींं, 5 than-- बड़ा नहीं होता या क्षमा करें, 3 than-- कम नहीं है। तो न्यूनतम मूल्य अभी भी 3 है। और फिर आप 2 को मिलता है। ओह, देखता कंप्यूटर, 2 कम से कम 3 है। 2 अब न्यूनतम मूल्य होना चाहिए। और इतना है कि पहले मूल्य के साथ 2 स्वैप। 

एक तो पास के बाद, हम वास्तव में देखते हैं कि 2 और 3 बदली हैं। और हम बस कर जारी करने जा रहे हैं इस बार फिर सरणी के आराम के साथ। तो हम बस के माध्यम से चलाने के लिए जा रहे हैं सरणी के अंतिम चार अनुक्रमित। हम 3 है कि देखेंगे अगले न्यूनतम मूल्य। इसलिए हम 4 के साथ कि स्वैप करने के लिए जा रहे हैं। और फिर हम सिर्फ रखने के लिए जा रहे हैं अंत में, जब तक के माध्यम से चल रहा है, आप एक सॉर्ट सरणी के लिए मिलता है, जिसमें 2, 3, 4, 5 और 6 सब क्रमबद्ध हैं। हर कोई तर्क समझ में आया एक चयन तरह कैसे काम करता है? 

तुम बस किसी प्रकार का है एक न्यूनतम मूल्य का। तुम्हें पता है कि क्या है का ट्रैक रख रहे हैं। आपको यह लगता है और जब भी, आप यह स्वैप array-- में पहली मूल्य के साथ या, न पहले value-- सरणी में अगले मूल्य। कूल। 

तो तुम लोगों के रूप में एक तरह से एक संक्षिप्त झलक से देखा था, हम इस बाहर pseudocode करने के लिए जा रहे हैं। तो पीठ में तुम लोगों के लिए चाहते हैं एक मेज पर एक समूह है, हर किसी के लिए फार्म एक छोटे साथी फार्म कर सकते हैं, मैं जा रहा हूँ आप तीन मिनट की तरह लोगों को देने के लिए बस के माध्यम से बात करने के लिए तर्क, अंग्रेजी में, हम लागू करने में सक्षम हो सकता है की कैसे स्यूडोकोड एक चयन तरह लिखने के लिए। और कैंडी नहीं है। आते हैं और कैंडी प्राप्त करें। आप पीठ में रहे हैं और आप चाहते हैं कैंडी, मैं अपने आप को कैंडी फेंक सकते हैं। असल में, you-- शांत करते हैं। मुझे माफ करें। ठीक। 

हम के रूप में, चाहते हैं तो अगर एक वर्ग है, लिखने स्यूडोकोड एक दृष्टिकोण हो सकता है कि कैसे के लिए यह समस्या सिर्फ स्वतंत्र। मैं बस के चारों ओर जाने के लिए और करेंगे, आदेश में, समूहों पूछना की अगली पंक्ति के लिए हम क्या कर किया जाना चाहिए। तुम लोगों को शुरू करना चाहते हैं तो बंद, पहली बात यह है कि क्या हो रहा है आप करने की कोशिश कर रहे हैं, जब ऐसा करने के लिए इस कार्यक्रम को हल करने के लिए एक तरह से लागू चुनिंदा एक सूची को सॉर्ट करने के लिए? अभी हम यह मान के चलो एक सरणी, सब ठीक है? 

दर्शकों: आप कुछ बनाना चाहते हैं की तरह [सुनाई] क्या आप कर रहे हैं कि अपने पूरे सरणी के माध्यम से चल रहा है। 

ANDI PENG: ठीक है। तो अगर आप पुनरावृति करना चाहते करने जा रहे हैं हर जगह के माध्यम से, है ना? इतना महान। तुम लोग मुझे देना चाहते हैं अगले पीठ में, हाँ line--। 

दर्शकों: उन्हें चेक सभी छोटी के लिए। 

ANDI PENG: हम वहाँ जाते हैं। इसलिए हम के माध्यम से जाने के लिए और करने के लिए जाँच करना चाहते हैं न्यूनतम मूल्य सही है, क्या देख रहे हो? मैं करने के लिए कि संक्षिप्त करने के लिए जा रहा हूँ "मि।" तुम लोगों को बाद क्या करना चाहते हैं आप कम से कम मूल्य मिल गया है? 

दर्शकों: [अश्राव्य] ANDI PENG: तो आप चाहते करने के लिए जा रहे हैं उस सरणी के पहले के साथ यह स्विच, है ना? यही कारण है कि मैं कहने जा रहा हूँ, शुरुआत है। ठीक है। तो अब आप पहली बार बदली है कि एक, क्या आपको लगता है कि बाद क्या करना चाहते हैं? तो अब हम जानते हैं कि इस यहाँ एक ठीक है, छोटी मूल्य होना चाहिए? तो फिर तुम एक अतिरिक्त बाकी है अवर्गीकृत है कि सरणी के। तो अगर आप हैं, तो यहाँ क्या करना चाहते हैं लोग मुझे अगली पंक्ति देना चाहते हैं? दर्शकों: तो फिर तुम पुनरावृति करना चाहते हैं सरणी के शेष के माध्यम से। ANDI PENG: हाँ। और तो के माध्यम से पुनरावृति करता है एक तरह से हम शायद आवश्यकता होगी समझा जाए? किस प्रकार का-- 

दर्शकों: ओह, एक अतिरिक्त चर? ANDI PENG: शायद पाश के लिए एक और, है ना? तो हम शायद चाहते करने के लिए जा रहे हैं through-- महान पुनरावृति करने के लिए। और फिर तुम वापस जाने के लिए जा रहे हैं और शायद फिर से न्यूनतम जाँच, है ना? और अगर आप को दोहरा रखने के लिए जा रहे हैं इस छोरों क्योंकि बस जा ठीक है, चालू रखने के लिए? 

तो तुम लोग, हम देख सकते हैं सिर्फ एक सामान्य स्यूडोकोड है हम चाहते हैं कि कैसे इस कार्यक्रम को देखने के लिए। यहां यह पुनरावृति, हम क्या करें आम तौर पर हमारे कोड में लिखने की जरूरत हम एक के माध्यम से पुनरावृति करना चाहते हैं संरचना की सरणी, किस तरह के? मैं क्राइस्टाबेल लगता है पहले से ही से पहले यह बात कही। 

दर्शकों: पाश के लिए एक। 

ANDI PENG: पाश के लिए एक? बिल्कुल सही। तो यह शायद है एक पाश के लिए होने जा रहा। संकेत करने के लिए जा रहा यहां एक जांच क्या है? आमतौर पर, आप जाँच करना चाहते हैं कुछ कुछ होता है, तो else-- 

दर्शकों: यदि। 

ANDI PENG: एक हैं, तो ठीक है? यहां स्वैप और फिर, हम करेंगे बाद में खत्म हो जाने के डेविड क्योंकि के रूप में अच्छी तरह से व्याख्यान में उस के माध्यम से चला गया। और फिर दूसरा पुनरावृति implies-- 

दर्शकों: पाश के लिए एक और। 

ANDI PENG: बिल्कुल, पाश के लिए --another। हम देख रहे हैं तो सही ढंग से इस पर, हम हम शायद रहे हैं कि देख सकते हैं पाश के लिए एक नेस्टेड की जरूरत जा वहाँ में एक सशर्त बयान के साथ और उसके बाद कोड की एक वास्तविक टुकड़ा है कि मूल्यों स्वैप करने के लिए जा रहा है। इसलिए मैं सिर्फ आम तौर पर लिखा है यहां एक स्यूडोकोड कोड। और फिर हम वास्तव में जा रहे हैं शारीरिक रूप से करने के लिए, एक वर्ग के रूप में, यह आज से लागू करने के लिए प्रयास करें। चलो इस आईडीई में वापस जाओ। 

उह ओह। वहाँ क्यों not-- यह है कि है। ठीक। क्षमा करें, मुझे थोड़ा और अधिक ज़ूम करने के लिए कोशिश करते हैं। हम वहाँ चलें। मैं यहाँ क्या कर रहा हूँ मैं बना लिया है एक कार्यक्रम में कहा, "चयन / sort.c।" मैं नौ वर्ष की एक सरणी बना लिया है मूल्यों, 4, 8, 2, 1, 6, 9, 7, 5, 3। वर्तमान में, के रूप में आप कर सकते हैं वे अव्यवस्थित हैं, देखते हैं। n संख्या होने जा रहा है कि आप मूल्यों की राशि बताता है आप अपने सरणी में है। इस मामले में, हम नौ मूल्य नहीं है। और मैं बस यहाँ एक पाश के लिए मिल गया है कि अवर्गीकृत सरणी बाहर प्रिंट। 

और अंत में, मैं भी एक मिल गया है बस इसे फिर से बाहर है कि प्रिंट पाश। तो सैद्धांतिक रूप से, इस कार्यक्रम यदि अंत में, सही ढंग से काम कर रहा है, आप एक पाश के लिए मुद्रित देखना चाहिए जिसमें 1, 2, 3, 4, 5, 6, 7, 8, 9 क्रम में सभी सही ढंग से कर रहे हैं। 

तो हम यहाँ हमारे स्यूडोकोड मिल गया है। मैं अभी कर रहा हूँ है-- किसी को चाहता है volunteers-- के लिए पूछने के लिए जाना जा रहा क्या हुआ अगर टाइप करने के लिए वास्तव में मुझे बताओ हम पहली बार, बस पुनरावृति करना चाहते हैं इस सरणी की शुरुआत के माध्यम से? मैं कर रहा हूँ कोड की लाइन क्या है शायद यहां की जरूरत के लिए जा रहे हैं? 

दर्शकों: [अश्राव्य] 

ANDI PENG: हाँ, लगता है मुक्त है-- क्षमा करें, आप up-- महसूस खड़ा करने के लिए नहीं है अपनी आवाज एक सा उठाने के लिए स्वतंत्र। 

दर्शकों: पूर्णांक मैं बराबर होती है के लिए 0-- 

ANDI PENG: हाँ, अच्छा है। 

दर्शकों: मैं सरणी लंबाई की तुलना में कम है। 

ANDI PENG: तो में रखना , यहाँ कोई आपत्ति क्योंकि हम एक समारोह में नहीं है कि हमें एक सरणी की लंबाई बताता है, हम पहले से ही एक है भंडार है कि कि मूल्य। है ना? एक और बात रखने के लिए एक सरणी में mind-- में नौ मूल्यों का, अनुक्रमित क्या कर रहे हैं? चलो बस इस सरणी 0-3 था कहते हैं। आप पिछले कि वहाँ सूचकांक वास्तव में 3 है। यह वहाँ है, भले ही 4 नहीं है सरणी में चार मूल्यों। 

यहाँ में तो, हम बहुत सावधान रहना होगा लंबाई के लिए क्या हमारी हालत की होने जा रहा है। 

दर्शकों: यह n शून्य से 1 नहीं होगा? ANDI PENG: यह हो रहा है वास्तव में एन शून्य से 1,। कि मतलब, क्यों करता है यह n है शून्य से 1, सबको? सरणियों शून्य अनुक्रमित रहे हैं क्योंकि यह है। वे 0 से शुरू और 1 एन शून्य तक चला। हाँ, यह थोड़ा मुश्किल है। ठीक। और फिर-- दर्शकों: Isnt'1 कि पहले से ही यद्यपि का ध्यान रखा, बस की तुलना में कम या ज्यादा "यह नहीं कह रहा द्वारा बराबर कम से कम "और सिर्फ यह कह" करने के लिए? " 

ANDI PENG: यह एक है वास्तव में अच्छा सवाल है। इसलिए हां। लेकिन यह भी, हम जिस तरह से कर रहे हैं कि जाँच सही लागू करने, आप दो मूल्यों की तुलना करने की जरूरत है। तो अगर आप वास्तव में करना चाहते हैं "करने के लिए" खाली छोड़ दें। यदि आप तुलना क्योंकि यह एक है, आप नहीं जा रहे हैं इसे करने के बाद कुछ भी ठीक है, के लिए की तुलना करने के लिए? हाँ। तो मैं ++। के दशक में हमारे कोष्ठक जोड़ दें। वूप्स। अच्छा है। इसलिए हम शुरुआत है हमारे बाहरी पाश की। तो अब हम शायद करना चाहते हैं रखने के लिए एक परिवर्तनीय बनाने छोटी मूल्य का ट्रैक, है ना? किसी ने मुझे देने के लिए चाहता है ऐसा होता है कि कोड की लाइन? हम जा रहे हैं, तो हम क्या जरूरत है कुछ स्टोर करने के लिए करना चाहते हैं? 

ठीक है। उस के लिए शायद एक बेहतर नाम "अस्थायी" be-- होगा पूरी तरह से works-- शायद अधिक जिसे उपयुक्त होगा नामक एक, हम सबसे छोटी value-- चाहते हैं 

दर्शकों: न्यूनतम। ANDI PENG: मिनट, वहाँ हम चले। मिनट के लिए अच्छा होगा। और यहाँ तो, हम क्या करें करने के लिए इसे प्रारंभ करने के लिए करना चाहते हैं? यह थोड़ा मुश्किल है। क्योंकि अभी पर इस सरणी की शुरुआत अगर आप सही, कुछ भी नहीं देखा है? स्वचालित रूप से तो क्या, यदि हम सिर्फ मैं 0 बराबरी पर हैं हम प्रारंभ करने के लिए क्या चाहते हो हमारी पहली न्यूनतम मूल्य है? दर्शकों: मैं। ANDI PENG: मैं, वास्तव में। क्राइस्टाबेल, हम क्यों चाहते हो मैं करने के लिए इसे प्रारंभ करने के लिए? 

दर्शकों: ठीक है, क्योंकि हम 0 के साथ शुरू कर रहे हैं। हम तुलना करने के लिए कुछ भी नहीं है क्योंकि तो यह न्यूनतम 0 खत्म किया जा रहा होगा। 

ANDI PENG: बिल्कुल। तो वह बिल्कुल सही है। हम वास्तव में नहीं है, क्योंकि , अभी तक कुछ भी देखा हम अपने न्यूनतम मूल्य क्या है पता नहीं है। हम सिर्फ करने के लिए इसे प्रारंभ करने के लिए करना चाहते हैं मैं, जो वर्तमान में, यहीं है। और हम करने के लिए जारी रखने के रूप इस सरणी नीचे ले जाते हैं, हम एक दूसरे के साथ, कि देख लेंगे अतिरिक्त पास, मैं वेतन वृद्धि। और तो उस बिंदु पर, मैं शायद जा रहा है न्यूनतम होना चाहता हूँ, यह जो कुछ भी होने जा रहा है क्योंकि अवर्गीकृत सरणी की शुरुआत है। कूल। 

तो अब हम जोड़ना चाहते हैं यहाँ इस पाश के लिए है कि के माध्यम से पुनरावृति करने के लिए जा रहा अवर्गीकृत, या इस सरणी के बाकी। किसी ने मुझे एक देने के लिए चाहता है ऐसा होता है कि कोड की लाइन? Hint-- क्या हम यहाँ नीचे की ज़रूरत है? क्या पाश के लिए इस में जाना जा रहा है? हाँ। दर्शकों: तो हम करने के लिए चाहता हूँ एक अलग पूर्णांक है, हम बाकी के माध्यम से चल रहे हैं, क्योंकि इसके बजाय मैं की सरणी, तो हो सकता है की जम्मू। 

ANDI PENG: हाँ, जम्मू मुझे अच्छा लगता है। बराबर होती है? 

दर्शकों: तो, क्योंकि मैं होना प्लस 1 होगा आप अगले मूल्य पर शुरू कर रहे हैं। और फिर तो फिर end-- करने के लिए, J है n शून्य से 1, और फिर J ++ से कम है। ANDI PENG: ग्रेट। 

और फिर यहाँ में, हम चाहते हैं करने के लिए जा रहे हैं हमारी शर्त पूरी होती है देखने के लिए जाँच करने के लिए, है ना? आप करना चाहते हैं क्योंकि न्यूनतम मूल्य बदल जाते हैं की तुलना में यह वास्तव में छोटा है, तो क्या आप सही करने के लिए यह तुलना कर रहे हैं? तो क्या हम यहाँ में चाहते करने के लिए जा रहे हैं? देखने के लिए जांचें। बयान किस प्रकार की हम शायद जा रहे हैं तिवारी यदि उपयोग करना चाहते हैं हम कुछ जाँच करना चाहते हैं? 

दर्शकों: एक बयान है। 

ANDI PENG: एक अगर बयान। तो if-- और होना करने के लिए क्या हो रहा है हम अंदर चाहते हैं कि हालत हमारे यदि बयान की? 

दर्शकों: यदि जम्मू के मूल्य i-- के मूल्य से कम है 

ANDI PENG: बिल्कुल। तो if-- तो यह सरणी "सरणी।" कहा जाता है अच्छा है। क्या था कि array-- तो अगर? दोबारा कहना। 

दर्शकों: सरणी-जम्मू से कम है सरणी-मैं, तो हम न्यूनतम बदल जाएगा। इसलिए मिनट जम्मू होगा। 

ANDI PENG: कि मतलब है? ठीक। और अब यहाँ नीचे, हम वास्तव में ठीक है, स्वैप लागू करना चाहते हैं? तो, व्याख्यान में, याद डेविड, जब कि वह the-- क्या था स्वैप करने के लिए कोशिश कर रहा था it-- संतरे का रस और milk-- 

दर्शकों: यह है कि सकल था। 

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

दर्शकों: एक अस्थायी चर। 

ANDI PENG: एक अस्थायी चर। तो चलो पूर्णांक अस्थायी करते हैं। यह एक बेहतर होगा, देखें वाह है-- समय, कि क्या था? ठीक। तो यह एक अच्छा होता समय चर "अस्थायी।" नाम करने के लिए तो चलो पूर्णांक अस्थायी करते हैं। हम क्या करने जा रहे हैं यहाँ के बराबर अस्थायी सेट? दर्शकों: न्यूनतम? ANDI PENG: यह थोड़ा मुश्किल है। यह वास्तव में अंत में कोई फर्क नहीं पड़ता। यह बात नहीं है क्या आदेश आप में स्वैप करने के लिए चुनें जब तक आप सुनिश्चित कर रहे हैं के रूप में आप कर रहे हैं आप स्वैपिंग क्या कर रहे हैं का ट्रैक रखने के। 

दर्शकों: यह सरणी-मैं हो सकता है। 

ANDI PENG: हाँ, चलो सरणी-मैं करते हैं। और फिर अगली पंक्ति क्या है कोड की हम यहाँ करना चाहते हैं? दर्शकों: सरणी-मैं सरणी-जम्मू के बराबर होती है। ANDI PENG: और अंत में? दर्शकों: सरणी-जम्मू सरणी-मैं के बराबर होती है। दर्शकों: या सरणी-जम्मू बराबरी सरणी-temp-- या, अस्थायी। 

ANDI PENG: ठीक है। तो चलो इस चलाते हैं और देखते हैं यह काम करने के लिए जा रहा है। कि कहाँ क्या हो रहा है? ओह, यह एक समस्या है। हम कर रहे हैं, लाइन 40 पर, देखें सरणी-जे का उपयोग करने की कोशिश कर रहा है? लेकिन जहां एक ही में जम्मू मौजूद है? 

दर्शकों: पाश के लिए। ANDI PENG: ठीक है। तो हम क्या करने की जरूरत के लिए जा रहे हैं? 

दर्शकों: the-- बाहर यह परिभाषित करें दर्शकों: हाँ, मैं तुम्हें लगता है कि बयान, सही है, तो दूसरे का उपयोग करने के लिए? तो, जैसे यदि minimum-- सब ठीक है, मुझे लगता है। 

ANDI PENG: दोस्तों, कोशिश एक नज़र चलो लेने के लिए , हम यहाँ कुछ क्या कर सकते हैं चलो देखते? 

दर्शकों: ठीक है। न्यूनतम बराबर नहीं करता है तो न्यूनतम है, तो j-- तो अभी भी i-- फिर हम स्वैप करने के लिए नहीं होता। 

ANDI PENG: मुझे लगता है कि बराबर करता है? आप यहाँ क्या कहना चाहते हो? 

दर्शकों: या हाँ, यदि न्यूनतम हाँ, बराबर नहीं मैं नहीं करता है। ANDI PENG: ठीक है। अच्छा है कि हमारी समस्याओं, एक तरह से हल करती है। लेकिन यह है कि अभी भी हल नहीं करता जम्मू के बाद से j-- क्या होता है अगर की समस्या इसके बारे में बाहर मौजूद नहीं है, क्या आप हम इसके साथ क्या करना चाहते हैं? बाहर यह घोषणा? चलो इस चलाने की कोशिश करते हैं। उह ओह। हमारी तरह काम नहीं कर रहा। 

यदि आप हमारे प्रारंभिक देख सकते हैं सरणी उन मूल्यों था। और इसे बाद में करना चाहिए था 1, 2, 3, 4, 5, 6, 7, 8, 9 में किया गया। काम नहीं कर रहा। आह। हम क्या करें? दर्शकों: डिबग। ANDI PENG: ठीक है, हम कोशिश कर सकते हैं। हम डिबग कर सकते हैं। थोड़ा बाहर ज़ूम। चलो हमारे breakpoint सेट करते हैं। के like-- ठीक चलते हैं। 

हम पहले से ही जानते हैं कि क्योंकि तो इन लाइनों, 15 22 के माध्यम से, मैं क्या कर रहा हूँ सब है, क्योंकि working-- रहे हैं बस के माध्यम से और printing-- पुनरावृति मुझे आगे जाना है और उस को छोड़ सकते हैं। की लाइन 25 पर शुरू करते हैं। OOP, मुझे उस से छुटकारा मिलता है। 

दर्शकों: तो ब्रेकप्वाइंट का डिबगिंग जहां शुरू होता है? ANDI PENG: या बंद हो जाता है। दर्शकों: या बंद हो जाता है। ANDI PENG: हाँ। आप कई ब्रेकप्वाइंट सेट कर सकते हैं और यह सिर्फ एक दूसरे से कूद कर सकते हैं। लेकिन इस मामले में हम नहीं जानते जहां गलती हो रहा है। तो हम बस करना चाहते हैं ऊपर से नीचे शुरू करते हैं। हाँ। ठीक। 

यहाँ तो इस लाइन में, हम में कदम कर सकते हैं। आप यहाँ नीचे देख सकते हैं हम एक सरणी मिल गया है। उन मान रहे हैं सरणी में हैं। तुम देखते हो, कि कैसे सूचकांक 0, यह , ओह value-- से मेल खाती है मैं में ज़ूम करने की कोशिश करने के लिए जा रहा हूँ। क्षमा करें, यह वास्तव में मुश्किल है सरणी 0 सूचकांक में see-- करने के लिए, हम 4 के एक मूल्य है और तो बहुत आगे है और इतने पर। हम अपने स्थानीय चर है। अभी मैं के बराबर है हम यह देखना चाहते हैं जो 0,। 

और तो के माध्यम से निकलते रहते हैं। हमारे न्यूनतम, 0 के बराबर है जो हम भी इसे देखना चाहते हैं। और फिर हम के लिए हमारी दूसरी दर्ज पाश, सरणी-जम्मू सरणी-मैं से कम है तो, जो ऐसा नहीं था। तो आप कैसे देखा था कि उस पर छोड़ दिया? 

दर्शकों: यदि हां चाहिए न्यूनतम, सभी that-- नहीं करना चाहिए कि पाश के लिए पहले के अंदर हो सकता है? ANDI PENG: नहीं, क्योंकि आप अभी भी परीक्षण करना चाहते हैं। आप हर एक तुलना करना चाहते हैं समय, आप इसे माध्यम से चलाने के बाद भी। आप सिर्फ यह करना है नहीं करना चाहते हैं पहले पास के माध्यम से पर। यह आप के साथ क्या करना चाहते हैं फिर प्रत्येक अतिरिक्त गुजरती हैं। तो क्या आप के लिए जाँच करना चाहते हैं अंदर अपनी हालत। तो हम बस करने के लिए जा रहे हैं यहाँ के माध्यम से चालू रखने के लिए। मैं तुम लोगों को एक संकेत देता हूँ। यह इस तथ्य के साथ क्या करना है जब कि यदि आप अपने सशर्त जाँच कर रहे हैं आप की जाँच नहीं कर रहे हैं सही सूचकांक के लिए। इसलिए अभी आप के लिए जाँच कर रहे हैं जम्मू की सरणी सूचकांक सरणी से भी कम है मैं के सूचकांक। लेकिन क्या आप पर क्या कर रहे हैं पाश के लिए की शुरुआत? तुम्हें पता है मैं के बराबर जम्मू की स्थापना नहीं कर रहे हैं? 

हाँ, तो हम वास्तव में कर सकते हैं यहां डिबगर से बाहर निकलें। तो चलो हमारे स्यूडोकोड पर एक नजर डालते हैं। For-- हम करने जा रहे हैं मैं 0 के बराबर होती है पर शुरू करते हैं। हम 1 एन शून्य तक जाने के लिए जा रहे हैं। की जांच करते हैं, हम चाहते हैं कि सही किया है? हाँ, यह सही था। 

तो फिर यहां के अंदर है, हम कर रहे हैं एक न्यूनतम मूल्य बनाने के लिए जा रहा और मैं करने के लिए कि बराबर सेट। हम जानते हैं कि क्या किया? हाँ, ऐसा ही किया। अब हमारे भीतर के लिए पाश में, हम कर रहे हैं जम्मू में क्या करने जा मैं n करने के लिए शून्य से 1 के बराबर होती है। हम जानते हैं कि क्या किया? दरअसल, हम ऐसा ही किया। 

ताकि हालांकि, हम यहाँ क्या तुलना कर रहे हैं? 

दर्शकों: जम्मू प्लस 1। ANDI PENG: बिल्कुल। और फिर आप सेट करना चाहते करने जा रहे हैं जम्मू प्लस 1 के रूप में अच्छी तरह से करने के लिए बराबर अपने न्यूनतम। इसलिए मैं वास्तव में जल्दी से उस के माध्यम से चला गया। आप लोग समझ रहे हो ऐसा क्यों है कि जम्मू प्लस 1 है? ठीक। 

अपने सरणी में, में तो के माध्यम से अपने पहले पास, अपने पाश के लिए, पूर्णांक के लिए मैं 0 के बराबर होती है, चलो बस जाने यह अभी तक बदला नहीं गया मान। हम पूरी तरह से, की एक सरणी है, सिर्फ चार अवर्गीकृत तत्वों, है ना? इसलिए हम मैं 0 के बराबर प्रारंभ करने के लिए चाहते हैं। और मैं करने जा रहा है सिर्फ इस लूप के माध्यम से चला रहे हैं। और तो पहले पास में, हम जा रहे हैं "मिनट" नामक एक चर प्रारंभ करने के लिए वह भी, क्योंकि मैं बराबर होती है हम एक न्यूनतम मूल्य नहीं है। तो यह है कि के रूप में अच्छी तरह से करने के लिए 0 वर्तमान बराबर है। और फिर हम के माध्यम से जाने के लिए जा रहे हैं। और हम फिर से पुनरावृति करना चाहते हैं। अब हमने पाया है कि क्या हमारे न्यूनतम हम के माध्यम से पुनरावृति करना चाहते है, यह तुलना है, तो फिर ठीक है, यह देखने के लिए? इसलिए जम्मू, यहाँ, जा रहा है बराबर मैं करने के लिए 0 है, जो। और फिर यदि सरणी जम्मू अलावा मैं, जो कम के रूप में, अगले खत्म हो चुका है कि एक है क्या अपने वर्तमान न्यूनतम से मूल्य आप स्वैप करने के लिए चाहते हैं। 

तो बस हम है कहना चलो 2, 5, 1, 8, जैसे, मिला है। अभी, मैं करने के लिए बराबर है 0 और जे 0 के बराबर है। और कहा कि हमारी न्यूनतम मूल्य है। सरणी-जम्मू प्लस अगर i-- एक है, इसलिए यदि कि हम देख रहे हैं एक के बाद है यह पहले एक से अधिक होता है यह न्यूनतम बनने जा रही है। 

यहाँ तो हम 5 कि वहाँ कि कम से कम नहीं है। तो यह 5 नहीं किया जा रहा है। हम एक सही, कम से कम 2 है कि वहाँ? तो अब हम हमारे न्यूनतम पता है कि 0, 1, 2 में सूचकांक मूल्य होने जा रहा। हाँ? और फिर तुम, यहाँ नीचे मिलता है जब आप सही मान स्वैप कर सकते हैं। 

तो तुम लोग सिर्फ जम्मू कर रहे थे जब इससे पहले, आप एक बार में नहीं दिख रहे थे इसके बाद। आप पर देख रहे थे एक ही मूल्य है, जो यह सिर्फ कुछ भी नहीं कर रहा था, यही वजह है। कि हर किसी के लिए समझ पड़ता है, यही कारण है कि हम उस के साथ साथ वहाँ 1 की ज़रूरत है? ठीक। अब इसे बनाने के लिए के माध्यम से चलो बस चलाते हैं सुनिश्चित करें कि कोड के बाकी सही है। यही वजह है कि क्या हो रहा है? आह, यह यहीं मिनट है। हम गलत मान तुलना थे। अरे नहीं। 

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

ठीक है। हम इस बारे में बात करने पर स्थानांतरित कर सकते हैं उपगामी संकेतन, जो कहने का सिर्फ एक अच्छा तरीका है इन प्रकार के सभी के runtimes। इसलिए मैं व्याख्यान में, डेविड पता है, runtimes पर छुआ। और वह पूरे सूत्र के माध्यम से चला गया के runtimes गणना करने के लिए कैसे। उस बारे में कोई चिंता नहीं है। क्या तुम सच में उत्सुक हैं कि कैसे काम करता है पर, अनुभाग के बाद मुझसे बात करने के लिए स्वतंत्र महसूस। हम के माध्यम से चल सकता है एक साथ फार्मूले। लेकिन यह सब आप लोग वास्तव में करने के लिए है जानते 2 n खत्म चुकता है कि n चुकता रूप में एक ही बात है। सबसे बड़ी संख्या है, इसलिए प्रतिपादक, सबसे बढ़ता है। और इसलिए हमारे उद्देश्यों के लिए, हम देखभाल के बारे में सब बढ़ रही है कि कि विशाल संख्या है। 

तो क्या सबसे अच्छा मामला है चयन प्रकार के क्रम? आपके पास करने के लिए जा रहे हैं एक सूची के माध्यम से पुनरावृति और उसके बाद के माध्यम से पुनरावृति उस सूची के बाकी है, कितनी बार कर रहे हैं आप शायद करने के लिए जा रहा में सबसे खराब case-- में मामले सबसे अच्छा माध्यम से चलाने के sorry--? शायद बेहतर सवाल है पूछने के लिए, सबसे खराब स्थिति क्या है चयन प्रकार का क्रम। दर्शकों: एन चुकता। ANDI PENG: यह पता सही, चुकता है। इस तरह से है की तो एक आसान तरीका लगता है, आप छोरों के लिए नेस्ट दो है किसी भी समय, यह n चुकता किया जा रहा है। आप कर रहे हैं, क्योंकि न केवल एक बार फिर से के माध्यम से चल रहा है, तुम वापस जाना है आसपास है और इसके माध्यम से चलाने के एक बार फिर हर मूल्य के लिए अंदर। उस मामले में तो, आप n चला रहे हैं बार n, माफ करना है- जो चुकता n बार एन, एन चुकता बराबर होती है जो। 

और तरह यह भी एक सा है इस अर्थ में अद्वितीय यह इन यदि कोई फर्क नहीं पड़ता कि मूल्यों क्रम में पहले से ही कर रहे हैं। यह अभी भी वैसे भी माध्यम से चलाने के लिए जा रहा है। चलो बस यह 1, 2, 3, 4 था कहते हैं। भले ही यह किया गया था या नहीं आदेश, यह अभी भी माध्यम से भाग गया होता और अभी भी कम से कम मूल्य की जाँच की। यह बना दिया जाएगा चेकों की एक ही नंबर हर एक समय, यहां तक ​​कि अगर यह वास्तव में कुछ भी नहीं छुआ। 

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

ठीक है। तो मैं बस जल्दी से चलाने के लिए जा रहा हूँ एक तरह की बाकी के माध्यम से। के लिए एल्गोरिथ्म बुलबुला, याद sort-- यह पहली बार एक था डेविड व्याख्यान में खत्म हो गया था। अनिवार्य रूप से, आप कदम पूरी सूची के माध्यम और तुम सिर्फ तुम swap-- एक समय में दो की तुलना करें। और एक, अधिक से अधिक है, तो आप की तुलना में सिर्फ उन्हें स्वैप। इन अधिक कर रहे हैं, तो आप स्वैप होगा। मैं यहीं अधिकारी मिल गया है। 

तो चलो बस आप 8, 6, 4, 2 था कहते हैं। आप 8 और एक 6 तुलना चाहते हैं। आप उन्हें स्वैप करने की जरूरत थी। आप 8 और 4 तुलना होगा। आप उन्हें स्वैप करने की जरूरत थी। आप 8 स्वैप करने के लिए है, तो और 2, के रूप में अच्छी तरह से बदल दिया है। इस तरह के एक अर्थ में तो, आप देख सकते हैं समय की एक लंबी अवधि में बाहर खेला, कैसे बुलबुला के मूल्यों तरह करने के लिए है, जो समाप्त हो जाती है, हम इसे क्यों फोन बुलबुले की तरह। 

हम बस पर फिर से के माध्यम से चला जाएगा हमारे दूसरे के पास है, और हमारे तीसरे पास, और हमारा चौथा गुजरती हैं। मूलतः, बुलबुला तरह बस चलाता है आप किसी भी अधिक स्वैप करना नहीं है जब तक। इस अर्थ में कि तो, यह सिर्फ है इसके लिए सामान्य स्यूडोकोड। कोई चिंता नहीं, इन सभी ऑनलाइन हो जाएगा। हम वास्तव में इस पर जाने के लिए नहीं है। 

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

तो सबसे अच्छा और सबसे खराब क्या कर रहे हैं मामले बुलबुला तरह के लिए Runtimes? और hint-- यह वास्तव में अलग है इस अर्थ में चयन प्रकार से इन दो जवाब ही नहीं हैं। में क्या होगा के बारे में सोचो एक मामले में यह पहले से ही हल किया गया था यदि। और के बारे में क्या सोचते हैं यह था तो क्या होगा मामले में जिसमें इसे हल नहीं किया गया था। और आप की तरह चला सकते हैं यही कारण है कि के माध्यम से हो रहा है। मैं 30 की तरह, तुम लोगों को दे दूँगा सेकंड उस बारे में सोचने के लिए। 

ठीक। किसी को क्या में एक अनुमान है बुलबुला तरह के सबसे ज्यादा मामले क्रम है? हाँ। 

दर्शकों: यह, जैसे, n बार होगा n शून्य से लगता है कि जैसे एक या कुछ और? की तरह यह भी चलाता है हर बार, यह एक स्वैप कम है, की तरह, सिर्फ है जो कुछ भी है कि यह गया था। 

ANDI PENG: हाँ, तो आप पूरी तरह से सही हो। और इस एक मामले में जो है आपके जवाब वास्तव में और अधिक जटिल था एक से हम देने की जरूरत है। तो यह है कि मैं कर रहा हूँ run-- जा रहा है यहां यह सब मिटा करने के लिए जा रहा है। हर किसी को अच्छा है? मैं इस मिटा सकता हूँ? ठीक। आप n के माध्यम से चलाने के लिए जा रहे हैं बार पहली बार है, है ना? और वे के माध्यम से चलाने के लिए जा रहे हैं n शून्य से 1 दूसरी बार, है ना? और फिर आप रखने के लिए जा रहे हैं एन खान 2, वगैरह, जा रहा है। डेविड जहां एक व्याख्यान में इस किया था, आप उन सभी मूल्यों के लिए कहा, तो आप है कि कुछ पाने के like-- yeah-- अनिवार्य रूप से सिर्फ कम कर देता है, जो 2, खत्म n करने के लिए नीचे चुकता। आप एक पाने के लिए जा रहे हैं वहाँ में अजीब अंश। और तो बस इतना पता है कि n हमेशा चुकता अंश पर पूर्वता लेता है। और हां, इस मामले में सबसे खराब क्रम n चुकता किया जाएगा। यह उतरते में था आदेश, आपको लगता है एक स्वैप हर बार बनाने के लिए है। 

संभवतः, क्या होगा, सबसे अच्छा मामले क्रम? सूची में पहले से ही था, तो चलो बस कहना है आदेश में, क्रम क्या होगा? 

दर्शकों: एन। ANDI PENG: यह वास्तव में, N है। और क्यों यह n है? दर्शकों: तुम क्योंकि बस प्रत्येक एक बार पर जांच के लिए है। ANDI PENG: बिल्कुल। श्रेष्ठ संभव क्रम में तो इस सूची में पहले से ही था, तो sorted--, चलो 1, 2, 3, हम कहते हैं 4-- आप बस के माध्यम से जाना होगा, आप, जांच होगी आप ओह, वे सब बाहर पैन, देखना होगा। मैं स्वैप करने के लिए नहीं था। मेरा काम हो गया। तो उस मामले में, यह सिर्फ n है या कदम की संख्या तुम सिर्फ पहली सूची में जांच की थी। 

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

तो उदाहरण के लिए, हम एक हैं 3 की सूची, 5, 2, 6, 4 फिर से। हम यह वर्तमान में है कि पता अवर्गीकृत हम सिर्फ है क्योंकि यह देख शुरू कर दिया। हम एक बार देख लेते हैं और हम जानते हैं कि पहले मूल्य, सही हल है? आप केवल की एक सरणी में देख रहे हैं आकार एक, आप यह हल है कि पता है। 

तो फिर हम जानते हैं कि अन्य चार अवर्गीकृत हैं। हम के माध्यम से जाने के लिए और हम उस मूल्य देखते हैं। चलिये वापस चलते हैं। 5 के उस मूल्य को देखने? हम इस पर एक नज़र रखना। हम 3 की तुलना करें। हम यह अधिक से अधिक है कि पता 3, तो हम उस हल है कि पता है। इसलिए अब हम जानते हैं कि पहले दो हल और पिछले तीन नहीं कर रहे हैं। 

हम 2 पर एक नज़र रखना। हम पहले 5 के साथ यह जाँच करें। यह 5 से कम है? यह नहीं। इसलिए हम नीचे देख कर रख दिया है। तो आप 3 से 2 की जाँच करें। की तुलना में यह कम है? नहीं। तो तुम एक दो डाला हो गया है पता है सामने में और 3 और 5 दोनों बाहर धक्का दे दिया जाना है। 6 और 4 के साथ फिर से यह मत करो। और हम बस, अनिवार्य रूप से जाँच कर रखना हम बस की जांच जहां, जाँच की जाँच करें। और यह सही में है जब तक स्थिति, हम किस तरह की बस सही स्थिति में डालने, जो इसे का नाम कहाँ से आया है। 

तो यह है कि सिर्फ एल्गोरिथ्म है, स्यूडोकोड प्रतिशत से है, एक तरह से, हम लागू होगा पर एक प्रविष्टि तरह। Pseudocode यहाँ है। यह सब ऑनलाइन है। कोई चिंता नहीं है कि तुम लोग कर रहे हैं यह नीचे की नकल करने की कोशिश कर रहा है। तो एक बार फिर से, एक ही question-- क्या सबसे अच्छा और सबसे खराब runtimes होगा प्रविष्टि प्रकार के लिए? यह आखिरी सवाल के समान है। मैं 30 की तरह, तुम लोगों को दे दूँगा सेकंड के रूप में अच्छी तरह से इस बारे में सोचने के लिए। 

किसी को भी चाहता है कि ठीक मुझे सबसे खराब क्रम दे? हाँ। 

दर्शकों: एन चुकता। 

ANDI PENG: यह n चुकता है। और क्यों यह n चुकता है? 

दर्शकों: में क्योंकि रिवर्स क्रम, आपके पास है- जो, एन समय के माध्यम से जाना n करने के लिए ANDI PENG: हाँ, बिल्कुल। बुलबुला तरह के रूप में तो एक ही बात है। इस सूची में है, तो अवरोही क्रम, आप कर रहे हैं पहले एक बार जांच करने के लिए किया जा रहा। और फिर साथ हर अतिरिक्त मूल्य, आप कर रहे हैं के लिए जा खिलाफ यह जांच करने के लिए सही हर एक मूल्य? और तो कुल मिलाकर, आप करने जा रहे हैं एक एन पास समय एक और एन, जो पास n चुकता है। क्या सबसे अच्छा मामले के बारे में? हाँ। 

दर्शकों: एन शून्य से 1, क्योंकि पहले एक पहले से ही चुकता है। 

ANDI PENG: तो, करीब है। जवाब वास्तव n है। पहले से एक है क्योंकि जब तक हल, यह है कि यह actually-- नहीं हो सकता हम बस में, बाहर lucked कि उदाहरण के लिए, कि 2 सबसे छोटी संख्या हो हुआ। लेकिन यह हमेशा मामला नहीं होगा। 2 पहले से ही शुरुआत में हल किया जाता है तो लेकिन आप देखते हैं और यहां एक 1 वहाँ 1 यह टक्कर करने के लिए जा रहा है। और यह अंत करने के लिए जा रहा है ऊपर वैसे भी टकरा जा रहा है। 

, सबसे अच्छी स्थिति में तो यह वास्तव में सिर्फ एन होने जा रहा है। यदि आपके पास 1, 2, 3, 4, 5, 6, 7, 8, आप कर रहे हैं के माध्यम से चलाने के लिए जा कि पूरी सूची एक बार सब कुछ ठीक है, तो देखने के लिए जाँच करने के लिए। चल रहा है पर हर किसी को स्पष्ट है के रूप में अच्छी तरह से चयन के समय? मैं मैं के माध्यम से जा रहा हूँ ये वास्तव में तेजी से। लेकिन सिर्फ अगर आप जानते हैं कि पता है सामान्य अवधारणाओं, आप अच्छा होना चाहिए। ठीक। तो मैं बस की तरह है, शायद तुम लोगों को दे देंगे, एक मिनट के अपने पड़ोसियों से बात करने के लिए क्या कर रहे हैं बस कुछ पर मुख्य अंतर एक तरह की इन प्रकार के बीच। हम जानते हैं कि जल्द ही खत्म जाना होगा। दर्शकों: ठीक है, ओह। ANDI PENG: हाँ। ठीक। कूल, चलो एक वर्ग के रूप में reconvene करते हैं। ठीक। तो यह था तरह का एक इस अर्थ में ओपन एंडेड सवाल कि उन्हें जवाब के बहुत सारे है। और हम संक्षेप उनमें से कुछ पर जायेंगे। मैं सिर्फ तुम लोगों को प्राप्त करना चाहता था विभेदित के बारे में क्या सोच एक तरह की सभी तीन प्रकार के। और मुझे लगता है, यह भी एक महान सुना क्या करना तरह मर्ज करता question--? बड़ा सवाल है, क्योंकि है कि क्या हम अगले कवर कर रहे हैं। 

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

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

तो यह है कि वास्तव में सार है। इसलिए इस स्यूडोकोड का सिर्फ एक सा है। उस में समझ बनाने के लिए यह चल रहा है तरीका है? तो बस आप एक का कहना है कि चलो n तत्वों की सरणी, है ना? 2 n से कम है, तो आप वापसी कर सकते हैं। क्योंकि तुम्हें पता है कि अगर वहाँ केवल एक ही बात है, इसे हल किया जाना चाहिए। वरना, आप बाईं आधे से तरह, और फिर तुम ठीक आधे से तरह, और फिर आप विलय। 

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

और फिर हम यह नेत्रहीन में देख लेंगे मैं एक दृश्य शिक्षार्थी हूँ क्योंकि। यह मेरे लिए बेहतर काम करता है। तो हम यहाँ एक दृश्य उदाहरण में देख लेंगे। 

छह की हम एक सरणी हम कहते हैं कि तत्वों, 3, 5, 2, 6, 4, 1, हल नहीं। ठीक है, इस पृष्ठ पर एक बहुत कुछ है। तुम लोगों को देख सकते हैं तो अगर यहाँ पहला कदम है, 3, 5, 2, 6, 4, 1, आप छमाही में विभाजित कर सकते हैं। आप 3, 5, 2, 6, 4, 1 है। आप इन आप aren't-- जानते हैं कि वे हल या नहीं कर रहे हैं पता नहीं है, इसलिए आप छमाही में, उन्हें टूट रखने के लिए, छमाही में, आधे में, अंत तक, आप केवल एक ही तत्व है। और एक तत्व हमेशा सही, हल है? 

इसलिए हम जानते हैं कि 3, 5, 2, 4, 6, 1, खुद के द्वारा हल कर रहे हैं। और अब हम उन्हें एक साथ वापस डाल सकते हैं। इसलिए हम 3, 5 में पता है। हम एक साथ उन डाल दिया। हम जानते हैं कि हल है पता है। वहाँ अभी भी 2। हम एक साथ 4 और 6 डाल सकते हैं। हम चाहते हैं कि हल है कि पता है इसलिए हम एक साथ डाल दिया है कि। और एक नहीं है। 

और फिर आप बस को देखो यहीं से इन दो हिस्सों। आप 3, 5, 2, 2, 3, 5 लोगों की है। तुम बस तुलना कर सकते हैं सब कुछ की शुरुआत। आप इस हल है कि क्योंकि मुझे पता है और आपको लगता है कि हल है कि पता है। तो फिर आप भी करने की जरूरत नहीं है 5 की तुलना, तुम सिर्फ 3 की तुलना करें। और 2 इसलिए, 3 की तुलना में कम है आप 2 अंत में जाना चाहिए पता है। 

वहाँ पर एक ही बात। 1 यहाँ से जाना चाहिए। जब तुम जाओ और फिर डाल करने के लिए एक साथ उन दो मूल्यों, आप इस हल है कि पता है और आपको लगता है कि हल है कि पता है। तो फिर एक और 2, 1 कम से कम 2 है। यही कारण है कि एक आपको बताता है कि इस के अंत पर जाना चाहिए यहां तक ​​कि 3 या 5 पर देख के बिना। और फिर 4, तुम सिर्फ कर सकते हैं यह यहाँ में ठीक हो जाता है, की जाँच करें। आप 5 में देखने की जरूरत नहीं है। 6 के साथ एक ही बात है। तुम्हें पता है 6-- यह है कि बस देखा होने की जरूरत नहीं होती। 

और तो उस रास्ते में, आप कर रहे हैं बस अपने आप बचत कदम की एक बहुत आप तुलना कर रहे हैं। आप हर की तुलना करने की जरूरत नहीं है अन्य तत्वों के खिलाफ तत्व। आप सिर्फ लोगों के खिलाफ तुलना यह आप के खिलाफ की तुलना करने की जरूरत है। तो यह है कि एक अमूर्त अवधारणा की तरह है। कोई चिंता नहीं है अगर ऐसा नहीं है बहुत सही अभी तक तुम मार। लेकिन आम तौर पर, यह है कैसे एक मर्ज तरह काम करता है। प्रश्न, जल्दी सवाल, मैं आगे बढ़ने से पहले? हाँ। 

दर्शकों: तो क्या आप ने कहा कि 1, और फिर 4 और 6 और में डाल दिया। तो those-- नहीं कर रहे हैं नहीं कर रहे हैं आप उन्हें देख नहीं पूरे के रूप में अलग तत्वों, के रूप में? ANDI PENG: हाँ। तो क्या चल रहा है आपको लगता है कि मूल रूप से है एक ब्रांड नई सरणी पैदा कर रहे हैं। तो तुम, यहाँ, मैं पता है कि आकार 3 के दो सरणियों, है ना? तो तुम्हें पता है कि मेरी सॉर्ट सरणी छह तत्वों की जरूरत है। तो तुम सिर्फ एक बनाने स्मृति की नई राशि। तो अगर आप की तरह की तरह कर रहे हैं स्मृति के बेकार जा रहा है लेकिन लगता है कि कोई फर्क नहीं पड़ता यह इतना छोटा है क्योंकि। तो अगर आप एक को देखने और आप 2 को देखो। और तुम 1 कम से कम 2 है कि पता है। तो तुम एक में जाना चाहिए पता उन सभी की शुरुआत। 

आप भी करने की जरूरत नहीं है 3 और 5 को देखो। तो अगर आप 1 वहाँ चला जाता है पता है। तो फिर आप मूल रूप से एक बंद काट लें। यह हमारे लिए मर चुका है, जैसे, है। तो फिर हम सिर्फ 2 है, 3, 5, और फिर 4 और 6। और फिर आप, आप जानते हैं कि तुलना 4 और 2, ओह, 2 में वहाँ जाना चाहिए। तो आप 2 नीचे खटखटाने, आप इसे बंद कर काट लें। तो फिर आप सिर्फ 3 है और 4 और 6 में 5। और आप बस इसे काट रखना आप सरणी में उन्हें डाल दिया जब तक। 

दर्शकों: तो तुम सिर्फ हमेशा से रहे हैं [अश्राव्य] की तुलना? 

ANDI PENG: बिल्कुल। तो उस अर्थ में, आप कर रहे हैं बस की तुलना, अनिवार्य रूप से, दूसरे नंबर के खिलाफ एक नंबर। और आप जानते हैं क्योंकि यह आप हल है कि के माध्यम से देखने की जरूरत नहीं है संख्या के सभी। आप सिर्फ पहले एक पर नजर है। और फिर आप बस खटखटाने से कर सकते हैं उन्हें नीचे, क्योंकि आप जानते हैं वे हैं जरूरत है, जहां वे हैं। हाँ। अच्छा प्रश्न। 

और फिर आप की यदि कोई हो एक सा महत्वाकांक्षी हैं, इस कोड को देखने के लिए स्वतंत्र महसूस। यह वास्तव में है शारीरिक कार्यान्वयन हम मर्ज तरह लिखना होगा कैसे की। और अगर आप इसे बहुत ही कम है, देख सकते हैं। पीछे लेकिन विचारों यह बहुत जटिल हैं। तो अगर आप इस बाहर ड्राइंग की तरह लग रहा है अपने होमवर्क आज रात में करने के लिए स्वतंत्र महसूस हो रहा है। 

ठीक। तब दाऊद भी व्याख्यान में यह खत्म हो गया था। सबसे अच्छा मामले में क्या कर रहे हैं runtimes, सबसे ज्यादा मामले runtimes, और मर्ज प्रकार की उम्मीद runtimes? कुछ सेकंड सोचने के लिए। यह बहुत मुश्किल है, लेकिन एक तरह से आप इसके बारे में सहज ज्ञान युक्त अगर आपको लगता। ठीक है। 

दर्शकों: सबसे बुरी स्थिति एन लॉग n है? ANDI PENG: बिल्कुल। और क्यों यह n लॉग एन जाता है। 

दर्शकों: ऐसा नहीं है कि यह क्योंकि , तेजी से तेजी से हो जाता है तो यह इस बात का एक समारोह की तरह है बजाय सिर्फ और सिर्फ एन होने का चुकता या कुछ और? ANDI PENG: बिल्कुल। तो कारण क्यों इस पर क्रम लॉग n है आप क्या कर रहे हैं because-- n है इन सभी चरणों के में कर रही है? तुम सिर्फ सही, यह आधे में काट रहे हैं? और इसलिए हम कर रहे हैं जब यह कर रहा है वह सब है, लॉग इन करें छमाही में एक समस्या विभाजित है, छमाही में, आधे में, अधिक हिस्सों में। और उस अर्थ में, आप की तरह कर सकते हैं के रेखीय मॉडल खत्म कि हम प्रयोग किया गया है। आप काट क्योंकि जब छमाही में बातें करते हैं, यह एक लॉग है। वह सिर्फ गणितीय है यह प्रतिनिधित्व करने का तरीका है। 

और फिर अंत में, अंत में, आप कर रहे हैं बस एक आखिरी पास के माध्यम से कर रही है ठीक है, क्रम में उन सभी को रखा है? और इसलिए तुम बस के लिए किया है एक बात की जांच, कि n है। और तो आप की तरह कर रहे हैं दोनों एक साथ गुणा। आपको लगता है कि अंतिम मिल गया है तो ऐसा है n का एक प्रवेश के साथ यहाँ नीचे N के लिए जाँच यहाँ। और आप गुणा यदि उन्हें, कि n लॉग एन रहा है। 

और इसलिए सबसे अच्छा मामले और सबसे खराब मामला है और सभी n लॉग एन रहे हैं उम्मीद है। यह एक और प्रकार की तरह भी है। यह चयन प्रकार की तरह है यह इस अर्थ में कि क्या कोई फर्क नहीं पड़ता अपने सूची में यह सिर्फ जा रहा है, है एक ही बात हर बार ऐसा करने के लिए। ठीक। भले ही, तुम लोगों को देख सकते हैं हम n through-- चला गया है कि प्रकार चुकता, यह बहुत ही कुशल नहीं है। और यहां तक ​​कि इस n लॉग n है सबसे कुशल नहीं। तुम लोगों को उत्सुक हैं, क्रमबद्ध तंत्र नहीं है, वे कर रहे हैं कि इतने कुशल हैं कि लगभग अनिवार्य रूप से फ्लैट क्रम में। 

आप कुछ लॉग एन के मिल गया है। आप कुछ लॉग लॉग एन के मिल गया है। हम उन पर नहीं टिकते अभी इस वर्ग में। लेकिन तुम लोगों को उत्सुक हैं, क्या है, गूगल के लिए स्वतंत्र महसूस सबसे कुशल छँटाई तंत्र। मैं देखते हैं, पता नहीं वास्तव में कुछ अजीब लोगों, like-- वास्तव में कुछ भी नहीं है लोगों को करना है कि अजीब वाले। और अगर आप आश्चर्य है कि कैसे वे कभी इस बारे में सोचा। आप कुछ खाली है, तो गूगल समय पर, कुछ अजीब तरीके क्या हैं उस के रूप में अच्छी तरह से people-- कुशल ways-- लोग एक तरह से लागू करने में सक्षम है। ठीक। और यहाँ सिर्फ एक आसान सा चार्ट है। मुझे लगता है कि प्रश्नोत्तरी 0 से पहले, आप सभी को पता है अपने कमरे में शायद कोशिश कर रहा होगा कि याद करने के लिए। तो यह है कि आप लोगों के लिए वहाँ में अच्छा है। बस made-- कि तर्क मत भूलना क्यों उन लोगों की संख्या उत्पन्न थे। आप हमेशा खो रहे हैं, सिर्फ बनाने सुनिश्चित करें कि आप एक तरह क्या कर रहे हैं पता है। और आप के माध्यम से चला सकते हैं उन्हें अपने मन में क्यों उन बाहर निकालने के लिए जवाब उन जवाब हैं। 

ठीक है। तो हम स्थानांतरित करने के लिए जा रहे हैं अंत में, खोज करने के लिए, पर। क्योंकि आप उन लोगों के रूप में कौन pset में पढ़ा है, खोज भी का हिस्सा है इस सप्ताह की समस्या सेट। आप को लागू करने के लिए कहा जाएगा खोजों के दो प्रकार के। एक एक रैखिक खोज है और एक एक द्विआधारी खोज है। 

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

फोन की किताब उदाहरण याद रखें वह ऊपर लाने रहता है कि, वह एक तरह से संघर्ष किया है कि एक यह पिछले वर्ष पर एक सा है, आप आधे में समस्या विभाजित जहां, छमाही में, आधे में, फिर और फिर, आप के लिए क्या देख रहे हैं लगता है जब तक? और अगर तुम मिल गया है साथ ही साथ इस बात का क्रम। और आप देख सकते हैं, यह है काफी अधिक कुशल खोज के किसी भी अन्य प्रकार की तुलना में। 

इसलिए हम के बारे में जाना होगा कि रास्ता एक द्विआधारी खोज लागू है, हम एक सरणी था, सूचकांक 0-6, सात तत्वों, हम right--, बीच में देख सकते हैं क्षमा करें, हमारे सवाल है, तो first-- हम से सवाल पूछना चाहते हैं, तो करता है सरणी, 7 के तत्व शामिल जाहिर है, मनुष्य जा रहा है, और कर रहे एक छोटा सा सरणी ऐसी है, यह हमारे लिए आसान है हाँ कहने के लिए। लेकिन जिस तरह से एक द्विआधारी को लागू करने के लिए खोज बीच में देखने के लिए होगा। 

हम सूचकांक 3 पता है कि मध्य, क्योंकि हम सात तत्व हैं पता है। क्या 7 2 से विभाजित? आप अतिरिक्त 1 कि काट कर सकते हैं। आप बीच में 3 मिल गया है। तो 7 के बराबर 3 की सरणी है? यह सही नहीं है? लेकिन हम जाँच के एक जोड़े को कर सकते हैं। 3 कम से कम 7 या की सरणी है 7 से अधिक 3 की सरणी है? 

और हम इसे कम से कम 7 है कि पता है। इसलिए हम जानते हैं कि ओह, यह करना चाहिए कि बाईं आधे में नहीं हो। हम यह होना चाहिए कि पता ठीक आधे में, है ना? तो हम बस आधे सरणी काट सकते हैं। हम भी करने की जरूरत नहीं है अब इसे देखो। हम जानते हैं कि क्योंकि हमारे problem-- के आधे हम जवाब में पता चला है कि हमारी समस्या का सही आधा। तो हम बस अब कि देखो। 

तो अब हम को देखने क्या बचा है के बीच। यही कारण है कि सूचकांक 5। हम फिर से एक ही जांच करते हैं और हम इसे छोटा है कि देखते हैं। तो हम उस के बाईं ओर देखो। और फिर हम उस चेक को देखते हैं। सरणी मूल्य पर है 7 के बराबर सूचकांक 4? यह हे। इसलिए हम सच वापसी क्योंकि सकते हैं हम हमारी सूची में मूल्य पाया। मैं के माध्यम से चला गया रास्ता करता है हर किसी के लिए है कि मतलब? ठीक। मैं जैसे, शायद आप लोग दे दूँगा तीन, चार मिनट के बाहर निकालने के लिए कैसे इस pseudocode करने के लिए। 

तो मैं एक लिखने के लिए कहा की कल्पना लौट आया है कि समारोह में बुलाया खोज () एक मूल्य, एक बूलियन मान, कि, की तरह सच था या false-- आप अगर मिल सच मूल्य, तुम नहीं किया है, तो गलत। और फिर तुम थे मूल्य में पारित आप मूल्यों में देख रहे थे जो array-- ओह, मैं निश्चित रूप से डाल दिया है गलत जगह में है। ठीक। वैसे भी, कि होना चाहिए मूल्यों का सही करने के लिए किया गया। और फिर पूर्णांक n संख्या है उस सरणी में तत्वों की। कैसे आप की कोशिश कर के बारे में जाना होगा में समस्या यह है कि pseudocode करने के लिए? मैं तुम जैसे लोगों को दे देंगे तीन मिनट है कि क्या करना है। नहीं, मैं only-- लगता है कि वहाँ हाँ, सही यहाँ वहाँ एक है। दर्शकों: मैं कर सकता हूँ? ANDI PENG: हाँ, मैं तुम्हें मिल गया। कि काम कर रहा है? अच्छा ठीक है। 

ठीक। सभी अधिकार दोस्तों, हम कर रहे हैं में यह लगाम लगाने के लिए जा रहा है। ठीक। इसलिए हम इस सुंदर मिल गया है ग्रहण उस में एन मूल्यों के साथ थोड़ा सरणी। मैं लाइनों आकर्षित नहीं किया। लेकिन हम के बारे में कैसे जाना होगा यह लिखने के लिए कोशिश कर रहा? किसी को भी करना चाहते हैं मुझे पहली पंक्ति दे? तुम मुझे देना चाहते हैं इस स्यूडोकोड की पहली पंक्ति। 

दर्शकों: [अश्राव्य] दर्शकों: आप चाहते हैं चाहते हैं through-- पुनरावृति करने के लिए दर्शकों: बस एक और पाश के लिए? दर्शकों: --FOr। 

ANDI PENG: तो यह एक थोड़ा मुश्किल है। आप चाहते हैं about-- सोचो इस लूप चालू रखने के लिए पर और फिर जब तक? 

दर्शकों: [अश्राव्य] तक मूल्य कि मूल्य के बराबर है। ANDI PENG: बिल्कुल। तो अगर आप वास्तव में सिर्फ write-- कर सकते हैं हम इसे और भी अधिक सरल कर सकते हैं। हम सिर्फ सही, थोड़ी देर के पाश कर सकते हैं? तो तुम सिर्फ loop-- हो सकता है हम यह एक समय है कि पता है। लेकिन अभी के लिए, मैं जा रहा हूँ क्या माध्यम से - "पाश" कहने के लिए? लूप क्या है until-- हमारे समाप्त होने की हालत? मैं इसके बारे में सुना लगता है। मैं किसी को यह कहते सुना। 

दर्शकों: मान बीच बराबर होती है। ANDI PENG: फिर से कहो। जब तक या,: दर्शकों मूल्य आप खोज रहे हैं के लिए मध्य मूल्य के बराबर है। 

ANDI PENG: यह वहाँ में नहीं है तो क्या होगा? क्या होगा यदि आप खोज रहे हैं मूल्य के लिए इस सरणी में वास्तव में नहीं है? दर्शकों: आप एक वापसी। 

ANDI PENG: लेकिन हम करने के लिए क्या करना चाहते हैं हम एक शर्त है, तो जब तक पाश? हाँ। 

दर्शकों: केवल एक ही मूल्य जब तक वहाँ? ANDI PENG: तुम पाश until-- तो क्या आप कर रहे हैं पता ठीक है, एक अधिकतम मूल्य के लिए जा रहे हैं? और आप जा रहे हैं कि पता सही एक न्यूनतम मूल्य है, करने के लिए? इसके अलावा, कुछ है कि क्योंकि मैंने पहले कहना भूल गया है कि कुछ है कि द्विआधारी खोज के बारे में महत्वपूर्ण अपने सरणी पहले से ही हल है कि है। ऐसा करने का कोई तरीका नहीं है क्योंकि यह है कि वे सिर्फ यादृच्छिक मूल्यों कर रहे हैं। एक अगर तुम नहीं जानते अन्य की तुलना में बड़ा है, है ना? 

तो तुम्हें पता है कि अपने अधिकतम और अपने मिनट ठीक है, यहाँ कर रहे हैं? आप को एडजस्ट करने के लिए जा रहे हैं अपने मिनट और mid-- में अपने अधिकतम चलो बस कल्पना करते हैं अपने मध्य मूल्य सही here-- है आप मूल रूप से करने के लिए जा रहे हैं पाश अपने न्यूनतम है, जब तक ठीक है, अपने अधिकतम के रूप में एक ही है, या के बारे में अपने अधिकतम अपने न्यूनतम के रूप में ही नहीं है। है ना? जब ऐसा होता है, क्योंकि आप जानते हैं कि आप अंततः एक ही मूल्य मारा है। तो अगर आप अपने मिनट तक लूप करना चाहते हैं , कम से कम या उफ़ बराबर है नहीं करने के लिए या बराबर कम, अधिकतम around-- अन्य तरीका है। 

वह समझ में आया था? मुझे लगता है कि अधिकार पाने के लिए कुछ कोशिश करता है ले लिया। लेकिन पाश अपने अधिकतम मूल्य तक अनिवार्य रूप से लगभग कम है से या अपने न्यूनतम करने के लिए बराबर है, है ना? क्या आप जानते हैं कि जब आप जुटे किया है। दर्शकों: जब होगा आपके अधिकतम मूल्य न्यूनतम से भी कम हो सकता है? ANDI PENG: आप रखने के लिए , यह समायोजन जो हम जा रहे हैं इस में क्या कर रही हो। समझ आया? न्यूनतम और अधिकतम बस रहे हैं हम शायद रहे हैं कि पूर्णांकों चाहते करने के लिए जा रहा रखने के लिए बनाने के लिए हम देख रहे हैं, जहां का ट्रैक। सरणी मौजूद है, क्योंकि भले ही हम क्या कर रहे हैं। की तरह, हम वास्तव में शारीरिक रूप से नहीं कर रहे हैं ठीक है, सरणी से काट रही? हम सिर्फ समायोजन कर रहे हैं जहां हम देख रहे हैं। समझ आया? 

दर्शकों: हाँ। 

ANDI PENG: ठीक है। कि हमारे पाश के लिए शर्त है तो, हम इस लूप के अंदर क्या चाहते हो? हम क्या करना चाहते हो जा रहे हैं? इसलिए अभी, हमें मिल गया है एक अधिकतम और एक मिनट, ठीक है, शायद यहीं कहीं ऊपर बनाया। हम शायद चाहते करने के लिए जा रहे हैं सही एक मध्यम, खोजने के लिए? हम कैसे होने जा रहे हैं बीच खोजने के लिए सक्षम? Mathematical-- क्या है दर्शकों: मैक्स प्लस 2 से विभाजित मिनट। ANDI PENG: बिल्कुल। समझ आया? और तुम लोग क्यों हम देख रहे हो हम ऐसा क्यों सिर्फ use-- नहीं किया बजाय करने का सिर्फ 2 n से विभाजित? N एक मूल्य है, क्योंकि यह है कि एक ही रहने के लिए जा रहा है। है ना? लेकिन हम अपने न्यूनतम समायोजित के रूप में और अधिकतम मान, वे बदलने जा रहे हैं। और एक परिणाम के रूप में, हमारे बीच भी बदलने जा रहा है। हम चाहते हैं तो यही कारण है यहाँ यह सही करने के लिए। ठीक। 

और फिर, कि अब हम हाँ our-- पाया है। 

दर्शकों: बस एक त्वरित question-- जब आप न्यूनतम और अधिकतम कहते हैं, हम मान रहे हैं कि यह पहले से ही हल है? 

ANDI PENG: हाँ, यह वास्तव में एक एक द्विआधारी खोज के लिए पूर्व शर्त, आपको लगता है कि यह हल है पता करने के लिए। क्यों तरह है, जो आप में लिखने के अपने समस्या अपने द्विआधारी खोज से पहले निर्धारित किया है। ठीक। तो अब हम जहां हमारे मध्यबिंदु पता है कि क्या आप यहाँ क्या करना चाहते हो रहा है? 

दर्शकों: हम तुलना करना चाहते हैं एक दूसरे के लिए है। ANDI PENG: बिल्कुल। तो अगर आप की तुलना करने के लिए जा रहे हैं मूल्य के मध्य, है ना? और कहा कि क्या बता करता है हमें हम तुलना कब? क्या हम बाद में क्या करना चाहते हैं? 

दर्शकों: मूल्य बड़ा है मध्य से, हम इसे बंद कटौती करना चाहते हैं। ANDI PENG: बिल्कुल। मूल्य बड़ा है तो अगर मध्य से, हम कर रहे हैं इन बदलने के लिए चाहते हो जा न्यूनतम और maxes, है ना? क्या हम बदलना चाहते हैं? हम जानते हैं कि मूल्य कहीं है यहाँ में, हम बदलने के लिए आप क्या करते हैं? हम अपने को बदलना चाहते हैं न्यूनतम सही, मध्य हो सकता है? और तो और, यह इस में है आधा है, क्या हम बदलना चाहते हैं? 

दर्शकों: आपका अधिकतम। ANDI PENG: हाँ। और फिर आप बस जा रहे हैं , सही पाशन रखने के लिए? क्योंकि अब, एक यात्रा के बाद के माध्यम से, आप यहाँ एक अधिकतम मिल गया है। और फिर आप एक मध्य पुनर्गणना कर सकते हैं। और फिर आप तुलना कर सकते हैं। और तुम जा रहा रखने के लिए जा रहे हैं मिनट और maxes तक अनिवार्य रूप से जुटे हैं। आप जानते हैं कि और है कि जब आप इसे के अंत मारा है। और या तो आप यह पाया है या तुम उस बिंदु पर नहीं है। 

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

तो यह पहली बार है एक pset जहां में समय कहा जाता है कि हम क्या तुम लोगों को दे सकता हूँ वितरण कोड, कोड है, जो हम पूर्व लिखा है कि, लेकिन बस से कुछ टुकड़े छोड़ दिया के लिए आप लिखने को समाप्त करने के लिए। आप इस पर जब देखो तुम लोग तो कोड, आप सच में डर हो सकता है। आप, आह, मैं बस की तरह कर रहे हैं कि क्या कर रहा है पता नहीं है, मैं की तरह, लगता है कि पता नहीं है, इतना जटिल, आह, आराम करो। यह ठीक है। कल्पना पढ़ें। कल्पना वास्तव में आप के लिए समझाना होगा इन सभी कार्यक्रमों के लिए क्या कर रहे हैं। 

उदाहरण के लिए, generate.c एक कार्यक्रम है कि अपने pset के साथ आ जाएगा। आप वास्तव में इसे छूने की जरूरत नहीं है, लेकिन आप यह क्या कर रहा है समझना चाहिए। और generate.c, यह कर रहा है सब है या तो यादृच्छिक संख्या पैदा या आप एक तरह, यह एक बीज दे सकते हैं लगता है कि यह योजनाबद्ध संख्या, और इसे और अधिक संख्या उत्पन्न करता है। तो एक विशिष्ट तरीके से करने के लिए नहीं है, generate.c लागू जिसमें तुम सिर्फ संख्या का एक गुच्छा बना सकते हैं आप अपने अन्य तरीकों पर परीक्षण करने के लिए। 

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

और फिर आप अनिवार्य रूप से करने के लिए जा रहे हैं बस उन्हें एक साथ सभी डाल दिया। कैसे करने के लिए कल्पना आपको बता देगा कमांड लाइन पर डाल दिया है कि। और तुम क्या परीक्षण करने में सक्षम हो जाएगा या नहीं अपने प्रकार और खोज कर रहे हैं। कूल। किसी को भी पहले से ही शुरू कर दिया है और आई समस्याओं या सवाल वे इस के साथ अब ठीक है? ठीक। 

दर्शकों: रुको। मेरा एक सवाल है। 

ANDI PENG: हाँ। 

दर्शकों: तो मैं शुरू कर रही है helpers.c में रैखिक खोज और यह वास्तव में काम नहीं कर रहा था। लेकिन फिर बाद में, मुझे लगता है हम अभी पता चला इसे हटा दें और द्विआधारी खोज करना है। यह काम नहीं करता है तो यह फर्क पड़ता है? 

ANDI PENG: संक्षिप्त जवाब नहीं है। लेकिन जब से हम not-- रहे दर्शकों: लेकिन कोई नहीं है वास्तव में जाँच। ANDI PENG: हम कभी नहीं कर रहे देखना है कि जा रही है। लेकिन आप शायद बनाना चाहते सुनिश्चित करें कि आपकी खोज कर रही है। अपने रैखिक क्योंकि अगर खोज काम नहीं करता है, तो संभावना है कि अपने द्विआधारी हैं खोज के रूप में अच्छी तरह से काम करने के लिए नहीं जा रहा है। आप इसी तरह की है, क्योंकि उन दोनों में तर्क। और नहीं, यह वास्तव में कोई फर्क नहीं है। तो केवल लोगों को आप बदल देंगे में क्रमबद्ध और द्विआधारी खोज कर रहे हैं। हाँ। 

और यह भी, बच्चों की एक बहुत थे helpers.c संकलन करने के लिए कोशिश कर रहा है। आप वास्तव में अनुमति नहीं कर रहे करना है कि, helpers.c क्योंकि लिए एक मुख्य समारोह में नहीं है। और इसलिए तुम ही चाहिए वास्तव में संकलन हो कॉल लगता है क्योंकि, पैदा करते हैं और मिल helpers.c और यह के भीतर काम करता है। कि डिबगिंग बनाता है तो बट में एक दर्द। लेकिन यह है कि हमें क्या करना है क्या है। दर्शकों: तुम सिर्फ सही, सब बनाते हैं? ANDI PENG: तुम सिर्फ कर सकते हैं हाँ, के रूप में अच्छी तरह से सभी करते हैं। ठीक। तो यह है कि क्या करने के मामले में यह बात है pset आप सब करने के लिए पूछ रहा है। आप किसी भी प्रश्न हैं, तो लग रहा है अनुभाग के बाद मुझे पूछने के लिए स्वतंत्र। मैं 20 मिनट, जैसे, के लिए यहाँ हो जाएगा। 

और हाँ, pset की सच है कि बुरा नहीं। तुम लोग ठीक किया जाना चाहिए। ये सिर्फ दिशा-निर्देशों का पालन करें। एक तरह से तार्किक रूप से, की भावना है, क्या चाहिए हो रहा हो और तुम ठीक हो जाओगे। भी डरो मत। कोड का एक बहुत कुछ है वहां पहले से ही लिखा है। अगर तुम नहीं भी डरो मत है कि सभी को इसका क्या मतलब समझते हैं। यह एक बहुत कुछ है, तो यह पूरी तरह से ठीक है। और कार्यालय समय के लिए आते हैं। हम आपको एक बार देख लेने में मदद करेंगे। 

दर्शकों: अतिरिक्त के साथ काम करता है, हम उन लोगों को देखने के लिए? 

ANDI PENG: हाँ, उन कोड में हैं। 15 का खेल है, आधे से में यह पहले से ही आप के लिए लिखा है। तो उन कार्य कर रहे हैं पहले से ही कोड में। हाँ। ठीक है। खैर, बेस्ट ऑफ लक। यह एक घृणित दिन है। इसलिए उम्मीद है कि आप लोगों को भी नहीं लग रहा है अंदर रह रही है और कोडिंग के बारे में बुरा नहीं है।