SPEAKER 1: هی همه! خوش آمدید به بخش. خیلی خوشحال برای دیدن بسیاری از شما هر دو در اینجا، و هر کس که در حال تماشای آنلاین. بنابراین، به عنوان بازگشت خوش آمدید معمول است. من امیدوارم که همه شما تا به حال دوست داشتنی آخر هفته، پر از استراحت، آرامش. همین دیروز زیبا از بود. بنابراین، من امیدوارم که شما خارج از منزل لذت می برد. 

بنابراین برای اولین بار یک زن و شوهر از اطلاعیه. درجه بندی. بنابراین، بسیاری از شما باید بدست ایمیل از من درباره Pset خراش خود را، و همچنین برای Pset 1 درجه بندی. بنابراین، فقط یک زن و شوهر از چیزهایی. مطمئن باشید که برای استفاده از check50 در style50. این به معنای منابع را برای شما بچه ها، مطمئن شوید که شما در حال گرفتن عنوان بسیاری از نقاط که شما می توانید بدون دلیلی از دست دادن آنها. بنابراین، چیزهایی مانند سبک بسیار مهم است. ما در حال رفتن به خارج از آن. برخی از شما ممکن است در حال حاضر متوجه شده است که از Pset شما. و check50 فقط یک واقعا راه آسان برای مطمئن شوید که ما در واقع بازگشت چه نیاز به بازگشت به کاربر، و که همه چیز به درستی کار می کند. 

در یادداشت دوم، مطمئن شوید که شما آپلود همه چیز را به پوشه درست باشد. این باعث می شود زندگی من فقط یک کمی مشکل تر اگر شما Pset 2 آپلود به Pset 1 چون وقتی که من همه چیز دانلود کنید، آنها را به درستی دانلود نشده است. و من می دانم که آن را ضعیف کمی در یک سیستم به آن عادت، اما فقط فوق العاده بود مراقب باشید، اگر تنها برای من، به طوری که زمانی که شما در حال گرفتن ایمیل در مثل 02:00 و من درجه بندی هستم. اگر نه چون من باید نگاه تمام اطراف برای Pset شما. سرد. 

من می دانم آن اوایل، اما من کاملا خاموش نگهبان گرفته شد توسط یک مقاله که به دلیل این جمعه که استادان من فقط می خواهم شد، آه آره. به یاد داشته باشید، شما باید مقاله با توجه به روز جمعه. بنابراین، من می دانم که هیچ کس دوست در مورد لاس فکر می کنم، اما اولین مسابقه خود را در اکتبر 15، که اکتبر شروع این هفته. بنابراین، ممکن است دیر شود از شما انتظار می رود تمام شده است. به طوری که شما در حال پرتاب کردن گارد هنگامی که من بخش هفته آینده که ذکر آه، هفته آینده مسابقه خود را، من فکر کردم من می خواهم به شما یک کمی بیشتر به من بدهید از سر در حال حاضر. 

بنابراین، مشکل خود را تعیین می کنند، تعداد سه. چگونه مردم را مشاهده کرده اند تنظیمات از روی کنجکاوی؟ OK. ما یک زن و شوهر است. نوع از گذشته هفته اما این OK. من می دانم که آن را زیبا بود. بنابراین شکستن. قطعا بعد از شما انجام می شود امروز مشخصات خود را حداقل به عنوان خوانده شده سعی کنید مانند دانلود کد توزیع و در حال اجرا مانند اولیه برای اولین بار چیزی که از شما خواسته. از آنجا که ما با استفاده از کد توزیع و کتابخانه که ما تنها شده using-- --It تنها بار دوم ما این Pset انجام داده ام، چیز دیوانه اتفاق می افتد با دستگاه خود، و شما می خواهید برای پیدا کردن که در حال حاضر در مقابل بعد. 

چرا که اگر آن شب پنجشنبه است و یا آن را چهارشنبه شب و برای برخی از دلیل لوازم خانگی خود را فقط نمی می خواهید برای اجرای با کتابخانه و یا با توزیع کد، که به معنای شما حتی نمی توانید شروع به انجام برنامه نویسی. از آنجا که شما نمی توانید چک کنید برای دیدن اگر آن کار می کند. نمی خوای شما قادر برای دیدن اگر آن را کامپایل. شما می خواهید به اوایل در مراقبت از آن هفته، هنگامی که شما هنوز هم می توانید به من ایمیل و یا یکی از TFS دیگر، و ما می توانیم آن ثابت است. از آنجا که این مسائل هستند که می رویم به شما را متوقف از هر گونه پیشرفت واقعی است. این یک اشکال را دوست ندارد، که شما فقط می توانید نوع جست و خیز است. اگر شما با داشتن مسائل با شما لوازم خانگی و یا کد توزیع، شما واقعا می خواهید برای دریافت کنید که گرفته مراقبت از زودتر و نه بعد. بنابراین حتی اگر شما نمی خوای در واقع شروع برنامه نویسی، دانلود توزیع کد، به عنوان خوانده شده مشخصات، مطمئن شوید که همه چیز کار می کند وجود دارد. OK؟ اگر شما فقط می توانید انجام این کار، من قول می دهم زندگی خود را ساده تر خواهد شد. و به این ترتیب شما احتمالا رفتن به انجام آن در حال حاضر درست است؟ OK. بنابراین، هر گونه سوال وجود دارد؟ هر چیز لجستیکی؟ هر کس خوب است؟ OK. 

سلب مسئولیت برای کسانی که از شما در اتاق و آنلاین. من قصد دارم به تلاش به تغییر بین پاورپوینت در لوازم خانگی از آنجا که ما در حال رفتن برای انجام برخی از برنامه نویسی امروز تقاضای محبوب از ناشناس نظرسنجی پیشنهاد من در هفته گذشته خبر از. بنابراین، ما انجام خواهد داد برخی از برنامه نویسی. بنابراین، اگر شما بچه ها همچنین می خواهم به آتش تا لوازم خود را، و شما باید یک ایمیل کردم از من، با یک فایل نمونه. لطفا در صورت تمایل به انجام این کار. 

بنابراین، ما قصد داریم به بحث در مورد GDB، که یک دیباگر. آن را برای کمک به شما نوع کشف کردن که در آن همه چیز اشتباه در کد شما. این واقعا تنها راه را برای شما به مرحله از طریق کد شما آن را به عنوان اتفاق می افتد، و قادر به چاپ کردن متغیر یا آنچه در واقع اتفاق می افتد در زیر هود آیات برنامه شما فقط در حال اجرا، آن را مانند گسل است، و دوست دارید، هیچ ایده هستید آنچه فقط در اینجا اتفاق افتاده است. من نمی دانم که چه آن را در خط شکست خورده است. من نمی دانم که در آن به خطا رفته است. بنابراین، GDB است رفتن به شما کمک کند با آن. همچنین، اگر شما تصمیم می گیرید ادامه بله، و 61، آن را واقعا خواهد شد، واقعا می شود شما بهترین دوست، چون من می تواند به شما بگوید چون من قصد دارم از طریق آن کلاس. 

ما قصد داریم تا در باینری نگاه جستجو، که اگر شما به یاد داشته باشید بچه ها بزرگ به عنوان مثال دفترچه تلفن عینک از کلاس. ما در اجرای آن، و راه رفتن را از طریق آن کمی بیشتر، و سپس ما در حال رفتن را از طریق چهار انواع مختلف، که حباب، انتخاب، درج، و ادغام. سرد. بنابراین، GDB به عنوان اشاره کردم، یک دیباگر است. و این نوع از بزرگ همه چیز، از توابع بزرگ و یا دستورات که شما در GDB استفاده کنید، و من راه رفتن خواهد شد شما را از طریق نسخه ی نمایشی از آن را در یک ثانیه. 

بنابراین، این است و نه فقط رفتن به ماندن انتزاعی. من سعی خواهم کرد و آن را به عنوان بتن که ممکن است برای شما بچه ها. بنابراین، شکستن. این هر دو خواهد شکست است مانند، برخی از شماره ها، که نشان دهنده یک خط در برنامه های خود، یا شما می توانید یک تابع نام. بنابراین، اگر شما می گویند شکستن اصلی، آن را در متوقف اصلی، و اجازه دهید شما را از طریق آن تابع به راه رفتن. 

به همین ترتیب، اگر شما برخی از خارجی عمل مانند تعویض یا مکعب، که ما در هفته گذشته نگاه کرد. اگر به شما می گویند شکستن یکی از آن، که هر زمان که برنامه شما بازدید، آن را برای شما صبر کنید آن را چه باید بکنید. قبل از آن فقط اجرا خواهد شد، بنابراین شما در واقع می تواند در داخل تابع گام به گام و ببینید چه خبر است. بنابراین، بعد، تنها بیش از پرش خط بعدی، می رود بیش از توابع. گام. این ها همه انتزاعی کم است. بنابراین، من فقط رفتن را از طریق آنها اجرا شود، اما شما آنها را در استفاده در یک ثانیه را ببینید. 

گام به یک تابع. بنابراین به عنوان I، گفت مانند تعویض در حالت روشن، آن را به شما اجازه در واقع به عنوان اگر شما مانند پله از لحاظ جسمی در داخل، شما می توانید با کسانی که متغیر ظرف غذا، چاپ از آنچه که هستند، ببینید چه خبر است. فهرست به معنای واقعی کلمه فقط چاپ از کد های اطراف. بنابراین، اگر شما نوع را فراموش کرده ام که در آن شما در برنامه های خود هستند، یا شما خوبی چه خبر است در اطراف آن، این فقط چاپ کردن یک بخش از دوست پنج یا شش خط در اطراف آن. بنابراین، شما می توانید گرا در مورد جایی که شما هستند. 

چاپ برخی از متغیر. بنابراین، اگر شما کلید مانند در سزار، که ما را نگاه کنید. شما می توانید چاپ کلیدی در هر نقطه می گویند. این به شما بگوید که چه مقدار است بنابراین که، شاید جایی در طول راه، شما کلید خود را overwrote. شما در واقع می تواند بگوید که به خاطر شما در واقع می تواند که ارزش را مشاهده کند. 

در مردم محلی، فقط چاپ از متغیرهای محلی خود را. بنابراین، در هر زمان که شما در یک حلقه هستید، و شما فقط می خواهید برای دیدن می کنم که. من من چیست؟ این مقدار کلید چیست که من اینجا مقداردهی اولیه؟ پیام در این نقطه چیست؟ این فقط تمام چاپ از آن، به طوری که شما آیا به صورت جداگانه نیست می گویند، چاپ اول چاپ پیام. چاپ کلیدی. و سپس نشان دادن. چه که انجام می دهد به شما به عنوان گام به گام از طریق این برنامه، آن فقط مطمئن شوید که این نمایش برخی از متغیر های خاص در هر نقطه. به طوری که شما also-- --it است نوع یک میانبر است که در آن شما لازم نیست به رفتن ادامه می کنم که. چاپ کلیدی و یا آن را چاپ I. فقط به طور خودکار آن را برای شما. 

بنابراین، با که، ما در حال رفتن تا ببینید که چگونه این می رود. من قصد دارم به سعی و سوئیچ به دستگاه من. ببینید اگر من می توانم این کار را انجام. همه. ما فقط در حال رفتن به آن را منعکس. هیچ چیز دیوانه وجود دارد در لپ تاپ من به هر حال. OK. این نیاز به این یکی. این خیلی کوچک. بیایید ببینیم که اگر ما می توانیم این کار را انجام. 

OK. آلیس است که به وضوح تلاش در اینجا فقط کمی، اما ما آن را در یک momento دریافت کنید. OK. ما فقط رفتن به افزایش این. OK. هر کس می تواند نوع دید که؟ شاید کمی؟ من می دانم که آن را کمی کوچک است. شما کاملا نمی فهمم چگونه این بزرگتر. اگر کسی می داند. آیا کسی می داند که چگونه به آن را بزرگتر؟ OK. ما قصد داریم به رول با آن است. مهم نیست به هر حال به دلیل آن را فقط که کد است که شما باید داشته باشد. 

آنچه مهم تر ترمینال در اینجا است. و ما را در اینجا چرا آنقدر کوچک؟ تنظیمات. اوه. آیک درست است. چگونه این چیست؟ از وجود دارد. این است که برای همه بهتر است؟ OK،. سرد. 

