अध्यक्ष 1: हे सब लोग! अनुभाग के लिए वापस स्वागत है. यहाँ आप दोनों के इतने देखकर बहुत खुशी है, और ऑनलाइन देख रहा है जो हर किसी के. तो, हमेशा की तरह स्वागत के रूप में वापस. मैं आप सभी को एक प्यारा था कि आशा बाकी का पूरा सप्ताह के अंत में, विश्राम. यह कल बाहर सुंदर था. तो, मैं तुम्हें सड़क पर मजा उम्मीद है. घोषणाओं की एक जोड़ी तो पहले. ग्रेडिंग. तो, आप में से अधिकांश मिल जाना चाहिए एक अपने स्क्रैच Pset बारे में मुझ से ईमेल, साथ ही साथ Pset 1 के लिए ग्रेडिंग. तो, बस एक दो बातें. Style50 में check50 उपयोग सुनिश्चित करें. इन के लिए होती हैं आप लोगों के लिए संसाधन, तुम हो रही है कि बनाना आप कर सकते हैं के रूप में कई अंक बेवजह उन्हें खोने के बिना. तो, शैली की तरह बातें बहुत महत्वपूर्ण हैं. हम इसके लिए दूर ले जा रहे हैं. आप में से कुछ पहले से ही हो सकता है अपने Pset से देखा. और check50 सिर्फ एक है बनाना बहुत आसान तरीका हम वास्तव में लौट रहे हैं कि क्या उपयोगकर्ता को लौट जाने की जरूरत है, और कहा कि सब कुछ ठीक से काम कर रहा है. दूसरे नोट पर, सुनिश्चित करें कि आपके सही फ़ोल्डर में चीजों को अपलोड. यह मेरे जीवन में सिर्फ एक बनाता है थोड़ा और अधिक मुश्किल आप Pset 1 में Pset 2 अपलोड अगर मैं चीजों को डाउनलोड करते हैं, क्योंकि वे सही ढंग से डाउनलोड नहीं करते. और मैं इसे एक छोटे से wonky है पता एक प्रणाली में करने के लिए इस्तेमाल किया हो, लेकिन सिर्फ सुपर हो सावधान, केवल मेरे लिए अगर, इतना है कि आप ईमेल हो रही है जब तरह 2 बजे और मैं ग्रेडिंग हूँ. यदि नहीं, तो मैं देखने के लिए कारण चारों ओर अपने Pset के लिए. कूल. मैं यह जल्दी है, लेकिन मैं पूरी तरह से गार्ड से लिया गया इस शुक्रवार कारण है कि एक निबंध, कि द्वारा मेरे प्रोफेसरों अरे हाँ, बस की तरह थे. याद रखें, आप एक है शुक्रवार को कारण निबंध. तो, मैं कोई नहीं पसंद करता है पता midterms के बारे में सोचने के लिए, लेकिन अपनी पहली प्रश्नोत्तरी, 15 अक्टूबर पर है अक्तूबर में इस सप्ताह शुरू हो रहा है. इसलिए, यह जितनी जल्दी हो सकता है आप से अधिक की उम्मीद है. तुम इतनी है कि गार्ड जब दूर फेंका नहीं रहे मैं, ओह कि अगले सप्ताह के खंड उल्लेख अपने प्रश्नोत्तरी अगले सप्ताह, मैंने सोचा था मैं जितना अधिक आप एक छोटा सा देना चाहते हैं अब एक को सिर की. तो, आपकी समस्या सेट, तीन नंबर. लोगों को पढ़ा है कैसे जिज्ञासा से बाहर कल्पना? ठीक. हम एक जोड़े को मिल गया. नीचे की तरह पिछले से कि लेकिन सप्ताह ठीक है. मैं यह सुंदर बाहर था. तो बाहर तोड़. निश्चित रूप से आप कर पाने के बाद आज कम से कम अपनी कल्पना पढ़ा डाउनलोड करने की तरह कोशिश वितरण कोड और चल रहा है पहले प्रारंभिक तरह वे करने के लिए आप से पूछना है कि बात. हम प्रयोग कर रहे हैं क्योंकि वितरण कोड और एक पुस्तकालय हम केवल --It ही है using-- गया है कि हम इस Pset किया है दूसरी बार, पागल बातें हो सकता है अपने उपकरणों के साथ, और आप को लगता है कि करना चाहते हैं बाहर अब बाद बनाम. यह गुरुवार की रात है या अगर यह बात है क्योंकि बुधवार की रात और किसी कारण के लिए अपने उपकरण अभी नहीं करता पुस्तकालय के साथ चलाना चाहते हैं या वितरण के साथ कोड, इसका मतलब है आप भी कोडिंग कर रही शुरू नहीं कर सकते हैं. आप की जाँच नहीं कर सकते हैं क्योंकि अगर यह काम करता है देखने के लिए. आपका नहीं करने वाले सक्षम हो यह compiles देखने के लिए यदि. आप जल्दी में उन का ख्याल रखना चाहते हैं सप्ताह, तुम अब भी मुझे ईमेल कर सकते हैं जब या अन्य TFS में से एक, और हम तय उन प्राप्त कर सकते हैं. क्योंकि उन मुद्दों कर रहे हैं कि आप को रोकने के लिए जा रहे हैं किसी भी वास्तविक प्रगति कर से. यह कि, एक बग की तरह नहीं है आप बस की तरह पर छोड़ सकते हैं. आप के साथ मुद्दों कर रहे हैं, तो आपके उपकरण या वितरण कोड, आप वास्तव में उस लिया करना चाहते हैं जल्दी बल्कि बाद में की परवाह है. तो भी आप वास्तव वाला नहीं कर रहे हैं कोडन शुरू, वितरण डाउनलोड कोड, कल्पना पढ़ा, बनाना सब कुछ वहाँ काम कर रहा है. ठीक है? आप कर सकते हैं बस, तो मैं आसान हो जाएगा अपने जीवन वादा करता हूँ. और तो आप शायद जा रहे हैं सही अब इसे ठीक करने के लिए? ठीक. तो, वहाँ कोई सवाल? किसी भी रसद बातें? हर कोई अच्छा है? ठीक. उन लोगों के लिए अस्वीकरण आप कमरे में और ऑनलाइन. मैं स्विच करने के लिए कोशिश कर रहा हो जा रहा हूँ उपकरण में PowerPoint के बीच हम जा रहे हैं क्योंकि कुछ कोडिंग कर रही हो गुमनाम की लोकप्रिय मांग से आज सुझाव सर्वेक्षण मैं पिछले हफ्ते बाहर भेजा. तो, हम कुछ कोडिंग कर रही हो जाएगा. तो, तुम लोग भी चाहते हैं अपने उपकरणों को आग, और आप एक ईमेल मिला है चाहिए एक नमूना फाइल के साथ, मुझ से. ऐसा करने के लिए स्वतंत्र. तो, हम इस बारे में बात करने जा रहे हैं एक डीबगर है जो GDB,. यह आप में मदद करने के लिए जा रहा है एक तरह से यह पता लगाने जहां बातें अपने कोड में गलत जा रहे हैं. यह वास्तव में आप कदम करने के लिए सिर्फ एक रास्ता है अपने कोड के माध्यम से यह हो रहा है के रूप में, और चर बाहर मुद्रित करने में सक्षम हो या वास्तव में क्या हो रहा है देखते हैं डाकू अपने कार्यक्रम छंद के तहत अभी चल रहा है, यह दोषयुक्त की तरह है, और तुम, कोई विचार पसंद कर रहे हैं क्या सिर्फ यहाँ हुआ. मैं इस पर विफल रही है क्या लाइन में पता नहीं है. यह गलत हो गया था, जहां मैं नहीं जानता. तो, GDB उस के साथ मदद करने जा रहा है. इसके अलावा, आप के लिए तय है हाँ जारी है, और 61 ले, यह वास्तव में, वास्तव में हो जाएगा आपके सबसे अच्छा दोस्त है, मैं आपको बता सकता है कारण मुझे लगता है कि वर्ग के माध्यम से जा रहा हूँ क्योंकि. हम द्विआधारी को देखने के लिए जा रहे हैं खोज, तुम लोगों को याद है जो महान फोन की किताब उदाहरण वर्ग से तमाशा. हम चाहते हैं कि लागू करने, और हो जाएगा एक छोटा सा और उस के माध्यम से चलने, और फिर हम चार के माध्यम से जा रहे हैं बुलबुला हैं जो विभिन्न प्रकार, चुनाव में, निवेशन, और मिलाएं. कूल. तो, मैंने उल्लेख किया GDB के रूप में, एक डीबगर है. और इन बड़े की तरह कर रहे हैं चीजें, बड़े कार्यों या आदेशों आप GDB के भीतर उपयोग, और मैं चलना होगा कि आप एक दूसरे में इसका एक डेमो के माध्यम से. तो, यह बस नहीं है सार रहने वाला. मैं कोशिश करते हैं और ठोस रूप में यह कर दूँगा आप लोगों के लिए संभव के रूप में. तो, टूट गया. यह या तो तोड़ हो जाएगा जैसे, कुछ संख्या, जो अपने कार्यक्रम में एक लाइन का प्रतिनिधित्व करता है या आप एक समारोह नाम कर सकते हैं. तो, आप मुख्य तोड़ने का कहना है अगर, यह मुख्य में बंद हो जाएगा और आपको लगता है कि समारोह के माध्यम से चलते हैं. इसी तरह, आप कुछ बाहरी है अगर स्वैप या घन की तरह कार्य, हम पिछले हफ्ते में देखा कि. आप उन लोगों में से एक को तोड़ने का कहना है, अपने कार्यक्रम हिट जब भी, कि यह करने के लिए आप के लिए इंतजार करेंगे क्या करना है यह बताओ. यह सिर्फ तुम इतने पर अमल से पहले वास्तव में समारोह के अंदर कदम सकता है और क्या हो रहा है देखते हैं. तो, अगली बस पर रुक जाती है अगली पंक्ति, कार्य खत्म हो जाता है. चरण. ये सभी छोटे सार हैं. तो, मैं तो बस उन के माध्यम से चलाने के लिए जा रहा हूँ, लेकिन आप एक दूसरे में उपयोग में उन्हें देखेंगे. एक समारोह में कदम. तो जैसा कि मैं कह रहा था, स्वैप के साथ, यह होगा की तरह आप वास्तव में आप कर रहे हैं के रूप में अगर की अनुमति जैसे शारीरिक रूप से अंदर घुसने, उन चर के साथ आप कर सकते हैं गंदगी, प्रिंट वे क्या कर रहे हैं, पर क्या हो रहा है देखते हैं. सूची सचमुच सिर्फ प्रिंट होगा आसपास के कोड बाहर. तो, आप की तरह भूल जाते हैं आप अपने प्रोग्राम में हैं, जहां या आप सोच रहे हैं क्या, यह चारों ओर हो रहा है यह सिर्फ एक खंड बाहर प्रिंट होगा की यह चारों ओर पाँच या छह लाइनों की तरह. तो, आप उन्मुख हो सकते हैं तुम कहाँ के बारे में. कुछ चर प्रिंट. तो, आप चाबी की तरह है अगर सीज़र में, हम में देख लेंगे कि. आप किसी भी बिंदु पर छापा कुंजी कह सकते हैं. मूल्य इतना है कि क्या यह आपको बताता हूँ कि, शायद कहीं रास्ते, आप अपने प्रमुख अधिलेखित कर दिया. आप वास्तव में क्योंकि बता सकते हैं कि आप वास्तव में है कि मूल्य का निरीक्षण कर सकते हैं. स्थानीय लोगों, सिर्फ प्रिंट में अपने स्थानीय चर बाहर. तो, जब भी आप एक पाश के भीतर कर रहे हैं, और आप सिर्फ ओह, जैसे देखना चाहते हैं. मेरे मैं क्या है? इस महत्वपूर्ण मूल्य क्या है मैं यहाँ इनिशियलाइज़ कि? इस बिंदु पर संदेश क्या है? यह सिर्फ सभी प्रिंट होगा उन की, तो आपको लगता है कि व्यक्तिगत रूप से करने की जरूरत नहीं है छापा मैं प्रिंट संदेश, कहते हैं. छापा की चाबी. और फिर प्रदर्शित करें. क्या करता है कि आप के रूप में है कार्यक्रम के माध्यम से कदम, यह सिर्फ यह है कि सुनिश्चित करेंगे कुछ कुछ चर प्रदर्शित हर बिंदु पर. इतनी है कि आप --it है also-- एक शॉर्टकट जहां की तरह आप ओह, जैसे जा रहा रखने की जरूरत नहीं है. छापा कुंजी या प्रिंट आई यह बस यह तुम्हारे लिए क्या स्वतः जाएगा. तो, उस के साथ, हम जा रहे हैं इस चला जाता है देखने के लिए कैसे. मैं कोशिश करते हैं और स्विच करने के लिए जा रहा हूँ मेरे उपकरण के लिए खत्म हो. मैं यह कर सकते हैं देखें. सभी. हम सिर्फ यह दर्पण जा रहे हैं. पागल कुछ भी नहीं है अपने लैपटॉप पर वैसे भी. ठीक. यह इस एक होने की जरूरत है. यह इतनी छोटी है. हम ऐसा कर सकते हैं तो चलो देखते हैं. ठीक. ऐलिस जाहिर संघर्ष कर रही है यहां सिर्फ एक छोटा सा, लेकिन हम एक momento में यह मिल जाएगा. ठीक. हम सिर्फ इस वृद्धि करने जा रहे हैं. ठीक. हर किसी तरह की है कि देख सकते हैं? शायद एक छोटा सा? मैं इसे एक छोटे से छोटा है पता है. आप काफी समझ नहीं कर सकते यह बड़ा बनाने के लिए. अगर कोई जानता है. किसी को भी यह बड़ा बनाने के लिए कैसे पता है? ठीक. हम इसके साथ रोल करने के लिए जा रहे हैं. यह सिर्फ इसलिए है क्योंकि वैसे भी कोई बात नहीं कि कि तुम लोगों को चाहिए कोड है है. क्या अधिक महत्वपूर्ण है यहां टर्मिनल है. और हम क्यों यह इतना छोटा है यहाँ है? सेटिंग्स. ओह. यह सच है कि आइक. यह कैसे है? वहाँ से बाहर. कि सभी के लिए बेहतर है? ठीक ,. कूल. आप एक सीएस में कर रहे हैं जब आप जानते हैं कक्षा तकनीकी कठिनाइयों the-- की तरह का हिस्सा हैं तो, चलो यह स्पष्ट करते हैं. ठीक. तो, यहीं अनुभाग में, जो हम यहाँ था. सीज़र एक निष्पादन योग्य फ़ाइल है. इसलिए मैं इसे बनाया है. तो, GDB के साथ महसूस करने के लिए एक बात है कि यह केवल निष्पादन योग्य फ़ाइलों पर काम करता है. तो, आप एक dotsy पर यह नहीं चल सकता. आप वास्तव में बनाने के लिए है अपने कोड संकलित यह सुनिश्चित करें कि, और यह वास्तव में चलाया जा सकता है. अगर यह नहीं है तो, सुनिश्चित करें कि संकलन, यह संकलन करने के लिए मिलता है, इतना है कि आप की तरह यह माध्यम से चला सकते हैं. तो, GDB शुरू करने के लिए, आप सभी करते हैं, ग्लोरिया प्रकार GDB, और फिर बस आप चाहते हैं कि फ़ाइल. मैं हमेशा सीज़र misspell. लेकिन आपको यह सुनिश्चित करना चाहते हैं यह एक निष्पादन के बाद से, तिवारी डॉट फ़्लैश इतना है कि आप जा रहे हैं इसका मतलब सीएसआई आप निष्पादित करने के लिए जा रहे हैं चलाने के लिए इस डिबगर के साथ या तो फाइलों. ठीक. तो, आपको लगता है कि, आप मिलता है अस्पष्ट के इस तरह के. यह डिबगर के बारे में अभी सब बातें है. तुम सच की जरूरत नहीं है इसके बारे में अभी चिंता. आप देखते हैं और, जैसा कि हम इस किया है खुले parens, सकल घरेलू उत्पाद, करीब parens, और बस की तरह की तरह लग रहा है हमारे कमांड लाइन, है ना? तो, हम do-- करने के लिए क्या चाहते हैं --So, पहली बात हम चयन करना चाहते है एक जगह इसे तोड़ने के लिए. तो, एक बग है इस सीजर कार्यक्रम में मुझे लगता है कि परिचय कि हम पता लगाने के लिए जा रहे हैं. यह इनपुट लेता है यह क्या करता है सभी टोपियां में Barfoo, और किसी कारण के लिए यह सिर्फ पत्ते ए परिवर्तन नहीं करता अकेले यह सही सब कुछ है लेकिन दूसरा पत्र एक अपरिवर्तित बनी हुई है. तो, हम कोशिश करने जा रहे हैं और यही वजह है कि यह पता लगाने. तो, पहली बात यह है कि आप आमतौर पर आप GDB पर शुरू जब भी करना चाहते हैं इसे तोड़ने के लिए जहां यह पता लगाने की है. तो सीज़र एक बहुत छोटी कार्यक्रम है. हम सिर्फ सही, एक समारोह है? सीज़र में हमारे कार्य क्या था? केवल एक ही समारोह, मुख्य अभी भी वहीं है? मुख्य एक समारोह है अपने सभी कार्यक्रमों के लिए. आप मुख्य नहीं था, तो मैं हो सकता है एक चिंतित थोड़ा सही अब हो सकता है, लेकिन मैं आप सब वहाँ में मुख्य था उम्मीद है. तो, हम क्या कर सकते हैं हम कर सकते है बस ऐसे ही, मुख्य टूट गया. इसलिए, यह ठीक है, कहते हैं. हम वहाँ हमारे ब्रेकपाइंट एक सेट. तो, याद करने के लिए अब बात सीज़र है एक कमांड लाइन तर्क सही लेता है और हम कहीं भी है कि अभी तक नहीं किया है. तो, आप क्या करते हैं जब है आप वास्तव में चलाने के लिए जाना कार्यक्रम, आप कर रहे हैं कि किसी भी कार्यक्रम GDB में चल रहा है कि कमांड लाइन की जरूरत तर्क, आप निवेश करने के लिए जा रहे हैं जब आप पहली बार इसे चलाने लगते हैं. इसलिए, इस मामले में, हम करते हैं तीन में से एक कुंजी के साथ भागो. और यह वास्तव में शुरू होगा. आप यहाँ देख तो, अगर हमारे पास आर सी 2 के बराबर नहीं है. तो आप लोग सब है अगर मैं ऊपर से बाहर भेज दिया कि उस फ़ाइल आपको लगता है कि तरह है कि देखेंगे पहली पंक्ति हमारे मुख्य समारोह, है ना? यह हम है देखने के लिए जाँच कर रहा है तर्कों की सही संख्या. तो, अगर आप सोच रहे आर सी सही है, आप बस प्रिंट आर सी की तरह कुछ कर सकते हैं. आर सी है, जो दो है हम सही होने की उम्मीद है क्या? तो, हम अगले जा सकते हैं, और के माध्यम से जारी है. तो, हम वहाँ कुछ महत्वपूर्ण है. और हम अपने कुंजी बाहर प्रिंट कर सकते हैं यह सही है बनाना. दिलचस्प है. काफी नहीं है कि हम क्या उम्मीद. तो, एक बात का एहसास करने के लिए भी GDB के साथ है, आप वास्तव में मारा जब तक यह नहीं है कि अगला, कि तुम सिर्फ देखा कि लाइन वास्तव में मार डाला है. इसलिए, इस मामले की चाबी में अभी तक आवंटित नहीं किया गया. तो, कुंजी कुछ कचरा मूल्य है तुम वहाँ तल पर देखते हैं. नकारात्मक $ 120-- --It के एक अरब और कुछ अजीब बातें सही? यह हम उम्मीद है कि कुंजी नहीं है. लेकिन हम उसके बाद मारा, और अगर हम कोशिश करते हैं और प्रिंट कुंजी, यह तीन है. हर कोई देखना है कि? तो, आप कुछ मिलता है आप की तरह कर रहे हैं, रुको. यह पूरी तरह से है गलत, और मैं नहीं जानता मैं सब चाहते हैं क्योंकि यह होगा कैसे एक नंबर आवंटित करना, एक चर, मुद्रण कोशिश, अगला मारने की कोशिश अगर यह काम करता है कि यह फिर से, और देखते हैं. यह केवल निष्पादित करने के लिए जा रहा है क्योंकि और वास्तव में आप के बाद कुछ आवंटित अगले मारा. हर कोई समझ बनाने के लिए? उह हुह? अध्यक्ष 2: जब आप यादृच्छिक संख्या कि क्या मतलब है? अध्यक्ष 1: यह सिर्फ यादृच्छिक है. यह सिर्फ कचरा है. यह सिर्फ कुछ है कि अपने कंप्यूटर बेतरतीब ढंग से आवंटित करेगा. कूल. तो, अब हम के माध्यम से कदम है, और इसलिए कर सकते हैं अब हम इस सादे पाठ GetString है. तो, मुझे सिर्फ परिचय क्या हम यहाँ अगले मारा जब कुछ नहीं होगा. हमारे GDB तरह से सही, गायब हो जाता है? यही GetString क्योंकि है अब निष्पादित कर रहा है, है ना? हमने देखा तो, जब सादे पाठ के बराबर होती है GetString, खुले parens और parens, और हम अगले मारा, कि है वास्तव में अब मार डाला. तो, इसके लिए इंतज़ार कर रहा है इनपुट कुछ करने के लिए हमें. तो, हम निवेश करने के लिए हमारे भोजन जा रहे हैं जो मैंने तुमसे कहा था के रूप में यह असफल साबित हुई है क्या है और कहा कि अभी यह कहना है कि बंद कि, क्रियान्वित समाप्त ब्रैकेट यह मतलब कि पाश से बाहर निकल. मैं हूँ तो, जैसा कि हम अब अगले मारा, और कर सकते हैं सुनिश्चित करें कि आप सीज़र से सभी परिचित हैं, ऐसा करने के लिए जा रहे इस पंक्ति क्या है, है. इंटरनैशनल मैं 0 के बराबर होती है के लिए है, एन के बराबर होती है Strlen, सादा पाठ, और उसके बाद मैं n, मैं, प्लस, प्लस से कम नहीं है. क्या करने जा इस लूप क्या है? अपने संदेश खोलें. कूल. तो, चलो कर रही है कि शुरू करते हैं. तो, इस हालत में होना चाहिए हमारे पहले एक के लिए, मैच? यह एक बी है, यह सादे पाठ आई हम है हमारे स्थानीय लोगों के बारे में जानकारी प्राप्त कर सकते हैं. तो, मैं शून्य है, और, छह अगर जो हम उम्मीद करते हैं, और हमारी प्रमुख तीन है. भावना करें कि सभी, सही? उन लोगों की संख्या सब कर रहे हैं वास्तव में वे क्या किया जाना चाहिए. तो, हम? अध्यक्ष 3: मेरे पास खदान के लिए यादृच्छिक संख्या. अध्यक्ष 1: ठीक है, हम --we check-- कर सकते हैं एक सेकंड में उस के बारे में बातचीत कर सकते हैं. लेकिन आप यह हो रही होना चाहिए. तो, हम एक पूंजी है अगर हमारे पहले एक के लिए बी, इस हालत ठीक है, इसे पकड़ने चाहिए? हम अगले मारा तो, अगर हम देखते हैं यदि यह वास्तव में कार्यान्वित कि. आप पीछा कर रहे हैं क्योंकि अगर अपने कोड में साथ, यहां इस लाइन, जहां सादे पाठ मैं इस गणित के साथ बदल जाता है, तभी तो कार्यान्वित हालत सही सही है? GDB केवल आपको दिखाने जा रही है वास्तव में क्रियान्वित कर रहे हैं कि चीजें. अगर यह शर्त पूरी नहीं की गई थी तो, अगर यह बात है बस अगली पंक्ति को छोड़ करने के लिए जा रहा है. ठीक है? इसलिए, हम कि है. इस ब्रैकेट यह मतलब अब उस लूप के बाहर बंद कर दिया. इसलिए, यह फिर से शुरू हो रहा है. बस ऐसे ही. तो, हम जानकारी प्राप्त कर सकते हैं हमारे यहाँ स्थानीय लोगों के बारे में, और हम अपने पहले देखते हैं कि पत्र, सही बदल गया है? यह होना चाहिए, क्योंकि यह अब एक ई है. तो, हम पर जारी रख सकते हैं. और हम इस चेक कर सकते है. और इस चेक, सही काम करना चाहिए? यह परिवर्तित किया जाना चाहिए ए है आगे तीन पत्र. लेकिन तुम, हम नोटिस कुछ अलग मिलता है. यहां इस मामले में तो, यह पकड़ा यह, और इसलिए इस लाइन, मार डाला हमारे बी संशोधित जो लेकिन, यहां इस मामले में, हम यह सिर्फ यह छोड़ दिया है कि, और [करने के लिए चला गया? एल Siff. ?] तो वहाँ कुछ हो रहा है. कि क्या है कि आप कह रही है है, हम यह यहाँ आकर्षित करना चाहिए कि पता लेकिन ऐसा नहीं है. किसी को भी देख सकते हैं जो हमारे समस्या यह है कि लाइन में है? यह एक बहुत मिनट बात है. और तुम भी अपने कोड पर लग सकता है. यह भी है कि यह क्या लाइन भूल जाते line-- है there-- में लेकिन यह [अश्राव्य] में है. हाँ? अध्यक्ष 4: यह अधिक से अधिक पर है पृष्ठ आप किताब में पढ़ा है. अध्यक्ष 1: बिल्कुल. तो, डिबगर नहीं बता सकता है आपको लगता है कि, लेकिन डिबगर एक लाइन के लिए आप नीचे मिल सकता है आप काम नहीं कर रहा है पता है कि. और कभी कभी, जब विशेष रूप से बाद में सेमेस्टर, जब में आप एक सौ, एक साथ काम कर रहे हैं कुछ सौ कोड की लाइनों, और आप यह असफल साबित हुई है जहां पता नहीं है, यह ऐसा करने का एक शानदार तरीका है. तो, हम हमारे बग मिला. आप अपने फाइल में यह तय कर सकते हैं और फिर आप इसे फिर से चला सकता है और सब कुछ पूरी तरह से काम करेगा. और सबसे बड़ी बात है इस ठीक है, की तरह लग सकता है. हाँ. कूल. आप के लिए देख रहे हैं क्या पता था. तो, आप क्या करना है पता था. GDB आप क्योंकि सुपर सहायक हो सकता है इन सब बातों को बाहर प्रिंट कर सकते हैं कि आप नहीं होगा. इसे और अधिक उपयोगी printf से है. आप में से कितने उपयोग की printf बयानों की तरह एक बग, सही था, जहां यह पता लगाने के लिए? तो, इस के साथ, तुम नहीं करते वापस जा रहा रखने के लिए है, और में टिप्पणी पसंद Printf, या, बाहर टिप्पणी और यह पता लगाने क्या आप मुद्रण किया जाना चाहिए. यह वास्तव में सिर्फ आपको अनुमति देता है , के माध्यम से कदम चीजें बाहर प्रिंट आप के माध्यम से जा रहे हैं, तो आप कर सकते हैं वे वास्तविक समय में परिवर्तन का पालन कैसे, अपने कार्यक्रम के रूप में चल रहा है. और यह एक छोटे ले करता है करने के लिए इस्तेमाल हो रही है की सा. मैं अत्यधिक बस तरह की सिफारिश करेंगे इसके साथ थोड़ा निराश किया जा रहा है अभी के लिए. आप पर एक घंटे खर्च करते हैं अगले सप्ताह कैसे GDB का उपयोग सीखने, आप अपने आप को बचाना होगा बाद में इतना समय. और सचमुच. हम बता यह लोगों के लिए हर साल, मैं लिया और जब मुझे याद है वर्ग, मुझे लगता है मैं ठीक हो जाएगा, जैसा था. नहीं. Pset 6 पर आया था और मैं था जैसे, मैं सीख रहा हूँ मैं नहीं है क्योंकि GDB का उपयोग कैसे करें यहाँ पर क्या हो रहा है. तुम इतना समय लगेगा तो अगर छोटे कार्यक्रमों पर इसका इस्तेमाल करते हैं आप हो जा रहे हैं कि काम करना पसंद है, पर काम की तरह कुछ के माध्यम से इस तरह Visionare,. आप अतिरिक्त अभ्यास चाहते हैं, तो मुझे यकीन है कि मैं छोटी गाड़ी कार्यक्रमों के साथ आ सकता है यदि आप चाहते हैं के लिए आप डिबग करने के लिए. लेकिन आप अभी कुछ समय लगेगा यदि पाने के लिए यह करने के लिए इस्तेमाल किया, बस के साथ खेलने के आसपास, यह वास्तव में अच्छी तरह से काम करेगा. और यह वास्तव में से एक है उन चीजों है कि आप बस कोशिश है, और अपने हाथ गंदे हो आप वास्तव में इसे समझ से पहले, के साथ. मैं वास्तव में केवल एक बार यह समझ में आ मैं इसके साथ डिबग बातें करना पड़ा और इसके बारे में एक विचार है बहुत अच्छे है कैसे जल्दी बल्कि बाद में डिबग करने के लिए. ठीक. कूल. मैं उस तरह की तरह है पता GDB में एक क्रैश कोर्स, और मैं निश्चित रूप से हो रही है पर काम करेंगे इन बड़ा अगली बार देखने के लिए. कूल. तो, हम वापस हमारे PowerPoint के लिए जाना है. इस काम चल रहा है? ए डब्ल्यु एच. हां. ठीक. तो, आप कभी किसी की जरूरत है उन फिर, सूची नहीं है. तो द्विआधारी खोज, जो हर कोई दाऊद के महान तमाशा याद रखता है आधे में फोन किताबें तेजस्वी. मैं वास्तव में नहीं मिलता अब फोन किताबें, आप जहां की तरह है क्योंकि इन दिनों फोन किताबें मिल? मैं वास्तव में नहीं पता है. द्विआधारी खोज. किसी को भी याद करता है कैसे द्विआधारी खोज काम करता है? किसी को भी सब पर? हाँ? अध्यक्ष 5: आप जब पता आप जो आधे पर देखने के लिए यह उस आधार पर, में होगा, और दूसरे आधे से छुटकारा. अध्यक्ष 1 बिल्कुल सही. तो, द्विआधारी खोज, इसके बारे में a-- तरह है --we यह विभाजन और जीत कॉल की तरह. तो, आप क्या करेंगे है आप बीच में देख लेंगे यह मैच यदि और आप देखेंगे क्या आप के लिए देख रहे हैं. यदि ऐसा नहीं होता है, तो आप करने की कोशिश यह पता लगाने, इसे छोड़ दिया जा रहा है आधा या सही आधा. आप देख रहे हैं तो, यह हो सकता है alphabetized है कि कुछ पर, आप ओह, देखें. एलीसन एम से पहले आया है? हां. तो, हम करने जा रहे हैं पहली छमाही में दिखेगा. या यह संख्या के साथ की तरह हो सकता है. कुछ भी है कि आप कर सकते हैं तुलना, इसे हल किया जा सकता है. आप पर द्विआधारी खोज का उपयोग कर सकते हैं. तो, किसी को भी यह याद ग्राफ या यह क्या है? यह Asymptotic जटिलता है. तो, यह ग्राफ बस कितनी देर का वर्णन करता है यह के रूप में एक समस्या को हल करने के लिए ले जाता है आप चीजों की संख्या में वृद्धि कि आप प्रयोग कर रहे हैं. तो, हम रैखिक समय है जो एन, है. थोड़ा है, जो दो से अधिक एन, तो बेहतर, अभी भी सुपर फास्ट होती है. और फिर हम जो, लॉगिन क्या हम द्विआधारी खोज पर विचार करें. हम देखते हैं, तो आपकी समस्या के रूप में , ज्यादा और ज्यादा बड़ा हो जाता है यह आपको लगता है समय इसे हल करने के लिए सच है कि ज्यादा वृद्धि नहीं करता है. यह तुलनीय की तरह है यहां शुरुआत में. आप ठीक है, की तरह हो. कुछ भी यहाँ सच नहीं करता बात जो हम उपयोग करते हैं, लेकिन अगर आप एक लाख के लिए एक अरब डॉलर बाहर निकलना. आप some-- --you're खोजने की कोशिश कर रहे हैं एक टेबल में एक सुई खोजने की कोशिश. मैं आपको इस समस्या चाहते हैं. आप इस जटिलता, नहीं चाहते रैखिक क्योंकि सभी के लिए आपकी वाला के माध्यम से खोज की जा पता प्रत्येक व्यक्ति सुई, घास की बात, अपने सुई के लिए देखने की कोशिश कर रहा. और कहा कि मेरी राय में बहुत मज़ा नहीं है. मैं तेजी से पसंद है. मैं कुशल पसंद है. और जैसे मेहनती छात्रों आप दोस्तों, आप होशियार काम जानते हैं, नहीं कठिन प्रकार की बात, आप कैसे इन एल्गोरिदम कर सकते हैं. तो, हम चलने के लिए जा रहे हैं बस एक त्वरित उदाहरण के माध्यम से. मैं तुम लोगों को होना चाहिए द्विआधारी खोज पर एक हाथ, लेकिन मामले में किसी को भी एक छोटी सी है फजी, इसे मजबूत करना चाहते हैं, हम बस जाने के लिए जा रहे हैं यहां एक उदाहरण के माध्यम से. अगर हां, तो हम देख रहे हैं सरणी सात शामिल हैं. तो, हम पहली बात है ठीक है, बीच में लग रही हो? और भी आप कोडिंग करने जा रहे हैं बस एक पल में द्विआधारी खोज. इसलिए, यह मजाक होने जा रहा है. तो हम में देखो मध्य थोड़ा सरणियों 3. 3 से 7 के बराबर है? नहीं करता है. यह छह है. तो, की तुलना में यह कम है या सात से अधिक? से कम. हां. अच्छा काम दोस्तों. मैं मैं मैं चाहिए की तरह लग रहा है कैंडी क्योंकि मैं गज की दूरी में इसे बाहर फेंक देना चाहते हैं. यह मैं अगले सप्ताह ऐसा करने जा रहा हूँ. यह तेज तुम लोगों को रखना होगा. इसलिए, हम कि दूर फेंक पहली छमाही, है ना? यह से भी कम था. हम चाहते हैं कि सब कुछ जानते हैं कि बाएं हाथ की ओर की तुलना में कम होने जा रहा है क्या हम वास्तव में के लिए देख रहे हैं. तो, कोई ज़रूरत नहीं है यह करने के लिए ध्यान देना. अभी इसके बारे में भूल जाते हैं. तो, अब हम अपने दाहिने हाथ की ओर देखो, और हम, वहाँ पर बीच में देखो और अब यह नौ है. तो, 9 is-- --Everyone? हम क्या कर रहे हैं इससे बड़ा ठीक है, के लिए देख रहे हैं? तो, हम फेंक करने के लिए जा रहे हैं सही करने के लिए सब कुछ दूर. इस तरह. अब, हम सब एक है साथ छोड़ रहे हैं. इसलिए हम जाँच, यह एक है क्या हम देख रहे हैं? यह है. हम हम क्या चाहते थे पाया. तो हम कर रहे हैं. द्विरेखीय खोज. और तुम, हम नोटिस वहाँ सात आदानों था. यह केवल तीन बार की तरह हमें ले लिया लेकिन यदि आप एक अरब की तरह कर रहे हैं, तुम लोग कितने कदम यह होगा पता हम चार अरब बातें था ले? कोई अनुमान? यह 32 है. कुछ खोजने के लिए 32 कदम एक चार अरब में क्योंकि दो की शक्तियों का तत्व सरणी. तो दो, 32 के लिए चार अरब डॉलर की है. तो सुंदर पागल कैसे आप अभी भी भीतर हो चरणों की एक काफी छोटी संख्या की तरह में कुछ खोजने के लिए चार अरब तत्वों. उस पर ध्यान दें तो, हम कर रहे हैं इस कोड के लिए जा रहा इसलिए तुम लोग वास्तव में कर सकते हैं एक तरह से यह कैसे काम करता है देखना. सब ठीक है, तुम लोगों को कोड कर सकते हैं तो. मैं आप लोगों को बताने के लिए जा रहा हूँ एक छोटा सा के लिए बात करते हैं. है, जो आप के आसपास के लोगों को पता हो जाओ क्या किसी को पिछले अनुभाग से चाहता था. तो क्या आप के आसपास के लोगों को जानते हैं. एक छोटा सा के लिए बात करें. और यह सब मैं आप से चाहते हैं लोग सही अब बस है स्यूडोकोड की एक रूपरेखा बनाने का प्रयास करें. ठीक है? वाह. मैं तुम लोगों से चाहते सभी आप कर रहे है सिर्फ इस जबकि मामले में भरने के लिए जा रहा है. इसलिए मैं इन ऊपरी निर्धारित किया है और कम सीमा जो शुरुआत प्रतिनिधित्व हमारे सरणी की और अंत. और अगर आप वास्तव में करने जा रहे हैं पाश के माध्यम से और बाहर आंकड़ा क्या हम इस जबकि पाश के भीतर कार्य कर रहे हैं. आप out-- समझ सकते हैं तो मेरे पास है मामले हैं क्या there-- एक संकेत कि हम यहाँ है? आप यह पता लगाने के लिए चाहते हैं, तो मामलों, हम उन pseudocode जाएगा और फिर हम वास्तव में उन्हें कोड करेंगे. और यह होने जा रहा है, मैं उम्मीद है कि यह होगा, लगता है आपकी अपेक्षा से थोड़ा आसान हो. , यह है कि बहुत कोड नहीं है क्योंकि वास्तव में, जो वास्तव में अच्छा है. मम-एचएम? छात्र: [अश्राव्य]? प्रशिक्षक: हाँ. कुछ था बीच में लगता है. छात्र: तो हम उस का उपयोग कर सकते हैं. ठीक. प्रशिक्षक: बिल्कुल सही. तो यह है कि हम क्या करने की जरूरत है पहली बात है. तो बीच पाते हैं. ग्रेट. तो आप में से एक विचार है कि कैसे हम हो सकता है वास्तव में कोड के साथ बीच पाते हैं? छात्र: हाँ. पर 2 एन? प्रशिक्षक: तो 2 n खत्म. तो याद करने की एक बात यह है कि अपने ऊपरी और निचले सीमा बदल जाते हैं. हम भाग में बाधा आते सरणी की हम देख रहे हैं. तो 2 n पर ही काम करेंगे पहली बात के लिए हम करते हैं. तो खाते में ऊपरी और निचले ले रही है, कैसे हम उस बीच तत्व मिल सकता है? हम मध्य चाहते हैं ऊपरी और निचले, सही के बीच? मम-एचएम? छात्र: [अश्राव्य]. प्रशिक्षक: तो हम कुछ मध्यम है. और यह ऊपरी प्लस 2 से अधिक कम हो जाएगा. बहुत बढ़िया. हम वहाँ जाना. एक पंक्ति नीचे. तुम लोग अपने रास्ते पर हैं. तो अब हम हमारी है कि मध्य, हम क्या करना चाहते हैं? सिर्फ सामान्य में. आप यह कोड की जरूरत नहीं है. हां. छात्र: [अश्राव्य]? प्रशिक्षक: तो यह है प्लस आप कर रहे हैं, क्योंकि दोनों के बीच औसत ढूँढने उनमें से. तो आप के रूप में उन्हें तरह के बारे में सोच अगर तरफ से बढ़ रही है, आप दृष्टिकोण के रूप में इसके बारे में सोचो मध्य, तुम इस तरह चाहते हैं. तो अगर आप के दोनों तरफ थे मध्य, और हम 5 और 7 की तरह है. आप उन्हें एक साथ जोड़ने के लिए 12 मिलता है, आप 2 से विभाजित, 6. कभी कभी यह मुश्किल है वह काम करता है क्यों समझा, लेकिन आप के माध्यम से काम करते हैं एक उदाहरण कभी कभी, यह आप अगर यह पता लगाने में मदद करेंगे यह प्लस या माइनस होना चाहिए. हां. छात्र: [अश्राव्य] बीचोबीच वे जहां एक मामला था छोटी संख्या का एक बहुत कुछ है और एक बड़ी संख्या की तरह? प्रशिक्षक: तो तुम सब की ज़रूरत सरणी के बीच है. तो अगर आप कम संख्या का एक गुच्छा था और फिर एक बहुत बड़ी संख्या अंत में, यह बात नहीं है. मायने रखता है कि यह है कि वे, आप अभी हल कर रहे हैं के बीच में देखना चाहता हूँ सरणी आप अभी भी कर रहे हैं क्योंकि आधे में आपकी समस्या का टुकड़ा करने की क्रिया. कूल. तो अब है कि हम मध्य, हम आगे क्या करना है? छात्र: तुलना करें. प्रशिक्षक: की तुलना करें. Value_wanted को तो बीच की तुलना करें. कूल. तो आप हमारे पास यहाँ देख हम यहाँ चाहते हैं तो यह मान. इस एक सरणी है याद रखें. तो मध्य सूचकांक को दर्शाता है. इसलिए हम मध्यम के मूल्यों को क्या करना चाहते हैं. अगर आप चाहते हैं मत भूलना , डबल बराबर की तुलना करना. आप ही आप कर रहे हैं के बराबर होती करना बस इसे पुन: असाइन करने के लिए जा रहा है, और फिर, बेशक, यह है आप चाहते हैं मूल्य होने जा रहा. तो ऐसा नहीं करते. इसलिए हम यह देखने के लिए जा रहे हैं बीच में मूल्यों हम चाहते हैं कि मूल्य के बराबर है. अपने ब्रेसिज़ मत भूलना. ड्रॉपबॉक्स दूर जाना चाहिए. इसलिए हम इस मामले में क्या करते हो? यह हम वापसी करना चाहते हैं क्या करते हैं? हम कहने की कोशिश कर रहे हैं. छात्र: बंद प्रिंट. प्रशिक्षक: ठीक है, हम बंद मुद्रित करने के लिए नहीं करना चाहती. तो यह यहाँ एक bool है, हम तो सही है या गलत लौटना चाहते हैं. हम इस नंबर है, कह रहे हैं एक [? RRA? ?] यह है तो अगर, हम सिर्फ यह सच वापसी. मैं सच जादू कर सकते हैं. छात्र: क्यों आप शून्य वापस नहीं होगा? प्रशिक्षक: तुम सकता है तो अगर तुम चाहते थे शून्य वापसी. लेकिन इस मामले क्योंकि में हमारे समारोह एक bool रिटर्न, हम सही है या गलत या तो वापस जाने की जरूरत है. छात्र: जब आप कर रहे हैं , बूलियन अभिव्यक्ति कह आप इसे गलत पर बराबर सेट कर सकते हैं? मैं कहना चाहता हूँ, अगर इस शर्त की तरह ऊपरी है झूठे बराबर होती है जैसे, नहीं मिले है. बस आप अगर यह समझ जाएगा दूसरी तरफ झूठी रखा है? प्रशिक्षक: हाँ. तो वास्तव में आप कर रहे हैं कभी कुछ कर रही है जैसे ऊपरी है या कम है, यह सच है या झूठ रिटर्न और यह वास्तव में बुरा शैली है कहते बराबर होती है सच या बराबर होती है झूठी बराबर होती है. आप उस परिणाम का उपयोग करना चाहते हैं अपनी जाँच के रूप में खुद के रूप में. मैं नहीं चाहता था क्या. यही कारण है कि मैं क्या चाहता है. पूछ रहे हैं कि आप के मामले में तो कुछ के बारे में तरह सी में इस बचा. तो हम int मुख्य (शून्य) हो, तो और कुछ इस तरह. ऊपरी है और अगर आपके पास आप कर रहे हैं और कुछ इनपुट की आप क्या कर सकते हैं अगर पूछ कुछ इस तरह? है ना? छात्र: मैं कोशिश कर रहा था यह [अश्राव्य] करने के लिए. It's-- क्योंकि अगर प्रशिक्षक: ठीक है. तो आप इस सही, गलत बनना चाहते हो? छात्र: हाँ. प्रशिक्षक: इस मामले में तो आप यह सच नहीं है अगर इसे लागू करना चाहते हैं. तो तुम वहाँ कर शांत बात यह है. तो विस्मयादिबोधक याद बिंदु बातें नकारती? यह [अश्राव्य] नहीं मतलब कहते हैं. हम बस पर देखने के लिए तो अगर यहाँ इस हिस्से, आप चाहते हैं कि करने के लिए मूल्यांकन का कहना है झूठी आप यह चाहते हैं के रूप में. झूठी नहीं जो सच है इस पर अमल होता है इसका मतलब है. कि मतलब? छात्र: हाँ. प्रशिक्षक: बहुत बढ़िया. ठीक. तो हम बस लौट सकता है इस मामले में सच है. तो अब हम अन्य दो हैं इस मामले में मामलों. हमारे दो अन्य मामलों में क्या कर रहे हैं? चलो बस इसे इस तरह से करते हैं. तो चलो किसी और के साथ शुरू करते हैं अगर बीच में मूल्यों हम चाहते हैं कि मूल्य से कम है. तो बीच में हमारे मूल्य भी कम है हम देख रहे हैं कि मूल्य से अधिक है. इसलिए बाध्य जो आप करना हम अद्यतन करना चाहते हैं लगता है? ऊपरी या निचले? अपर? सरणी की तो जो पक्ष हम देख होने जा रहे हैं? छात्र: कम. प्रशिक्षक: हम जा रहे हैं बाएं को देख सकता है. छोटे मूल्य कम है तो अगर कोई और. यहां आपके बीच मूल्य तो हम क्या चाहते हैं की तुलना में कम है. तो हम ले जाना चाहता हूँ हमारे सरणी के दाईं ओर. तो हम करने जा रहे हैं हमारे निचले बाध्य अद्यतन करें. इसलिए हम अपने निचले पुन: असाइन कर देंगे. और आप कम होना चाहिए क्या सोचते हैं? छात्र: मध्यम मूल्य है? प्रशिक्षक: तो बीच value-- छात्र: प्लस 1. प्रशिक्षक: --plus 1. किसी को क्यों मुझे बता सकते हैं हम चाहते हैं कि प्लस 1 है? छात्र: [? कोई मूल्य है?] यह करने के लिए अधिक बराबर है. प्रशिक्षक: ठीक है. हम पहले से ही जानते हैं कि क्योंकि हमारे बीच मूल्य के बराबर नहीं है यह और हम इसे बाहर करना चाहते हैं बाद के सभी खोजों से. आपको लगता है कि प्लस 1, यह भूल जाते हैं अनिश्चित काल के पाश की तरह होगा. और तुम सिर्फ एक में पकड़ा हो जाएगा अनंत लूप और फिर आप segfault करेंगे और हालात खराब जाओ. तो हमेशा आप नहीं कर रहे हैं कि यह सुनिश्चित कर लें मूल्य सहित कि आप बस देखा. तो हम एक प्लस 1 के साथ इस बात का ध्यान रखना. तो अब हम हमारे पिछले शर्त है सुरक्षा खातिर जो हमेशा मैं आप में मूल्य अगर नहीं तो, यहाँ जाँच कर सकते हैं मध्य मूल्य से अधिक है हम चाहते हैं. यही कारण है कि हम चाहते हैं कि इसका मतलब है बाएं हाथ आधा. तो जो एक हम अद्यतन करने के लिए जा रहे हैं? अपर. और समान करने के लिए जा रहा यह एक क्या है? मध्य शून्य से 1, क्योंकि जाहिर है, हम चाहते हैं हम नहीं कर रहे हैं कि सुनिश्चित करने के लिए फिर उस बीच मूल्य पर देख रहे हैं. और फिर हमारे पास है. यह बात है. यह सब द्विआधारी खोज है. यह सही है, कि बुरा नहीं है? यह की 10 लाइनों की तरह है सफेद अंतरिक्ष के साथ कोड. तो बहुत शक्तिशाली, बहुत उपयोगी, तुम जाएगा आपके बाद psets में से एक में इसे का उपयोग किया. शायद यह एक नहीं, लेकिन बाद में. तो यह सीखते हैं. इसे प्यार करना. यह अच्छी तरह से आप का इलाज करेंगे. इसलिए किसी को भी किसी भी है द्विआधारी खोज पर सवाल? हां. छात्र: यह बात है अपने एन भी या विषम है कि क्या? प्रशिक्षक: नहीं. हम के रूप में मध्यम करने के लिए डाली क्योंकि एक पूर्णांक, यह सिर्फ इसे छोटा कर देगा. यह एक पूर्णांक रहने के लिए और होगा तो यह होगा अंत में सब कुछ के माध्यम से हल. इसलिए आप इस बारे में चिंता करने की ज़रूरत नहीं है. हर कोई अच्छा? बहुत बढ़िया. कूल. तो, तुम लोगों को यह मिल गया. स्लाइड शो. हम बात कर रहे थे तो, जैसा कि मुझे पता है डेविड जटिलता runtimes उल्लेख किया है. तो सबसे अच्छा मामले में, यह सिर्फ है हम लगातार समय कॉल एक है, जो. हो सकता है कि क्यों किसी ने मुझे बता सकते हैं? उस परिदृश्य किस प्रकार करना पड़ेगा? मम-एचएम. छात्र: [अश्राव्य] first-- प्रशिक्षक: मध्यम जा रहा है तो हम करने के लिए आते हैं कि पहला तत्व है, है ना? तो एक की एक सरणी या जो कुछ भी हम अभी के लिए देख रहे हैं बीच में एक प्रकार का जहाज़ थपका होना होता है. इसलिए कि हमारे सर्वश्रेष्ठ मामला है. तुम्हें शायद, असली समस्याओं में नहीं मिलता कि अक्सर [अश्राव्य] तक पहुंचने के लिए जा रहा है. क्या हमारे सबसे खराब स्थिति के बारे में? हमारी सबसे ज्यादा मामले प्रवेश n है. और कहा कि पूरे के साथ क्या करना है मैं बारे में बात की है कि दो बात की शक्तियों. तो सबसे खराब स्थिति में यह मतलब होगा हम नीचे सरणी काटना पड़ा यह एक का एक तत्व था जब तक. इसलिए हम छमाही में यह नीचे काटना पड़ा के रूप में हम संभवतः सकता है के रूप में कई बार. यह प्रवेश एन क्योंकि यही कारण है कि आप सिर्फ दो से विभाजित रहते हैं. तो मान्यताओं, बातें आप आप कभी भी कर रहे हैं पता करने की जरूरत एक द्विआधारी खोज का उपयोग करने के लिए जा रहा है. अपने तत्वों को हल किया जाना चाहिए. क्योंकि वे हल किया जाना है कि एक ही रास्ता तुम हो आप कर रहे हैं पता कर सकते हैं इसमें से आधा बाहर फेंकने के लिए. आप इस पेचीदा बैग था और संख्या की आप कह रहे हैं, ठीक है, मैं बीच की जाँच करने के लिए जा रहा हूँ संख्या और मेरी चाहत संख्या उस से भी कम है, मैं अभी जा रहा हूँ मनमाने ढंग से एक आधा बाहर फेंकने के लिए. आप अगर पता नहीं होता अपनी कि दूसरे आधे में संख्या. अपनी सूची को हल किया जाना है. साथ ही, यह हो सकता है आगे एक छोटा सा जा रहा है, लेकिन आप रैंडम एक्सेस की आवश्यकता है. आप करने में सक्षम होने की जरूरत है तो बस कि मध्य तत्व के पास जाओ. आप तय करने के लिए है कुछ के माध्यम से या यह आप अतिरिक्त कदम उठा लेता है कि मध्य तत्व को पाने के लिए, यह लॉग इन एन अब क्योंकि नहीं है आप इसे में अधिक काम जोड़ रहे हैं. और यह एक छोटे से कर देगा दो सप्ताह में अधिक समझ, लेकिन मैं बस की तरह, प्रस्तावना करना चाहता था तुम लोग क्या है की एक विचार दे आने के लिए. लेकिन उन दोनों कर रहे हैं महत्वपूर्ण मान्यताओं आप एक द्विआधारी सूची के लिए जरूरत है. इसे हल सुनिश्चित करें. बड़ा है कि एक है आप अभी लोग. और उस पर हम में जा सकते हैं हमारे प्रकार के बाकी. तो चार sorts-- बुलबुला, प्रविष्टि, चयन, और मर्ज. वे शांत के सभी प्रकार के कर रहे हैं. तुम लोग सीएस 124 लेने का निर्णय लेते हैं, आप प्रकार के सभी प्रकार के बारे में सीखना होगा. और तुम एक xkcd प्रशंसक रहे हैं, वहाँ एक बहुत अच्छा हास्य के बारे में है वास्तव में अप्रभावी प्रकार, जैसे जो मैं अत्यधिक आप को देखने जा सलाह देते हैं. उनमें से एक आतंक तरह की तरह है जो जैसे, ओह नहीं, यादृच्छिक सरणी वापस है. शटडाउन प्रणाली. छोड़ दो. तो geeky हास्य हमेशा अच्छा होता है. तो किसी तरह याद करता है का सिर्फ एक सामान्य विचार की तरह बुलबुला तरह कैसे काम करता है. तुम्हें याद है? छात्र: हाँ. प्रशिक्षक: इसके लिए जाओ. छात्र: आप के माध्यम से जा रहे हैं तो और यह बड़ा है, तो आप दो स्वैप. प्रशिक्षक: मम-एचएम. बिल्कुल सही. तो आप बस के माध्यम से पुनरावृति. आप दो नंबर की जाँच करें. एक से पहले ज्यादा है बाद में एक से, आप सिर्फ इतना है कि उन्हें स्वैप इस तरह से अधिक संख्या के सभी सूची के अंत में बुलबुला और सब कम संख्या बुलबुला नीचे. वह शांत तुम लोगों को दिखाने के लिए किया था वीडियो छँटाई प्रभाव ध्वनि? यह शांत की तरह है. रॉबर्ट बस के रूप में कहा, एल्गोरिथ्म तो तुम सिर्फ सूची के माध्यम से कदम है कि, आसन्न मूल्यों स्वैपिंग वे क्रम में नहीं कर रहे हैं. और फिर सिर्फ दोहराते रहते हैं जब तक आप किसी भी स्वैप नहीं बनाते हैं. इतना बुरा नहीं है, है ना? तो हम बस यहाँ एक त्वरित उदाहरण है. तो यह सॉर्ट करने के लिए जा रहा है आरोही क्रम में उन्हें. इसलिए हम पहले के माध्यम से जाने के लिए जब समय, हम आठ के माध्यम से देखो और छह स्पष्ट रूप से नहीं कर रहे हैं आदेश में, हम उन्हें स्वैप. तो अगले एक पर दिखेगा. आठ और क्रम में चार नहीं. उन्हें स्वैप. और फिर आठ और दो, उन्हें स्वैप. हम वहाँ जाना. तो अपने पहले पारित करने के बाद, आप पता है कि आपकी सबसे बड़ी संख्या सभी तरह होने जा रहा है यह सिर्फ इसलिए है क्योंकि शीर्ष पर लगातार होने जा रहा बाकी सब से बड़ा और यह सिर्फ बुलबुला जा रहा है वहाँ समाप्त करने के लिए सभी तरह से ऊपर. कि हर किसी को समझ में आता है? कूल. तो फिर हम अपने दूसरे दर्रे पर दिखेगा. छह और चार, स्विच. छह और दो, स्विच. और अब हम क्रम में कुछ बातें हैं. हर पारित करने के लिए तो यह है कि हम हमारी पूरी सूची के माध्यम से बनाने, हम जानते हैं कि कि कई नंबर की तरह अंत में सुलझा लिया गया होगा. तो हम एक तिहाई पास करना, जो एक स्वैप है. और फिर हमारे चौथे पर हम शून्य स्लॉट्स है, गुजरती हैं. और इसलिए हम जानते हैं कि हमारे सरणी सुलझा लिया गया है. और वह बड़ा है बुलबुला प्रकार के साथ बात. हम जानते हैं कि जब हम उस , कि शून्य स्वैप है कि सब कुछ है पूरा क्रम में है. यह हम जाँच कैसे की तरह है. तो हम भी बुलबुला कोड के लिए जा रहे हैं क्रमबद्ध जो भी बुरा नहीं है. इनमें से कोई नहीं कि खराब कर रहे हैं. मुझे लगता है वे थोड़ा डरावना लग सकता है पता है. मैं ले लिया जब मुझे पता है वर्ग, यहां तक ​​कि जब मैं के लिए वर्ग सिखा रहा था पहली बार पिछले साल, मैं जैसे, मैं यह कैसे करते हो रहा था? यह सिद्धांत में समझ में आता है, लेकिन हम वास्तव में यह कैसे करते हो? कौन सा मैं भी चलना चाहता हूँ क्यों है यहां तुम लोगों के साथ कोड के माध्यम से. तो मैं एक pseudocode है तुम लोग इस समय के लिए. तो बस के रूप में इसे ध्यान में रखना हम पर संक्रमण करने वाले हैं. इसलिए हम कुछ काउंटर है कि , हमारे स्वैप का ट्रैक रखता है हम सुनिश्चित करने की जरूरत है क्योंकि हम चाहते हैं कि जाँच कर रहे हैं कि. और हम पूरे सरणी पुनरावृति हम सिर्फ इस उदाहरण के साथ किया था. तत्व पहले से बड़ा है हम पर हैं जहां के बाद तत्व, हम उन्हें स्वैप और हम अपने वेतन वृद्धि काउंटर, हम स्वैप जैसे ही क्योंकि हम अपने काउंटर कि बताना चाहते हैं. वहाँ कोई सवाल? कुछ यहाँ पर अजीब लगता है. छात्र: आप शून्य करने के लिए काउंटर स्थापित करूँ आप पाश के माध्यम से जाना हर बार? तुम जा न रखें वापस हर बार शून्य करने के लिए? प्रशिक्षक: जरूरी नहीं है. तो क्या होता है जब हम यहाँ के माध्यम से जाना है. तो, जबकि, यह याद करना असफल बिना एक बार अमल करेंगे. तो यह निर्धारित करने के लिए जा रहा है शून्य के बराबर काउंटर, तो यह माध्यम से पुनरावृति करने जा रहा है. इसके माध्यम से iterates के रूप में, यह काउंटर अद्यतन करेगा. यह काउंटर अद्यतन के रूप में, जब यह किया है, यह सरणी के अंत तक पहुँच गया है जब, हमारी सूची हल नहीं किया गया तो, काउंटर अद्यतन हो जाएँगे. तो फिर यह हालत की जांच करता है और यह ठीक है, शून्य से काउंटर अधिक है, कहते हैं. अगर ऐसा है, इसे फिर से करना. आप तो जब आपको लगता है कि फिर से कायम करना चाहते हैं के माध्यम से जाना, काउंटर शून्य के बराबर है. आप एक हल के माध्यम से जाना सरणी, कुछ भी नहीं, परिवर्तन यह विफल रहता है, और आप सॉर्ट की गई सूची वापस जाएँ. वह समझ में आता है? छात्र: एक छोटा सा में हो सकता है यह. प्रशिक्षक: ठीक है. किसी भी अन्य अगर वहाँ ऊपर आता है कि प्रश्न. हां. छात्र: क्या होगा समारोह तत्वों स्वैपिंग के लिए हो सकता है? प्रशिक्षक: तो क्या हम वास्तव में लिख सकते हैं हम अभी जा रहे हैं कि. कूल. उस पर ध्यान दें तो, एलिसन जा रहा है वापस उपकरणों को स्विच करने के लिए. यह मजाक होने जा रहा है. और हम अपने अच्छा है यहाँ बुलबुला तरह बात. तो मैं पहले से ही साइकिल चालन किया सरणी के माध्यम से. हम अपने स्वैप है कि शून्य के बराबर हैं. इसलिए हम आसन्न स्वैप करना चाहते हैं तत्वों वे आदेश से बाहर रहे हैं. तो पहली बात यह है कि हम करने की आवश्यकता है हमारे सरणी के माध्यम से पुनरावृति है है. तो आप कैसे हम शायद लगता है हमारे सरणी के माध्यम से पुनरावृति? हम के लिए है और मैं 0 के बराबर होती है. हम मैं कम होना चाहते हैं एन शून्य से 1 घटा कश्मीर से. और मैं एक दूसरे में है कि समझाता हूँ. तो यह एक अनुकूलन यहाँ है जहां, मैं हर पारित होने के बाद कहा कैसे याद सरणी के माध्यम से हम जो कुछ on-- है कि पता तो एक पास के बाद हम इस हल है कि पता है. दो गुजरता के बाद हम जानते हैं यह सब हल है कि. तीन गुजरता के बाद हम कि हल है पता. रास्ता तो मैं पुनरावृति हूँ यहाँ सरणी के माध्यम से, यह केवल जाना सुनिश्चित करने के लिए है क्या हम जानते हैं के माध्यम से unsorted है. ठीक है? वह सिर्फ एक अनुकूलन है. तुम बस भोलेपन से यह लिख सकते हैं सब कुछ के माध्यम से पुनरावृति, यह सिर्फ लंबे समय तक ले जाएगा. इस चार लूप के साथ यह है सिर्फ एक अच्छा अनुकूलन हम चाहते हैं कि हर पूर्ण होने के बाद पता क्योंकि यहाँ सरणी के माध्यम से चलना, यहां हर पूर्ण लूप की तरह, हम जानते हैं इन तत्वों में से एक अधिक है कि अंत में सुलझा लिया जाएगा. तो हम उन लोगों के बारे में चिंता करने की जरूरत नहीं है. कि हर किसी को समझ में आता है? वह शांत छोटी सी चाल? उस मामले में, तो अगर हम से होकर फिर रहे हैं हम हम अगर जाँच करना चाहते हैं कि पता सरणी और एन एन प्लस 1 क्रम में हैं. ठीक. तो यहाँ pseudocode है. हम अगर जाँच करना चाहते सरणी एन और एन प्लस 1 क्रम में हैं. इसलिए हम वहाँ क्या हो सकता है? यह कुछ सशर्त होने जा रहा है. यह एक अगर हो जाएगा. छात्र: सरणी n है तो सरणी एन प्लस 1 से भी कम. प्रशिक्षक: मम-एचएम. खैर, कम से कम या अधिक से अधिक. छात्र: से ग्रेटर. तो फिर हम उन्हें स्वैप करना चाहते हैं. बिल्कुल सही. तो अब हम क्या में मिलता है उन्हें स्वैपिंग के लिए तंत्र? इसलिए हम इस संक्षिप्त माध्यम से चला गया, स्वैप समारोह का एक प्रकार पिछले सप्ताह. किसी को भी यह काम कैसे याद करता है? तो हम सिर्फ सही, उन्हें पुन: असाइन नहीं कर सकते? उनमें से एक खो दिया हो जाएगा. हम ने कहा कि एक तो बी बी और के बराबर है एक के बराबर है, उन दोनों के अचानक बी के लिए बस के बराबर हैं तो हमें क्या करना है क्या हम है है कि एक अस्थायी चर हमारा जबकि में से एक पकड़ के लिए जा रहा हम स्वैपिंग की प्रक्रिया में हैं. तो क्या हमारे पास है हम कुछ पूर्णांक होगा है आप यह निर्दिष्ट कर सकते हैं to-- अस्थायी बराबर है जो भी एक के लिए आप बस चाहते हैं आप it-- का ट्रैक यकीन रख कर इसलिए इस मामले में, मैं जा रहा हूँ सरणी एन प्लस 1 को आवंटित. इसलिए कि आयोजित करने जा रहा है जो कुछ भी मूल्य कि दूसरे ब्लॉक में है हम देख रहे हैं कि. और हम जा सकते हैं तो हम क्या कर सकते है आगे और फिर सरणी एन प्लस 1, हम हम जानते हैं क्योंकि संग्रहित कि मूल्य है. यह भी बड़ी में से एक है आप में से किसी भी अगर things-- मैं नहीं जानता आप दो स्विच जहां मुद्दों था कोड की लाइनों अचानक चीजें काम किया. आदेश सीएस में बहुत महत्वपूर्ण है. तो सुनिश्चित करें कि आप चित्र बनाने चीजें बाहर यदि संभव हो तो के रूप में वास्तव में क्या हो रहा है. तो अब हम जा रहे हैं , सरणी एन प्लस 1 फिरसेआबंटितकरें हम हम जानते हैं क्योंकि संग्रहित कि मूल्य है. और हम सरणी के लिए कि असाइन कर सकते हैं एन या इस मामले सरणी मैं में. बहुत सारे चर. ठीक. तो अब हम फिर नियत किया है सरणी मैं प्लस 1 सरणी मैं में क्या बराबर करने के लिए. और अब हम वापस जा सकते हैं और क्या सरणी मैं आवंटित? कोई है? छात्र: 10. प्रशिक्षक: 10. बिल्कुल सही. और एक आखिरी बात. अब हम यह बदली है, तो क्या हम ऐसा करने की क्या ज़रूरत है? एक बात क्या है कि हमें बताने के लिए जा रहा है हम कभी भी इस कार्यक्रम को समाप्त तो क्या होगा? क्या हम हमें बताता है कि A हल सूची है? हम किसी भी स्वैप प्रदर्शन नहीं करते हैं, सही? स्वैप हैं के बराबर है इस के अंत में शून्य. इसलिए जब भी आप हम के रूप में, एक स्वैप प्रदर्शन बस यहाँ किया था, हम स्वैप अद्यतन करना चाहते हैं. और मैं वहां गया था पता एक सवाल पहले के बारे में आप कर सकते हैं बजाय शून्य या एक का उपयोग की सही है या गलत. और कहा कि इस यहाँ क्या करता है. तो यह तो नहीं स्वैप कहते हैं. स्वैप शून्य है, तो अगर जो हमेशा मैं is-- माय सत्य और मेरे falses मिलाया. हम हमें मूल्यांकन करना चाहते हैं सच करने के लिए और यह नहीं है. यह शून्य है, तो यह गलत है. आप एक साथ यह नकारना हैं [? धमाके?] यह सच हो जाता है. तो फिर इस लाइन कार्यान्वित. सत्य और झूठे और शून्य और लोगों को पागल मिलता है. बस आप धीरे धीरे चलना अगर इसके माध्यम से यह समझ कर देगा. लेकिन यह है कि क्या इस छोटे से है कोड की बिट यहाँ करता है. तो यह देखने के लिए जाँच करता है हम किसी भी स्वैप किया है. तो यह कुछ भी इसके अलावा अगर है शून्य, यह गलत होने जा रहा है और पूरी बात है फिर से निष्पादित करने के लिए जा रहा है. कूल? छात्र: तोड़ क्या करता है? प्रशिक्षक: सिर्फ तोड़ लूप से बाहर टूट जाता है. इस मामले में यह होता तो बस कार्यक्रम अंत की तरह और तुम सिर्फ होगा आपके सॉर्ट की गई सूची है. छात्र: कमाल है. प्रशिक्षक: मैं माफी चाहता हूँ? छात्र: क्योंकि हम पहले से शून्य लिखा पर 1 लिखा करते थे अगर उस पेश करने के लिए वह काम करेंगे या नहीं. प्रशिक्षक: हाँ. तो आप शून्य या 1 लौट सकते हैं. इस मामले में, क्योंकि हम वास्तव में नहीं कर रहे हैं समारोह के साथ कुछ भी कर रही है, हम सिर्फ इसे तोड़ने के लिए चाहते हैं. हम वास्तव में इसके बारे में परवाह नहीं है. ब्रेक भी अगर अच्छा है यह बाहर तोड़ने के लिए प्रयोग किया जाता है चार छोरों या स्थितियों की कि आप क्रियान्वित रखने के लिए नहीं करना चाहती. यह सिर्फ उनमें से बाहर ले जाता है. यह एक अति सूक्ष्म अंतर बात का एक सा है. वहाँ मुझे लगता है हाथ लहराते की एक बहुत, जैसे आप जल्द ही इस बारे में सीखना होगा. लेकिन आप जल्दी ही इस बारे में सीखना होगा. मैं वादा करता हूं. ठीक. तो हर कोई बुलबुला प्रकार प्राप्त करता है? बहुत बुरा नहीं है. के माध्यम से पुनरावृति, स्वैप बातें एक का उपयोग अस्थायी चर, और हम सब वहाँ स्थापित कर रहे हैं? कूल. बहुत बढ़िया. ठीक. वापस PowerPoint के लिए. सामान्य में किसी भी सवाल के बारे में इन अब तक? कूल. मम-एचएम. छात्र: [अश्राव्य] आमतौर पर मुख्य इंट. इस बात के लिए कि है की आप की क्या ज़रूरत है? प्रशिक्षक: तो हम बस देख रहे थे सिर्फ वास्तविक छँटाई एल्गोरिथ्म पर. तुम्हारे भीतर यह था एक बड़े कार्यक्रम की तरह, आप एक int मुख्य कहीं होगा. जहां आप पर निर्भर करता है इस कलन विधि का उपयोग, यह क्या हो रहा है यह निर्धारित होगा यह द्वारा वापस किया जा रहा है. लेकिन हमारे मामले के लिए, हम कड़ाई से कर रहे हैं वास्तव में यह कैसे करता है पर देख रहे हैं एक सरणी के माध्यम से पुनरावृति. तो हम इसके बारे में चिंता मत करो. इसलिए हम के बारे में सबसे अच्छी स्थिति में बात कर रहे थे और द्विआधारी खोज के लिए सबसे ज्यादा मामले परिदृश्यों. तो यह करने के लिए भी महत्वपूर्ण है हमारे प्रकार से प्रत्येक के लिए कि. तो क्या आपको लगता है कि सबसे बुरा है बुलबुला तरह के मामले क्रम? तुम लोग याद है? छात्र: एन माइनस 1. प्रशिक्षक: एन माइनस 1. इसलिए कि वहाँ का मतलब एन माइनस 1 तुलना. तो साकार करने के लिए एक बात है पहली यात्रा पर कि, हम, हम तुलना के माध्यम से जाना इन two-- इसलिए कि 1 है. इन दो, तीन, चार. तो एक यात्रा के बाद हम पहले से ही चार तुलना है. जब मैं क्रम और एन के बारे में बात कर रहा हूँ. एन तुलना की संख्या का प्रतिनिधित्व करता है कितने तत्वों के एक समारोह के रूप में हमारे पास है. ठीक है? इसलिए हम के माध्यम से जाना, हम चार है. तुम्हें पता है अगली बार हम नहीं इस बात का ध्यान रखना होगा. हम इन दोनों की तुलना इन दो, इन दो, और हम हैं कि अनुकूलन नहीं था मैंने लिखा था कि चार लूप के साथ, आप वैसे भी यहाँ की तुलना की जाएगी. तो आप करना होगा सरणी के माध्यम से चलाने के और एन तुलना करने n कई बार, हर बार हम क्योंकि यह की तरह एक बात हम के माध्यम से चला रहे हैं. और हम के माध्यम से चलाने के लिए हर समय सरणी, हम n तुलना करने. तो इस के लिए हमारे क्रम है वास्तव में एन, चुकता जो में बहुत बुरा है हमारी कि क्योंकि अंत लॉग इन हम चार पड़ा तो इसका मतलब है अरब तत्वों, यह है हमें चार अरब ले जा रहा बजाय 32 की चुकता. तो सबसे अच्छा नहीं रनटाइम, लेकिन कुछ बातों के लिए, तुम्हारे भीतर हो अगर आप जानते हैं, तत्वों की एक निश्चित सीमा बुलबुला प्रकार का उपयोग करने के लिए ठीक हो सकता है. ठीक. तो अब सबसे अच्छा मामले क्रम क्या है? छात्र: शून्य? या 1? प्रशिक्षक: तो 1 होगा एक तुलना हो. ठीक है. छात्र: एन माइनस 1? प्रशिक्षक: तो, हाँ. तो एन माइनस 1. आप n की तरह एक अवधारणा है जब भी शून्य से 1, हम सिर्फ यह छोड़ जाते हैं आपके पास और क्योंकि हम सिर्फ n कहना these-- प्रत्येक जोड़ी में से प्रत्येक की तुलना करना. तो यह 1 एन होना शून्य से होगा जो हम हम सिर्फ लगभग n है कहूँगा. आप क्रम के साथ काम कर रहे हैं, सब कुछ approximates में है. जब तक प्रतिपादक के रूप में सही, तुम बहुत अच्छा कर रहे हैं. हम इसके साथ सौदा कैसे है. सबसे अच्छा मामले N, इतना है कि जो , सूची में पहले से ही हल है कि इसका मतलब है और हम सब के माध्यम से चलाया जाता है और इसे हल है कि जाँच करें. कूल. ठीक है. आप यहाँ देख तो, जैसा कि हम अभी कुछ और रेखांकन है. तो एन चुकता. मज़ा. जितना हम देख एन से भी बदतर है, और लॉग 2N से भी बदतर, ज्यादा. और फिर आप भी प्रवेश लॉग में मिलता है. और आप 124 ले, आप में मिलता है पागलों की तरह है जो प्रवेश स्टार की तरह. आप रुचि रखते हैं तो, देखने का प्रवेश सितारा. यह मजाक की तरह है. इसलिए हम इस महान चार्ट है. सिर्फ एक को सिर, यह एक अद्भुत चार्ट है करने के लिए हम क्योंकि अपनी मध्य अवधि के लिए आप इन thins पूछने के लिए लंबे समय. तो सिर्फ एक को सिर, पर यह है आपकी अपने अच्छे धोखा शीट पर मध्यावधि क्या आप वहां मौजूद हैं. तो हम बस बुलबुला तरह देखा. सबसे बुरी स्थिति, एन, एन सबसे अच्छा मामले चुकता. और हम दूसरों को देखने के लिए जा रहे हैं. और आप ही देख सकते हैं वास्तव में अच्छी तरह से करता है कि एक हम क्यों में मिल जाएगा जो मर्ज तरह है. तो हम पर जाने के लिए जा रहे हैं अगले एक here-- चयन तरह. किसी को कैसे याद करता है चयन प्रकार का काम किया है? इसके लिए जाओ. छात्र: असल में के माध्यम से जाना एक आदेश और एक नई सूची बनाने. और तुम तत्व डाल रहे हैं बस के रूप में में, सही जगह में डाल नई सूची में. प्रशिक्षक: तो लगता है कि प्रविष्टि प्रकार की तरह अधिक. लेकिन अगर आप वास्तव में बंद कर रहे हैं. वे बहुत समान हैं. यहां तक ​​कि मैं उन्हें कभी कभी मिश्रित मिलता है. मैं जैसा था इस खंड से पहले, रुको. ठीक. तो आप करना चाहते हैं करना, चयन प्रकार है आप सोच सकते हैं रास्ता यह और रास्ते के बारे में मुझे यकीन है कि मैं पाने के लिए नहीं की कोशिश कर उन्हें यह माध्यम से चला जाता है, मिलाया और यह चुनता है सबसे छोटी संख्या है और यह अपनी सूची की शुरुआत में उस डालता है. ऐसा लगता है कि पहले स्थान के साथ यह स्वैप. वे वास्तव में मेरे लिए एक उदाहरण है. बहुत बढ़िया. तो सिर्फ एक रास्ता it-- चयन के बारे में सोच क्रमबद्ध, छोटी मूल्य का चयन करें. और हम करने जा रहे हैं एक उदाहरण के माध्यम से चलाने के मैं क्योंकि मदद करेगा लगता है कि मैं दृश्यों हमेशा मदद लगता है. इसलिए हम कुछ के साथ बाहर शुरू कि पूरी तरह से unsorted है. लाल, unsorted हो जाएगा हरी हल किया जाएगा. यह सब एक दूसरे में समझ कर देगा. इसलिए हम के माध्यम से जाने के लिए और हम पुनरावृति शुरू से अंत तक. और हम ठीक है, 2 है, का कहना है हमारी सबसे छोटी संख्या. इसलिए हम 2 लेने के लिए जा रहे हैं और हम जा रहे हैं हमारे सरणी के सामने करने के लिए यह कदम यह इसलिए है क्योंकि सबसे छोटी संख्या हमने. इसलिए कि यह यहाँ क्या कर रहा है है. यह सिर्फ उन दो स्वैप करने के लिए जा रहा है. तो अब हम एक हल हिस्सा और एक unsorted हिस्सा. और याद करने के लिए क्या अच्छा है चयन प्रकार के बारे में हम केवल चयन किये जा रहे है unsorted भाग से. हल हिस्सा आप सिर्फ अकेला छोड़ दो. मम-एचएम? छात्र: क्या है यह पता है कैसे यह तुलना के बिना सबसे छोटी सरणी में हर दूसरे मूल्य के लिए. प्रशिक्षक: यह तुलना करता है. हम इसे छोड़ दिया पसंद है. यह समग्र अभी सामान्य है. हाँ. हम मैं हूँ कोड लिखने सुनिश्चित करें कि आप अधिक से संतुष्ट हो जाएगा. लेकिन अगर आप पहली बार इस दुकान छोटी से छोटी के रूप में तत्व. आप तुलना और आप ठीक है, यह छोटा है, कहते हैं? हां. यह रखें. यहाँ यह छोटा होता है? कोई? यह आपकी छोटी से छोटी है अपने मूल्य के लिए इसे पुन: असाइन. और तुम बहुत खुश हो जाएगा हम कोड के माध्यम से जाना. इसलिए हम के माध्यम से जाना, हम तो फिर, यह स्वैप हम इस unsorted हिस्से पर दिखेगा. इसलिए हम तीन बाहर का चयन करने के लिए जा रहे हैं. हम पर उस पर डाल करने के लिए जा रहे हैं हमारे हल भाग के अंत. और हम बस कर रखने के लिए जा रहे हैं कर रही है कि, और कर रही है कि, कि. तो यह यहाँ pseudocode की हमारी तरह है. हम एक दूसरे में यहाँ यह अप कोड करेंगे. लेकिन अभी कुछ चलने के लिए एक उच्च स्तर पर के माध्यम से. आप से जाने के लिए जा रहे हैं मैं n करने के लिए शून्य से 2 0 के बराबर होती है. यही एक और अनुकूलन है. इसके बारे में बहुत ज्यादा चिंता मत करो. तो जैसा कि आप कह रहे थे. याकूब कह रहा था, हम कैसे करते हैं हमारे न्यूनतम है क्या का ट्रैक रखने? हमें कैसे पता है? हम तुलना करने के लिए है हमारी सूची में सब कुछ. तो कम से कम मैं बराबर होती है. यह सिर्फ इस मामले में कह रहा है हमारे न्यूनतम मूल्य सूचकांक. तो फिर यह माध्यम से पुनरावृति जा रहा है जम्मू मैं प्लस 1 के बराबर होती है और यह हो जाता है. तो हम पहले से ही जानते हैं कि कि हमारा पहला तत्व है. हम खुद के लिए यह तुलना करने की जरूरत नहीं है. इसलिए हम अगले करने के लिए यह तुलना शुरू यह मैं प्लस 1 n करने के लिए कारण है जिनमें से एक है शून्य से 1, जो वहाँ सरणी के अंत. और हम सरणी में अगर कहा जम्मू, सरणी मिनट से भी कम समय है तो हम जहां फिरसेआबंटितकरें हमारे न्यूनतम सूचकांकों है. और अगर मिनट के रूप में, मैं करने के बराबर नहीं है जहां में हम वापस यहाँ पर थे. हम पहली बार इस एक था जब बहुत पसंद है. इस मामले में, यह कम से शुरू होगा शून्य, यह दो खत्म किया जा रहा होगा. तो मिनट अंत में मैं बराबर नहीं होता. यही कारण है कि हमें पता है कि हम उन्हें स्वैप करने की जरूरत है. मैं एक ठोस उदाहरण की तरह लग रहा है इस तुलना में बहुत अधिक मदद मिलेगी. इसलिए मैं आप लोगों के साथ इस कोड करेंगे अब ठीक है और मैं इसे बेहतर हो जाएगा. प्रकार है कि उस तरह से काम करते हैं यह सिर्फ उन्हें देखने के लिए अक्सर बेहतर है. तो हम क्या करना चाहते है हम पहली बार सबसे छोटी चाहते हैं सरणी में अपनी स्थिति में तत्व. वास्तव में याकूब क्या कह रहा था. आप किसी भी तरह कि दुकान की जरूरत है. तो हम यहाँ शुरू करने जा रहे हैं सरणी पर पुनरावृति. हम यह कहने के लिए जा रहे हैं हमारे बस के साथ शुरू करने के लिए सबसे पहले एक. तो हम int करने जा रहे हैं सबसे छोटी मैं पर सरणी के बराबर है. तो एक बात, हर सूचना के लिए इस पाश कार्यान्वित समय, हम साथ एक कदम आगे शुरू कर रहे हैं. जब हम शुरू हम इस एक पर दिखेगा. हम के माध्यम से पुनरावृति अगली बार, हम इस एक में शुरू कर रहे हैं और यह हमारे सबसे छोटे मूल्य बताए. तो यह बुलबुला तरह के समान है हम जानते हैं कि जहां एक पास के बाद कि, यह पिछले तत्व हल है. चयन प्रकार के साथ, यह सिर्फ विपरीत है. हर दर्रे पर, हम जानते हैं कि पहले एक हल है. दूसरा पास करने के बाद, दूसरा एक सुलझा लिया जाएगा. और आप स्लाइड उदाहरण के साथ देखा था, हमारे छाँटे गए भाग सिर्फ बढ़ती रहती है. इसलिए हमारे सबसे छोटी एक सेट करके सरणियों के लिए मैं यह सब कर रहा है बाधा है क्या हम इतने के रूप में देख रहे हैं संख्या कम करने के लिए तुलना की हम बनाते हैं. कि हर किसी को मतलब? क्या आपको लगता है कि के माध्यम से चलाने के लिए मेरी जरूरत फिर धीमी या अलग शब्दों में? मैं खुश हूँ. ठीक. इसलिए हम भंडारण कर रहे हैं इस बिंदु पर मूल्य, लेकिन हम भी सूचकांक संग्रहीत करना चाहते हैं. इसलिए हम स्टोर करने के लिए जा रहे हैं छोटी से छोटी की स्थिति बस मैं होने जा रहा है, जो एक. तो अब याकूब संतुष्ट है. हम संग्रहीत बातें हैं. और अब हम के माध्यम से देखने की जरूरत सरणी की unsorted हिस्सा. इस मामले में यह तो हमारे unsorted होगा. यह मैं है. ठीक. तो क्या हम क्या करने जा रहे हैं एक पाश के लिए होने जा रहा है. आप जब भी जरूरत एक सरणी के माध्यम से पुनरावृति, अपने मन एक पाश के लिए करने के लिए जा सकते हैं. कुछ पूर्णांक कश्मीर के लिए तो हम क्या सोचते हैं equals-- कश्मीर के साथ शुरू करने के लिए बराबर करने के लिए जा रहा है? यह हम अपने सबसे छोटे रूप में सेट क्या है मूल्य और हम यह तुलना करना चाहते हैं. हम करने के लिए यह तुलना करने के लिए क्या चाहिए? यह सही है, यह अगले एक होने जा रहा है? इसलिए हम प्रारंभ की जा कश्मीर चाहते हैं मैं प्लस 1 शुरू करने के लिए. और हम इस मामले में कश्मीर चाहते हैं हम पहले से ही आकार यहां संग्रहीत है, तो हम सिर्फ आकार का उपयोग कर सकते हैं. आकार सरणी के आकार जा रहा है. और हम बस करना चाहते हैं एक-एक समय से कश्मीर का अद्यतन करें. कूल. तो अब हम खोजने की जरूरत है यहाँ सबसे छोटी तत्व. इसलिए हम के माध्यम से पुनरावृति, तो हम कहना चाहता हूँ, अगर कश्मीर में सरणी हमारी छोटी से छोटी value-- से कम है हम वास्तव में कर रहे हैं जहां यह है क्या का ट्रैक रखने छोटी से छोटी here-- तो हम पुन: असाइन करना चाहते हैं हमारे सबसे छोटे मूल्य क्या है. इस ओह, हम कर रहे हैं, इसका मतलब है कि यहां से होकर फिर. जो भी मूल्य यहाँ है नहीं हमारे सबसे छोटी बात. हम यह नहीं चाहते हैं. हम इसे पुन: असाइन करना चाहते हैं. हम इसे फिर नियत कर रहे हैं, क्या करते हैं आप यहाँ इस कोड में हो सकता है? हम पुन: असाइन करना चाहते हैं छोटी से छोटी और स्थिति. तो अब सबसे छोटी क्या है? छात्र: ऐरे कश्मीर. प्रशिक्षक: ऐरे कश्मीर. और स्थिति अब क्या है? के सूचकांक क्या है हमारी छोटी से छोटी मूल्य है? यह सिर्फ कश्मीर है. सरणी कश्मीर, कश्मीर तो, वे मैच. इसलिए हम चाहते हैं कि पुन: असाइन करना चाहता था. और हम, हमारी सबसे छोटी पाया तो बाद पाश के लिए इस के अंत में तो यहाँ हमने पाया है कि क्या हमारी छोटी से छोटी मूल्य है, तो हम सिर्फ यह स्वैप. इस मामले में, जैसे हमारे कहने छोटे मूल्य के यहाँ बाहर है. यह हमारी सबसे छोटी मूल्य है. हम बस है, जो यहाँ यह स्वैप करना चाहते हैं क्या तल पर कि स्वैप समारोह हम सिर्फ लिखा था, जो किया एक साथ एक दो मिनट पहले. तो यह परिचित दिखना चाहिए. और फिर यह सिर्फ पुनरावृति होगी के माध्यम से यह सभी तरह पहुँचता तक आप जिसका मतलब है कि अंत करने के लिए unsorted हैं कि शून्य तत्व है और सब कुछ सुलझा लिया गया है. समझ बनाने के लिए? अधिक concretely एक छोटी सी? कोड की मदद? छात्र: एक आकार के लिए, आप कभी नहीं वास्तव में यह परिभाषित या इसे बदलने, यह कैसे पता है? प्रशिक्षक: तो एक बात करने के लिए पूर्णांक आकार है यहाँ नोटिस. इसलिए हम इस sort-- प्रकार में कह रहे हैं इस में एक समारोह में यह है case-- चयन प्रकार, यह पारित कर दिया है समारोह के साथ में. इसे पारित नहीं किया गया तो अगर में, आप कुछ करना होगा सरणी की लंबाई के साथ की तरह या आप के माध्यम से पुनरावृति होगी लंबाई लगता है. लेकिन यह पारित कर दिया है, क्योंकि में, हम सिर्फ इसका इस्तेमाल कर सकते हैं. तुम सिर्फ उपयोगकर्ता को लगता है कि आप एक वैध आकार दिया कि वास्तव में प्रतिनिधित्व करता है आपके सरणी के आकार. कूल? तुम लोगों को इन के साथ किसी भी मुसीबत है या अधिक अभ्यास कोडिंग प्रकार चाहते हैं अपने दम पर, तुम चाहिए study.cs50 के पास जाओ. यह एक उपकरण है. वे एक चेकर है कि आप वास्तव में लिख सकते हैं. वे स्यूडोकोड करते हैं. वे और अधिक वीडियो और स्लाइड है मैं यहाँ का उपयोग लोगों सहित. आप अभी भी एक महसूस कर रहे हैं तो थोड़ा फजी, कि बाहर की कोशिश. हमेशा की तरह, भी, मुझसे बात आते हैं. प्रश्न? छात्र: आप कह रहे हैं आकार पहले से परिभाषित किया गया है? प्रशिक्षक: हाँ. आकार पहले से परिभाषित किया गया है यहां समारोह घोषणा में. तो आप उस में पारित किया गया है कि ग्रहण उपयोगकर्ता द्वारा, और सादगी की खातिर, हम मानते हैं कि करने के लिए जा रहे हैं उपयोगकर्ता हमें सही आकार दिया. कूल. इसलिए कि चयन प्रकार है. दोस्तों, मैं हम आज बहुत कुछ सीख रहे हैं. यह खंड के लिए एक सघन डेटा है. उस के साथ तो, हम जा रहे हैं प्रविष्टि प्रकार के लिए जाने के लिए. ठीक. इसलिए कि इससे पहले कि हम क्या करना है हमारे यहाँ क्रम विश्लेषण. , सबसे अच्छा मामले में तो मैं तुम से पता चला के बाद दी तालिका में पहले से ही मैं एक तरह से इसे दूर दे दी है. लेकिन सबसे अच्छा मामले क्रम, हम क्या सोचते हैं? सब कुछ हल. एन चुकता. किसी को भी एक व्याख्या है तुम क्यों लगता है? छात्र: आप through-- तुलना कर रहे हैं प्रशिक्षक: ठीक है. आप के माध्यम से तुलना कर रहे हैं. हर यात्रा में, भले ही हम एक एक करके इस decrementing रहे आप अभी के माध्यम से खोज कर रहे हैं सब कुछ छोटी से छोटी एक खोजने के लिए. तो भले ही अपनी छोटी मूल्य शुरुआत में यहाँ है आप अभी भी यह तुलना कर रहे हैं सब कुछ के खिलाफ यह छोटी से छोटी बात है बनाना. तो आप के माध्यम से चल रहा समाप्त होगा लगभग एन बार चुकता. ठीक है. और सबसे खराब स्थिति क्या है? आप जा रहे हैं, क्योंकि इसके अलावा एन चुकता कि एक ही प्रक्रिया कर रही हो. इस मामले में, चयन तो क्रमबद्ध कुछ है हम यह भी उम्मीद क्रम कि कॉल. तो दूसरों में, हम सिर्फ इतना पता ऊपरी और निचले सीमा. कैसे पागल के आधार पर हमारे सूची है या कैसे unsorted यह है, वे n या n चुकता बीच बदलती हैं. हम नहीं जानते. लेकिन चयन प्रकार का ही है क्योंकि सबसे खराब और सबसे अच्छा मामले, कि हमें बताता है कि इनपुट की कोई बात नहीं किस प्रकार हम यह पूरी तरह से है कि क्या है, हल या पूरी तरह से यह है, हल रिवर्स समय का एक ही राशि लेने के लिए जा रहा है. उस मामले में तो, आप अगर हमारी मेज से याद है, यह वास्तव में एक मूल्य था कि इन दो प्रकार नहीं है जो उम्मीद की क्रम है. इसलिए हम जानते हैं कि जब भी हम चयन क्रमबद्ध चलाने, यह करने के लिए गारंटी है एक n चुकता समय चला रहे हैं. वहाँ कोई परिवर्तनशीलता है. यह सिर्फ उम्मीद है. और, फिर से, आप सीखना चाहते हैं अधिक वसंत में सीएस 124 ले. ठीक है. हम इस एक देखा है. कूल. तो प्रविष्टि तरह. और मैं शायद जा रहा हूँ इस के माध्यम से ज्वाला. मैं तुम लोगों से यह कोड नहीं होगा. हम सिर्फ यह माध्यम से चलना होगा. तो सम्मिलन सॉर्ट तरह है चयन सॉर्ट के समान उस में हम दोनों एक unsorted है और सरणी का हिस्सा हल. लेकिन क्या अलग है कि है हम एक-एक कर के माध्यम से जाने के रूप में, हम अभी जो कुछ भी संख्या ले , हमारे unsorted में अगले है और इसे सही ढंग से सॉर्ट हमारे हल सरणी में. यह एक उदाहरण के साथ और अधिक समझ कर दूँगा. इतना सब कुछ unsorted के रूप में शुरू होता है, सिर्फ चयन प्रकार के साथ पसंद है. और हम में सॉर्ट करने के लिए जा रहे हैं हम किया गया है के रूप में आरोही क्रम. हमारी पहली पास पर तो हम पहले मान ले और हम ठीक है, आप कर रहे हैं, का कहना है अब अपने आप से एक सूची में. आप एक सूची में हैं क्योंकि अपने आप से, आप हल कर रहे हैं. होने के लिए बधाई इस सरणी में पहला तत्व. आप पहले से ही अपने दम पर सब हल कर रहे हैं. तो अब हम एक हल और एक unsorted सरणी. तो अब हम पहले ले. क्या यहाँ के बीच होता है और यहाँ, हम कहते हैं कि है ठीक है, हम को देखने के लिए जा रहे हैं हमारे unsorted सरणी के पहले मूल्य और हम में निवेश करने के लिए यह जा रहे हैं इसकी हल सरणी में सही जगह है. इसलिए हम 5 ले जाता है कि हमें क्या करना है और हम, 5 में से 3 से अधिक है, ठीक है, कहना तो हम सिर्फ सही डालें उस के अधिकार के लिए. हम अच्छा कर रहे हैं. तो फिर हम अपने अगले एक पर चलते हैं. और हम 2 ले. हम ठीक है, 2 कम है, का कहना है 3 से, तो हम जानते हैं कि यह है कि पर होने की जरूरत है अब हमारी सूची के सामने. तो क्या हम क्या हम नीचे 3 और 5 धक्का है और हम हैं कि पहले स्लॉट में 2 चाल है. तो हम बस में डालने रहे यह होना चाहिए सही जगह है. तो फिर हम पर देखने के लिए हमारे अगले एक, और हम 6 कहना. ठीक है, 6 से अधिक है हमारे हल सरणी में सब कुछ, तो हम सिर्फ अंत करने के लिए उस पर टैग. और फिर हम 4 पर दिखेगा. 4 से 6 से कम नहीं है, यह कम है 5 से लेकिन यह 3 से अधिक है. तो हम सिर्फ सही में डालें 3 और 5 के बीच के बीच. तो एक छोटे से बनाना अधिक ठोस सा, यहाँ की तरह है क्या हुआ विचार. प्रत्येक unsorted तत्व के लिए तो, हम जहां हल हिस्से में निर्धारित यह है. तो ध्यान में रखते हुए हल और unsorted, हम के माध्यम से और आंकड़ा पार करने के लिए है इसे हल सरणी में फिट बैठता है, जहां बाहर. और हम स्थानांतरण द्वारा डालें इसे सही करने के लिए नीचे तत्वों. और फिर हम सिर्फ रखना हम जब तक के माध्यम से पुनरावृति एक पूरी तरह से सॉर्ट की गई सूची है अब शून्य जहां unsorted है और हल तक ले जाता है हमारी सूची की सम्पूर्णता. तो, फिर से, यहां तक ​​कि चीजें बनाने के लिए अधिक ठोस, हम स्यूडोकोड है. तो बुनियादी तौर पर मैं है के लिए एन शून्य से 1 0 के बराबर, कि हमारे सरणी की सिर्फ लंबाई है. हम के बराबर है कि कुछ तत्व है पहले सरणी या पहले सूचकांकों. हम बराबर जम्मू निर्धारित किया है. जम्मू से अधिक है तो, जबकि शून्य और सरणी, जम्मू शून्य से 1 से अधिक है तत्व, यह सब इसलिए कर रहा है कि यकीन कर रहा है आपकी जम्मू वास्तव में प्रतिनिधित्व करता है सरणी की unsorted भाग. अभी भी वहाँ चीज़ें है इसलिए जब सॉर्ट और जम्मू शून्य से एक क्या is-- को तत्व उसकी है? जम्मू यहां परिभाषित नहीं किया गया. यह कष्टप्रद की तरह है. ठीक. वैसे भी. इसलिए जम्मू शून्य से 1, आप जाँच कर रहे हैं यह पहले तत्व. आप ठीक है, तत्व है, कह रहे हैं मैं चलो am-- जहाँ भी पहले वास्तव में यह बाहर खींचना. तो चलो यह है हम कहते हैं हमारे दूसरा पास पर पसंद है. तो मैं बराबर होने जा रहा है 1 को, जो यहाँ है. तो मैं 1 के बराबर होने जा रहा है. यह 2, 4, 5, 6, 7 होगा. ठीक है. इस मामले में तो हमारे तत्व 4 के बराबर होने जा रहा है. और हम हैं कि कुछ J है 1 के बराबर होने जा रहा. ओह, जम्मू decrementing है. यही कारण है कि यह क्या है. इसलिए जम्मू मैं करने के लिए बराबर है, तो यह क्या है कहावत है, हम आगे बढ़ना है कि है हम सिर्फ यह सुनिश्चित कर रहे हैं हम खत्म नहीं कर रहे हैं कि हम कोशिश कर रहे हैं जब इस तरह अनुक्रमण हमारे सॉर्ट की गई सूची में चीजें डालने के लिए. इसलिए जम्मू इस मामले में 1 के बराबर है और जब इसलिए सरणी जम्मू शून्य से 1 one-- सरणी जम्मू ऋण कि अगर इस case-- में 2 है तत्व से अधिक, तो यह सब कर रही है बातें नीचे जा रहा है. इस मामले में, सरणी जम्मू शून्य से एक तो 2 है जो सरणी शून्य होगा. 2, 4 से अधिक नहीं है इसलिए इस पर अमल नहीं करता है. तो पारी नीचे कदम नहीं करता है. क्या इस यहाँ करता है नीचे अपने हल सरणी चलती. इस मामले में, वास्तव में, हम do-- सकता है, इस 3 बनाते हैं. तो हम साथ के माध्यम से चलने के लिए कर रहे हैं इस उदाहरण के लिए, हम यहाँ अब कर रहे हैं. यह हल है. इस unsorted है. कूल? तो मैं तो, 2 के बराबर है हमारे तत्व 3 के बराबर है. और हमारे जे 2 के बराबर है. तो हम हम और के माध्यम से देखो ठीक है, सरणी जम्मू शून्य से एक है, का कहना है तत्व से अधिक हम देख रहे हैं कि? और जवाब सही, हां में है? 4 3 और जम्मू से अधिक है 2 है, इसलिए इस कोड को निष्पादित करता है. तो अब हम पर एक सरणी क्या 2, यहीं तो, हम उन्हें स्वैप. तो हम बस ठीक है, सरणी, कहना 2 पर अब 3 होने जा रहा है. और जम्मू बराबर करने के लिए जा रहा है 1 है जो जम्मू शून्य से 1,. यही कारण है, भयानक है लेकिन तुम लोग विचार मिलता है. जम्मू अब 1 के बराबर है. और सरणी जम्मू बस होने जा रहा है 4 थी जो हमारे तत्व, के बराबर. मैं कुछ मिट मैं नहीं करना चाहिए है या miswrote कुछ, लेकिन तुम लोगों को विचार मिलता है. यह n पर ले जाते हैं. इस थे तो और, अगर यह पाश होगा फिर और यह ठीक है, जे अब 1 है, कहेंगे. और सरणी जम्मू शून्य से 1 अब 2 है. 2 हमारे तत्व से कम है? कोई? यही कारण है कि हम है कि इसका मतलब है इस तत्व डाला हमारे हल सरणी में सही जगह में. तो फिर हम इस ले जा सकते हैं और हम कहते हैं, ठीक है, हमारे हल सरणी यहाँ है. और यह इस संख्या 6 ले और होगा जैसे, ठीक है, यह संख्या 6 से कम है? कोई? कूल. हम ठीक कर रहे हैं. इसे फिर से करना. हम 7 कहना. अंत से 7 कम है हमारे हल सरणी की? नहीं. तो हम ठीक कर रहे हैं. तो इस हल किया जाएगा. असल में यह सब होता है इसे ले कह रहा है का पहला तत्व अपने unsorted सरणी, यह हो जाता है जहां यह पता लगाने आपके हल सरणी में. और यह सिर्फ ख्याल रखता है स्वैप के ऐसा करने के लिए. आप मूल रूप से बस गमागमन रहे जब तक यह सही जगह में है. दृश्य छवि आप कर रहे हैं कि है कि ऐसा करके सब कुछ नीचे घूम रहा है. तो यह आधा बुलबुले की तरह क्रमबद्ध-esque एक है. अध्ययन में 50 की जाँच करें. मैं अत्यधिक कोशिश की सिफारिश अपने दम पर इस कोड को. आप किसी भी मुद्दे या आप चाहते हैं एक प्रविष्टि प्रकार के लिए नमूना कोड देखते हैं, कृपया मुझे बताओ. मैं हमेशा के आसपास रहा हूँ. तो सबसे ज्यादा मामले क्रम और सबसे अच्छा मामले क्रम. आप आदमी को मैं पहले से ही मेज से देखा यह चुकता और एन दोनों N, आप दिखाया. इतनी तरह की हम बात क्या की बंद रहा हमारे पिछले प्रकार के साथ के बारे में, सबसे खराब मामले क्रम है कि अगर यह पूरी तरह से unsorted है, हम इन एन बार के सभी तुलना करने के लिए है. हम तुलना की एक पूरी बहुत कुछ यह रिवर्स क्रम में है क्योंकि अगर, हम, ठीक है, यह कहने के लिए जा रहे हैं , यह अच्छा है, एक ही है और इस एक तुलना करना होगा पहले एक के खिलाफ वापस ले जाया जाना है. और हम की ओर पाने के रूप में पूंछ अंत, हम हैं तुलना तुलना, और करने के लिए सब कुछ के खिलाफ की तुलना करें. तो यह जा रहा है लगभग एन चुकता. यह तो आप सही है आप अच्छा कर रहे हैं, 2, ठीक है, का कहना है. 3, आप 2 की तुलना कर रहे हैं. आप अच्छे हो. 4, तुम सिर्फ पूंछ से तुलना करें. आप अच्छे हो. 6, तुम ठीक हो, पूंछ से तुलना करें. इसलिए हर जगह के लिए यह पहले से ही है तो हल, आप एक तुलना कर रहे हैं. तो यह सिर्फ एन. और हम एक सबसे अच्छा मामले क्रम है क्योंकि और एन एन के एक सबसे खराब स्थिति क्रम के चुकता, हम कोई उम्मीद क्रम है. यह बस पर निर्भर करता है वहाँ हमारी सूची की अराजकता. और फिर, एक और ग्राफ और एक अन्य टेबल. प्रकार के बीच मतभेद तो. मैं बस के माध्यम से हवा करने के लिए जा रहा हूँ, मैं हम बड़े पैमाने पर बात की है की तरह लग रहा है कैसे वे सभी तरह के बारे में की बदलती हैं और एक साथ जोड़ने. तो क्रमबद्ध पिछले एक है विलय मैं के साथ तुम लोग बोर करेगा. हम एक बहुत रंगीन तस्वीर है. तो प्रकार का एक पुनरावर्ती एल्गोरिथ्म है विलय. तो तुम लोगों को पता है क्या एक पुनरावर्ती समारोह है? किसी को भी कहना चाहते हैं? आप कोशिश करना चाहते हैं? तो एक पुनरावर्ती समारोह बस है खुद कहता है कि एक समारोह. तो तुम लोग परिचित हैं फाइबोनैचि अनुक्रम के साथ, कि क्योंकि पुनरावर्ती समझा है आप पिछले दो ले और उन्हें एक साथ जोड़ने अपने अगले एक पाने के लिए. तो पुनरावर्ती, मुझे हमेशा लगता है एक सर्पिल तरह के रूप में प्रत्यावर्तन की तो आप यह नीचे में चढ़ती पसंद कर रहे हैं. लेकिन यह सिर्फ एक समारोह है कि खुद कहता है. और, वास्तव में, वास्तव में जल्दी से मैं कि कैसा लग रहा है आपको दिखा सकते हैं. हम देखें तो यहाँ तो पुनरावर्ती, यह है पुनरावर्ती रास्ता एक सरणी से अधिक योग करने के लिए. तो सब है कि हम क्या है हम योग समारोह एक आकार और एक सरणी लेता है कि राशि. और अगर तुम नोटिस, आकार एक-एक समय से decrements. और यह सब होता एक्स के बराबर है यदि है zero-- इसलिए यदि सरणी के आकार यह शून्य रिटर्न zero-- के बराबर है. अन्यथा यह इस रकम सरणी के अंतिम तत्व, और तब की राशि लेता है सरणी के बाकी. तो यह सिर्फ यह टूट रहा है और छोटे छोटे समस्याओं में. लंबी कहानी संक्षेप, प्रत्यावर्तन, खुद कहता है कि समारोह. कि तुम इस से बाहर हो गया सब है, कि एक पुनरावर्ती समारोह में है. आप 51 ले, तो आप बहुत मिल जाएगा, प्रत्यावर्तन के साथ बहुत सहज. यह वास्तव में अच्छा है. यह तरह में समझदारी है बाहर 3 हूँ एक रात. और मैं, क्यों की तरह था मैं इस का उपयोग कभी नहीं किया है? असल में, मर्ज प्रकार के लिए तो क्या ऐसा करने जा रहा है यह बात है इसे तोड़ने के नीचे और इसे तोड़ने के लिए जा रहा यह सिर्फ एक तत्व है जब तक नीचे. एकल तत्वों सॉर्ट करने के लिए आसान कर रहे हैं. हम देखते हैं कि. आप एक तत्व है, यह है पहले से ही हल माना. N तत्वों की एक इनपुट पर तो, एन कम से कम 2 है, सिर्फ इतना है कि क्योंकि इसका मतलब लौटने यह हमने देखा है के रूप में 0 या 1 या तो है. उन हल तत्व माना जाता है. अन्यथा यह आधे में टूट गया. दूसरा सॉर्ट, पहली छमाही क्रमबद्ध आधा, और फिर उन्हें एक साथ विलय. क्यों यह मर्ज प्रकार का कहा जाता है. हम इन सुलझा लेंगे तो हम यहाँ है. इसलिए हम उन्हें कर रखना सरणी आकार 1 है जब तक. यह 1 है, इसलिए जब हम बस वापस जाने इस एक हल सरणी है क्योंकि, और यह एक हल सरणी है, और वह है एक हल सरणी, हम सब हल कर रहे हैं. तो फिर हम क्या हम है उन्हें एक साथ विलय शुरू करते हैं. तो जिस तरह से आप कर सकते हैं विलय के बारे में सोचना तुम सिर्फ छोटे हटाने उप सरणियों में से प्रत्येक की संख्या और सिर्फ उभरा सरणी के लिए संलग्न. तो अगर हम जब तुम, यहाँ देखो इन सेटों हम 4, 6, और 1 है. हम इन मर्ज करना चाहते हैं, हम इन पहले दो पर देखने के लिए और हम 1 छोटा होता है, ठीक है, का कहना है, यह सामने करने के लिए चला जाता है. 4 और 6, तुलना करने के लिए कुछ भी नहीं है यह सिर्फ अंत करने के लिए उस पर टैग करने के लिए. हम इन दो गठबंधन है, हम बस , इन दोनों के छोटे से एक ले तो यह 1 है. और अब हम ले इन दो, तो 2 से छोटे. इन दो, 3 की छोटी. इन दो, 4, 5, 6 के छोटे. तो तुम सिर्फ इन खींच रहे हैं. और वे है क्योंकि पहले से सुलझा लिया गया, आप सिर्फ एक है तुलना वहाँ हर बार. यहाँ तो अधिक कोड, सिर्फ प्रतिनिधित्व. तो आप बीच में शुरू और आप क्रमबद्ध बाएँ और दाएँ और तो आप सिर्फ उन विलय. और हम कोड नहीं है के लिए यहीं विलय. लेकिन, फिर से, आप पर जाना 50 अध्ययन, यह वहाँ हो जाएगा. अन्यथा मुझे बात करने आते हैं यदि आप अभी भी उलझन में है. यहाँ तो शांत बात यह है कि सबसे अच्छी स्थिति है, सबसे खराब स्थिति, और उम्मीद क्रम एन सभी प्रवेश में जो कर रहे हैं हम है की तुलना में कहीं बेहतर है हमारे प्रकार के आराम के लिए देखा. हमने देखा एन चुकता कर लिया है और वास्तव में क्या हम जो महान है, एन लॉग है यहां मिलता है. वह यह है कि कितना बेहतर कर रहे हैं. इस तरह एक अच्छा वक्र. इसलिए बहुत अधिक कुशल है. आप कभी भी कर सकते हैं, उपयोग प्रकार का विलय. यह समय की बचत होगी. तो फिर, जैसा कि हमने कहा, अगर यदि आप इस निचले क्षेत्र में नीचे रहे हैं यह कि नहीं कर सकता है एक फर्क इतना. आप हजारों करने के लिए उठो और जानकारी के हजारों, आप निश्चित रूप से एक चाहते अधिक कुशल एल्गोरिथ्म. सभी की और, फिर से, हमारी प्यारी तालिका तुम लोग आज सीखा कि तरह. इसलिए मैं इसे एक घने दिन हो गया है पता है. यह जरूरी नहीं जा रहा है अपने pset के साथ मदद करने के लिए. लेकिन मैं सिर्फ एक त्याग करना चाहते हैं कि खंड सिर्फ psets के बारे में नहीं है. यह सब सामग्री उचित है अपने midterms के लिए खेल. और तुम सीएस के साथ जारी करना भी अगर, ये वास्तव में महत्वपूर्ण बुनियादी बातों हैं कि आप को पता है की आवश्यकता होगी. तो कुछ दिनों में हो जाएगा एक थोड़ा अधिक pset मदद, लेकिन कुछ सप्ताह हो जाएगा और अधिक वास्तविक सामग्री कि सुपर प्रतीत नहीं हो सकता अब ठीक है आप के लिए उपयोगी, आप जारी रखते हैं, लेकिन मैं वादा करता हूँ पर बहुत, बहुत उपयोगी हो जाएगा. तो यह है कि खंड के लिए है. तार के लिए नीचे. मैं एक मिनट के भीतर ऐसा किया था. लेकिन वहाँ तुम जाओ. और मैं डोनट्स या कैंडी होगा. एलर्जी किसी को है वैसे कुछ भी,? अंडे और दूध. तो डोनट्स एक नहीं हैं? ठीक. ठीक है. चॉकलेट नहीं? स्टारबर्स्ट. Starbursts अच्छा कर रहे हैं. ठीक. हम करने जा रहे हैं फिर अगले सप्ताह स्टारबर्स्ट. यही कारण है कि मैं क्या मिलेगा है. तुम लोग एक महान सप्ताह है. अपनी कल्पना पढ़ें. आप किसी भी प्रश्न हैं मुझे जानते हैं. Pset दो ग्रेड होना चाहिए गुरुवार को आप को बाहर. आप किसी भी सवाल है, तो मैं कुछ श्रेणीबद्ध तरीके के बारे में या क्यों मैं जिस तरह से मैं कुछ श्रेणीबद्ध , कृपया मुझे ईमेल किया था, मुझसे बात आते हैं. मैं एक छोटे से पागल इस हूँ सप्ताह, लेकिन मैं वादा करता हूँ मैं अभी भी 24 घंटे के भीतर जवाब देंगे. तो एक महान सप्ताह, हर किसी को है. अपने pset पर गुड लक.