رئيس 1: يا الجميع! أهلا بكم من جديد إلى القسم. سعيدة للغاية لرؤية العديد منكم سواء هنا، وكل من يراقب على الانترنت. لذلك، كالعادة يعود ترحيب. أرجو أن كل ما كان جميل عطلة نهاية الأسبوع، والكامل من الراحة والاسترخاء. كانت جميلة من أمس. لذلك، أرجو أن تتمتع في الهواء الطلق. أولا حتى بضعة إعلانات. الدرجات. لذلك، يجب أن معظمكم قد حصلت على البريد الإلكتروني من لي عن PSET خدش الخاص بك، وكذلك الدرجات لPSET 1. لذلك، فإن الأمور مجرد زوجين. تأكد من استخدام check50 في style50. وتهدف هذه لتكون موارد لليا رفاق، للتأكد من أنك تحصل العديد من النقاط كما يمكنك دون أن تفقد مبرر لها. لذلك، أشياء مثل أسلوب هي مهمة جدا. نحن نذهب لخلع لذلك. البعض منكم قد يكون بالفعل لاحظت أن من PSET الخاص بك. وcheck50 هو مجرد طريقة سهلة حقا للتأكد من اننا يعود في الواقع ما يحتاج إلى أن تعاد للمستخدم، وبأن كل شيء يعمل بشكل صحيح. على المذكرة الثانية، تأكد الخاص بك تحميل الأشياء إلى المجلد الصحيح. يجعل حياتي مجرد أصعب قليلا إذا قمت بتحميل PSET 2 في 1 PSET لأنه عندما أحمل أشياء، انهم لا تحميل بشكل صحيح. وأنا أعلم أنه قليلا متزعزع في نظام لتعتاد على، ولكن مجرد أن تكون فائقة حذرا، إلا إذا كان بالنسبة لي، حتى عندما كنت الحصول على رسائل البريد الإلكتروني في مثل 02:00 وأنا الدرجات. إذا لم تسبب لي للبحث في كل مكان لPSET الخاص بك. بارد. وأنا أعلم أنه في وقت مبكر، ولكن أنا تماما حصلت تؤخذ على حين غرة من خلال مقال هذا بسبب هذا الجمعة، أن كان أساتذتي تماما مثل، أوه نعم. تذكر، لديك مقال المقرر يوم الجمعة. لذلك، وأنا أعلم لا أحد يحب أن نفكر في انتخابات التجديد النصفي، ولكن الأولى هي مسابقة على 15 أكتوبر، أكتوبر الذي بدأ هذا الاسبوع. لذلك، قد يكون عاجلا مما كنت متوقعا هو كل شيء. بحيث كنت لا القيت على حين غرة عندما أذكر القسم الأسبوع المقبل أن أوه، مسابقة الاسبوع الخاص بك المقبل، فكرت فما استقاموا لكم فاستقيموا تعطيك قليلا أكثر من رؤساء حتى الآن. لذلك، مشكلتك مجموعة، رقم ثلاثة. كيف قرأ الناس المواصفات من باب الفضول؟ موافق. وصلنا زوجين. نوع من أسفل من الماضي ولكن هذا الأسبوع على ما يرام. وأنا أعلم أنه كان من الجميل. حتى الخروج. بالتأكيد بعد الحصول على القيام به اليوم قراءة المواصفات الخاصة بك على الأقل مثل محاولة تحميل كود التوزيع والتشغيل مثل الأولية الأولى الشيء الذي يطلبونه لك. لأننا تستخدم كود التوزيع ومكتبة أننا قمت فقط تم using-- --It فقط للمرة الثانية فعلناه هذا PSET، أشياء مجنونة يمكن أن يحدث مع الأجهزة الخاصة بك، وتريد أن تجد أن من الآن مقابل في وقت لاحق. لأنه إذا كان ليلة الخميس أو أنه ليلة الاربعاء ولسبب الجهاز الخاص بك لا فقط تريد تشغيل مع المكتبة أو مع التوزيع رمز، وهذا يعني لا يمكنك حتى تبدأ في فعل الترميز. لأنك لا يمكن أن تحقق لنرى ما اذا كان يعمل. الخاص بك لا gonna تكون قادرة لمعرفة ما اذا كان يجمع. كنت تريد أن تأخذ الرعاية من تلك في وقت مبكر هذا الأسبوع، عندما لا يزال بإمكانك الكتابة لي أو واحدة من TFS أخرى، ويمكننا الحصول على تلك الثابتة. لأن تلك هي القضايا التي سوف يمنعك من إحراز أي تقدم حقيقي. انها ليست مثل علة واحدة، أن يمكنك فقط نوع من القفز فوق. إذا كنت تواجه مشاكل مع الخاص بك الأجهزة أو كود التوزيع، كنت تريد حقا للحصول على أن تؤخذ رعاية عاجلا وليس آجلا. لذلك حتى لو كنت لا ستعمل في الواقع بدء الترميز، تحميل التوزيع رمز، قراءة المواصفات، تأكد كل شيء على ما يعملون هناك. موافق؟ إذا كنت تستطيع فعل ذلك، وأنا وعد حياتكم ستكون أسهل. وهكذا ربما كنت ذاهب للقيام بذلك الحق الآن؟ موافق. لذلك، هناك أي أسئلة؟ أي الأمور اللوجستية؟ الجميع جيدا؟ موافق. تنويه بالنسبة لأولئك كنت في الغرفة وعلى الانترنت. أنا ذاهب ليكون محاولة للتبديل بين PowerPoint في الجهاز لأننا ذاهبون أن القيام ببعض الترميز اليوم مطلب شعبي للمجهول بعثت اقتراح استطلاع الأسبوع الماضي. لذلك، فإننا سوف تفعل بعض الترميز. لذلك، إذا كنت تريد الرجال أيضا لاطلاق النار حتى الأجهزة الخاصة بك، ويجب أن قد حصلت على رسالة بريد إلكتروني من لي، مع ملف عينة. لا تتردد في القيام بذلك. لذلك، نحن ذاهبون الى الحديث عن GDB، وهو المصحح. انها سوف تساعدك نوع من معرفة أين الأمور تسير على نحو خاطئ في التعليمات البرمجية. انها حقا مجرد طريقة لمضاعفة من خلال التعليمات البرمجية كما أنه يحدث، وتكون قادرة على طباعة المتغيرات أو رؤية ما يحدث في الواقع تحت غطاء محرك السيارة الآيات برنامجك تشغيل فقط، انها مثل يخطأ، وكنت مثل أي فكرة ما حدث هنا. أنا لا أعرف ما خط فشلت في. أنا لا أعرف أين ذهب خطأ. لذلك، GDB يتم الانتقال إلى مساعدتك في ذلك. أيضا، إذا قررت ل مواصلة نعم، واتخاذ 61، سيكون حقا، حقا أن يكون لديك أفضل صديق، والسبب استطيع ان اقول لكم لأنني ذاهب من خلال تلك الفئة. ونحن في طريقنا للبحث في ثنائي البحث، والذي إذا يا رفاق نتذكر عظيم المثال دليل الهاتف مشهد من الطبقة. سنكون تنفيذ ذلك، و المشي من خلال ذلك أكثر قليلا، ومن ثم نحن ذاهبون من خلال أربعة أنواع مختلفة، وهي فقاعة، الاختيار، والإدراج، ودمج. بارد. لذلك، GDB كما ذكرت، هو المصحح. وهذه هي نوع من كبير الأشياء، وظائف كبيرة أو أوامر التي تستخدمها في GDB، وأنا سوف المشي يمكنك من خلال التجريبي منه في الثانية. لذلك، هذا ليس عدلا تنوي البقاء المجرد. وسأحاول جعله الخرسانة ممكن ليا رفاق. لذلك، كسر. أنه سوف يكون إما كسر مثل، بعض الأرقام، التي يمثل خط في البرنامج، أو يمكنك تسمية وظيفة. لذلك، إذا أنت تقول كسر الرئيسي، فإنه سيتم التوقف عند الرئيسي، وتتيح لك المشي من خلال تلك الوظيفة. وبالمثل، إذا كان لديك بعض خارجي تعمل مثل مبادلة أو مكعب، إن نظرنا في الاسبوع الماضي. إذا أنت تقول كسر واحد من هؤلاء، كلما يضرب برنامجك ذلك، انها سوف ننتظر منك ل أقول ذلك ما يجب القيام به. قبل ان مجرد تنفيذ ذلك أنت يمكن في الواقع خطوة داخل وظيفة ونرى ما يحدث. هكذا، وبعد ذلك، يتخطى بقليل السطر التالي، يذهب أكثر الوظائف. خطوة. هذه كلها مجردة قليلا. لذلك، أنا مجرد الذهاب لتشغيل خلالهم، ولكن سوف تراهم في استخدامها في الثانية. خطوة الى وظيفة. بما كنت أقوله، مثل مع مبادلة، فإنه سوف تسمح لك في الواقع كما لو كنت مثل يخطو داخل جسديا، يمكنك الفوضى مع هذه المتغيرات، والطباعة من ما هي عليه، ونرى ما يحدث. سيتم طباعة قائمة حرفيا فقط من رمز المحيطة بها. لذلك، إذا كنت من النوع تنس أين أنت في البرنامج، أو كنت أتساءل ما يجري حوله، هذا ستطبع للتو شريحة من مثل خمسة أو ستة خطوط من حوله. لذلك، يمكنك الحصول على المنحى عن مكان وجودك. طباعة بعض متغير. لذلك، إذا كان لديك مفتاح مثل في قيصر، وأننا سوف ننظر. يمكنك أن تقول مفتاح طباعة في أي لحظة. انها سوف اقول لكم ما هي قيمة ذلك ذلك، وربما في مكان ما على طول الطريق، كنت overwrote المفتاح الخاص. يمكن أن أقول لكم فعلا أن ل هل يمكن أن نلاحظ في الواقع أن قيمة. في السكان المحليين، ويطبع فقط من المتغيرات المحلية. لذلك، في أي وقت كنت ضمن حلقة، وكنت فقط أريد أن أرى مثل، أوه. ما هو لي أنا؟ ما هي قيمة هذا المفتاح أنني تهيئة هنا؟ ما هي الرسالة في هذه المرحلة؟ سيكون مجرد طباعة جميع من هؤلاء، حتى يتسنى لك لا داعي للفردي أقول، أولا طباعة طباعة الرسائل. طباعة مفتاح. ثم عرض. ما الذي يفعله هو كما كنت الخطوة من خلال هذا البرنامج، انها سوف مجرد التأكد من أنها عرض بعض متغير معين في كل نقطة. حتى يتسنى لك also-- --it من نوع من الاختصار فيها لم يكن لديك على الاستمرار مثل، أوه. مفتاح الطباعة أو طباعة أولا انها فقط سوف تفعل تلقائيا لانها لكم. لذلك، مع ذلك، نحن ذاهبون لنرى كيف ستسير الامور. انا ذاهب الى محاولة والتبديل أكثر من الأجهزة بلدي. أرى إن كنت أستطيع القيام بذلك. جميع. نحن ذاهبون لمجرد مرآة لها. لا يوجد شيء مجنون على جهاز الكمبيوتر المحمول على أي حال. موافق. هذا يحتاج إلى أن يكون هذا واحد. انها صغيرة جدا. دعونا نرى ما اذا كنا نستطيع القيام بذلك. موافق. أليس من الواضح يكافح هنا قليلا، ولكن نحن سوف تحصل عليه في مومنتو. موافق. نحن مجرد الذهاب الى زيادة هذا. موافق. يمكن للجميع نوع من يرى ذلك؟ ربما قليلا؟ وأنا أعلم أنه صغير قليلا. لا يمكنك معرفة تماما خارج كيفية جعل هذا أكبر. إذا كان أي شخص يعرف. لا أحد يعرف كيفية جعله أكبر؟ موافق. ونحن في طريقنا للفة معها. لا يهم على أي حال لأنه فقط هذا هو الرمز الذي يجب عليك الرجال ديك. ما هو أكثر أهمية هي محطة هنا. وعلينا هنا لماذا هو صغير جدا؟ الإعدادات. أوه. صحيح آيك. كيف هذا؟ من هناك. هو أفضل للجميع؟ موافق،. بارد. تعلمون عندما كنت في CS صعوبات تقنية الطبقة هي نوع من جزء من the-- لذلك، دعونا مسح هذا. موافق. لذلك، والحق هنا في القسم، الذي كان لدينا هنا. قيصر هو ملف تنفيذي. لذلك أنا جعلت. لذلك، هناك شيء واحد لتحقيق مع GDB هو أنه يعمل فقط على الملفات القابلة للتنفيذ. لذلك، لا يمكن تشغيله على dotsy. لديك لجعل الواقع تأكد من أن التعليمات البرمجية يجمع، وأنه يمكن بالفعل تشغيل. لذلك، تأكد من أنه إذا لم يحدث ذلك تجميع، والحصول عليها لتجميع، بحيث يمكنك النوع من تشغيل من خلال ذلك. لذلك، لبدء GDB، كل ما عليك فعله، غلوريا نوع GDB، وبعد ذلك فقط لل الملف الذي تريد. أنا دائما كتابتها قيصر. ولكن هل نريد أن نتأكد من منذ حان للتنفيذ، نقطة فلاش تي بحيث يعني وأنت تسير لتشغيل CSI كنت تريد الذهاب لتنفيذ هذه الملفات إما مع المصحح. موافق. لذلك، يمكنك أن تفعل ذلك، وتحصل هذا النوع من رطانة. انها مجرد كل شيء حول المصحح. لم يكن لديك حقا ل تقلق بشأن ذلك الآن. وكما ترون، لدينا هذا أقواس مفتوحة، الناتج المحلي الإجمالي، أقواس وثيقة، ومجرد نوع من يشبه سطر الأوامر لدينا، أليس كذلك؟ لذلك، ما نريد أن do-- --So، فإن أول شيء غير أننا نريد أن اختيار مكان لكسرها. لذلك، هناك خلل واحد في هذا البرنامج قيصر أن أعرض، أن ونحن في طريقنا لمعرفة ذلك. ذلك ما تقوم به هو أنه يأخذ مدخلات Barfoo في كل مباراة دولية، و لسبب ما لا يغير A. فإنه يترك فقط وحدها، هل كل شيء صحيح، ولكن الرسالة الثانية ويبقى دون تغيير. لذلك، نحن ذاهبون لمحاولة و معرفة لماذا هذا هو. لذا، فإن أول شيء كنت عادة تريد أن تفعل كلما تبدأ في GDB هو معرفة إلى أين كسرها. حتى قيصر هو برنامج قصير جدا. لدينا وظيفة واحدة فقط، أليس كذلك؟ ما كان لدينا في وظيفة قيصر؟ هناك واحد فقط وظيفة، والحق الرئيسي؟ الرئيسي هو وظيفة عن كل ما تبذلونه من البرامج. إذا لم يكن لديك منزل، وأنا قد تكون قلقة بعض الشيء في الوقت الراهن، ولكن أرجو أن كل ما كان في منزل هناك. لذلك، ما يمكننا القيام به هو أننا يمكن أن فقط كسر الرئيسي، تماما مثل ذلك. لذلك، فإنه يقول: موافق. وضعناها لدينا نقطة توقف واحدة هناك. لذلك، والآن الشيء هو أن نتذكر قيصر أمر واحد يأخذ وسيطة سطر الحق ونحن لم نفعل ذلك في أي مكان بعد. لذا، ما عليك القيام به هو عندما كنت في الواقع تذهب الى تشغيل برنامج، أي البرنامج الذي كنت يعمل في GDB الذي يحتاج سطر الأوامر الحجج، وأنت تسير لمدخلات عند بدء تشغيل أول تشغيله. لذلك، في هذه الحالة، ونحن نفعل تشغيل مع مفتاح لثلاثة. وسوف تبدأ فعلا. لذلك، إذا كنت ترى هنا، لدينا إذا RC لا تساوي 2. حتى إذا كنت الرجال قد كل هذا الملف أنني أرسلت ما يصل سترى أن هذا مثل السطر الأول الوظيفة الرئيسية لدينا، أليس كذلك؟ انها فحص لمعرفة ما إذا كان لدينا العدد الصحيح من الحجج. لذلك، إذا كنت أتساءل إذا RC هو الصحيح، يمكنك أن تفعل شيئا تماما مثل طباعة RC. RC من اثنين، وهو ما كنا نتوقعه، أليس كذلك؟ لذلك، يمكننا أن نذهب بعد ذلك، وتستمر خلال. لذلك، لدينا بعض المفتاح هناك. ويمكننا طباعة مفتاح لدينا للتأكد من هذا هو الصحيح. مثيرة للاهتمام. ليس تماما ما كنا نتوقعه. لذلك، هناك شيء واحد لتحقيق مع GDB أيضا، و انها ليست حتى تصل فعلا بعد ذلك، أن الخط الذي رأيت فقط يتم تنفيذه فعليا. لذلك، في هذه الحالة مفتاح لم يتم تعيينه بعد. لذلك، المفتاح هو بعض القيمة القمامة التي تراها على أسفل هناك. سلبي $ 120-- في المليار --It وشيء أشياء غريبة أليس كذلك؟ انها ليست المفتاح الذي كنا نتوقعه. ولكن إذا ضربنا التالي، ومن ثم نحن محاولة ومفتاح طباعة، انها الثلاث. الجميع يرى ذلك؟ لذلك، إذا كنت تحصل على شيء ان كنت مثل، الانتظار. هذا هو تماما خطأ، وأنا لا أعرف كيف يمكن أن يحدث هذا لأن كل ما أريد القيام به هو تخصيص رقم، متغير، محاولة ضرب بعد ذلك، حاول الطباعة مرة أخرى، ونرى ما اذا كان يعمل. لأنه لن يؤدي الا الى تنفيذ و في الواقع تعيين شيء بعد ضرب التالي. من المنطقي أن الجميع؟ اه هاه؟ المتحدث 2: عند عشوائي أرقام ماذا يعني ذلك؟ رئيس 1: انها مجرد عشوائي. انها مجرد القمامة. انها مجرد شيء بأن ما تتمتعون به سوف الكمبيوتر تعيين عشوائيا. بارد. لذلك، والآن يمكننا أن ننتقل من خلال، وذلك الآن لدينا هذا GetString نص عادي. لذا، اسمحوا لي أن أعرض فقط ما سيحدث عندما ضربنا التالي هنا. لدينا نوع من GDB يختفي، أليس كذلك؟ ذلك لأن GetString تنفذ الآن، أليس كذلك؟ لذلك، عندما رأينا نص عادي يساوي GetString، أقواس مفتوحة ولية، ونحن ضرب المقبل، والتي لديها أعدم فعلا الآن. لذلك، انها تنتظر لنا لإدخال شيء. لذلك، نحن ذاهبون لإدخال طعامنا الذي ما انها فشلت كما قلت لك وتقول فقط انه الانتهاء من تنفيذ، على أن يغلق قوس يعني انها الخروج من تلك الحلقة. لذلك، فإننا يمكن أن تصل بعد ذلك، والآن، وأنا من أنك مألوفة من قيصر، وهذا هو، ما هو هذا الخط تنوي القيام به. انها لكثافة العمليات I يساوي 0، N يساوي Strlen، نص عادي، ومن ثم أنا أقل من N، I، زائد، زائد. ما هي هذه الحلقة تنوي القيام به؟ فتح رسالتك. بارد. لذلك، دعونا نبدأ القيام بذلك. لذلك، يجب أن هذا الشرط مباراة، لأول واحد لدينا؟ لو انها B، انها نص عادي أولا نحن يمكن الحصول على معلومات عن السكان المحليين لدينا. لذلك، أنا هو صفر، وإذا الستة، التي نتوقع، والمفتاح لدينا هو ثلاثة. كل ذلك له معنى، أليس كذلك؟ هذه الأرقام كلها بالضبط ما ينبغي أن يكون. لذلك، همهمة؟ SPEAKER 3: لدي أرقام عشوائية لإزالة الألغام. رئيس 1: حسنا، يمكننا أن check-- --we يمكن التحدث عن ذلك في الثانية. ولكن يجب أن يكون الحصول على هذا. لذلك، إذا كان لدينا المال ب لأول واحد لدينا، هذا الشرط يجب أن قبض عليه، أليس كذلك؟ لذلك، إذا ضربنا المقبل، ونحن نرى أن هذا إذا كان ينفذ فعليا. لأنه إذا كنت التالية جنبا إلى جنب في التعليمات البرمجية، هذا الخط هنا، حيث نص عادي أنا يتم استبدال هذا الحساب، ينفذ إلا إذا كان في حالة الشرط هو الحق الصحيح؟ GDB لن يؤدي الا لتظهر لك الأشياء التي يتم تنفيذها في الواقع. حتى إذا لم يتحقق هذا الشرط إذا، هو مجرد الذهاب إلى القفز إلى السطر التالي. موافق؟ لذلك، لدينا ذلك. هذه الفئة يعني انها أغلقت من أن حلقة الآن. لذلك، انها سوف تبدأ مرة أخرى. تماما مثل ذلك. لذلك، أن نتمكن من الحصول على المعلومات عن السكان المحليين لدينا هنا، ونحن نرى أن لدينا أولا لقد تغيرت إلكتروني، أليس كذلك؟ حان الآن E، كما ينبغي أن يكون. لذلك، لا يمكننا الاستمرار على. ولدينا هذا الاختيار. ويجب أن يعمل هذا الاختيار، أليس كذلك؟ انها A. يجب تغييره ثلاث رسائل إلى الأمام. ولكن إذا لاحظت، نحن الحصول على شيء مختلف. حتى في هذه الحالة هنا، اشتعلت ذلك، وحتى هذا الخط تنفيذها، التي عدلت لدينا B. ولكن، في هذه الحالة هنا، لدينا أنه مجرد تخطي ذلك، وذهب إلى [؟ L SIFF. ؟] ذلك شيء يحدث هناك. ما هذا ما أقول لك هو أنه، نحن نعرف أنه ينبغي أن يمسك هنا، ولكن ذلك ليس صحيحا. يمكن لأي شخص رؤية ما لدينا المشكلة هي في هذا الخط؟ انه شيء دقيقة جدا. ويمكنك أيضا أن ننظر في التعليمات البرمجية. انها line-- أيضا نسيان ما هو خط في there-- ولكن هذا في [غير مسموع]. نعم؟ SPEAKER 4: انها على أكثر من الصفحة إذا كنت تقرأ في كتاب. رئيس 1: بالضبط. لذلك، المصحح لا يمكن أن نقول لك ذلك، ولكن المصحح يمكن أن تحصل وصولا الى خط عليك أن تعرف لا يعمل. وأحيانا، عندما خاصة في وقت لاحق في الفصل الدراسي، عندما كنت تتعامل مع مائة و مئات الأسطر القليلة من رمز، ولك لا أعرف من أين انها فشلت، هذا هو وسيلة رائعة للقيام بذلك. لذلك، وجدنا علة لدينا. يمكنك إصلاحه في الملف الخاص بك، ثم هل يمكن تشغيله مرة أخرى، وسيعمل كل شيء تماما. وأهم شيء هو هذا يمكن أن يبدو مثل، موافق. نعم. بارد. كنت تعرف ما الذي تبحث عنه. لذلك، كنت تعرف ماذا تفعل. GDB يمكن أن تكون مفيدة لأنك السوبر يمكن طباعة كل هذه الأشياء التي كنت لن. انها أكثر فائدة بكثير من PrintF. كم منكم استخدام مثل البيانات PrintF لمعرفة أين كان الخلل، أليس كذلك؟ لذلك، مع هذا، كنت لا لديهم للحفاظ على العودة، وترغب في التعليق PrintF، أو يعلق بها، ومعرفة ما يجب أن تكون الطباعة. هذا الواقع يسمح لك فقط ل الخطوة من خلال، طباعة الأشياء كما كنت تمر، لذلك، يمكنك نلاحظ كيف أنها تغيير في الوقت الحقيقي، كما برنامجك يعمل. ويستغرق قليلا قليلا من التعود. سأكون في غاية يوصي مجرد نوع يجري بالاحباط قليلا معها لفي الوقت الحالي. إذا كنت تنفق ساعة على الأسبوع المقبل تعلم كيفية استخدام GDB، سوف توفر على نفسك لذلك الكثير من الوقت في وقت لاحق. وحرفيا. نقول هذا لشخص سنويا، وأتذكر عندما أخذت الدرجة، كنت مثل، وسوف يكون على ما يرام. لا. وجاء PSET 6 على وكنت مثل، أنا ستعمل تعلم كيفية استخدام GDB لأنني لا تعرف ما الذي يحدث هنا. لذلك إذا كنت تأخذ من الوقت لذلك استخدامه على البرامج الصغيرة ان كنت تريد الذهاب لتكون تعمل على، مثل العمل من خلال شيء من هذا القبيل Visionare، مثل هذا. أو إذا كنت تريد ممارسة اضافية، وأنا متأكد أنا يمكن أن نخرج برامج عربات التي تجرها الدواب، بالنسبة لك لتصحيح إذا كنت ترغب. ولكن إذا كنت تأخذ فقط بعض الوقت للحصول على تستخدم لذلك، مجرد لعب مع حولها، سوف تخدم لك جيدا حقا. وانها حقا واحدة من تلك الأشياء التي كنت للتو يجب أن نحاول، والحصول على أيديكم القذرة مع، قبل أن نفهم حقا. أنا حقا يفهم سوى مرة واحدة واضطررت الى تصحيح الامور معها، وانها أجمل بكثير لديك فكرة عن كيفية تصحيح عاجلا وليس آجلا. موافق. بارد. أنا أعلم أن هذا نوع من مثل دورة مكثفة في GDB، وسأعمل بالتأكيد على الحصول على هذه لتبدو أكبر في المرة القادمة. بارد. لذلك، إذا عدنا إلى PowerPoint لدينا. هذا هو الذهاب إلى العمل؟ مستشفى الوصل. نعم. موافق. لذلك، إذا كنت من أي وقت مضى بحاجة إلى أي من تلك مرة أخرى، وهناك قائمة. بحث ثنائي لذلك، مما الجميع يتذكر مشهد رائع من ديفيد تمزيق الكتب الهاتف في النصف. أنا لا حقا الحصول على الكتب الهاتف بعد الآن، لأن مثل أين أنت الحصول على الكتب الهاتف هذه الأيام؟ أنا حقا لا أعرف. وبحث ثنائي. هل يتذكر أحد كيف ثنائي أعمال البحث؟ أي شخص على الإطلاق؟ نعم؟ SPEAKER 5: أنت تعرف متى نظرتم نصفها سيكون في، وبناء على ذلك، والتخلص من النصف الآخر. رئيس 1 بالضبط. لذا، ثنائي البحث، انها نوع من a-- --we أحب أن أسميها فرق تسد. لذا، ما عليك القيام به هو سوف ننظر في الوسط، وسوف نرى ما اذا كان يطابق ما كنت أبحث عنه. وإذا لم يحدث ذلك، ثم محاولة معرفة، والحال أن تترك النصف أو النصف الأيمن. لذلك، قد يكون هذا إذا كنت تبحث في شيء ما أبجديا، ترى، يا. لا أليسون تأتي قبل M؟ نعم. لذلك، نحن في طريقنا لل ننظر في الشوط الاول. أو يمكن أن يكون مثل مع الأرقام. كل ما استطعت المقارنة، فإنه يمكن فرزها. يمكنك استخدام البحث الثنائي على. لذلك، يتذكر أحد هذا الرسم البياني أو ما هذا؟ انها التعقيد مقارب. لذلك، هذا الرسم البياني فقط يصف متى يأخذك إلى حل المشكلة على النحو يمكنك زيادة عدد من الأمور الذي تستخدمه. لذلك، لدينا N، وهو الزمن الخطي. إذا N مدى سنتين، وهو قليلا أفضل، لا يزال ينمو بسرعة فائقة. ثم قمنا تسجيل الدخول، الذي هو ما نعتبره ثنائي البحث. اذا لاحظنا، كما مشكلتك يحصل الكثير والكثير أكبر، الوقت الذي يستغرقه لك لحلها لا يزيد حقا كثيرا. انها مثل مقارنة هنا في البداية. كنت مثل، موافق. أي شيء هنا لا حقا الأمر الذي احدة نستخدمها، ولكن عليك الخروج إلى مليون، مليار. كنت في محاولة للعثور some-- --you're محاولة العثور على إبرة في كومة قش. أعتقد أنك تريد هذه المشكلة. تريد هذا التعقيد، وليس خطية لأن كل ما ل تعرف ستعمل بك أن تبحث من خلال كل إبرة الفردية، شيء من القش، في محاولة للبحث عن إبرة الخاص بك. وهذا ليس ممتعا جدا في رأيي. أحب الصيام. أنا أحب درجة من الكفاءة. والطلاب المجتهدين كما كنت الرجال، كما تعلمون العمل أكثر ذكاء، لا شيء أصعب نوع، كيف يمكن أن يعوض هذه الخوارزميات. لذلك، نحن ذاهبون للمشي من خلال مجرد مثال سريع. أعتقد أنه ينبغي أن يكون رفاق اليد على ثنائي البحث، ولكن في حالة أي شخص هو قليلا غامض، تريد تعزيزه، ونحن في طريقنا للذهاب فقط من خلال مثال هنا. لذلك، نحن نبحث عن إذا مجموعة تحتوي على سبع. لذلك، أول شيء نقوم به هو ننظر في الوسط، أليس كذلك؟ وأيضا كنت على وشك أن الترميز ثنائي البحث فقط في الثانية. لذلك، فإنه سيكون من المرح. لذلك نحن ننظر في مصفوفات صغيرة الوسطى 3. لا يساوي 3 7؟ لا. انها ستة. لذلك، هو أقل من أو أكبر من السبعة؟ أقل من. نعم. رفاق العمل لطيف. أشعر أنني يجب أن أحب لدينا الحلوى لأنني تريد رميها في ساحات. هذا ما أنا ذاهب الى القيام به الأسبوع المقبل. أنها سوف تبقي يا رفاق حاد. لذلك، فإننا نرمي أن النصف الأول، أليس كذلك؟ كان أقل من. نحن نعرف أن كل شيء على أن الجانب الأيسر ستكون أقل مما نحن في الواقع تبحث عنه. لذلك، ليس هناك حاجة ل تولي اهتماما لذلك. مجرد نسيانها. لذلك، ونحن الآن ننظر في الجانب الأيمن، ونحن ننظر في منتصف هناك، والآن حان تسعة. لذا، 9 is-- --Everyone؟ أكبر من ما نحن تبحث عنه، أليس كذلك؟ لذلك، نحن ذاهبون لرمي كل شيء بعيدا إلى اليمين. من هذا القبيل. الآن، كل ما كنت تركت مع أحد. لذلك نحن تحقق، وهذا واحد ما نحن نبحث عنه؟ هو. وجدنا ما كنا نريده. حتى ننتهي. شبه خطيه البحث. وإذا لاحظت، نحن كان هناك سبعة المدخلات. استغرق الأمر فقط لنا مثل ثلاث مرات، ولكن إذا كنت تفعل مثل مليار دولار، يا رفاق معرفة عدد الخطوات التي سوف اتخاذ لو كان لدينا أربعة مليارات الأشياء؟ أي التخمينات؟ انها 32. 32 خطوات للعثور على شيء في أربعة مليارات عنصر صفيف بسبب قوى من اثنين. حتى اثنين هو 32، هو أربعة مليارات. كيف ذلك مجنون جدا كنت لا تزال داخل مثل عدد صغير نسبيا من الخطوات العثور على شيء في أربعة مليارات العناصر. لذلك على تلك المذكرة، ونحن الذهاب إلى رمز هذا حتى يمكن لكم رفاق الواقع نوع نرى كيف يعمل هذا. كل الحق، لذلك يا رفاق يمكن أن التعليمات البرمجية. انا ذاهب لتمكنك من الرجال الحديث عن قليلا. تعرف على الناس من حولك، والتي هي ما أراد شخص ما من القسم الأخير. حتى تعرف على الناس من حولك. الحديث عن قليلا. وكل ما أريده منك الرجال الآن هو فقط محاولة إنشاء مخطط شبة الكود. موافق؟ قف. كل ما أريده منك هو أنك الرجال مجرد الذهاب لملء هذه الحالة بعض الوقت. لذلك أنا وضعت هذه العلوي والحدود الدنيا التي تمثل بداية ونهاية مجموعة لدينا. وأنت ذاهب إلى الواقع من خلال حلقة ومعرفة ما نقوم به في هذا الوقت حلقة. لذلك إذا كنت تستطيع معرفة out-- لدي تلميح there-- ما هي الحالات ان لدينا هنا؟ حتى إذا كنت ترغب في معرفة الحالات، ونحن سوف شبة الكود تلك ثم سنقوم رمز لهم في الواقع. وأنه سيكون، وأنا أعتقد، ونأمل انها سوف أكون يكون أسهل قليلا مما كنت تتوقع. لأنها ليست أن الكثير من الرمز، في الواقع، وهو أمر رائع حقا. مم-HM؟ الطالب: [غير مسموع]؟ المدرب: نعم. كان هناك شيء العثور في الوسط. الطالب: وهكذا يمكننا استخدام ذلك. موافق. المدرب: الكمال. ولهذا فإن أول شيء يتعين علينا القيام به. لذلك تجد الوسط. عظيم. حتى لا يكون لديك فكرة عن الكيفية التي قد في الواقع نجد وسط مع رمز؟ الطالب: نعم. ن أكثر من 2؟ المدرب: حتى ن أكثر من 2. ذلك شيء واحد هو أن نتذكر أن تتغير الحدود العليا والسفلى. واصلنا تشنجا الجزء من مجموعة نحن نبحث ل. حتى ن أكثر من 2 ستعمل فقط لأول شيء نقوم به. لذلك أخذ العلوي والسفلي في الاعتبار، كيف يمكن أن نحصل على هذا العنصر الأوسط؟ لأننا نريد منتصف بين العلوي والسفلي، أليس كذلك؟ مم-HM؟ الطالب: [غير مسموع]. المدرب: لذلك لدينا بعض الوسط. وأنه سوف يكون أقل العلوي بالإضافة إلى أكثر من 2. رهيبة. هناك نذهب. أسفل سطر واحد. يا رفاق في طريقك. حتى الآن أن لدينا الوسط، وماذا نريد أن نفعل؟ فقط في العام. لم يكن لديك إلى رمز له. نعم. الطالب: [غير مسموع]؟ المدرب: لذلك فمن بالإضافة لأنك العثور على المتوسط ​​بين اثنين منهم. لذلك إذا كنت تعتقد منهم كنوع زيادة في من الجانبين، تفكر في ذلك كما كنت الاقتراب وسط، وتريد من هذا القبيل. حتى لو كنت على جانبي الوسط ولدينا مثل 5 و 7. عند إضافتها معا لك الحصول على 12، وكنت القسمة على 2، هو 6. أحيانا من الصعب أن شرح لماذا يعمل، ولكن إذا كنت تعمل من خلال على سبيل المثال في بعض الأحيان، انها سوف تساعدك على معرفة ما اذا كان ينبغي أن يكون زائد أو ناقص. نعم. الطالب: [غير مسموع] بالضبط في الوسط إذا كان لديهم حالة هناك الكثير من الأرقام الصغيرة ومثل عدد كبير واحد؟ المدرب: لذلك كل ما تحتاجه هو وسط مجموعة. حتى إذا كان لديك مجموعة من الأرقام الصغيرة واحدة ثم عدد كبير حقا في النهاية، لا يهم. كل ما يهم هو أن انهم فرزها، أنت فقط تريد أن ننظر إلى منتصف مجموعة لأنك لا تزال تشريح مشكلتك في النصف. بارد. حتى الآن أن لدينا الوسط، وماذا نفعل بعد ذلك؟ الطالب: قارن. المدرب: إن المقارنة. ذلك مقارنة الوسط إلى value_wanted. بارد. لذلك ترى هنا لدينا هذه القيمة نريد هنا. تذكر هذا هو صفيف. لذلك يشير الوسط إلى المؤشر. لذلك نحن نريد أن نفعل قيم الوسط. لا تنسى إذا كنت تريد للمقارنة، متساوين مزدوجة. كنت لا يساوي واحد انت مجرد الذهاب الى إعادة تعيين ذلك، وبعد ذلك، بالطبع، انها ستكون القيمة التي تريدها. لذلك لا تفعل ذلك. لذلك نحن في طريقنا لمعرفة ما إذا كان القيم في منتصف تساوي القيمة التي تريدها. لا ننسى الأقواس الخاصة بك. دروببوإكس يجب ان تذهب بعيدا. فماذا نفعل في هذه الحالة؟ إذا كان هذا هو ما نريد أن يعود؟ نحن نحاول أن نقول. الطالب: طباعة قبالة. المدرب: حسنا، نحن لا نريد لطباعة قبالة. لذلك هذا هو منطقي هنا، لذلك نحن يريدون العودة صحيحة أو خاطئة. نقوله، هو هذا العدد و[؟ RRA؟ ؟] حتى إذا كان صحيحا، نحن فقط إعادته صحيح. اذا كنت استطيع توضيح صحيح. الطالب: لماذا لن تعود الصفر؟ المدرب: لذلك يمكن أن إرجاع صفر إذا أردت. ولكن في هذه الحالة بسبب وظيفتنا إرجاع منطقي، نحن بحاجة إلى العودة إما صحيحة أو خاطئة. الطالب: عندما كنت قائلا تعبير منطقي، يمكنك تعيين يساوي كاذبة؟ كما لو كنت أريد أن أقول، إذا كان هذا الشرط لم يتم الوفاء بها، مثل هو الجزء العلوي يساوي كاذبة. هل نفهم إذا كنت فقط وضع كاذبة على الجانب الآخر؟ المدرب: نعم. حتى إذا كنت فعلا تفعل شيئا على الإطلاق كما هو العلوي أو السفلي هو، وترجع صحيحة أو خاطئة وانها اسلوب سيء فعلا ل مثلا يساوي يساوي صحيح أو أنداد يساوي كاذبة. كنت ترغب في استخدام تلك النتيجة كما نفسها الشيك. ليس ما أردت. هذا ما أردت. حتى في حالة كنت طالبا عن شيء مثل هذا في انقاذ ج. حتى إذا كان لدينا كثافة العمليات الرئيسي (الفراغ) وشيء من هذا القبيل. وإذا كان لديك هي العليا بعض المدخلات وكنت تسألك إذا كنت تستطيع أن تفعل شيء من هذا القبيل؟ أليس كذلك؟ الطالب: كنت أحاول للقيام بذلك (غير مسموع). لأنه إذا it's-- المدرب: الحق. لذلك أردت أن تكون كاذبة، أليس كذلك؟ الطالب: نعم. المدرب: حتى في هذه الحالة لك تريد أن تنفيذ إذا لم يكن صحيحا. ذلك الشيء باردة كنت تفعل هناك هذا. لذلك تذكر تعجب نقطة ينفي الأشياء؟ تقول [غير مسموع] يعني لا. لذلك إذا نظرنا فقط هذا الجزء هنا، كنت القول بأن يقيم ل كاذبة كما كنت ترغب فيها. لا كاذبة صحيح الذي يعني هذا من شأنه تنفيذ. هل هذا يعقل؟ الطالب: نعم. المدرب: ممتاز. موافق. حتى نتمكن من العودة فقط صحيح في هذه الحالة. حتى الآن لدينا اثنين آخرين الحالات في هذه الحالة. ما هي لدينا حالتين أخريين؟ دعونا فقط تفعل ذلك بهذه الطريقة. لذلك دعونا نبدأ مع آخر إذا القيم في منتصف هو أقل من القيمة التي نريدها. لذلك لدينا قيمة في منتصف أقل من القيمة التي نبحث عنه. ذلك الذي متجهة هل أعتقد أننا نريد أن التحديث؟ العلوي أو السفلي؟ العلوي؟ لذلك أي جانب من مجموعة نحن ذاهبون إلى أن تبحث في؟ الطالب: إن أقل. المدرب: نحن سنذهب أن تبحث في اليسار. حتى آخر إذا كانت القيمة أقل قليلا. لذا القيمة المتوسطة هنا أقل من ما نريد. لذلك نحن نريد أن يأخذ الجانب الأيمن من مجموعة لدينا. لذلك نحن ذاهبون ل تحديث الأدنى لدينا. ولذا فإننا سوف إعادة تعيين لدينا أدنى. وماذا تعتقد يجب أن يكون أقل؟ الطالب: القيمة المتوسطة؟ المدرب: إذن value-- الأوسط الطالب: زائد 1. المدرب: --plus 1. يمكن لأحد أن يقول لي لماذا علينا أن زائد 1؟ الطالب: [؟ لا قيمة؟] أكثر يعادل ذلك. المدرب: الحق. لأننا نعلم بالفعل أن القيمة المتوسطة لدينا ليست مساوية ل ذلك، ونحن نريد أن استبعاده من جميع عمليات البحث اللاحقة. إذا كنت قد نسيت أن زائد 1، وهذا سيحب حلقة إلى أجل غير مسمى. وسوف يكون مجرد واقعة في حلقة لا نهائية ثم عليك سوف segfault وسارت الامور سيئة. لذلك دائما التأكد من أنك لا بما في ذلك القيمة التي قمت للتو نظرت. لذلك نحن نحرص على أن مع زائد 1. حتى الآن لدينا الشرط الأخير لدينا وأنا دائما من اجل سلامة يمكنك التحقق من هنا، إلا إذا كانت القيمة في وسط أكبر من قيمة نريد. وهذا يعني أننا نريد النصف الأيسر. لذلك أي واحد نحن ذاهبون إلى تحديث؟ العلوي. وما هو هذا واحد الذهاب إلى تساوي؟ وسط ناقص 1 ل، بالطبع، نريد للتأكد من أننا لا النظر في تلك القيمة المتوسطة مرة أخرى. ثم لدينا ذلك. هذا هو. هذا كل بحث ثنائي. انها ليست سيئة لهذه الدرجة، أليس كذلك؟ انها مثل 10 خطوط الرمز مع المساحة البيضاء. هكذا قوية جدا، ومفيدة جدا، وسوف يكون استخدامه في واحدة من psets في وقت لاحق بك. ربما ليس هذا واحد، ولكن في وقت لاحق. حتى معرفة ذلك. أحب ذلك. وسوف يعاملك بشكل جيد. لذلك لا أحد لديه أي أسئلة البحث على ثنائي؟ نعم. الطالب: هل يهم سواء الخاص أو حتى ن هو الغريب؟ المدرب: رقم لأننا يطرح للالاوسط عدد صحيح، فإنه سيتم فقط باقتطاع ذلك. لذلك سوف يبقى عدد صحيح، وسوف فرز في نهاية المطاف من خلال كل شيء. لذلك كنت لا داعي للقلق حول ذلك. الجميع جيدا؟ رهيبة. بارد. لذلك، حصل هذا يا رفاق. عرض الشرائح. بحيث كنا نتحدث عنها، وأنا أعلم ديفيد المذكورة أوقات التشغيل التعقيد. حتى في أفضل الأحوال، انها مجرد واحد، والتي نسميها الزمن المستمر. يمكن لأحد أن يقول لي لماذا يمكن أن يكون؟ ما هو نوع من السيناريو فإن ذلك يترتب عليه؟ مم-HM. الطالب: [غير مسموع] first-- المدرب: حتى منتصف يجري و العنصر الأول أن نأتي ل، أليس كذلك؟ لذلك إما مجموعة واحدة أو كل ما نبحث عنه فقط يحدث أن تكون صفعة الداب في الوسط. ذلك أن أفضل حالتنا. تحصل في مشاكل حقيقية، وربما لا الذهاب لتصل إلى (غير مسموع) التي غالبا. ماذا عن أسوأ حالتنا؟ أسوأ حالتنا هي السجل ن. وهذا له علاقة مع العموم صلاحيات اثنين الشيء الذي تحدثت عنه. حتى في أسوأ الحالات فإن ذلك يعني أن كان لدينا لتقطيع مجموعة الأسفل حتى كان عنصر واحد. لذلك كان علينا أن ختم عليه في النصف عدة مرات كما أننا ربما يمكن. هذا هو السبب في أنه من السجل ن ل عليك أن تبقي فقط يقسم على اثنين. هكذا افتراضات، الأشياء التي بحاجة إلى معرفة ما إذا كنت من أي وقت مضى تنوي استخدام البحث الثنائي. يجب فرز العناصر الخاصة بك. لديهم ليتم فرزها ل هذه هي الطريقة الوحيدة التي ويمكن معرفة ما إذا كنت قادرا لطرد نصفه. إذا كان لديك هذه الحقيبة الملتبسة من الأرقام وتقوله، حسنا، أنا ذاهب للتحقق من منتصف عدد وعدد أنا أبحث عن هو أقل من ذلك، انا فقط لرمي تعسفا من النصف. وكنت لا أعرف إذا كان لديك أرقام في أن النصف الآخر. قائمتك لابد من فرزها. كذلك، قد يكون هذا المضي قدما قليلا، ولكن تحتاج إلى أن يكون الوصول العشوائي. عليك أن تكون قادرا على مجرد الذهاب إلى هذا العنصر الأوسط. إذا كان لديك لاجتياز من خلال شيء أو أنه يأخذك خطوات اضافية للوصول إلى هذا العنصر الأوسط، انها ليست بعد الآن لتسجيل ن كنت تقوم بإضافة المزيد من العمل فيه. وهذا سيجعل قليلا أكثر منطقية في أسبوعين ولكن أنا مجرد نوع من أراد أن أمهد، تعطيك فكرة عن الرجال ما قادمة. ولكن تلك هي اثنين الافتراضات الهامة التي تحتاجها للحصول على قائمة الثنائية. تأكد من انه تم فرزها ذلك. هذا هو واحد كبير ل يا رفاق الحق الآن. وعلى ذلك يمكننا أن نذهب إلى بقية أنواع لدينا. حتى أربعة فقاعة sorts--، الإدراج، والاختيار، والدمج. انهم جميعا نوع من باردة. إذا يا رفاق تقرر اتخاذ CS 124، ستتعرف على جميع أنواع أنواع. وإذا كنت من محبي XKCD، هناك هو حوالي كوميدي رائع حقا مثل أنواع غير فعالة حقا، وأنا نوصي بشدة الذهاب لإلقاء نظرة. واحد منهم هو مثل الذعر النوع الذي هو مثل، أوه لا، تعود مجموعة عشوائية. نظام الاغلاق. ترك. لذلك العبقري غريب الأطوار الفكاهة جيدة دائما. لذلك لا أحد يتذكر النوع وكأنه مجرد فكرة عامة كيف يعمل فقاعة النوع. هل تذكر؟ الطالب: نعم. المدرب: الذهاب لذلك. الطالب: حتى وأنت تسير من خلال و إذا كان أكبر، فإنك مبادلة اثنين. المدرب: مم-HM. بالضبط. لذلك أنت فقط من خلال تكرار. يمكنك التحقق من رقمين. إذا كان واحد من قبل هو اكبر من واحد بعد ذلك، يمكنك مبادلة منهم فقط حتى أنه في بهذه الطريقة كل الأرقام أعلى فقاعة يصل نحو نهاية القائمة وجميع الأرقام أقل فقاعة أسفل. وقال انه تبين لكم رفاق بارد تأثير الصوت فرز الفيديو؟ انها نوع من باردة. حتى قال روبرت فقط، الخوارزمية ان كنت خطوة فقط من خلال القائمة، مبادلة القيم المجاورة لو لم يكن في محله. ثم تبقي فقط تكرار حتى لا تجعل أي مقايضة. لذلك ليس سيئا، أليس كذلك؟ لذلك علينا مجرد مثال سريع هنا. لذلك هذا هو الذهاب لفرز لهم في ترتيب تصاعدي. لذلك عندما نذهب من خلال أولا الوقت، ونحن ننظر من خلال ثمانية وستة من الواضح أنها لا في النظام، ومقايضتهم. حتى ننظر في واحد القادم. ثمانية وأربعة وليس في النظام. مقايضتهم. وبعد ثمانية واثنين، ومقايضتهم. هناك نذهب. حتى بعد مرور الأول الخاص بك، فإنك نعرف أن أكبر رقمك ستكون على طول الطريق في الجزء العلوي لأنها مجرد سيكون باستمرار أكبر من كل شيء آخر وانها مجرد الذهاب إلى فقاعة يصل طول الطريق إلى النهاية هناك. يفعل ذلك من المنطقي أن الجميع؟ بارد. لذلك فإننا ننظر إلى مسار الثاني لدينا. ستة وأربعة، والتبديل. ستة واثنين، والتبديل. والآن لدينا عدد قليل من الأشياء في النظام. لذلك كل تمريرة أننا جعل من خلال قائمتنا بأكملها، ونحن نعلم أن مثل ذلك أعداد كثيرة في النهاية سيكون قد تم فرزها. لذلك نحن نفعل تمريرة الثالث، وهو مبادلة واحدة. ثم في المركز الرابع لدينا تمر، لدينا فتحات الصفر. وهكذا نعرف أن لدينا تم فرز مجموعة. وهذا هو كبير الشيء مع فقاعة نوع. نحن نعرف أننا عندما يكون الصفر مقايضة، أن يعني أن كل شيء هو في النظام الكامل. انها نوع من الكيفية التي تحقق. لذلك نحن نذهب أيضا إلى رمز الفقاعة وهو نوع أيضا ليس بهذا السوء. أيا من هؤلاء هم بهذا السوء. وأنا أعلم أنها يمكن أن يبدو مخيفا بعض الشيء. أعرف أنني عندما تولى الطبقة، حتى عندما كنت تم تدريس فئة ل للمرة الأولى في العام الماضي، كنت مثل، كيف أفعل ذلك؟ فمن المنطقي من الناحية النظرية، ولكن كيف نفعل ذلك في الواقع؟ وهذا هو السبب وأريد أيضا أن المشي خلال التعليمات البرمجية مع رفاق هنا. لذلك لدي شبة الكود ليا رفاق هذا الوقت. حتى مجرد تضع ذلك في الاعتبار و نحن على وشك الانتقال من جديد. لذلك لدينا بعض المضادة التي يتتبع مقايضة لدينا، لأننا بحاجة للتأكد من اننا التحقق من ذلك. ونحن تكرار مجموعة كاملة كما فعلنا للتو مع هذا المثال. إذا كان العنصر هو أكبر من قبل العنصر بعد حيث أننا في، نحن مقايضتهم، ونحن لدينا زيادة مكافحة بسبب بأسرع ما مبادلة، نريد أن ندع مضادة لدينا يعرفون ذلك. أي أسئلة هناك؟ شيء يبدو مضحكا أكثر من هنا. الطالب: هل تعيين العداد إلى الصفر في كل مرة تذهب من خلال حلقة؟ لا يمكنك الاستمرار العودة إلى الصفر في كل مرة؟ المدرب: ليس بالضرورة. فما يحدث هو أن نذهب من هنا. تفعل ذلك في حين، وتذكر، وهذا سيتم تنفيذ مرة واحدة دون أن تفشل. لذلك سيكون لتعيين مكافحة تساوي الصفر، ثم انه سيكون تكرار خلال. كما تتكرر خلال، فإنه سيتم تحديث مضادة. كما يستكمل العداد، عندما يكون القيام به، عندما يكون التوصل إليه في نهاية المصفوفة، إذا لم يتم فرزها قائمتنا، سيكون قد تم تحديث مضادة. حتى ذلك الحين فإنه يتحقق الشرط و وتقول، حسنا، هو أكبر مضادة من الصفر. إذا كان، يفعل ذلك مرة أخرى. تريد إعادة تعيين بحيث عند من خلال الذهاب، ومكافحة تساوي الصفر. إذا كنت تذهب من خلال التصنيف مجموعة، لم يتغير شيء، فشل هذا، وأنت العودة إلى قائمة تم فرزها. هل هذا منطقي؟ الطالب: قد في قليلا. المدرب: موافق. إذا كان هناك أي شيء آخر السؤال الذي يأتي. نعم. الطالب: ما وظيفة يكون لضخ العناصر؟ المدرب: لذلك نحن يمكن أن يكتب في الواقع أنه إذا نحن ذاهبون إلى الآن. بارد. لذلك على تلك المذكرة، أليسون يجري للرجوع إلى الجهاز. انها سوف تكون ممتعة. ولدينا لطيف لدينا فقاعة شيء نوع هنا. لذلك أنا بالفعل فعلت الدراجات من خلال صفيف. لدينا مقايضة لدينا أن تساوي الصفر. لذلك نحن نريد لمبادلة المجاورة لو انهم عناصر من النظام. لذا فإن أول شيء يتعين علينا القيام لا يتم تكرار خلال مجموعة لدينا. فكيف تظن أننا قد تكرار خلال مجموعة لدينا؟ لدينا لوأنا يساوي 0. نريد أن أكون أقل من ن ناقص 1 ناقص ك. وساوضح ذلك في الثانية. لذلك هذا هو الأمثل هنا حيث، تذكر كيف قلت بعد كل تمريرة نحن من خلال مجموعة أعرف أن كل ما هو on-- حتى بعد مرور واحد نحن أعرف أن هذا تم فرزها. بعد مرورين نعرف أن كل هذا تم فرزها. بعد ثلاث تمريرات نحن أعلم أن فرزها. وبالتالي فإن الطريقة أنا بالتكرار من خلال مجموعة هنا، وانها التأكد من أن تذهب فقط من خلال ما نعرفه هو غير مصنفة. موافق؟ هذا مجرد التحسين. هل يمكن الكتابة عليه بسذاجة فقط بالتكرار عبر كل شيء، ان الامر سيستغرق وقتا أطول فقط. مع هذه الحلقة أربعة انها مجرد الأمثل لطيفة لأننا نعلم أن بعد كل كامل التكرار من خلال مجموعة هنا، مثل كل حلقة كاملة هنا، ونحن نعلم إن أحد أكثر من هذه العناصر سيتم فرز في نهاية المطاف. لذلك نحن لا داعي للقلق حول تلك. يفعل ذلك من المنطقي أن الجميع؟ إن خدعة باردة قليلا؟ حتى في هذه الحالة، إذا نحن بالتكرار عبر، نحن نعلم أننا نريد للتحقق مما إذا مجموعة ن و ن 1 زائدا هم بالترتيب. موافق. وحتى هنا في شبة الكود. نحن نريد للتحقق مما إذا مجموعة ن ون 1 زائدا هي في النظام. ذلك ما يمكن أن لدينا هناك؟ انها سوف تكون بعض مشروطة. وسوف يكون إذا. الطالب: إذا هو مجموعة ن أقل من مجموعة ن زائد 1. المدرب: مم-HM. حسنا، أقل من أو أكبر من. الطالب: أكبر من. ثم نريد أن مقايضتهم. بالضبط. حتى الآن نحن ندخل في ما هو آلية لضخ لهم؟ لذلك ذهبنا من خلال هذه لفترة وجيزة، نوع من وظيفة مبادلة الأسبوع الماضي. هل يتذكر أحد كيف يعمل؟ لذلك لا يمكننا فقط إعادة تعيين لهم، أليس كذلك؟ لأنه سوف تضيع واحد منهم. إذا قلنا ويساوي إلى B ثم B تساوي A، كل فجأة كل منهما تساوي فقط لB. وذلك ما يتعين علينا القيام به هو أننا لديك متغير مؤقت هذا الذهاب لعقد واحد من حين لنا نحن في عملية مبادلة. فما لدينا هو أننا سيكون لديك بعض الباحث درجة الحرارة تساوي علي: يمكنك تعيينها إلى أي واحد تريد، فقط تأكد من أنك تتبع it-- حتى في هذه الحالة، أنا ذاهب ل إسناد ذلك إلى مجموعة ن زائد 1. بحيث يجري عقد أيا كان القيمة هي في أن كتلة الثاني أننا نبحث في. ومن ثم يمكننا القيام به هو أننا يمكن أن تذهب وقبل إعادة تعيين مجموعة ن زائد 1، لأننا نعلم أننا لديهم تلك القيمة المخزنة. وهذا هو أيضا واحدة من الكبيرة things-- أنا لا أعرف إذا كان أي منكم كانت القضايا التي إذا قمت بالتبديل اثنين الأسطر من التعليمات البرمجية فجأة عملت الأشياء. الترتيب مهم جدا في CS. لذلك تأكد من الرسم التخطيطي الأمور إن أمكن كما أن ما يحدث في الواقع. حتى الآن نحن في طريقنا لل إعادة تعيين مجموعة ن زائد 1، لأننا نعلم أننا لديهم تلك القيمة المخزنة. ويمكننا تعيين ذلك إلى مجموعة ن أو في هذه الحالة مجموعة ط. متغيرات كثيرة جدا. موافق. مجموعة حتى الآن قمنا تعيينهم ط زائد 1 ليساوي ما في مجموعة ط. والآن يمكننا أن نعود و تعيين مجموعة ط لماذا؟ أي شخص؟ الطالب: 10. المدرب: 10. بالضبط. وآخر شيء واحد. إذا كنا قد تبادلت عليه الآن، ماذا علينا أن نفعل؟ ما هو الشيء الوحيد ما يجري ليقول لنا إذا كان لنا أي وقت مضى إنهاء هذا البرنامج؟ ما يخبرنا بأننا لدينا قائمة تم فرزها؟ إذا كنا لا يؤدون أي مقايضة، أليس كذلك؟ إذا مقايضة تساوي الصفر في نهاية هذا. لذلك كلما قمت بإجراء مبادلة، ونحن مجرد فعل هنا، ونحن نريد لتحديث مقايضة. وأنا أعرف كان هناك السؤال في وقت سابق عن يمكنك استخدام صفر أو واحد بدلا من صحيحة أو خاطئة. وهذا ما يفعل هذا هنا. لذلك هذا يقول إذا لم مقايضة. حتى إذا مقايضة صفرا، التي is-- أنا دائما أحصل على الحقائق و FALSE بلدي اختلطت. نريد لنا لتقييم إلى صحيح وانها لا. حتى لو كان صفر، ثم انها كاذبة. إذا كنت ينفي ذلك مع [؟ فرقعة؟] يصبح صحيحا. حتى ذلك الحين ينفذ هذا الخط. حقائق وكاذبة و الأصفار ومنها الحصول على مجنون. فقط إذا كنت تمشي ببطء من خلال ذلك أنه لن يكون له معنى. ولكن هذا ما يذكر هذا قليلا من التعليمات البرمجية هنا لا. لذلك هذا يتحقق لرؤية فعلنا أي مقايضة. لذلك إذا كان أي شيء إلى جانب الصفر، فإنه سيكون كاذبة والشيء كله الذهاب لتنفيذ مرة أخرى. بارد؟ الطالب: ماذا يعني كسر تفعل؟ المدرب: كسر فقط يكسر لكم من الحلقة. حتى في هذه الحالة سيكون تماما مثل إنهاء البرنامج وكنت فقط ديك قائمتك فرزها. الطالب: مدهش. المدرب: أنا آسف؟ الطالب: لأن سابقا نحن استخدمت مكتوبة 1 فوق الصفر مكتوبة أن يقدم أنه إذا التي ستعمل أم لا. المدرب: نعم. حتى تتمكن من العودة صفر أو 1. في هذه الحالة، لأننا لسنا في الواقع فعل أي شيء مع وظيفة، نحن نريد فقط أن كسر. نحن لا نهتم حقا عن ذلك. الفرامل هي أيضا جيدة إذا انها تستخدم لالخروج أربع حلقات أو الظروف التي كنت لا تريد أن تبقي المنفذة. فإنه يأخذ فقط لأنك للخروج منها. انها قليلا من شيء فارق بسيط. أشعر هناك الكثير من ناحية التلويح، كما ستعرف عن هذا قريبا. ولكن عليك أن تعلم عن هذا قريبا. أعدك. موافق. حتى لا يحصل الجميع فقاعة نوع؟ ليست سيئة للغاية. تكرار خلال، تبادل الأشياء باستخدام متغير مؤقت، ونحن جميعا وضع هناك؟ بارد. رهيبة. موافق. العودة إلى باور بوينت. أي أسئلة في عام حول هذه حتى الآن؟ بارد. مم-HM. الطالب: [غير مسموع] كثافة العمليات الرئيسية عادة. لا يكون لديك أن لهذا؟ المدرب: لذا كنا نبحث فقط فقط في خوارزمية الفرز الفعلية. إذا كان ذلك داخل مثل برنامج أكبر، هل سيكون لها مكان الرئيسي كثافة العمليات. تبعا للمكان الذي تستخدم هذه الخوارزمية، سيكون تحديد ما هو يجري عاد به. ولكن بالنسبة لحالتنا، ونحن بشكل صارم تبحث في كيفية يفعل هذا في الواقع تكرار خلال صفيف. لذلك نحن لا تقلق بشأن ذلك. لذلك كنا نتحدث عن أفضل حالة و أسوأ السيناريوهات للبحث ثنائي. لذلك فمن المهم أيضا أن تفعل أن لكل من أنواع لدينا. فما رأيك هو الأسوأ حالة وقت التشغيل من نوع فقاعة؟ تذكر يا رفاق؟ الطالب: N ناقص 1. المدرب: N ناقص 1. وهذا يعني أن هناك ن ناقص 1 المقارنات. ذلك شيء واحد هو أن ندرك على أن التكرار الأول، نذهب من خلال قارنا هذه two-- ذلك أن 1. هؤلاء اثنان، ثلاثة، أربعة. حتى بعد التكرار واحد ونحن لدينا بالفعل أربعة المقارنات. عندما أتحدث عن وقت ون. N يمثل عدد من المقارنات كدالة لكيفية العديد من العناصر لدينا. موافق؟ لذلك نحن من خلال الذهاب، لدينا أربعة. في المرة القادمة التي نعلم أننا لا يجب أن تأخذ الرعاية من ذلك. قارنا هذين، هذين، وهذين، وإذا لم يكن لدينا هذا التحسين مع حلقة الأربع التي كتبت، سيكون لكم هنا مقارنة في أي حال. لذلك سيكون لديك ل من خلال تشغيل مجموعة وجعل المقارنات ن ن مرات، لأنه في كل مرة نقوم فيها تشغيل من خلال ذلك يمكننا ترتيب شيء واحد. ونحن في كل مرة من خلال تشغيل مجموعة، يمكننا أن نجعل ن المقارنات. لذلك لدينا وقت لذلك هو في الواقع ن المربعة، والتي هو أسوأ بكثير في موقعنا تسجيل نهاية لأن ذلك يعني لو كان لدينا أربعة مليار العناصر، انها الذهاب لنقلنا أربعة مليارات مربع بدلا من 32. حتى لا يكون أفضل وقت، ولكن بالنسبة لبعض الأشياء، أنت تعرف، إذا كنت داخل مجموعة معينة من العناصر قد تكون فقاعة نوعا ما يرام لاستخدام. موافق. حتى الآن ما هو أفضل وقت الحال؟ الطالب: صفر؟ أو 1؟ المدرب: حتى لو 1 المقارنة تكون واحدة. الحق. الطالب: N ناقص 1؟ المدرب: لذا، نعم. حتى ن ناقص 1. كلما كان لديك مفهوم مثل ن ناقص 1، فإننا نميل إلى مجرد قطرة تشغيله ونحن نقول فقط ن لديك للمقارنة بين كل من these-- كل زوج. لذلك سيكون ن ناقص 1، ونحن كنا نقول فقط ما يقرب من ن. عندما كنت تتعامل مع وقت التشغيل، كل شيء في تقارب. طالما هو الأس صحيح، كنت جيدة جدا. هذه هي الطريقة التي نتعامل معها. ذلك أن أفضل حالة هي ن، والتي يعني أن يتم فرز القائمة بالفعل، وكل ما فعله هو تشغيل من خلال وهذا ما تحقق ذلك فرزها. بارد. حسنا. هكذا كما ترون هنا، فإننا لدينا فقط بعض أكثر الرسوم البيانية. حتى ن المربعة. متعة. أسوأ بكثير من ن كما نرى، و كثيرا، أسوأ بكثير من سجل 2N. ثم تحصل أيضا في سجلات السجل. وتأخذ 124، تحصل في مثل نجم السجل، الذي هو مثل مجنون. لذلك إذا كنت مهتما، نجم سجل البحث. انها نوع من المرح. لذلك لدينا هذا المخطط الكبير. مجرد رؤساء حتى، هذا الرسم البياني الرائع أن يكون لديك منتصف المدة لأننا طالما أن أسألك هذه يخفف. حتى مجرد رؤساء حتى، يكون هذا على الخاص منتصف المدة على ورقة الغش الخاص بك لطيف هناك. لذلك نحن مجرد النظر في ترتيب الفقاعات. أسوأ الحالات، ن مربع، وأفضل حال، ن. ونحن في طريقنا لننظر إلى الآخرين. وكما ترون، فإن فقط واحد أن يفعل بشكل جيد حقا هو دمج النوع، ونحن سوف ندخل لماذا. لذلك نحن في طريقنا للذهاب إلى المقبل اختيار نوع واحد here--. هل يتذكر أحد كيف اختيار عملت نوع؟ لأنها تذهب. الطالب: اذهب أساسا من خلال أمر وإنشاء قائمة جديدة. وتماما كما أنك تضع العناصر في، ووضعها في المكان المناسب في القائمة الجديدة. المدرب: ذلك أن الأصوات أشبه الإدراج النوع. ولكن كنت قريبة جدا. انهم مشابهة جدا. حتى أحصل عليها الخلط أحيانا. قبل هذا القسم كنت مثل، الانتظار. موافق. وذلك ما تريد القيام به هو اختيار نوع، الطريقة يمكن ان يخطر لك حول هذا الموضوع والطريقة أتأكد من أنني ليس محاولة للحصول على اختلطت عليهم، هو أن يذهب من خلال ويختار أقل عدد و أن يضع في بداية القائمة. انها مقايضة مع تلك البقعة الأولى. لديهم في الواقع مثالا بالنسبة لي. رهيبة. حتى مجرد وسيلة للتفكير في اختيار it-- نوع، حدد أصغر قيمة. ونحن في طريقنا ل تشغيل من خلال مثال وأعتقد أنه سوف يساعد ل أعتقد مرئيات تساعد دائما. لذلك نحن تبدأ مع شيء هذا هو تماما لم يتم فرزها. سوف تكون حمراء لم يتم فرزها، سيتم فرز الأخضر. وستجعل كل معنى في الثانية. حتى نذهب ونحن من خلال تكرار من البداية إلى النهاية. ونحن نقول، حسنا، هو 2 رقم أصغر لدينا. لذلك نحن ذاهبون الى اتخاذ 2، ونحن ذاهبون لنقلها إلى الجزء الأمامي من مجموعة لدينا لأنه هو أقل عدد لدينا. ذلك أن هذا هو ما تقوم به هنا. انها مجرد الذهاب لمبادلة هذين. حتى الآن لدينا فرز جزء وجزء لم يتم فرزها. وما هو جيد أن نتذكر حول اختيار نوع غير أننا اختيار فقط من جزء لم يتم فرزها. الجزء فرزها كنت مجرد ترك وحده. مم-HM؟ الطالب: كيف نعرف ما هو أصغر دون مقارنتها إلى كل قيمة أخرى في صفيف. المدرب: وهو يفعل مقارنتها. نحن أحب تخطي ذلك. هذا هو مجرد العام عموما. نعم. عندما نكتب رمز أنا متأكد من أنك سوف تكون أكثر ارتياحا. ولكن يمكنك تخزين هذا أولا كما أصغر عنصر. وقارنت لك نقول، حسنا، هو أصغر؟ نعم. يبقيه. هنا هو أصغر؟ لا؟ هذا هو أصغر الخاص بك، إعادة تعيين إلى القيمة الخاصة بك. وعليك أن تكون أكثر سعادة عندما نذهب من خلال التعليمات البرمجية. لذلك نحن من خلال الذهاب، ونحن مبادلة، لذلك ثم نحن ننظر إلى هذا الجزء لم يتم فرزها. لذلك نحن ذاهبون لاختيار ثلاثة من أصل. ونحن في طريقنا لوضعها على في نهاية لدينا جزء فرزها. ونحن ذاهبون لمجرد الاحتفاظ به أن يفعل ذلك، وتفعل ذلك. لذلك هذا هو لدينا نوع من شبة الكود هنا. سنقوم رمز عنه هنا في الثانية. ولكن مجرد شيء على المشي من خلال على مستوى عال. وأنت تسير للانتقال من ط ن يساوي 0 إلى ناقص 2. هذا هو الأمثل أخرى. لا تقلق كثيرا حول هذا الموضوع. لذلك كما كنت تقول. كما كان يعقوب قائلا: كيف يمكننا تتبع ما هو الحد الأدنى لدينا؟ كيف لنا أن نعرف؟ علينا أن المقارنة كل شيء في قائمتنا. حتى الحد الأدنى يساوي ط. انها مجرد قوله في هذه الحالة الرقم القياسي لقيمة الحد الأدنى لدينا. لذلك فإنه سيكون لتكرار خلال وغني عن ي ط يساوي زائد 1. لذلك نحن نعلم بالفعل أن هذا هو العنصر الأول. نحن لسنا بحاجة لذلك لمقارنة نفسها. حتى نبدأ مقارنتها إلى أخرى واحد الذي هو السبب في انها ط زائد 1 إلى ن ناقص 1، والذي هو نهاية مجموعة هناك. وإذا قلنا في مجموعة ي أقل من دقيقة مجموعة، ثم نقوم بإعادة تعيين حيث الحد الأدنى من المؤشرات لدينا. وإذا كانت دقيقة لا تساوي ط، و في المكان الذي كنا فيه إلى أكثر من هنا. حتى عندما كنا نود أولا فعلت هذا واحد. في هذه الحالة، فإنها تبدأ في الصفر، فإنه ينتهي به الأمر إلى اثنين. حتى لو دقيقة لا تساوي أنا في نهاية المطاف. الذي يتيح لنا أن نعرف أنه نحن بحاجة لمقايضتهم. أشعر مثالا ملموسا سوف تساعد أكثر من ذلك بكثير. ولذا فإنني سوف رمز هذا الأمر مع رفاق الآن، وأعتقد أنه سوف يكون أفضل. أنواع تميل إلى العمل بهذه الطريقة في ذلك فمن الأفضل لمجرد أن نرى لهم. ذلك ما نريد القيام به هو نريد أولا أصغر عنصر في موقفها في صفيف. بالضبط ما كان يقوله يعقوب. تحتاج إلى تخزين بطريقة أو بأخرى. لذلك نحن ذاهبون لتبدأ هنا بالتكرار عبر مجموعة. نحن ذاهبون الى القول انه لدينا أول واحدة فقط لتبدأ. لذلك نحن ستكون لدينا كثافة العمليات أصغر يساوي في مجموعة ط. ذلك شيء واحد لإشعار، كل الوقت ينفذ هذه الحلقة، بدأنا خطوة واحدة أبعد على طول. عندما نبدأ نحن ننظر إلى هذا واحد. في المرة القادمة ونحن من خلال تكرار، بدأنا في هذا واحد وأسند لها أصغر قيمة لدينا. حتى انها تشبه الى حد بعيد فقاعة النوع حيث أننا نعلم أنه بعد مرور واحد، يتم فرز هذا العنصر الأخير. مع اختيار نوع، انها عكس ذلك تماما. في كل تمريرة، ونحن نعلم أن يتم فرز أول واحد. بعد مرور الثاني، و ستحفظ ثانية واحدة. وكما رأيتم مع أمثلة الشريحة، لدينا جزء فرزها وتبقي فقط المتنامية. ذلك من خلال وضع أصغر واحد لدينا لصفائف أنا، كل ما يفعل وتشنجا ما نحن نبحث في ذلك لتقليل عدد من المقارنات التي نتخذها. فهل يعقل أن الجميع؟ هل أنت بحاجة لي لتشغيل من خلال ذلك مرة أخرى أبطأ أو بكلمات مختلفة؟ انا سعيدة ل. موافق. لذلك نحن تخزين القيمة عند هذه النقطة، لكننا نريد أيضا لتخزين المؤشر. لذلك نحن ذاهبون لتخزين موقف أصغر واحد، والذي هو مجرد الذهاب لتكون ط. حتى الآن هو راض يعقوب. لدينا أشياء المخزنة. ونحن الآن بحاجة الى ان ننظر من خلال جزء من مجموعة لم يتم فرزها. حتى في هذه الحالة هذا سيكون لدينا غير مصنفة. هذا هو الأول. موافق. فما نحن في طريقنا للقيام سيكون للحلقة. كلما كنت في حاجة ل تكرار خلال صفيف، عقلك يمكن أن تذهب إلى للحلقة. حتى بالنسبة لبعض الباحث ك equals-- ماذا نفكر ك يجري على قدم المساواة لتبدأ؟ هذا ما وضعنا كما لدينا أصغر القيمة، ونحن نريد لمقارنتها. ماذا نريد مقارنتها؟ انها سوف تكون هذه واحدة المقبل، أليس كذلك؟ لذلك نحن نريد ك ليتم تهيئتها لط زائد 1 للبدء. ونريد ك في هذه الحالة نحن بالفعل حجم تخزين يصل هنا، حتى نتمكن من مجرد استخدام الحجم. حجم يجري على حجم المصفوفة. ونحن نريد فقط ل تحديث ك من جانب واحد في كل مرة. بارد. حتى الآن نحن بحاجة إلى إيجاد أصغر عنصر هنا. لذلك إذا أردنا تكرار خلال، نحن أريد أن أقول، إن مجموعة في ك أقل من أصغر value-- لدينا هذا هو المكان الذي نحن فعلا تتبع ما أصغر here-- ثم نريد أن إعادة تعيين ما هي أصغر قيمة لدينا. هذا يعني أنه، أوه، نحن بالتكرار عبر هنا. مهما كانت القيمة هي هنا ليس لدينا شيء أصغر. نحن لا نريد ذلك. نريد إعادة تعيين ذلك. حتى إذا كنا إعادة تعيين ذلك، ما فعله كنت تعتقد أنه قد يكون في هذا الرمز هنا؟ نريد إعادة تعيين أصغر والموقف. فما هو أصغر الآن؟ الطالب: صفيف ك. المدرب: صفيف ك. وما هو الموقف الآن؟ ما هي مؤشرات أصغر قيمة لدينا؟ انها ك فقط. لذلك ك مجموعة، ك، فإنها تصل المباراة. لذلك أردنا أن إعادة تعيين ذلك. ثم بعد أن وجدنا لدينا أصغر، حتى في نهاية هذه الحلقة ل هنا وجدنا ما أصغر لدينا القيمة، ولذا فإننا مبادلتها فقط. في هذه الحالة، لدينا مثل يقول أصغر قيمة هي هنا. هذا هو أصغر قيمة لدينا. نحن نريد فقط لمبادلة هنا، وهو ما أن وظيفة مبادلة في أسفل فعلت، والتي كتبنا للتو معا قبل بضع دقائق. لذلك ينبغي أن تبدو مألوفة. وبعد ذلك سيتم تكرار فقط من خلال حتى يصل كل الطريق لهذه الغاية، مما يعني أنك يكون الصفر العناصر التي لم يتم فرزها وكل شيء تم فرزها. معنى؟ قليلا أكثر تحديدا؟ مساعدة الرمز؟ الطالب: بالنسبة لحجم، لا يمكن ان تحديد ذلك حقا أو تغييره، كيف لا تعرف؟ المدرب: لذا شيء واحد ل نلاحظ هنا هو حجم كثافة العمليات. لذلك نحن نقول في هذا النوع sort-- هي وظيفة في هذا case-- انها اختيار نوع، لقد مرت عليه في مع وظيفة. حتى إذا لم يكن مرت عليه في، كنت ستفعل شيئا كما هو الحال مع طول المصفوفة أو كنت تكرار خلال للعثور على طول. ولكن لانها مرت عليه في، يمكننا فقط استخدامها. أنت مجرد افتراض أن المستخدم منحكم صحيح أن حجم يمثل في الواقع حجم من مجموعة الخاصة بك. بارد؟ إذا يا رفاق لديه أي مشكلة مع هذه أو تريد المزيد من ممارسة أنواع الترميز لوحدك، يجب عليك الذهاب إلى study.cs50. انها أداة. لديهم المدقق أن يمكنك الكتابة فعلا. يفعلون شبة الكود. لديهم المزيد من أشرطة الفيديو والشرائح بما في ذلك تلك التي كنت تستخدم هنا. حتى إذا كنت لا تزال شعور غامض قليلا، حاول أن الخروج. كما هو الحال دائما، ويأتي الحديث معي أيضا. السؤال؟ الطالب: هل تقول ل ويعرف حجم سابقا؟ المدرب: نعم. ويعرف حجم ما يصل سابقا هنا في تعريف الدالة. هكذا تفترض التي تم تمريرها في من قبل المستخدم، وتبسيط، نحن ذاهبون لنفترض أن أعطى المستعمل لنا الحجم الصحيح. بارد. ذلك أن اختيار نوع. الرجال، وأنا أعلم أننا نتعلم الكثير اليوم. انها بيانات كثيفة للقسم. حتى مع ذلك، نحن ذاهبون الذهاب إلى الإدراج النوع. موافق. حتى قبل أن يتعين علينا القيام به تحليلنا وقت هنا. حتى في أفضل الأحوال، منحت منذ أن أظهر لكم الجدول أنا بالفعل نوع من أعطى بعيدا. ولكن أفضل وقت الحال، ماذا نفكر؟ كل شيء تم فرزها. N المربعة. أي شخص له تفسير لماذا تظن؟ الطالب: أنت مقارنة through-- المدرب: الحق. كنت من خلال مقارنة. في كل التكرار، على الرغم من نحن decrementing هذا من جانب واحد، كنت لا تزال تبحث عن طريق كل شيء للعثور على أصغر واحد. لذلك حتى لو قيمة أصغر بك هنا في البداية، كنت لا تزال مقارنتها ضد كل شيء آخر للتأكد من أنها أصغر شيء. وهكذا لن تضطر في نهاية المطاف من خلال تشغيل ن مربع تقريبا مرات. حسنا. وما هو أسوأ الحالات؟ كما ن تربيع لأنك ذاهب أن تفعل ذلك الإجراء نفسه. حتى في هذه الحالة، واختيار لديه شيء الفرز أننا ندعو أيضا وقت التشغيل المتوقع. حتى في البعض الآخر، ونحن نعلم فقط الحدود العليا والسفلى. اعتمادا على كيفية مجنون لدينا القائمة أو كيف أنه لم يتم فرزها، أنها تختلف بين ن ن أو المربعة. نحن لا نعرف. ولكن لاختيار نوع له نفس أسوأ وأفضل حال، أن يخبرنا بأن مهما يكن نوع من المدخلات نحن لديهم، سواء كان ذلك كليا فرز أو كليا عكس فرزها، انها ذاهب الى اتخاذ نفس المقدار من الوقت. حتى في هذه الحالة، إذا كان ل تذكر من طاولتنا، كان في الواقع قيمة هذه الأنواع اثنين لا يكون، وهو وقت التشغيل المتوقع. لذلك نحن نعلم أنه كلما ندير اختيار نوع، انها مضمونة ل تشغيل الوقت ن المربعة. لا يوجد هناك تباين. من المتوقع فقط. ومرة أخرى، إذا كنت تريد أن تتعلم أكثر من ذلك، تأخذ CS 124 في الربيع. حسنا. لقد رأينا هذا واحد. بارد. نوع الإدراج ذلك. وانا ذاهب على الارجح على الحريق من خلال هذا. أنا لن يكون يا رفاق رمز ذلك. سنقوم مجرد المشي من خلال ذلك. لذلك الإدراج النوع هو النوع من مماثلة لاختيار نوع في أن لدينا كل من لم يتم فرزها وفرزها جزء من مجموعة. ولكن ما هو مختلف هو أن ونحن نمضي من خلال واحدا تلو الآخر، نأخذ فقط مهما كان عدد هو القادم في منطقتنا لم يتم فرزها، وترتيب هذا الامر بشكل صحيح في مجموعة فرزها لدينا. أنه سوف يكون أكثر منطقية مع مثال. لذلك كل شيء يبدأ كما لم يتم فرزها، تماما مثل مع اختيار نوع. ونحن في طريقنا لفرز هذا في ترتيب تصاعدي كما كنا. هكذا الأول تمريرة لدينا نأخذ القيمة الأولى ونحن نقول، حسنا، أنت الآن في قائمة من قبل نفسك. لأنك في قائمة من قبل نفسك، يتم فرز لك. تهنئة لكونها العنصر الأول في هذه المجموعة. كنت بالفعل فرز جميع لوحدك. حتى الآن لدينا فرز ومجموعة لم يتم فرزها. حتى الآن نحن نأخذ أولا. ما يحدث بين هنا وهنا هو أن نقول، حسنا، نحن ذاهبون للنظر في القيمة الأولى للمجموعة التي لم يتم فرزها لدينا ونحن في طريقنا للمساهمة في في المكان الصحيح في مجموعة فرزها. فما نقوم به هو أن نأخذ 5 و نقول، حسنا، 5 أكبر من 3، لذلك نحن مجرد حق أدخله إلى اليمين من ذلك. نحن في حالة جيدة. لذلك فإننا نذهب إلى موقعنا على احد القادم. ونحن نأخذ 2. نقول، حسنا، 2 أقل من 3، لذلك نحن نعرف أنه يجب أن يكون في أمام قائمتنا الآن. فما نقوم به هو أننا دفع 3 و 5 الأسفل وننتقل إلى 2 أن الفتحة الأولى. لذلك نحن مجرد إدخاله المكان الصحيح ينبغي أن يكون. ثم ننظر لدينا واحدة المقبل، ونحن نقول 6. OK، 6 هو أكبر من كل شيء في مجموعة فرزها لدينا، لذلك نحن مجرد علامة على أن النهاية. ثم ننظر إلى 4. 4 أقل من 6، انها أقل من 5 ولكن هذا أكبر من 3. لذلك نحن فقط ضع ذلك الحق في الوسط بين 3 و 5. لجعل هذا قليلا قليلا أكثر واقعية، هنا هو نوع من فكرة عما حدث. لذلك لكل عنصر لم يتم فرزها، ونحن تحديد مكان في الجزء فرزها هو. حتى مع الأخذ في الاعتبار فرزها ولم يتم فرزها، علينا أن تعبر من خلال والشكل من حيث تناسبها في مجموعة فرزها. ونحن أدخله عن طريق تحويل العناصر على يمين عليه. ثم واصلنا فقط بالتكرار عبر حتى نحن لدينا قائمة تم فرزها تماما حيث لم يتم فرزها الآن هو الصفر وفرزها يستغرق فترة تصل إلى مجمل قائمتنا. هكذا، مرة أخرى، لجعل الأمور أكثر أكثر واقعية، لدينا شبة الكود. وذلك أساسا لأني غير يساوي 0 إلى ن ناقص 1، هذا مجرد طول مجموعة لدينا. لدينا بعض العناصر التي تساوي مجموعة الأولى أو المؤشرات الأولى. وضعنا ي يساوي ذلك. وذلك في حين ي أكبر من الصفر ومجموعة، ي ناقص 1 أكبر من عنصر، لذلك كل ما يفعل والتأكد من أن ك ي تمثل حقا جزء من مجموعة لم يتم فرزها. وذلك في حين لا يزال هناك أشياء لفرز وي ناقص واحد ما is-- هو العنصر لها؟ كان يعرف أبدا J هنا. انها نوع من مزعج. موافق. على أي حال. لذلك ي ناقص 1، كنت فحص العنصر أمامها. كنت تقول، حسنا، هو العنصر قبل أينما كنت am-- دعنا رسم الواقع من ذلك. لذلك دعونا نقول أن هذا مثل على مسار الثاني لدينا. لذلك أنا ذاهب ليكون مساويا إلى 1، والذي هو هنا. لذلك أنا ذاهب ليكون مساويا ل1. وهذا سيكون 2، 4، 5، 6، 7. حسنا. لذلك العنصر لدينا في هذه الحالة سيكون يساوي 4. ولدينا بعض ي هذا سيكون يساوي 1. أوه، ي وdecrementing. هذا ما هو عليه. لذلك ي يساوي ط، فما هو هذا القول بأن ونحن نمضي قدما، نحن فقط التأكد من اننا لم تنته فهرسة هذه الطريقة عندما نحاول لإدراج الأشياء في القائمة التي تم فرزها لدينا. لذلك عندما ي يساوي 1 في هذه الحالة و مجموعة ي ناقص one-- ذلك مجموعة ي ناقص 1 هو 2 في هذا case-- اذا كان هذا أكثر من عنصر، ثم كل هذا تقوم به وتحول الأمور. حتى في هذه الحالة، مجموعة ي ناقص واحد ستكون مجموعة الصفر، وهو 2. 2 ليس أكبر من 4، لذلك هذا لا يتم تنفيذ. لذلك التحول لا يتحرك إلى أسفل. هذا ما يفعله هنا هو فقط تتحرك مجموعة فرزها الخاص بك إلى أسفل. في هذه الحالة، في الواقع، نحن يمكن do-- دعونا نجعل هذا 3. حتى لو كنا على المشي من خلال و هذا المثال، نحن الآن هنا. يتم فرز هذا. وهذا لم يتم فرزها. بارد؟ لذلك أنا يساوي 2، وذلك عنصر لدينا هو يساوي 3. ولنا ي يساوي 2. ولذا فإننا نتطلع من خلال ونحن نقول، حسنا، هو مجموعة ي ناقص واحد أكبر من العنصر أننا نبحث في؟ والجواب هو نعم، أليس كذلك؟ 4 أكبر من 3 و ي هو 2، بحيث ينفذ هذا القانون. حتى الآن ما نقوم به في مجموعة 2، لذلك هنا، فإننا مقايضتهم. لذلك نحن نقول فقط، حسنا، مجموعة في 2 والآن ستكون 3. وي يسير على قدم المساواة ي ناقص 1، والذي هو 1. هذا فظيع، ولكن يا رفاق على هذه الفكرة. J هو الآن يساوي 1. ومجموعة ي هو مجرد الذهاب ليكون يساوي عنصر لدينا، والتي كانت 4. فرحت الممحاة شيء أنا لا ينبغي أو يكون شيئا miswrote، ولكن يا رفاق على هذه الفكرة. انها تتحرك في ن. ثم لو كان هذا، فإنه سيكون حلقة ومرة أخرى فإن ذلك نقول، حسنا، هو 1 ي الآن. ومجموعة ي ناقص 1 هو الآن 2. 2 هو أقل من عنصر لدينا؟ لا؟ وهذا يعني أن لدينا إدراج هذا العنصر في المكان الصحيح في مجموعة وفرزها لدينا. ثم يمكننا اتخاذ هذا ونحن نقول، حسنا، لدينا مجموعة وفرزها هنا. وسيستغرق هذا الرقم 6 ويكون مثل، حسنا، هو 6 أقل من هذا العدد؟ لا؟ بارد. نحن بخير. نفعل ذلك مرة أخرى. نقول 7. هو أقل من 7 نهاية مجموعة من فرزها لدينا؟ لا. لذلك نحن بخير. ولذلك فإن هذا من شأنه أن فرزها. أساسا كل هذا لا لأنها تأخذ قائلا العنصر الأول من مجموعة غير مصنفة الخاص بك، معرفة أين تذهب في مجموعة فرزها الخاص بك. وهذا يستغرق سوى الرعاية مقايضة للقيام بذلك. كنت في الأساس مجرد مقايضة حتى انها في المكان الصحيح. الصورة المرئية هي أن كنت كل شيء يتحرك أسفل عن طريق القيام بذلك. حتى انها مثل نصف فقاعة نوع سقو. تحقق من دراسة 50. أنا أوصي تحاول إلى رمز هذا بنفسك. إذا كان لديك أي مشاكل أو تريد رؤية رمز عينة لنوع الإدراج، واسمحوا لي أن أعرف. أنا دائما حولها. حتى أسوأ حالة وقت التشغيل وأفضل حالة التشغيل. كما رأيتم الرجل من الجدول أنا بالفعل أظهر لك، وانها على حد سواء ن مربع و n. ذلك نوع من الخروج عن ما تحدثنا حول أنواع السابقة مع دينا، والأسوأ حالة وقت التشغيل هو أنه إذا كان انه لم يتم فرزها تماما، لدينا لمقارنة كل هذه الأوقات ن. ونحن نفعل الكثير من المقارنات كله لأنه إذا كان في ترتيب عكسي، نحن ذاهبون لنقول، حسنا، هذا هو نفسه، وهذا أمر جيد، وهذا واحد سوف يتعين مقارنة ضد أول واحد لنقلها إلى الخلف. وكلما تقدمنا ​​نحو نهاية الذيل، لدينا للمقارنة، مقارنة، و مقارنة ضد كل شيء. لذلك ينتهي به الأمر ن مربع تقريبا. إذا كان صحيحا فإنك نقول، حسنا، 2، كنت جيدة. 3، وكنت مقارنة مع 2. كنت جيدة. 4، يمكنك فقط مقارنة الذيل. كنت جيدة. 6، مقارنة الذيل، وكنت على ما يرام. لذلك كل بقعة لو كان بالفعل فرزها، كنت صنع المقارنة احدة. حتى انها مجرد ن. ولأن لدينا حالة أفضل وقت ن وأسوأ وقت التشغيل حالة ن مربع، وليس لدينا وقت التشغيل المتوقع. ذلك يعتمد فقط على فوضى قائمتنا هناك. ومرة أخرى، وآخر رسم بياني وجدول آخر. حتى الاختلافات بين الأنواع. أنا مجرد الذهاب إلى نسيم من خلال، و أشعر أننا تحدثنا على نطاق واسع حول كيف كل نوع وتختلف وربط معا. لذا تصنيف دمجي هو آخر واحد وسوف يحمل لكم مع الرجال. نحن لدينا صورة ملونة جميلة. حتى دمج النوع هو خوارزمية العودية. لذلك يا رفاق معرفة ما وظيفة متكررة هي؟ أي شخص يريد أن يقول؟ تريد أن تجرب؟ ولذلك فإن وظيفة متكررة هي فقط وظيفة تطلق على نفسها. حتى إذا كنت على دراية الرجال مع تسلسل فيبوناتشي، وهذا ما تراه العودية ل كنت تأخذ السابقتين وإضافتها معا للحصول على واحد الخاص بك المقبل. العودية لذلك، أعتقد دائما من العودية كما مثل دوامة لذلك كنت مثل المتصاعد وصولا الى ذلك. ولكن انها مجرد وظيفة تطلق على نفسها. و، في الواقع، أنا حقا بسرعة يمكن أن تظهر لك ما يشبه. حتى العودية هنا، إذا نظرنا، وهذا هو الطريق عودي إلى تلخيص أكثر من صفيف. لذلك كل ما نقوم به هو لدينا وظيفة المبلغ خلاصة القول أن يأخذ حجم وصفيف. وإذا لاحظت، وحجم التناقصات من جانب واحد في كل مرة. وكل ما يفعله هو إذا كان x يساوي zero-- ذلك إذا كان حجم المصفوفة تساوي zero-- ذلك بإرجاع صفر. وإلا فإنه يلخص هذا العنصر الأخير للمجموعة، ثم يأخذ مبلغا من بقية المصفوفة. حتى انها مجرد تقسمها إلى مشاكل أصغر وأصغر. قصة قصيرة طويلة، العودية، وظيفة تطلق على نفسها. إذا كان هذا هو كل ما خرج من هذا، هذا هو ما هي وظيفة متكررة. إذا كنت تأخذ 51، سوف تحصل جدا، مريحة جدا مع العودية. انها حقا بارد. فقد كان من المنطقي في مثل 03:00 ليلة واحدة خارج. وكنت مثل، لماذا وأنا أبدا استخدام هذا؟ وذلك لدمج النوع، أساسا ما يجري القيام به هو انها ل الذهاب إلى كسرها نزولا وكسرها لأسفل حتى انها عناصر واحدة فقط. عناصر واحدة هي سهلة لفرز. نرى ذلك. إذا كان لديك عنصر واحد، هو يعتبر بالفعل تم فرزها. إلى ذلك مدخلا من عناصر N، إذا كان n أقل من 2، العودة فقط لأن ذلك وسيلة انها إما 0 أو 1 كما رأينا. تعتبر هذه العناصر فرزها. كسر خلاف ذلك في نصف. فرز الشوط الأول، فرز الثانية النصف، ومن ثم دمجها معا. لماذا يسمى ذلك دمج النوع. لذلك لدينا هنا سنقوم فرز هذه. حتى نحافظ على وجود لهم حتى حجم المصفوفة هو 1. حتى عندما يكون 1، نعود فقط لأن هذا هو مجموعة فرزها، وهذا هو مجموعة وفرزها، وهذا مجموعة وفرزها، ونحن فرز جميع. حتى ذلك الحين ما نفعله هو أننا بدء دمجها معا. وبالتالي فإن الطريقة يمكنك التفكير هو دمج يمكنك فقط إزالة أصغر عدد كل من المصفوفات الفرعية ومجرد إلحاق إلى مجموعة ظهرت. حتى إذا كنت انظر هنا، عندما يكون لدينا هذه مجموعات لدينا 4 و 6 و 1. عندما نريد أن دمج هذه، نحن ننظر إلى هذه الأولين ونحن نقول، حسنا، 1 هو أصغر، فإنه يذهب إلى الجبهة. 4 و 6، لا يوجد شيء للمقارنة ل، مجرد علامة على أن النهاية. عندما كنا الجمع بين هذين، نحن فقط أخذ واحد أصغر من هذين، لذلك فمن 1. والآن نأخذ أصغر من هذين، بحيث 2. أصغر من هذين، 3. أصغر من هذين، 4، 5، 6. لذلك كنت سحب قبالة هذه. لأنهم و تم فرزها سابقا، لديك واحد فقط المقارنة في كل مرة هناك. لذلك المزيد من أكواد هنا، والتمثيل العادل. لذلك يمكنك البدء في الوسط و أنت اليسار نوع والحق ثم انك دمج تلك. وليس لدينا كود لدمج الحق هنا. ولكن، مرة أخرى، وإذا ذهبت على 50 دراسة، وأنها سوف تكون هناك. تأتي خلاف الكلام لي إذا كنت لا تزال مشوشة. ذلك شيء بارد هنا هو أن أفضل الأحوال، أسوأ حال، ووقت التشغيل المتوقع كلها في سجل ن، والتي هو أفضل بكثير مما كنا بحثنا ينظر لبقية أنواع لدينا. رأيناه ن تربيع وما نحن في الواقع تحصل هنا ون ن تسجيل، وهو أمر عظيم. ننظر في كيفية أفضل بكثير وهذا هو. هذا منحنى لطيف. أكثر من ذلك بكثير كفاءة. إذا كنت من أي وقت مضى يمكن، استخدام دمج النوع. سيوفر لك الوقت. ثم مرة أخرى، كما قلنا، إذا كنت أسفل في هذه المنطقة أقل، لا يجعل هذا الكثير من الفرق. يمكنك الحصول على ما يصل إلى الآلاف والآلاف من المدخلات، تريد بالتأكيد خوارزمية أكثر كفاءة. ومرة أخرى، لدينا جدول جميل للجميع أنواع الرجال التي كنت تعلمت اليوم. إذا كنت لا تعرف انها كانت يوما كثيفة. هذا لن بالضرورة لمساعدتك في PSET الخاص بك. ولكن أريد فقط أن تجعل إخلاء هذا القسم لا يقتصر فقط على psets. كل هذه المواد هي عادلة اللعبة لانتخابات التجديد النصفي لديك. وأيضا إذا كان لديك على تواصل مع CS، هذه هي الأسس الهامة حقا ان كنت بحاجة إلى معرفته. وحتى بعض الأيام سيكون المزيد من القليل من المساعدة PSET، لكن بضعة أسابيع سيكون المزيد من المحتوى الفعلي قد لا يبدو السوبر مفيد لك في الوقت الراهن، ولكن أعدك إذا كنت لا تزال سيكون على جدا، ومفيدة جدا. لذلك هذا كل شيء عن القسم. وصولا الى السلك. أنا فعلت هذا في غضون دقيقة واحدة. ولكن هناك تذهب. وسوف يكون لي الكعك أو الحلوى. هو أي شخص حساسية ل أي شيء، بالمناسبة؟ البيض والحليب. حتى الكعك هي لا؟ موافق. حسنا. الشوكولاته لا؟ النجمي. النجمية جيدة. موافق. ونحن في طريقنا ل النجمي الاسبوع المقبل ثم. هذا ما سوف يحصل. يا رفاق ديك أسبوع عظيم. قراءة المواصفات الخاصة بك. اسمحوا لي أن أعرف إذا كان لديك أي أسئلة. وينبغي أن يكون PSET درجتين أصل إليك بحلول يوم الخميس. إذا كان لديك أي أسئلة حول كيف متدرج شيء أو لماذا أنا متدرج شيء الطريق أنا لم، يرجى الكتابة لي، وتأتي التحدث معي. أنا مجنون هذا القليل الاسبوع، ولكن أعدك ما زلت سوف الرد في غضون 24 ساعة. حتى يكون لها عظيم الأسبوع، الجميع. حظا سعيدا على PSET الخاص بك.