شما می دانید زمانی که شما در یک CS هستید مشکلات فنی کلاس از نوع بخشی از the-- بنابراین، اجازه دهید این روشن است. OK. بنابراین، حق در اینجا در بخش، که ما در اینجا بود. سزار یک فایل اجرایی می باشد. پس من آن را ساخته شده است. بنابراین، یک چیز را به درک با GDB است که آن را تنها بر روی فایل های اجرایی کار می کند. بنابراین، شما می توانید آن را در یک dotsy اجرا کنید. شما باید به واقع اطمینان حاصل کنید که کد خود را کامپایل، و که آن را در واقع می تواند اجرا شود. 

بنابراین، مطمئن شوید که اگر آن را نمی کند کامپایل، می توانید آن را به کامپایل، به طوری که شما می توانید از طریق نوع آن را اجرا کنید. بنابراین، برای شروع GDB، همه شما باید انجام دهید، گلوریا نوع GDB، و پس از آن فقط فایلی که شما می خواهید. من همیشه املای غلط سزار. اما شما می خواهید مطمئن شوید از آن اجرایی است، تیتانیم در نقطه فلش به طوری که معنی است که شما در حال رفتن برای اجرای CSI شما به اجرا این فایل یا با دیباگر. OK. بنابراین، شما انجام این کار، شما این نوع از عجیب. این فقط همه چیز در مورد دیباگر است. شما واقعا به نگرانی در مورد آن در حال حاضر. و به عنوان شما می بینید، ما باید این پرانتز باز، تولید ناخالص داخلی، پرانتز بسته، و فقط نوع به نظر می رسد خط فرمان ما، درست است؟ 

بنابراین، آنچه ما می خواهیم به do-- --So، اولین چیزی که این است که ما می خواهیم انتخاب جایی برای شکستن آن. بنابراین، یکی از اشکال وجود دارد در این برنامه سزار که من معرفی، که ما قصد داریم برای پیدا کردن. این چه می کند آن را می کشد ورودی Barfoo در همه کلاه، و برای برخی از دلیل آن A. تغییر نمی این فقط برگ آن را به تنهایی، آیا هر چیز دیگری درست است، اما نامه دوم بدون تغییر باقی مانده است. بنابراین، ما در حال رفتن را امتحان کنید و که چرا از آن است. بنابراین، اولین چیزی که شما به طور معمول می خواهید برای انجام هر زمان که شما در GDB شروع است شکل که در آن به شکستن آن. 

بنابراین سزار یک برنامه بسیار کوتاه است. ما فقط باید یک تابع، درست است؟ عملکرد ما در سزار چه بود؟ فقط یک تابع، از سمت راست به اصلی وجود دارد؟ اصلی یک تابع است برای همه برنامه های خود را. اگر شما اصلی را نداشته باشند، ممکن است کمی نگران است در حال حاضر، اما من امیدوارم که همه شما در صفحه اصلی وجود دارد. بنابراین، آنچه ما می توانیم انجام دهیم، این است که می تواند فقط شکستن اصلی، فقط می خواهم که. بنابراین، آن را می گوید، OK. ما یک نقطه انفصال ما مجموعه ای وجود دارد. 

بنابراین، در حال حاضر چیزی که به یاد داشته باشید سزار است یک فرمان سمت راست خط استدلال می گیرد و ما انجام داده اند که در هر نقطه است. بنابراین، آنچه که شما باید انجام دهید این است که هنگامی که شما در واقع به اجرا این برنامه، هر برنامه ای که شما هستید در حال اجرا در GDB که نیاز به خط فرمان استدلال، شما در حال رفتن به ورودی زمانی که شما برای اولین بار شروع به در حال اجرا است. بنابراین، در این مورد، ما اجرا با یک کلید سه. و آن را در واقع شروع خواهد شد. 

بنابراین، اگر شما اینجا را ببینید، ما باید اگر RC است به 2 برابر نیست. بنابراین اگر شما بچه ها همه که فایلی که من تا ارسال می شود شما خواهید دید که که مانند خط اول تابع اصلی ما، درست است؟ این چک کردن برای دیدن اگر ما تعداد صحیح استدلال. بنابراین، اگر شما خوبی اگر RC درست باشد، شما می توانید چیزی درست مثل چاپ RC انجام دهد. RC دو است، که آنچه که ما انتظار می رود، درست است؟ 

بنابراین، ما می توانیم بعدی بروید، و ادامه را از طریق. بنابراین، ما باید برخی از کلید وجود دارد. و ما می توانیم از چاپ کلیدی ما مطمئن شوید که درست است. جالب است. نه کاملا آنچه که ما انتظار می رود. بنابراین، یک چیز به درک با GDB نیز است، که این تا زمانی که شما در واقع برخورد کند در مرحله بعد، که خط است که شما فقط دیدم در واقع اعدام. بنابراین، در این مورد کلیدی هنوز اختصاص داده نشده است. بنابراین، برخی از ارزش های کلیدی زباله است که شما در پایین وجود دارد را ببینید. منفی $ 120-- --It یک میلیارد و چیزی چیز عجیب و غریب درست است؟ این کلیدی است که ما انتظار نمی رود. اما اگر ما ضربه بعدی، و پس از آن ما امتحان کنید و کلید چاپ، آن را سه. 

هر کس می بینید که؟ بنابراین، اگر شما چیزی که شما مثل هستید، صبر کنید. این است به طور کامل اشتباه است، و من نمی دانم چگونه این اتفاق می افتد چرا که همه من می خواهم برای انجام این کار است اختصاص یک شماره، یک متغیر، سعی کنید ضربه بعدی، چاپ سعی دوباره آن را، و ببینید اگر که کار می کند. از آنجا که آن را تنها رفتن به اجرا و چیزی پس از شما در واقع اختصاص ضربه بعدی. ایجاد حس برای همه؟ خودت؟ 

SPEAKER 2: هنگامی که شما به صورت تصادفی اعداد چه معنا است؟ 

SPEAKER 1: این فقط تصادفی است. این فقط زباله است. این تنها چیزی است که شما کامپیوتر به صورت تصادفی تعیین خواهد شد. سرد. بنابراین، در حال حاضر ما می توانید از طریق حرکت، و به همین ترتیب در حال حاضر ما این GetString متن ساده. بنابراین، اجازه دهید من فقط معرفی چه اتفاقی خواهد افتاد وقتی که ما در اینجا ضربه بعدی. GDB ما نوع از بین می رود، درست است؟ این به آن دلیل GetString در حال حاضر اجرا، درست است؟ بنابراین، هنگامی که ما دیدیم متن ساده برابر با GetString، پرانتز باز و پرانتز، و ما ضربه بعدی، که دارای در واقع در حال حاضر اجرا می شود. بنابراین، آن را در انتظار ما را به ورودی چیزی. 

بنابراین، ما در حال رفتن به ورودی مواد غذایی ما است که همان چیزی است که آن را به عنوان شکست من به شما گفتم و فقط می گوید که این اجرای به پایان رسید، که بسته براکت به معنی آن است خروج از حلقه. بنابراین، ما می توانیم بعدی رسید، و در حال حاضر، به عنوان من مطمئن هستید که همه از سزار آشنا، این، چیزی است که این خط را به انجام است. این اینترنت من برابر با 0، N برابر Strlen، متن ساده، و پس از آن من کمتر از N، I، به علاوه، اضافه شده است. این حلقه را به انجام چیزی است؟ پیام خود را باز کنید. سرد. بنابراین، اجازه دهید شروع به انجام آن است. 

بنابراین، باید این وضعیت مسابقه، برای اولین بار یکی از ما؟ اگر B، آن متن ساده I. ما می توانید اطلاعات در مورد مردم محلی ما دریافت کنید. بنابراین، من صفر است، و اگر شش، که ما انتظار داریم، و کلید ما سه می باشد. همه که باعث احساس، درست است؟ کسانی که اعداد همه دقیقا همان چیزی است که باید باشد. بنابراین، همهمه؟ SPEAKER 3: من اعداد تصادفی برای من. SPEAKER 1: خب، ما می توانیم --we check-- می توانید در مورد که در یک ثانیه چت. اما شما باید گرفتن این باشد. بنابراین، اگر ما یک سرمایه B برای اولین بار یکی از ما، این وضعیت باید آن را گرفتن، درست است؟ بنابراین، اگر ما ضربه بعدی، ما می بینیم که این در واقع اگر اجرا می کند. چرا که اگر شما دنبال همراه در کد خود را، این خط در اینجا، که در آن متن من ساده با این حساب جایگزین، تنها در صورتی که اگر اجرا شرایط راست صحیح است؟ 

GDB است تنها رفتن به شما نشان می دهد چیزهایی که در واقع اجرای. بنابراین اگر این شرایط اگر آشنا نیست، آن را فقط رفتن به رفتن به خط بعدی. OK؟ بنابراین، ما باید که. این بدان معنی است که این براکت از آن حلقه بسته در حال حاضر. بنابراین، آن را به شروع دوباره. فقط می خواهم که. بنابراین، که ما می توانیم اطلاعات را دریافت کنید درباره مردم محلی ما در اینجا، و ما می بینیم که برای اولین بار ما نامه تغییر کرده است، درست است؟ این در حال حاضر E، آن گونه که باید باشد. بنابراین، ما می توانیم در ادامه. 

و ما باید این را بررسی کنید. و این چک باید کار کند، درست است؟ این A. باید تغییر است سه حرف رو به جلو. اما اگر شما متوجه ما چیزی متفاوت است. بنابراین در این مورد در اینجا، آن را گرفتار آن، و به همین ترتیب این خط اعدام، که ما B. اصلاح اما، در این مورد در اینجا، ما که فقط آن را نادیده گرفته، و به [رفت؟ L siff. ؟] بنابراین چیزی در رفتن وجود دارد. چه که به شما گفتن است که، ما می دانیم که آن را باید در اینجا گرفتن، اما این طور نیست. آیا می توانم هر کسی را ببینید که چه ما مشکل در این خط است؟ این یک چیز بسیار دقیقه است. و شما نیز می توانند در کد خود را نگاه کنید. همچنین line-- فراموش کرده ام چه خط است در there-- اما در [نامفهوم] است. بله؟ 

SPEAKER 4: آن را در بیشتر از صفحه اگر شما آن را بخوانید در کتاب. SPEAKER 1: دقیقا. بنابراین، دیباگر نمی تواند بگوید شما که، اما دیباگر می تواند شما را به یک خط که شما می دانید در حال حاضر کار نمی کند. و گاهی اوقات، زمانی که به خصوص در ترم بعدی، هنگامی که شما در حال برخورد با یک صد، صد چند خط کد، و شما نمی دانم از کجا آن را شکست، این یک راه بسیار خوبی برای انجام آن است. بنابراین، ما اشکال ما در بر داشت. شما می توانید آن را در فایل خود را تعمیر کنند، و سپس شما می توانید آن را دوباره اجرا شود، و همه چیز را کاملا کار می کنند. و بزرگترین چیز است این می تواند به نظر می رسد مانند، OK. آره. سرد. شما می دانستم که آنچه شما دنبال آن هستید. بنابراین، شما می دانستم که چه باید بکنید. 

GDB می تواند فوق العاده به خاطر شما مفید است می توانید نسخه قابل چاپ کردن همه این چیزهایی که شما نیست. این بسیار مفید تر از printf را. چگونه بسیاری از شما استفاده مانند بیانیه printf را برای کشف کردن که یک اشکال بود، درست است؟ بنابراین، با این، شما نمی باید به رفتن ادامه بازگشت، و دوست اظهار نظر در printf را، و یا اظهار نظر کردن، و کشف کردن آنچه شما باید چاپ شود. این در واقع فقط شما اجازه می دهد تا به گام به گام از طریق، چاپ کردن همه چیز به عنوان شما را از طریق رفتن، بنابراین، شما می توانید مشاهده که چگونه آنها را در زمان واقعی تغییر، به عنوان برنامه های خود را در حال اجرا است. 

و آن را کمی کمی از مورد استفاده قرار گرفتن به. من به شدت توصیه فقط نوع بودن کمی نا امید با آن برای حال حاضر. اگر شما صرف یک ساعت در طول هفته آینده یادگیری چگونگی استفاده از GDB، شما خودتان را ذخیره کنید بنابراین زمان زیادی بعد از آن. و به معنای واقعی کلمه. ما بگویید این به مردم در هر سال، و من به یاد داشته باشید زمانی که من در زمان کلاس، من بود، من خوب خواهد شد. شماره Pset 6 در آمد و من بود مانند، من میخوام یادگیری نحوه استفاده از GDB چون من نمی می دانم آنچه در اینجا. 

بنابراین اگر شما وقت تا استفاده از آن در برنامه های کوچکتر که شما برای رفتن به کار بر روی، مانند کار از طریق چیزی شبیه به Visionare، مثل این. و یا اگر شما می خواهید عمل فوق العاده، من مطمئن هستم من می توانم آمد تا با برنامه حشره دار، برای شما برای اشکالزدایی اگر شما می خواهم. 

اما اگر شما فقط به زمان نیاز برای به دست آوردن استفاده می شود به آن، فقط در اطراف بازی با آن، آن را واقعا شما را به خوبی خدمت می کنند. و این واقعا یکی از آن چیزهایی است که شما فقط را امتحان کنید، و دست خود را کثیف با، قبل از اینکه شما واقعا آن را درک کنند. من واقعا فقط یک بار آن را درک من به همه چیز اشکال زدایی با آن حال، و آن را بسیار بهتر به یک ایده از چگونه برای اشکالزدایی زودتر و نه بعد. OK. سرد. من می دانم که نوع مانند یک دوره سقوط در GDB، و من قطعا کار خواهد کرد در گرفتن این به زمان بعدی بزرگتر است. سرد. 

بنابراین، اگر ما به عقب برویم به پاورپوینت ما. آیا این رفتن به کار می کند؟ AWH. بله. OK. بنابراین، اگر شما تا به حال نیاز به هر یک از کسانی دیگر، در لیست وجود دارد. جستجو بنابراین دودویی، که هر کس به یاد عینک بزرگ دیوید تبدیل کتاب های تلفن در نیم. من واقعا نمی گرفتن کتاب تلفن دیگر، چرا که مانند جایی که شما انجام دریافت دفترچه تلفن این روزها؟ من واقعا نمی دانم. جستجو دودویی. آیا کسی به یاد داشته باشید چگونه دودویی آثار جستجو؟ هر کسی در همه؟ آره؟ SPEAKER 5: شما می دانید زمانی که شما که در آن نیم نگاه این امر می تواند در، که بر اساس آن، را دریافت و از نیمه دیگر خلاص شوید. 

SPEAKER 1 دقیقا. بنابراین، دودویی جستجو، این نوع از a-- --we دوست دارم را از آن تقسیم و تسخیر. بنابراین، آنچه شما انجام است شما در وسط نگاه کنید، و شما ببینید که اگر آن مسابقات آنچه شما دنبال آن هستید. و اگر آن را نمی کند، و سپس شما را امتحان کنید کشف کردن، آن را با رفتن به سمت چپ نیم یا نیمه سمت راست. بنابراین، این ممکن است اگر شما به دنبال در چیزی است که alphabetized، شما ببینید، آه. آیا قبل از آلیسون M می آیند؟ بله. بنابراین، ما در حال رفتن به در نیمه اول نگاه کنید. 

یا آن را می مانند با شماره باشد. هر چیزی که شما می توانید مقایسه، می توان آن را طبقه بندی شده اند. شما می توانید جستجوی دودویی استفاده کنید. بنابراین، هر کسی به یاد داشته باشید این نمودار و یا این چیست؟ این پیچیدگی مجانبی است. بنابراین، این نمودار تنها توصیف چه مدت آن شما را به حل یک مشکل به عنوان شما تعدادی از چیزهایی افزایش که شما با استفاده از. 

بنابراین، ما باید N، که زمان خطی. اگر N بیش از دو، که کمی بهتر است، هنوز هم رشد می کند فوق العاده سریع. و بعد ما وارد شوید اند، که آنچه ما دودویی جستجو در نظر بگیرند. در صورت توجه به، به عنوان مشکل خود را می شود بسیار بسیار بزرگتر و، زمان آن را به شما طول می کشد تا آن را حل کند واقعا افزایش نمی دهد که بسیار. آن را مانند مقایسه است در اینجا در ابتدا. شما مانند هستید، OK. هر چیزی در اینجا واقعا نمی مهم نیست که یک استفاده می کنیم، اما شما از این که به یک میلیون، یک میلیارد. شما در حال تلاش برای پیدا کردن some-- --you're تلاش برای پیدا کردن یک سوزن در انبار کاه. 

من فکر می کنم شما می خواهید این مشکل است. شما می خواهید این پیچیدگی، نه خطی چرا که برای همه شما می دانم که تو داری می شود از طریق جستجو هر یک سوزن های فردی، چیزی که از یونجه، تلاش برای سوزن خود را نگاه کنید. و این به نظر من خیلی سرگرم کننده نیست. من دوست دارم سریع می باشد. من دوست دارم کارآمد می باشد. و دانش آموزان به عنوان سخت کوش شما بچه ها، شما می دانید کار دقیق، نه از نوع چیز سخت تر است، چگونه شما می توانید از این الگوریتم را تشکیل می دهند. 

بنابراین، ما در حال رفتن به راه رفتن از طریق فقط یک مثال سریع است. من فکر می کنم شما بچه ها باید دست در دودویی جستجو، اما در مورد هر کسی کمی است فازی، می خواهید آن را تقویت، ما قصد داریم به فقط به از طریق یک مثال در اینجا. بنابراین، ما به دنبال اگر آرایه شامل هفت. 

بنابراین، اولین چیزی که ما انجام می دهیم است نگاه در وسط، درست است؟ و همچنین شما در حال رفتن به برنامه نویسی می شود دودویی جستجو در یک ثانیه. بنابراین، آن را به پاپ. بنابراین ما در نگاه آرایه های کوچک متوسط ​​3. آیا 3 برابر 7؟ نمی کند. این شش است. بنابراین، آن را از کمتر یا بیشتر از هفت؟ کمتر از. بله. بچه ها کار خوب. من احساس می کنم دوست دارم من باید باید آب نبات به خاطر من می خواهم آن را دور انداخت و به حیاط. این چیزی است که من می خواهم به انجام این کار در هفته آینده. آن را به شما بچه های تیز نگه می دارد. 

بنابراین، ما دور می ریزیم که نیمه اول، درست است؟ آن کمتر از بود. ما می دانیم که همه چیز در آن طرف دست چپ در حال رفتن به کمتر از آنچه که ما در واقع به دنبال. بنابراین، نیازی به وجود توجه به آن را. فقط در مورد آن را فراموش کرده ام. بنابراین، در حال حاضر ما در سمت راست ما نگاه کنید، و ما در وسط نگاه بیش از وجود دارد، و در حال حاضر آن را نه. بنابراین، 9 is-- --Everyone؟ بیشتر از آنچه که ما هستیم به دنبال، درست است؟ بنابراین، ما در حال رفتن به پرتاب دور همه چیز را به سمت راست. که می خواهم. در حال حاضر، همه ما به سمت چپ با یک است. بنابراین ما را بررسی کنید، این یک چیزی است که ما به دنبال؟ آن است. ما در بر داشت آنچه ما می خواستیم. بنابراین ما در حال انجام می شود. دارای دو خط مستقیم جستجو. 

و اگر شما متوجه ما هفت ورودی وجود دارد. این تنها ما را مانند سه بار در زمان، اما اگر شما در حال انجام مانند یک میلیارد، شما بچه ها می دانند که چگونه بسیاری از مراحل آن را اگر ما تا به حال چهار میلیارد چیز؟ هر حدس بزند؟ این 32 است. 32 گام برای رسیدن به پیدا کردن چیزی در چهار میلیارد آرایه عنصر به دلیل قدرت دو. بنابراین دو به 32 است، به چهار میلیارد. 

چگونه پس خیلی دیوانه که هنوز هستیم مانند یک تعداد نسبتا کمی از مراحل برای پیدا کردن چیزی در چهار میلیارد عناصر. پس در آن توجه داشته باشید، ما هستیم رفتن به کد این بنابراین شما می تواند در حقیقت بچه ها نوع ببینید که چگونه این کار می کند. همه حق است، بنابراین شما بچه ها می توانید کد. من قصد دارم به شما بچه ها اجازه صحبت برای کمی. دریافت به دانستن مردم در اطراف شما است که چه کسی می خواستم از بخش گذشته است. 

بنابراین به دانستن مردم در اطراف شما. بحث برای کمی. و همه من از تو می خواهم بچه ها در حال حاضر فقط سعی کنید برای ایجاد یک طرح کلی از شبه. OK؟ ایست. همه من از شما بچه ها می خواهم شما فقط برای پر کردن در این مورد در حالی که. بنابراین من تعیین کرده اند این بالا و نشیب های پایین تر که نشان دهنده آغاز و پایان آرایه ما است. و شما در حال رفتن به واقع حلقه را از طریق شکل و خارج آنچه ما انجام می دهیم در حالی که در این حلقه. 

بنابراین اگر شما می تواند شکل out-- من یک اشاره there-- موارد چه می باشد که ما را در اینجا؟ بنابراین اگر شما می خواهید برای کشف کردن موارد، ما به کسانی شبه و سپس ما در واقع آنها را کد. و آن را به، من فکر می کنم، امیدوارم آن را خواهید کمی راحت تر از شما انتظار می رود. از آنجا که آن را که کد بسیار نیست، در واقع، این است که واقعا سرد. 

MM-HM؟ 

دانشجو: [نامفهوم]؟ استاد: بله. چیزی وجود دارد برای پیدا کردن در وسط. 

دانشجو: بنابراین ما می توانیم استفاده از آن. OK. 

استاد: کامل. به طوری که اولین چیزی که ما باید انجام دهیم این است. بنابراین وسط پیدا کنید. بزرگ است. بنابراین آیا شما یک ایده چگونه ممکن است ما در واقع وسط با کد پیدا کنم؟ 

دانشجو: آره. N بیش از 2؟ استاد: پس N بیش از 2. بنابراین یک چیز به خاطر داشته باشید این است که مرزهای بالایی و پایینی خود را تغییر دهید. ما را محدود بخش از آرایه ما به دنبال به. بنابراین N بیش از 2 تنها کار خواهد کرد برای اولین چیزی که ما انجام می دهیم. بنابراین در نظر گرفتن بالا و پایین به حساب، چگونه ممکن است ما را دریافت کنید که عنصر وسط؟ از آنجا که ما می خواهیم وسط بین بالا و پایین، درست است؟ MM-HM؟ 

دانشجو: [نامفهوم]. 

استاد: پس ما باید برخی از متوسط ​​است. و آن خواهید بود بالا به علاوه پایین بیش از 2. بسیار جذاب است. ما وجود دارد. یکی از پایین خط. شما بچه ها در راه خود را می باشد. بنابراین در حال حاضر که ما ما میانه، آنچه ما می خواهیم انجام دهیم؟ فقط به طور کلی. شما لازم نیست که به آن کد. بله. دانشجو: [نامفهوم]؟ استاد: پس از آن به علاوه چون تو یافتن طور متوسط ​​بین دو از آنها. بنابراین اگر شما از آنها را به عنوان نوع افزایش در از دو طرف، فکر می کنم در مورد آن به عنوان رویکرد شما وسط، شما می خواهم که می خواهید. بنابراین اگر شما در هر دو طرف بود میانه، و ما مانند 5 و 7 را داشته باشد. هنگامی که شما آنها را با هم اضافه کنید به شما دریافت 12، شما 2 تقسیم، 6 است. 

گاهی اوقات آن را سخت به توضیح دهد که چرا که کار می کند، اما اگر شما از طریق کار به عنوان مثال گاهی اوقات، آن را به شما کمک کند تا متوجه شوید باید آن را به اضافه یا منهای باشد. بله. 

دانشجو: [نامفهوم] درست در وسط در صورتی که یک مورد که در آن حال در بسیاری از اعداد کوچکتر وجود دارد و مانند یک تعداد زیادی؟ 

استاد: پس همه شما نیاز دارید وسط آرایه است. بنابراین اگر شما یک دسته از اعداد کوچک به حال و سپس یک عدد خیلی بزرگ در پایان، مهم نیست. تمام آنچه که مهم است که آنها طبقه بندی شده اند، شما فقط می خواهم به در وسط نگاه آرایه چون شما هنوز هم هستیم برش مشکل خود را در نیم. سرد. بنابراین در حال حاضر که در حال حاضر میانه، ما چه چیزی داریم انجام بعدی؟ 

دانشجو: مقایسه کنید. مربی: مقایسه کنید. بنابراین وسط نسبت به value_wanted. سرد. بنابراین می بینید تا اینجا ما این مقدار ما می خواهیم در اینجا. به یاد داشته باشید این یک آرایه است. بنابراین وسط اشاره به شاخص. بنابراین ما می خواهیم انجام دهیم ارزشهای متوسط. فراموش نکنید که اگر شما می خواهید برای مقایسه، دو برابر. شما انجام تک برابر شما فقط رفتن به آن جابهجا، و پس از آن، البته، آن را رفتن به ارزش شما می خواهید. بنابراین کار را نمی کنند. 

بنابراین ما در حال رفتن به دیدن اگر ارزش در وسط به ارزش ما می خواهیم برابر است. آیا پرانتز خود را فراموش نکنید. Dropbox را باید از بین برود. بنابراین چه چیزی ما را در این مورد انجام دهید؟ اگر آن چه می خواهیم به بازگشت؟ ما در حال تلاش برای گفتن دارد. 

دانشجو: نسخه قابل چاپ کردن. 

استاد: خب، ما نمی خواهید برای چاپ کردن. بنابراین این بولی در اینجا این است، بنابراین ما می خواهید به بازگشت به درست یا غلط. ما در حال گفت، این تعداد است [؟ RRA؟ ؟] بنابراین اگر از آن است، ما فقط بازگشت آن درست است. اگر من می توانم طلسم درست است. 

دانشجو: چرا به نظر شما صفر بازگشت؟ مربی: بنابراین شما می تواند بازگشت به صفر اگر شما می خواهید. اما در این مورد به دلیل تابع بولی ما گرداند، ما نیاز به بازگشت به درست یا نادرست. دانشجو: زمانی که شما گفت عبارات بولین، می تواند به شما آن را به نادرست برابر است؟ مثل اگر من می خواهم بگویم، اگر این وضعیت است آشنا نیست، مانند بالا برابر نادرست است. اگر شما فقط آن را درک قرار داده کاذب در طرف دیگر؟ استاد: آره. پس در واقع اگر شما تا کنون انجام کاری مانند بالا است یا پایین تر است، که درست یا غلط و آن را در واقع به سبک بد به مثلا معادل برابر درست است یا برابر برابر نادرست است. شما می خواهید به استفاده از آن نتیجه به عنوان خود را به عنوان چک کنید. نه آنچه که من می خواستم. این چیزی است که من می خواستم. بنابراین در مورد شما درخواست درباره چیزی شبیه به این در نجات ج. 

بنابراین اگر ما اعضای هیات تحریریه اصلی (خالی) و چیزی شبیه به این. و شما باید در صورت بالا است برخی از ورودی و شما درخواست اگر شما می توانید انجام دهید چیزی شبیه به این؟ درست است؟ دانشجو: من در تلاش بود به انجام آن [نامفهوم]. از آنجا که اگر it's-- استاد: راست. بنابراین شما می خواهید این را به غلط، درست است؟ دانشجو: آره. استاد: پس در این حالت شما می خواهم آن را به اجرا اگر آن درست نیست. بنابراین چیزی که شما باید انجام دهید سرد وجود دارد این است. بنابراین به یاد داشته باشید علامت تعجب نقطه نفی همه چیز؟ این گزارش می گوید [نامفهوم] معنی نه. بنابراین اگر ما فقط نگاه این بخش در اینجا، شما می خواهم می گویند که ارزیابی به غلط که شما می خواهید آن را به. غلط درست است که به معنای این خواهد بود را اجرا کند. آیا این را حس؟ دانشجو: آره. مربی: بسیار جذاب است. OK. بنابراین ما فقط می تواند بازگشت در این مورد درست است. بنابراین در حال حاضر ما دو نفر دیگر موارد در این مورد. ما دو مورد دیگر چه هستند؟ اجازه دهید فقط آن را در این راه انجام دهد. بنابراین با دیگری شروع اجازه اگر ارزش در وسط کمتر از ارزش ما می خواهیم باشد. بنابراین ارزش ما در وسط کمتر است از ارزش است که ما دنبال آن هستید. 

بنابراین که موظف است شما را انجام دهد فکر می کنم ما می خواهیم برای به روز رسانی؟ بالایی یا پایینی؟ بالا؟ بنابراین کدام طرف از آرایه می خواهیم به دنبال در؟ 

دانشجو: پایین تر است. 

استاد: ما می خواهیم در سمت چپ به دنبال. بنابراین اگر ارزش دیگری کمی کمتر است. بنابراین مقدار متوسط ​​خود را در اینجا کمتر از آنچه ما می خواهیم باشد. بنابراین ما می خواهیم را به سمت راست آرایه ما است. بنابراین ما در حال رفتن به به روز رسانی حد پایین است. بنابراین ما پایین تر ما تخصیص دهید. و چه چیزی شما فکر می کنم کمتر باید باشد؟ دانشجو: مقدار متوسط؟ استاد: پس value-- وسط دانشجو: به علاوه 1. مربی: --plus 1. هر کسی می تواند به من بگو چرا ما که به همراه 1؟ 

دانشجو: [؟ بدون مقدار؟] بیشتر به آن برابر است. 

استاد: راست. از آنجا که ما در حال حاضر می دانیم که مقدار متوسط ​​ما این است که برابر نیست و ما می خواهیم آن را به آن حذف از تمام جستجوهای پس از آن. اگر شما فراموش نکنید که به علاوه 1، این خواهد شد حلقه به طور نامحدود می خواهم. و شما فقط در یک گرفتار شود حلقه بی نهایت و پس از آن شما segfault و همه چیز بد است. پس همیشه مطمئن شوید که شما نمی از جمله ارزش است که شما فقط در نگاه کرد. بنابراین ما مراقبت از آن با به علاوه 1 را. 

بنابراین در حال حاضر ما آخرین وضعیت ما که من همیشه به خاطر ایمنی شما می توانید در اینجا چک کنید، اگر ارزش دیگری در وسط بیشتر از ارزش است ما می خواهیم. این بدان معناست که ما می خواهیم نیمه دست چپ. پس کدام یک می خواهیم برای به روز رسانی؟ بالا. و آنچه این یکی رفتن به برابر است با؟ میانه منهای 1 به دلیل، البته، ما می خواهیم مطمئن شوید که ما نیست نگاه که مقدار متوسط ​​دوباره. و سپس ما آن را داشته باشد. همین. این همه جستجوی دودویی است. این که بد نیست، درست است؟ آن را مانند 10 خط است کد با فضای سفید. بنابراین بسیار قدرتمند، بسیار مفید است، به شما خواهد شد استفاده از آن در یکی از psets بعد خود را. شاید نه این یکی، اما بعد. بنابراین آن را یاد بگیریم. آن را دوست دارم. این شما را به خوبی درمان کند. پس آیا کسی سوال در مورد جستجوی دودویی؟ بله. 

دانشجو: آیا مهم آیا شما N است فرد و یا زوج؟ 

مربی: شماره از آنجا که ما آن را به وسط به عنوان بازیگران متوسط، آن را فقط به آن را حذف می کند، پس از آن یک عدد صحیح خواهد ماند و از آن خواهد شد در نهایت از طریق همه چیز مرتب کردن. بنابراین شما لازم نیست که در مورد آن نگران باشید. هر کس خوب است؟ بسیار جذاب است. سرد. بنابراین، شما بچه ها این است. نمایش به صورت اسلاید. پس همچنان که صحبت کردن در مورد، من می دانم دیوید زمان های اجرا پیچیدگی ذکر شده است. 

پس در بهترین حالت، آن را فقط یکی، که ما زمان ثابت تماس بگیرید. هر کسی می تواند به من بگو چرا که ممکن است؟ چه نوع سناریو را که به همراه دارد؟ MM-HM. 

دانشجو: [نامفهوم] first-- استاد: پس وسط بودن اولین عنصری است که ما آمده است، درست است؟ بنابراین یا مجموعه ای از یک یا هر آنچه ما به دنبال فقط اتفاق می افتد به د افغانستان بانک با صدا غذا خوردن در وسط. به طوری که بهترین حالت ما است. شما را به مشکلات واقعی دریافت کنید، احتمالا نه رفتن برای رسیدن به [نامفهوم] که اغلب. چه در مورد بدترین حالت ما؟ بدترین حالت ما ورود N است. و این است که با تمام قدرت از دو چیز است که من در مورد صحبت کردیم. 

پس در بدترین حالت آن به معنی که ما تا به حال به ریز ریز آرایه پایین تا زمانی که یک عنصر از یک بود. بنابراین ما تا به حال به آن ریز ریز کردن را به نصف هر چند بار که ما احتمالا می تواند. به همین دلیل ورود N چون شما فقط حفظ تقسیم دو. بنابراین فرض، همه چیز به شما باید بدانید که اگر شما همیشه هستید رفتن به استفاده از جستجوی دودویی. عناصر شما باید طبقه بندی شده اند می شود. آنها به دلیل مرتب که تنها راه شما می دانم اگر شما قادر به بیرون انداختن از نیمی از آن. 

اگر این کیسه چندپاره و فاقد تأثیرگذاری حال اعداد و شما می گویید، OK، من قصد دارم به بررسی متوسط تعداد و تعداد من به دنبال کمتر از آن است که، من فقط رفتن به خودسرانه بیرون انداختن یک نیم. شما نمی خواهد می دانم که اگر شما تعداد در آن نیمه دیگر. لیست خود را به طبقه بندی شده اند می شود. همچنین، این ممکن است پیش رفتن کمی، اما شما نیاز به دسترسی تصادفی. شما باید قادر به تنها رفتن به که عنصر وسط. اگر شما مجبور به گذشتن از چیزی و یا آن را به شما طول می کشد گام اضافی برای رسیدن به آن عنصر وسط، آن را ثبت نخواهد N دیگر به دلیل شما با اضافه کردن کار بیشتر به آن. و این کمی خواهد شد حس بیشتر در دو هفته، اما من فقط می خواستم به نوعی از مقدمه، شما بچه ها ایده چه چیزی را به آمده است. ولی برای کسانی که دو مفروضات مهم که شما را برای یک لیست باینری نیاز دارید. اطمینان حاصل کنید که طبقه بندی شده اند. که یکی از بزرگ برای است شما بچه ها در حال حاضر. و در آن ما می توانیم به به بقیه انواع ما. بنابراین چهار حباب sorts--، درج، انتخاب، ادغام و. آنها همه نوع سرد است. اگر شما بچه ها تصمیم به گرفتن CS 124، شما در مورد تمام انواع از انواع یادگیری. و اگر شما از طرفداران XKCD هستید، وجود دارد درباره کمیک واقعا سرد است مانند انواع واقعا بی اثر، که من به شدت توصیه شما برای رفتن به در نگاه کنید. یکی از آنها است مانند مرتب سازی بر وحشت، که مانند، آه، نه، بازگشت آرایه تصادفی. سیستم خاموش کردن. ترک. بنابراین طنز نخبه را همیشه خوب است. 

بنابراین هر کسی به یاد داشته باشید نوع مانند فقط یک ایده کلی چگونه مرتب سازی بر حباب کار می کند. شما به یاد داشته باشید؟ 

دانشجو: آره. 

استاد: برو برای آن. 

دانشجو: بنابراین شما رفتن را از طریق و اگر آن را بزرگتر، پس شما دو مبادله. 

مربی: MM-HM. دقیقا. بنابراین شما فقط از طریق تکرار. شما چک کنید دو عدد. اگر به قبل بزرگتر است از یکی از پس از آن، شما فقط آنها مبادله به طوری که در این راه تمام اعداد بالاتر حباب به سمت انتهای فهرست و تمام اعداد پایین حباب به پایین. 

آیا او به شما بچه ها سرد نشان می دهد تأثیر صدا مرتب سازی ویدیو؟ این نوع خنک است. بنابراین به عنوان رابرت فقط گفت، الگوریتم که شما فقط از طریق لیست قدم، انتقال ارزش های مجاور اگر آنها در جهت نیستید. و پس از آن فقط حفظ تکرار تا زمانی که شما هیچ سواپ را ندارد. بنابراین بد نیست، درست است؟ بنابراین ما فقط یک مثال سریع را در اینجا. پس این است که رفتن به مرتب کردن بر اساس آنها را به ترتیب صعودی. بنابراین، هنگامی که ما از طریق اول زمان، ما را از طریق هشت نگاه و شش هستند بدیهی است که نه به منظور، ما آنها را مبادله. 

بنابراین در یک نگاه بعدی. هشت و چهار به منظور نیست. آنها مبادله. و پس از آن هشت و دو، آنها مبادله. ما وجود دارد. بنابراین پس از اولین گذر خود را، شما می دانیم که بیشترین تعداد خود را در حال رفتن به تمام راه را در بالای این دلیل آن را فقط رفتن به طور مداوم بزرگتر از هر چیز دیگری و آن را فقط رفتن به حباب تا تمام راه را به پایان وجود دارد. آیا که حس می کند به همه؟ سرد. 

بنابراین پس از آن ما در پاس دوم ما است. شش و چهار، سوئیچ. شش و دو، سوئیچ. و در حال حاضر ما چند چیز را به منظور. بنابراین برای هر پاس که ما از طریق لیست کامل ما را، ما می دانیم که مانند که تعداد بسیاری از در پایان اند طبقه بندی شده اند خواهد شده است. بنابراین ما یک پاس سوم، که یکی از مبادله است. و سپس در چهارم ما تصویب، ما باید صفر اسلات. و به این ترتیب ما می دانیم که ما آرایه مرتب شده است. 

و این بزرگ چیزی که با مرتب سازی بر حباب. ما می دانیم که زمانی که ما صفر معاوضه، که بدان معنی است که همه چیز را به منظور کامل است. این نوع از چک چگونه ما است. پس ما هم به کد حباب مرتب سازی بر آن نیز این است که بد نیست. هیچ کدام از این که بد هستند. من می دانم که آنها می توانند به نظر می رسد کمی ترسناک باشد. من می دانم که زمانی که من در زمان طبقه، حتی وقتی که من تدریس کلاس برای اولین بار در سال گذشته، من مانند، چگونه این کار را انجام دهم؟ این را حس می کند در تئوری، اما چگونه ما در واقع انجام این کار؟ به همین دلیل است من همچنین می خواهم به راه رفتن از طریق کد با شما بچه ها در اینجا. بنابراین من یک شبه برای شما بچه ها در این زمان. پس فقط این را در ذهن به عنوان ما در مورد انتقال بیشتر است. بنابراین ما باید برخی از مقابله با آن نگه می دارد آهنگ از سواپ ما، چون ما باید مطمئن شوید که ما در حال بررسی آن است. و ما تکرار کل آرایه که ما فقط با این مثال بود. اگر عنصر بزرگتر از قبل است عنصر بعد از آن ما در هستی، ما آنها را مبادله و ما افزایش ما ضد چون به محض مبادله، ما می خواهیم به ما اجازه مقابله می دانم که. هر گونه سؤال وجود دارد؟ چیزی خنده دار به نظر می رسد بیش از اینجا. دانشجو: آیا به شما در تنظیم مقابله با صفر هر زمانی که شما از طریق حلقه برود؟ آیا شما نمی ادامه بازگشت به صفر در هر زمان؟ استاد: نه لزوما. پس چه اتفاقی می افتد این است که ما از طریق اینجا بروید. بنابراین در حالی که انجام این کار، به یاد داشته باشید، این یک بار بدون شکست را اجرا خواهد کرد. بنابراین آن را به مجموعه ای از شمارنده صفر، سپس آن را از طریق تکرار. آن را به عنوان تکرار از طریق، از آن خواهد شد به روز رسانی ضد. آن را به عنوان به روز رسانی ضد، هنگامی که آن را انجام داده، هنگامی که آن را به پایان رسید آرایه، اگر لیست ما است طبقه بندی شده اند نشده است، شمارنده به روز خواهد شد شده است. 

پس از آن شرایط را بررسی میکند و آن را به می گوید، OK، است ضد بزرگتر از صفر. اگر در آن است، آن را دوباره. شما می خواهید برای تنظیم مجدد به طوری که زمانی که شما رفتن را از طریق، مبارزه برابر با صفر است. اگر شما از طریق مرتب به آرایه، هیچ چیز تغییر، این می افتد، و شما بازگشت به لیست طبقه بندی شده اند. آیا که حس می کند؟ دانشجو: این ممکن است در کمی. مربی: OK. در صورتی که هیچ دیگر وجود دارد سوالی است که می آید. بله. 

دانشجو: چه تابع برای انتقال عناصر است؟ 

استاد: پس ما در واقع می تواند ارسال که اگر ما در حال رفتن به در حال حاضر. سرد. پس در آن توجه داشته باشید، آلیسون در حال رفتن برای برگشت به دستگاه. این رفتن به سرگرم کننده است. و ما به خوبی ما حباب چیزی که مرتب سازی بر اینجا. بنابراین من در حال حاضر انجام دوچرخه سواری از طریق آرایه. ما سواپ ما که برابر با صفر می باشد. بنابراین ما می خواهیم به مبادله مجاور عناصر در صورتی که خارج از دستور است. بنابراین اولین چیزی که ما به نیاز آیا از طریق آرایه ما تکرار. 

پس چگونه شما فکر می کنم که ما ممکن است تکرار از طریق آرایه های ما؟ ما برای دارند و من برابر با 0. ما می خواهیم من به کمتر از N منهای 1 منهای K. و من توضیح می دهند که در یک ثانیه. بنابراین این بهینه سازی در اینجا این است که در آن، به یاد داشته باشید که چگونه من بعد از هر پاس گفت: از طریق ما آرایه می دانیم که هر آنچه on-- 

بنابراین پس از یک پاس ما می دانم که این است طبقه بندی شده اند. پس از دو پاس ما می دانیم که این همه طبقه بندی شده اند است. پس از سه پاس ما می دانیم که طبقه بندی شده اند. پس راه من تکرار از طریق آرایه در اینجا، است این که مطمئن شوید به تنها رفتن از آنچه ما می دانیم جدانشده است. OK؟ که فقط برای بهینه سازی است. شما می توانید آن را ساده لوحانه فقط ارسال تکرار از طریق همه چیز، که فقط بیشتر طول بکشد. با استفاده از این چهار حلقه آن فقط یک بهینه سازی خوب زیرا ما می دانیم که بعد از هر کامل تکرار از طریق آرایه در اینجا، مانند هر حلقه کامل در اینجا، ما می دانیم که یکی بیشتر از این عناصر خواهد شد در پایان طبقه بندی شده اند. 

بنابراین ما لازم نیست که در مورد آن نگران باشید. آیا که حس می کند به همه؟ که کمی فوت و فن خنک؟ پس در آن صورت، اگر ما در حال تکرار از طریق، ما می دانیم که ما می خواهیم اگر برای بررسی آرایه N و N به علاوه 1 به منظور هستند. OK. بنابراین در اینجا شبه است. ما می خواهیم اگر به بررسی آرایه N و n به علاوه 1 به منظور هستند. پس چه ممکن است ما وجود دارد؟ آن را به برخی از مشروط. از آن خواهد شد اگر. 

دانشجو: اگر آرایه N است کمتر از آرایه N به علاوه 1. مربی: MM-HM. خوب، کمتر یا بیشتر از. STUDENT: بیشتر از. سپس ما می خواهیم به آنها مبادله. دقیقا. بنابراین در حال حاضر ما به آنچه دریافت مکانیزم برای مبادله آنها؟ بنابراین ما از طریق این به طور خلاصه رفت، یک نوع از تابع مبادله هفته گذشته است. آیا کسی به یاد داشته باشید که چگونه آن کار می کرد؟ بنابراین ما نمی توانیم فقط آنها را جابهجا، درست است؟ از آنجا که یکی از آنها گم خواهد شد. اگر ما گفت A به B و سپس B برابر است با به برابر است، همه ناگهان هر دو آنها فقط به B. برابر 

بنابراین آنچه که ما باید انجام دهیم این است که ما یک متغیر موقت که رفتن به برگزاری یکی از ما در حالی که ما در روند مبادله است. بنابراین آنچه که ما داریم این است که ما برخی از اعضای هیات باید دمای برابر است to-- شما می توانید آن اختصاص به هر کدام یکی از شما می خواهید، فقط مطمئن شوید که شما پیگیری it-- حفظ بنابراین در این مورد، من قصد دارم به به آرایه N به علاوه 1 اختصاص آن. به طوری که رفتن به برگزاری هر چه ارزش در آن بلوک دوم که ما به دنبال در. 

و پس از آن ما می توانیم انجام دهیم این است که ما می توانیم به جلو و آرایه جابهجا N به علاوه 1، از آنجا که ما می دانیم که ارزش ذخیره می شود. این هم یکی از بزرگ things-- من اگر هر کدام از شما نمی دانم مسائل که اگر شما تغییر دهید دو حال خط کد به طور ناگهانی همه چیز کار می کرد. ترتیب CS بسیار مهم است. بنابراین مطمئن شوید که شما را دیاگرام مسائل را در صورت امکان به آنچه در واقع اتفاق می افتد. بنابراین در حال حاضر ما در حال رفتن به جابهجا کردن آرایه N به علاوه 1، از آنجا که ما می دانیم که ارزش ذخیره می شود. 

و ما می توانیم اختصاص که به آرایه N یا در این مورد آرایه من. بیش از حد بسیاری از متغیرهای. OK. آرایه بنابراین در حال حاضر ما منصوب کرده ام من به علاوه 1 را برابر چه چیزی در آرایه من. و در حال حاضر ما می توانیم به عقب برگرده و اختصاص آرایه من به چه؟ هر کسی؟ 

دانشجو: 10. 

مربی: 10. دقیقا. و یه چیزی. اگر ما آن را در حال حاضر تعویض، آنچه ما باید انجام دهیم؟ یک چیز چه که رفتن به ما بگویید اگر ما تا به حال این برنامه را خاتمه؟ چه به ما می گوید که ما یک لیست طبقه بندی شده اند؟ اگر ما هر گونه معاوضه انجام نیست، درست است؟ اگر معاوضه برابر است با در پایان این صفر است. بنابراین هر زمان که شما انجام مبادله، به عنوان ما فقط در اینجا انجام داد، ما می خواهیم برای به روز رسانی سواپ. و من می دانم که وجود دارد سوال قبلی در مورد شما می توانید به جای استفاده از صفر یا یک از درست یا غلط. و این چیزی است که این کار در اینجا. پس این می گوید اگر نه سواپ. بنابراین اگر معاوضه صفر است که من همیشه is-- دریافت حقایق من و falses من مخلوط. ما می خواهیم ما را به ارزیابی به درست و آن نیست. بنابراین اگر آن را صفر، و سپس آن را نادرست است. اگر شما آن را نفی با [؟ صدای بلند؟] درست می شود. پس این خط اجرا می کند. 

حقایق و دروغ و صفر و آنهایی را دیوانه کنید. فقط اگر شما به آرامی راه رفتن از طریق آن را حس کند. اما این این چه کمی کمی از کد در اینجا می کند. بنابراین این بررسی می آیا ما را سواپ انجام می شود. بنابراین اگر آن را هر چیزی به غیر از صفر، آن را به نادرست و همه چیز است رفتن به اجرای دوباره. سرد؟ 

دانشجو: چه استراحت انجام دهید؟ 

مربی: فقط شکستن شما می شکند خارج از حلقه. بنابراین در این مورد آن را درست مثل پایان دادن به برنامه و شما می توانید تنها لیست طبقه بندی شده اند باید خود را. دانشجو: شگفت انگیز. استاد: من متاسفم؟ دانشجو: از آنجا که پیش از ما نوشته شده استفاده بیش از 1 نوشته شده صفر حاضر است که اگر که کار خواهد کرد یا نه. 

استاد: آره. بنابراین شما می توانید صفر یا 1 بازگشت. در این مورد، از آنجا که ما در واقع نیست انجام هر کاری با عملکرد، ما فقط می خواهم آن را به شکستن. ما واقعا در مورد مراقبت از. ترمز هم خوب است اگر آن را برای شکستن استفاده می شود چهار حلقه یا شرایط که شما نمی خواهید به نگه داشتن اجرای. این فقط طول می کشد شما را از آنها. این بیت از یک چیز نکات دقیق وظریف است. من احساس می وجود دارد بسیاری از تکان دادن دست، مثل شما در مورد این زودی یاد می گیرند. 

اما شما در مورد این زودی یاد می گیرند. من قول می دهم. OK. بنابراین آیا همه مرتب سازی بر حباب؟ نه خیلی بد است. تکرار طریق، همه چیز مبادله با استفاده از یک متغیر دما، و ما همه وجود دارد قرار داده است؟ سرد. بسیار جذاب است. OK. بازگشت به پاورپوینت. هر گونه سؤال به طور کلی در مورد این که تا کنون؟ سرد. MM-HM. 

دانشجو: [نامفهوم] اعضای هیات تحریریه اصلی معمولا. آیا شما به که برای این؟ 

استاد: پس ما فقط به دنبال فقط در الگوریتم مرتب سازی واقعی. اگر شما آن را در حال مانند یک برنامه بزرگتر، شما می توانید در جایی اصلی بین المللی داشته باشد. بسته به جایی که شما استفاده از این الگوریتم، آن را تعیین چه توسط آن بازگشت. اما برای این مورد، ما به شدت هستید نگاه چگونه این کار را در واقع تکرار از طریق یک آرایه. بنابراین ما در مورد آن نگران نباشید. 

بنابراین ما در مورد بهترین مورد صحبت می کردند و بدترین سناریوها مورد برای جستجوی دودویی. پس از آن نیز مهم است به انجام که برای هر یک از انواع ما. بنابراین چه چیزی شما فکر می کنم بدترین است مورد زمان اجرای مرتب سازی بر حباب؟ شما به یاد داشته باشید بچه ها؟ 

دانشجو: N منهای 1. مربی: N منهای 1. به طوری که به معنی وجود دارد N منهای 1 مقایسه. بنابراین یک چیز برای تحقق است که در تکرار اول، ما از طریق رفتن، ما به مقایسه این two-- به طوری که 1. این دو، سه، چهار. بنابراین بعد از یک تکرار ما در حال حاضر چهار مقایسه. هنگامی که من صحبت کردن در مورد زمان اجرا و N. N نشان دهنده تعداد مقایسه به عنوان یک تابع از تعداد عناصر ما داشته باشد. OK؟ 

بنابراین ما از طریق رفتن، ما چهار. دفعه بعد که می دانید ما نمی باید برای مراقبت از این. ما مقایسه این دو، این دو، دو، و اگر ما که بهینه سازی ندارد با چهار حلقه که من نوشتم، به شما خواهد بود نسبت به هر حال در اینجا. بنابراین شما می توانید به اجرا را از طریق آرایه و N مقایسه N بار، چرا که هر بار ما اجرا از طریق آن ما برای مرتب کردن یک چیز. 

و هر بار که ما را از طریق اجرا آرایه، ما را مقایسه N. بنابراین در زمان اجرا ما این است در واقع N مربع، که است در بدتر ما ورود به سیستم پایان چرا که یعنی اگر ما چهار به حال میلیارد عناصر، آن را به ما را چهار میلیارد به جای 32 مربع. بنابراین بهترین زمان اجرا، اما برای برخی از چیزها، شما می دانید، اگر شما در هستی محدوده خاصی از عناصر مرتب سازی بر حباب ممکن است خوب استفاده کنید. 

OK. بنابراین در حال حاضر بهترین زمان اجرا مورد است؟ دانشجو: صفر؟ و یا 1؟ 

استاد: پس 1 را یکی مقایسه. راست. 

دانشجو: N منهای 1؟ 

استاد: پس، آره. بنابراین N منهای 1. هر زمان که شما یک مفهوم مانند N منهای 1، ما تمایل به فقط آن را رها کردن و ما فقط می گویند N به خاطر شما برای مقایسه هر یک از these-- هر جفت. بنابراین این امر می تواند N منهای 1، که ما ما فقط می خواهم بگویم این است حدود N. هنگامی که شما با خرید و فروش در زمان اجرا، همه چیز را در تخمین است. تا زمانی که توان است درست است، شما خیلی خوب است. 

که ما چگونه با آن برخورد. به طوری که بهترین حالت است N، که بدان معنی است که این فهرست در حال حاضر طبقه بندی شده اند، و همه ما این است که از طریق اجرا و بررسی کنید که آن را طبقه بندی شده اند. سرد. همه راست. همانگونه که شما در اینجا مشاهده کنید ما فقط باید برخی ها نمودار ها تازه تر. بنابراین N مربع. سرگرم کننده است. بسیار بدتر از N به عنوان ما می بینیم، و خیلی، خیلی بدتر از ورود 2N. و سپس شما را نیز به ورود سیاهههای مربوط را دریافت کنید. و تو را به 124، شما را به دریافت مانند ستاره ورود، که مانند دیوانه. بنابراین اگر شما علاقه مند هستید، ورود مراجعه ستاره. این نوع از سرگرم کننده است. بنابراین ما باید این نمودار بزرگ است. فقط یک سر این نمودار فوق العاده به برای میان مدت چون ما طولانی به شما این رقیق بپرسید. پس فقط سر، این باید در خود اواسط مدت در بازی ورق زیبا خود را وجود دارد. بنابراین ما فقط در مرتب سازی بر حباب نگاه کرد. بدترین حالت، N مربع، بهترین حالت، N. و ما قصد داریم تا در دیگران است. 

و همانطور که می بینید، تنها یکی که واقعا خوب مرتب سازی بر ادغام، که ما آن را به همین دلیل است. بنابراین ما در حال رفتن به رفتن به بعدی یک نوع انتخاب here--. آیا کسی به یاد داشته باشید که چگونه انتخاب مرتب سازی بر کار کرده است؟ برو برای آن. 

دانشجو: در واقع از طریق رفتن نظم و ایجاد یک لیست جدید. و فقط به عنوان شما در حال قرار دادن عناصر در، آنها را در جای مناسب قرار داده در فهرست جدید. 

استاد: به طوری که برای تلفن های موبایل بیشتر شبیه به مرتب سازی بر درج. اما شما واقعا نزدیک است. آنها خیلی مشابه هستند. حتی من آنها را مخلوط گاهی اوقات. پیش از این بخش من مانند بود، صبر کنید. OK. پس چه می خواهید انجام انتخاب مرتب سازی بر است، راه شما می توانید فکر می کنم در مورد آن و راه من مطمئن شوید من سعی می کنم می کنید آنها را مخلوط است، آن را می رود از طریق و آن را انتخاب کوچکترین عدد و قرار می دهد که در ابتدای فهرست شما. آن را جا به جا با آن نقطه اول است. آنها در واقع یک مثال برای من داشته باشد. بسیار جذاب است. پس فقط یک راه برای انتخاب it-- فکر می کنم مرتب کردن بر اساس، کوچکترین ارزش را انتخاب کنید. و ما قصد داریم به اجرا را از طریق مثال که من فکر می کنم به دلیل کمک خواهد کرد من فکر می کنم تصاویری همیشه کمک کند. بنابراین ما شروع با چیزی که به طور کامل جدانشده است. سرخ جدانشده خواهد بود، سبز خواهد شد طبقه بندی شده اند. این همه حس را در یک ثانیه. 

بنابراین ما از طریق رفتن و ما تکرار از آغاز تا پایان. و ما می گویند، OK، 2 است تعداد کوچکترین ما. بنابراین ما در حال رفتن به 2 و ما قصد داریم به این حرکت را به جلو آرایه ما زیرا این تعداد کوچکترین ما. بنابراین این چیزی است که این انجام شده است در اینجا. این فقط رفتن به مبادله آن دو. بنابراین در حال حاضر ما یک طبقه بندی شده اند بخشی و بخش جدانشده. و چه خوب است به خاطر داشته باشید درباره انتخاب مرتب سازی بر این است که ما فقط انتخاب از بخش جدانشده. 

بخش مرتب شده شما فقط به تنهایی ترک. MM-HM؟ 

دانشجو: چگونه آن را می دانم چه چیزی است کوچکترین بدون مقایسه آن به هر مقدار دیگر در آرایه. استاد: این کار مقایسه آن. ما می خواهیم که نادیده گرفته شوند. این فقط به طور کلی کلی است. آره. هنگامی که ما نوشتن کد من مطمئن هستم که شما راضی تر. اما شما این ذخیره برای اولین بار عنصر به عنوان کوچکترین. شما مقایسه و شما می گویند، خوب، آن را کوچکتر است؟ بله. آن را نگه دارید. در اینجا آن است که کوچکتر؟ هیچ؟ 

این کوچکترین خود است، جابهجا کردن آن را به ارزش خود را. و شما بسیار خوشحال می شود زمانی که ما از طریق کد بروید. بنابراین ما از طریق رفتن، که ما آن را مبادله، تا بعد ما در این بخش جدانشده است. بنابراین ما در حال رفتن به انتخاب سه نفر. ما در حال رفتن به آن را در در پایان بخش مرتب شده است. و ما فقط رفتن به انجام که انجام این کار، و انجام آن. بنابراین این نوع ما را از شبه در اینجا است. ما آن را در اینجا در یک دوم کد. اما تنها چیزی به راه رفتن در سطح بالا است. شما در حال رفتن به رفتن از من برابر با 0 تا N منهای 2. که بهینه سازی دیگری است. نگران نباشید بیش از حد در مورد آن. بنابراین همانطور که گفت شد. به عنوان یعقوب گفت، چگونه کار می کنیم پیگیری آنچه حداقل ما است؟ چگونه ما می دانیم؟ ما باید به مقایسه همه چیز را در لیست ما است. 

بنابراین حداقل برابر من. این فقط در این مورد گفت: شاخص حداقل مقدار ما. پس آن را به تکرار از طریق و از آن می رود از j برابر من به علاوه 1. بنابراین ما در حال حاضر می دانیم که که اولین عنصر ما است. ما نیازی به مقایسه آن را به خودی خود. بنابراین ما شروع آن نسبت به آینده یکی همین دلیل است که آن را به من به همراه 1 تا N منهای 1 است، که پایان آرایه وجود دارد. و ما اگر آرایه در گفت J کمتر از آرایه دقیقه می باشد، پس ما که در آن جابهجا حداقل شاخص ما است. 

و اگر در دقیقه است به من برابر نیست، به عنوان در جایی که ما به بیش از اینجا بود. پس چون زمانی که ما برای اولین بار این یکی. در این مورد، آن را در شروع صفر آن تا پایان بودن دو. بنابراین دقیقه که برابر من در پایان نیست. که اجازه می دهد ما می دانیم که ما باید به آنها مبادله. من مانند یک مثال احساس خیلی بیشتر از این کمک خواهد کرد. پس من این را با شما بچه ها کد در حال حاضر و من فکر می کنم آن را بهتر خواهید بود. 

انواع تمایل به کار در آن راه که آن اغلب بهتر فقط به آنها نگاه کنید. بنابراین آنچه ما می خواهیم انجام دهیم این است ما برای اولین بار می خواهید کوچکترین عنصر در جایگاه خود را در آرایه. دقیقا همان چیزی یعقوب گفت. شما نیاز به ذخیره که به نحوی. بنابراین ما در حال رفتن به شروع در اینجا شمارش آرایه. ما در حال رفتن به می گویند آن ما یکی از اولین فقط برای شروع با. بنابراین ما در حال رفتن به بین المللی کوچکترین به آرایه برابر من است. 

بنابراین یک چیز را به اطلاع، هر زمان این حلقه اجرا، ما در حال شروع یک قدم بیشتر همراه است. هنگامی که ما شروع ما در این یکی نگاه کنید. دفعه بعد که ما از طریق تکرار، ما در حال شروع در این یکی و اختصاص آن کوچکترین مقدار ما. پس از آن بسیار شبیه به مرتب سازی بر حباب که در آن ما می دانیم که پس از یک پاس، این عنصر آخرین طبقه بندی شده اند است. با انتخاب مرتب سازی بر، آن را فقط در مقابل است. 

در هر گذر، ما می دانیم که یکی از اولین طبقه بندی شده اند است. بعد از پاس دوم، دوم طبقه بندی شده اند خواهد شد. و به عنوان شما را با نمونه های اسلاید را دیدم، بخش طبقه بندی شده اند ما فقط نگه می دارد در حال رشد. بنابراین با تنظیم کوچکترین یکی ما به آرایه های من، همه آن را انجام می دهند است محدود به آنچه ما به دنبال در به طوری که برای به حداقل رساندن تعداد از مقایسه ما را. آیا این را حس برای همه؟ آیا شما به من نیاز به از طریق آن اجرا دوباره آهسته تر و یا به عبارت دیگر؟ من خوشحال هستم. OK. 

بنابراین ما در حال ذخیره سازی ارزش در این مرحله، اما ما همچنین می خواهم برای ذخیره صفحه. بنابراین ما در حال رفتن به مغازه موقعیت کوچکترین یکی، که فقط برای رفتن به من. بنابراین در حال حاضر یعقوب راضی است. ما همه چیز ذخیره می شود. و در حال حاضر ما نیاز به از طریق نگاه بخش جدانشده از آرایه. بنابراین در این مورد از این خواهد بود جدانشده است. این من است. OK. 

بنابراین آنچه که ما قصد انجام برای رفتن به یک حلقه باشد. هر زمان که شما نیاز به تکرار از طریق یک آرایه، ذهن شما می تواند برای یک حلقه به آن بروید. بنابراین برای برخی از اعضای هیات K equals-- چه فکر می کنم ما K است که برابر با شروع کنم؟ این چیزی است که ما به عنوان کوچکترین ما مجموعه ارزش و ما می خواهیم به مقایسه آن. چه ما می خواهیم به مقایسه آن را به؟ این برای رفتن به این بعد، درست است؟ بنابراین ما می خواهیم K تا مقداردهی اولیه شود به علاوه من 1 شروع می شود. 

و ما می خواهیم K در این مورد ما در حال حاضر حجم ذخیره شده در اینجا، بنابراین ما فقط می تواند به اندازه استفاده کنید. اندازه بودن اندازه آرایه. و ما فقط به به روز رسانی K توسط یکی در هر زمان. سرد. بنابراین در حال حاضر ما نیاز به پیدا کردن کوچکترین عنصر در اینجا. بنابراین اگر ما از طریق تکرار، ما می خواهم بگویم، اگر آرایه در K کمتر از کوچکترین value-- ما این جایی است که ما در واقع هستید پیگیری چه کوچکترین here-- پس از آن ما می خواهیم به جابهجا چه کوچکترین ارزش ما است. 

این به این معنی است که، آه، ما هستیم تکرار از طریق اینجا. هر چه مقدار است که در اینجا است نمی کوچکترین چیز ما است. ما آن را نمی خواهیم. ما می خواهیم به آن تخصیص دهید. بنابراین اگر ما آن را مجدد، چه شما فکر می کنید ممکن است در این کد اینجا؟ ما می خواهیم جابهجا کوچکترین و موقعیت. بنابراین در حال حاضر آنچه که کوچکترین است؟ دانشجو: آرایه K. مربی: آرایه K. و در حال حاضر چه جایگاهی است؟ شاخص از آنچه که کوچکترین ارزش ما؟ این فقط ک. بنابراین آرایه K، K، آنها هماهنگ باشد. بنابراین ما می خواستیم جابهجا که. و سپس بعد از ما در بر داشت کوچکترین ما، بنابراین در پایان این حلقه در اینجا ما پیدا کرده اند که چه کوچکترین ما ارزش است، بنابراین ما فقط آن را مبادله. در این مورد، مانند می گویند ما کوچکترین ارزش است را اینجا ببینید. این کوچکترین ارزش ما است. 

ما فقط می خواهیم به آن مبادله در اینجا، این است که آنچه که تابع مبادله در پایین انجام داد، که ما آن را فقط نوشتم تا با هم چند دقیقه پیش. پس از آن باید نگاه آشنا. و سپس آن را فقط تکرار خواهد شد از طریق می رسد تا زمانی تمام راه به پایان، که بدان معنی است که شما صفر عناصری که جدانشده است و هر چیز دیگری مرتب شده است. را حس؟ کمی مشخص تر؟ کمک کد؟ 

دانشجو: برای اندازه، شما هرگز واقعا آن را تعریف و یا تغییر آن، چگونه آن را می دانم؟ 

استاد: پس یک چیز را به متوجه اینجا size از نوع int است. بنابراین ما گفت: در این نوع sort-- یک تابع در این case-- آن مرتب سازی بر انتخاب، آن را به تصویب رساند در با تابع. بنابراین اگر آن را تصویب نمی شد در، شما می توانید چیزی را انجام دهید مانند با طول آرایه یا شما می توانید از طریق تکرار برای پیدا کردن طول. اما از آنجا که آن را به تصویب رساند در، ما فقط می تواند از آن استفاده کنید. شما فقط فرض کنیم که کاربر اندازه معتبر است که به شما در واقع نشان دهنده اندازه آرایه خود را. سرد؟ 

اگر شما هر گونه مشکل با این و یا می خواهید تمرین بیشتر برنامه نویسی انواع در خود شما، شما باید رفتن به study.cs50. این یک ابزاری است. آنها یک جستجوگر که شما در واقع می تواند ارسال. آنها این کار شبه. آنها فیلم ها و اسلاید تر از جمله آنهایی که من استفاده کنید. بنابراین اگر شما هنوز هم احساس کمی فازی، سعی کنید که از. مثل همیشه، آمده با من صحبت کنی، بیش از حد. سوال؟ 

دانشجو: آیا شما گفت اندازه قبلا تعریف شده؟ استاد: بله. اندازه قبلا تعریف کردن در اینجا در اعلان تابع. بنابراین شما تصور می کنیم که در گذشت توسط کاربر، و برای سهولت کار، ما قصد داریم که فرض کنیم که کاربر به ما به اندازه درست باشد. سرد. به طوری که مرتب سازی بر اساس انتخاب است. بچه ها، من می دانم که ما در حال یادگیری بسیاری است. این داده های انبوه برای بخش. بنابراین با آن، ما می رویم برای رفتن به مرتبسازی درجی. 

OK. بنابراین قبل از این که ما را مجبور به انجام تجزیه و تحلیل زمان اجرا ما در اینجا. پس در بهترین حالت، از آنجایی که من به شما اعطا نشان داد جدول من در حال حاضر نوع آن را به دور. اما بهترین حالت در زمان اجرا، چه چیزی فکر می کنم ما؟ همه چیز طبقه بندی شده اند. N مربع. هر کسی یک توضیح چرا شما فکر می کنید؟ 

دانشجو: شما مقایسه through-- استاد: راست. شما از طریق مقایسه. در هر تکرار، حتی اگر ما یک طرح ساده از این یک، شما هنوز هم در حال جستجو از طریق همه چیز برای پیدا کردن یکی از کوچکترین. بنابراین حتی اگر کوچکترین مقدار خود است که در اینجا در آغاز، شما هنوز هم آن را در مقایسه با در برابر هر چیز دیگری مطمئن شوید آن را کوچکترین چیز. پس شما در نهایت در حال اجرا را از طریق حدود N بار مربع. همه راست. و آنچه را که بدترین حالت است؟ همچنین N مربع دلیل این که شما در حال رفتن به انجام است که همان روش. بنابراین در این مورد، انتخاب مرتب سازی بر چیزی که ما نیز در زمان اجرا مورد انتظار تماس بگیرید. بنابراین در دیگران، ما فقط می دانم بالا و پایین محدوده. بسته به اینکه چگونه دیوانه ما لیست و یا چگونه جدانشده از آن است، آنها بین N یا N مربع متفاوت است. ما نمی دانیم. 

اما از آنجا که مرتب سازی بر انتخاب است، همان بدترین و بهترین حالت، که به ما می گوید که مهم نیست که چه نوع از ورودی ما داشته باشد، که آیا آن را به طور کامل طبقه بندی شده اند و یا به طور کامل معکوس طبقه بندی شده اند، آن را رفتن به همان مقدار از زمان. پس در آن صورت، اگر شما به یاد داشته باشید از جدول ما، آن را در واقع یک مقدار حال که این دو نوع را ندارد، که در زمان اجرا انتظار است. بنابراین ما می دانیم که هر زمان که ما اجرا انتخاب مرتب سازی بر، آن را به تضمین زمان N مربع اجرا شود. هیچ تنوع وجود دارد. این فقط انتظار می رود. و، دوباره، اگر شما می خواهید برای یادگیری بیشتر، را CS 124 در بهار. همه راست. ما این را دیده ام. سرد. مرتب سازی بر بنابراین درج. و من احتمالا از طریق این تصویر نشان دادن. من نمی خواهد که شما بچه ها آن کد. ما فقط از آن عبور کند. بنابراین مرتب سازی بر درج نوع از شبیه به انتخاب مرتب سازی بر در این که ما هر دو جدانشده و بخشی از آرایه طبقه بندی شده اند. 

اما آنچه متفاوت است که به عنوان ما را از طریق یک به یک رفتن، ما فقط هر چه تعداد را بعدی در جدانشده ما است، و به درستی آن را به مرتب کردن بر اساس به آرایه مرتب شده است. آن را حس بیشتری را با یک مثال را. بنابراین همه چیز به عنوان جدانشده شروع می شود، فقط با انتخاب مرتب سازی بر دوست دارم. و ما قصد داریم برای مرتب کردن این در صعودی که ما بوده است. بنابراین در اولین گذر ما ما ارزش اول و ما می گوییم، خوب، شما در حال حاضر در یک لیست توسط خودتان. 

از آنجا که شما در یک لیست هستند توسط خودتان، شما طبقه بندی شده اند. تبریک برای بودن اولین عنصر در این مجموعه. شما در حال حاضر در تمام خود را طبقه بندی شده اند. بنابراین در حال حاضر ما یک طبقه بندی شده اند و یک آرایه جدانشده. بنابراین در حال حاضر ما برای اولین بار برد. چه اتفاقی می افتد در اینجا بین و در اینجا این است که ما می گویند، OK، ما در حال رفتن به در نگاه ارزش اول آرایه جدانشده ما و ما در حال رفتن به آن را در ورودی آن محل صحیح در آرایه مرتب شده است. 

بنابراین آنچه که ما انجام میدهیم را 5 و به ما می گویند، OK، 5 بزرگتر از 3 است، بنابراین ما فقط به آن وارد سمت راست در سمت راست است. ما خوب است. بنابراین پس از آن ما به یکی بعدی ما بروید. و ما را 2. ما می گوییم، خوب، 2 کمتر است از 3، بنابراین ما می دانیم که آن را نیاز به در می شود جلو لیست ما در حال حاضر. بنابراین آنچه که ما انجام دهیم این است که ما فشار 3 و 5 پایین و ما حرکت 2 به که برای اولین بار از حافظه. بنابراین ما فقط آن را به قرار دادن محل صحیح آن باید باشد. 

پس از آن ما در نگاه ما یک بعد، و ما می گویند 6. OK، 6 بزرگتر از است همه چیز را در آرایه مرتب شده ما، بنابراین ما فقط آن را بر روی برچسب به پایان است. و سپس ما در 4 نگاه کنید. 4 کمتر از 6 است، آن را کمتر از 5 اما آن را بیشتر از 3. بنابراین ما فقط آن را به سمت راست وارد وسط بین 3 و 5. بنابراین برای اینکه که کمی کمی ملموس تر، در اینجا نوع است ایده از آنچه اتفاق افتاده است. بنابراین برای هر یک از عناصر جدانشده، ما تعیین جایی که در قسمت مرتب آن است. 

بنابراین با در نظر گرفتن طبقه بندی شده اند و جدانشده، ما باید از طریق شکل و گذشتن از جایی که آن را در آرایه مرتب شده متناسب. و ما آن را درج کنید با تغییر عناصر در سمت راست آن را به پایین. و پس از آن ما فقط نگه داشتن تکرار از طریق تا زمانی که ما یک لیست به طور کامل طبقه بندی شده اند که در آن جدانشده است در حال حاضر صفر و مرتب طول می کشد تا کل لیست ما است. پس، دوباره، تا همه چیز را حتی بتن تر، ما شبه. 

بنابراین اساسا برای من است 0 برابر با N منهای 1، که فقط طول آرایه ما است. در حال حاضر برخی از عناصر برابر است که آرایه اول و یا شاخص برای اولین بار. ما مجموعه ای J به آن برابر است. بنابراین در حالی که بیشتر از J است صفر و آرایه، J منهای 1 بزرگتر از است عنصر، پس همه که انجام است مطمئن شوید که J خود را واقعا نشان دهنده بخش جدانشده از آرایه. 

بنابراین در حالی که هنوز هم چیزهایی وجود دارد برای مرتب کردن و J منهای is-- چه عنصر او است؟ J هرگز در اینجا تعریف شده است. این نوع از آزار دهنده است. OK. به هر حال. بنابراین J منهای 1، شما چک کردن عنصر قبل از آن. شما می گویید، OK، عنصر است قبل از هر جا که من am-- بیایید در واقع این رسم است. بنابراین اجازه دهید می گویند این است مثل در گذر دوم ما است. بنابراین من در حال رفتن به برابر باشد به 1 است که در اینجا. 

بنابراین من در حال رفتن به برابر با 1 باشد. این امر می تواند 2، 4، 5، 6، 7. همه راست. بنابراین عنصر ما در این مورد در حال رفتن به به 4 برابر می شود. و ما باید برخی از J که رفتن به برابر با 1 باشد. اوه، J یک طرح ساده است. این چیزی است که در آن است. بنابراین J به من برابر است، پس چه است این ضرب المثل این است که ما به عنوان حرکت به جلو، ما فقط مطمئن شوید که ما بیش نیست نمایه سازی این راه زمانی که ما در حال تلاش برای وارد کردن همه چیز را به لیست طبقه بندی شده اند ما. 

بنابراین، هنگامی که J برابر با 1 در این مورد است و آرایه J منهای one-- تا آرایه J منهای 1 2 در این case-- اگر این بیشتر از این عنصر، سپس همه این است که انجام است تغییر چیزهایی که از پایین. بنابراین در این مورد، آرایه J منهای یک خواهد بود آرایه صفر است که 2. 2 نمی باشد بزرگتر از 4، و این کار را اجرا نمی کند. بنابراین تغییر حرکت نمی کردن. چه می کند این است در اینجا فقط حرکت آرایه مرتب شده خود را کاهش دهید. در این مورد، در واقع، ما می تواند do-- اجازه دهید این 3. بنابراین اگر ما به از طریق راه رفتن با هستی این مثال، ما در حال حاضر در اینجا. این طبقه بندی شده اند است. این جدانشده است. سرد؟ ولی من به 2 برابر است، بنابراین عنصر ما را به 3 برابر است. و ما را به J 2 برابر است. بنابراین ما از طریق و ما نگاه می گویند، OK، یک آرایه J منفی است بزرگتر از عنصر که ما به دنبال در؟ و پاسخ مثبت است، درست است؟ 4 بیشتر از 3 و j است 2، پس این کد را اجرا میکند. 

بنابراین در حال حاضر چه کار می کنیم یک آرایه در 2، تا حق در اینجا، ما آنها را مبادله. بنابراین ما فقط می گویند، OK، آرایه در حال حاضر 2 رفتن به 3. و J است که برابر J منهای 1 است که 1. که وحشتناک است، اما شما بچه ها می توانید از ایده. J در حال حاضر برابر با 1. و آرایه j است که فقط برای رفتن به به عنصر ما، که 4 برابر است. من چیزی پاک من باید نیست داشته و یا چیزی miswrote، اما شما بچه ها ایده را دریافت می. 

این در N حرکت می کند. و پس از آن اگر این بود، آن را حلقه دوباره و آن را می گویند، OK، J 1 در حال حاضر است. و آرایه J منهای 1 در حال حاضر 2. آیا کمتر از 2 عنصر ما؟ هیچ؟ این بدان معناست که ما کرده ایم درج این عنصر در نقطه درست در آرایه مرتب شده است. پس ما می توانیم این را و ما می گویند، OK، آرایه مرتب شده است ما در اینجا. و آن را از این تعداد 6 را و مانند، OK، 6 کمتر از این تعداد؟ هیچ؟ سرد. خوب هستیم. 

آیا دوباره آن را. ما می گوییم 7. 7 کمتر از پایان از آرایه مرتب شده ما؟ شماره بنابراین خوب هستیم. پس این که طبقه بندی شده اند می شود. در واقع همه این کار را است این گفت را عنصر اول آرایه جدانشده خود را، کشف کردن که در آن می رود در آرایه مرتب شده خود را. و این فقط طول می کشد مراقبت معاوضه به انجام این کار. شما اساسا مبادله تا زمانی که در نقطه سمت راست است. تصویر بصری است که شما هستید حرکت همه چیز را با انجام آن است. 

پس آن را مانند نیم حباب نوعی-esque. مطالعه 50 را بررسی کنید. من به شدت توصیه می شود سعی کد این در خود تغییر دهید. اگر شما هر گونه مسائل و یا می خواهید به کد نمونه را مشاهده کنید برای مرتبسازی درجی، لطفا اجازه دهید من می دانم. من همیشه در اطراف هستم. بنابراین بدترین حالت زمان اجرا و بهترین حالت در زمان اجرا. همانطور که شما پسر از جدول را دیدم من در حال حاضر شما نشان داد، آن را به هر دو N مربع و N. 

بنابراین نوع خارج شدن از آنچه که ما صحبت کردیم درباره با انواع قبلی ما، بدترین مورد در زمان اجرا است که اگر آن را به طور کامل نامرتب، ما باید به مقایسه تمام این بار N. ما می توانم در یک مقدار زیادی از کل مقایسه چرا که اگر آن را در جهت معکوس است، ما در حال رفتن به می گویند، OK، از این همان است، این خوب است، و این یکی باید به مقایسه شود در برابر یکی از اولین به عقب منتقل شد. و همانطور که ما نسبت دریافت پایان دم، ما برای مقایسه، مقایسه، و مقایسه در برابر همه چیز. 

پس از آن پایان می رسد تا حدود N مربع. اگر آن را درست پس از آن شما می گویند، OK، 2، شما خوب هستید. 3، شما به 2 مقایسه شده است. شما خوب است. 4، شما فقط به دم مقایسه. شما خوب است. 6، در مقایسه با دم، شما خوب هستید. بنابراین برای هر نقطه اگر آن را در حال حاضر طبقه بندی شده اند، شما در حال ساخت یک مقایسه. بنابراین آن را فقط به N. و چون ما بهترین حالت زمان اجرا از N و بدترین حالت زمان اجرا از N مربع، ما هیچ زمان اجرا مورد انتظار. 

این فقط در بستگی دارد هرج و مرج از لیست ما وجود دارد. و دوباره، یکی دیگر از نمودار و جدول دیگر. بنابراین تفاوت بین انواع. من فقط رفتن به نسیم از من احساس می کنیم به طور گسترده صحبت کردیم در مورد روشی که همه نوع از متفاوت است و پیوند با یکدیگر. بنابراین مرتبسازی ادغامی یکی از آخرین است من باید به شما بچه ها با مته سوراخ. ما یک عکس بسیار رنگارنگ. بنابراین ادغام مرتب سازی بر الگوریتم بازگشتی است. پس شما بچه ها می دانید چه یک تابع بازگشتی است؟ 

هر کسی می خواهم بگویم؟ شما می خواهید امتحان کنید؟ بنابراین یک تابع بازگشتی است فقط یک تابع است که خود را می نامد. بنابراین اگر شما بچه ها آشنا هستند با دنباله فیبوناچی، که بازگشتی به دلیل تلقی شما را از دو قبلی و آنها را با هم اضافه کنید به یک بعدی شما. بنابراین بازگشتی، من همیشه فکر می کنم بازگشت به عنوان مثل یک کهکشان مارپیچی بنابراین شما می خواهم فزاینده به آن هستیم. اما این تنها یک تابع که خود می نامد. 

و، در واقع، واقعا سرعت من می تواند شما را به آنچه که به نظر می رسد نشان می دهد. بنابراین بازگشتی در اینجا، اگر ما نگاه کنید، این است راه بازگشتی به جمع بیش از یک آرایه. پس همه که ما انجام می دهیم است ما باید تابع مجموع مجموع طول می کشد که یک اندازه و یک آرایه. و اگر شما متوجه، اندازه decrements توسط یکی در هر زمان. و همه آن را انجام می دهد اگر x برابر است با zero-- بنابراین اگر اندازه آرایه برابر با zero-- آن را برمی گرداند صفر است. 

در غیر این صورت آن را به این جمع بندی آخرین عنصر از آرایه، و پس از آن طول می کشد مجموع بقیه از آرایه. بنابراین آن را فقط شکستن آن را پایین به مشکلات کوچکتر و کوچکتر. داستان کوتاه مدت، بازگشت، تابع است که خود را می خواند. در صورتی که همه شما را از این رو، این چیزی است که یک تابع بازگشتی است. اگر شما 51، شما بسیار خواهد شد، خیلی راحت با بازگشت. این واقعا سرد است. این حس را در ساخته شده مانند 03:00 یک شب است. و من دوست دارم، به همین دلیل بود من هرگز این استفاده کنید؟ 

بنابراین برای جور کردن و ادغام، اساسا چه آن را به انجام آن است رفتن به آن شکستن و شکستن آن تا زمانی که این عناصر فقط تک. عناصر تک آسان به مرتب کردن. ما می بینیم که. اگر شما یک عنصر، آن را در حال حاضر در نظر گرفته مرتب شده است. بنابراین در ورودی از عناصر N، اگر n کمتر از 2 است، فقط به خاطر اینکه معنی بازگشت آن را یا 0 یا 1 که ما دیده ایم. اینها عناصر مرتب شده در نظر گرفته. 

در غیر این صورت آن را در نیم شکستن. مرتب کردن بر اساس نیمه اول، مرتب دوم نیم، و سپس آنها را با هم ادغام خواهند شد. چرا این نوع ادغام نامیده می شود. بنابراین ما باید در اینجا ما این را مرتب کردن. بنابراین ما نگه داشتن داشتن آنها تا اندازه آرایه 1 است. بنابراین، هنگامی که آن را به 1، ما فقط بازگشت چرا که این یک آرایه مرتب شده است، و این یک آرایه مرتب شده است، و این یک آرایه مرتب شده باشد، ما همه طبقه بندی شده اند. پس چه کار می کنیم ما است شروع ادغام آنها را با هم. 

پس راه شما می توانید فکر می کنم در مورد ادغام است شما فقط حذف کوچکتر تعداد هر یک از زیر آرایه ها و فقط آن را به آرایه ظهور پیوست. بنابراین اگر شما در اینجا نگاه کنید، که ما باید این مجموعه در حال حاضر 4، 6، و 1. هنگامی که ما می خواهیم به ادغام این، ما در این دو اولین نگاه و ما می گویند، OK، 1 کوچکتر است، آن را به جلو می رود. 4 و 6، چیزی برای مقایسه وجود ندارد آن را به، فقط آن را بر روی برچسب به پایان است. 

هنگامی که ما ترکیب این دو، ما فقط را به یک کوچکتر از این دو، پس از آن 1. و در حال حاضر ما را به کوچکتر از این دو، به طوری که 2. کوچکتر از این دو، 3. کوچکتر از این دو، 4، 5، 6. بنابراین شما فقط کشیده شدن این. و از آنجایی که آنها به قبلا مرتب شده است، شما فقط باید یک مقایسه هر زمان وجود دارد. کد پس بیشتر اینجا، نمایندگی فقط. بنابراین شما در وسط شروع و مرتب سازی بر شما سمت چپ و سمت راست و سپس شما فقط آن ادغام خواهند شد. 

و ما کد ندارد برای ادغام در اینجا ببینید. اما، دوباره، اگر شما در رفتن مطالعه 50، آن آنجا خواهد بود. در غیر این صورت به من آمده بحث اگر شما هنوز هم اشتباه گرفته شود. بنابراین نکته جالب در اینجا است که بهترین حالت است، بدترین حالت، زمان اجرا و انتظار همه در ورود می باشد N، که به مراتب بهتر از ما کرده ایم برای بقیه از انواع ما دیده می شود. ما دیده ایم N مربع و آنچه ما در واقع دریافت در اینجا n log n استفاده شده است که بزرگ است. 

در چقدر بهتر است که نگاه کنید. مانند یک منحنی زیبا. خیلی بیشتر موثر است. اگر شما همیشه می توانید، استفاده مرتب سازی بر ادغام خواهند شد. آن را به شما صرفه جویی در وقت. سپس دوباره، همانطور که گفتیم، اگر شما را در این منطقه پایین تر هستید، آن که را ندارد بسیاری از تفاوت. شما دریافت می کنید به هزاران و هزاران نفر از ورودی، شما قطعا می خواهید الگوریتم کارآمد تر. و، دوباره، دوست داشتنی جدول ما از همه انواع است که شما امروز آموخته است. 

بنابراین من می دانم آن روز متراکم شده است. این است که لزوما نمی برای کمک به شما pset شما. اما من فقط می خواهم یک سلب مسئولیت آن بخش است فقط در مورد psets نیست. همه این مواد عادلانه است بازی برای لاس خود را. و همچنین اگر شما در ادامه با CS، این اصول واقعا مهم هستند که شما نیاز به دانستن. بنابراین چند روز خواهد بود کمی کمک pset بیشتر، اما چند هفته خواهد بود محتوای واقعی خیلی بیشتر که ممکن است فوق العاده به نظر نمی رسد در حال حاضر برای شما مفید، اما من قول می دهم اگر شما ادامه در خواهد شد بسیار، بسیار مفید است. 

به طوری که آن را برای بخش. پایین به سیم. من آن را در یک دقیقه انجام داد. اما وجود دارد که شما بروید. و من دونات و یا آب نبات را داشته باشد. آیا هر کسی حساسیتی به هر چیزی، به هر حال؟ تخم مرغ و شیر. بنابراین دونات هستند نه؟ OK. همه راست. بدون شکلات؟ با ستارگان انفجاری و. Starbursts خوب است. OK. ما قصد داریم به با ستارگان انفجاری و پس از آن در هفته آینده. این چیزی است که من دریافت کنید. شما بچه ها یک هفته بزرگ است. به عنوان خوانده شده مشخصات خود را. 

اجازه دهید من می دانم اگر شما هر گونه سوال. Pset دو درجه باید باشد به شما توسط پنجشنبه. اگر شما هر گونه سؤال در مورد من چگونه چیزی مدرج و یا چرا من مدرج چیزی راه من بود، لطفا با ایمیل من، بیا با من صحبت کنی. من این دیوانه کمی هستم هفته، اما من قول می دهم من هنوز هم در عرض 24 ساعت خواهد پاسخ دهید. بنابراین یک هفته، هر کس داشته باشد. موفق باشید در pset شما.