HOPARLÖR 1: Hey hər kəs! Bölmə geri xoş gəlmisiniz. Burada həm çox görmək üçün şad, və online seyr edən hər kəs. Belə ki, adi xoş geri kimi. Mən sizə bütün bir sevimli idi ki, ümid edirik istirahət tam həftə sonu, istirahət. Bu dünən gözəl idi. Belə ki, mən açıq havada həzz ümid edirik. 

Elanlar bir neçə Belə ki, ilk. Grading. Belə ki, sizin ən kazanılmış olmalıdır bir Sizin Scratch Pset barədə mənə e-poçt, habelə Pset 1 grading. Belə ki, yalnız bir neçə şeyi. Style50 da check50 istifadə etmək üçün əmin olun. Bu üçün nəzərdə edilir uşaqlar üçün resursları, Siz əldə etdiyiniz əmin etmək Siz kimi çox xal ehtiyacsız onlara kaybetmeden. Belə ki, stil kimi şeylər çox vacibdir. Biz bunun üçün off almaq üçün gedir. Siz bəzi artıq ola bilər Pset ki, qeyd. Və check50 yalnız bir deyil əmin etmək həqiqətən asan bir yoldur biz, həqiqətən qaytarılması edirik ki, nə istifadəçi geri olmalıdır, və hər şey düzgün çalışır. 

İkinci qeyd, əmin sizin doğru qovluğa şeyi yüklemek. Bu, mənim həyat yalnız bir edir az daha çətin Siz pset 1-pset 2 yüklemek əgər Mən hər şeyi download zaman, çünki, Onlar düzgün download etməyin. Mən bir az bitkin bilirik sistemi üçün istifadə almaq üçün, lakin yalnız super olacaq Ehtiyatlı olun, yalnız mənə əgər, ki, e-poçt əldə etdiyiniz zaman kimi 2 günortaya qədər at Mən grading edirəm. Əgər mən baxmaq lazımdır səbəb bütün ətrafında Pset üçün. Cool. 

Mən erkən olduğunu bilirik, lakin mən tamamilə qarovul off götürülmüş oldu Bu cümə görə ki, inşa, tərəfindən mənim professor yeah oh, istədiyiniz yalnız idi. Unutmayın, bir var Cümə günü səbəbiylə inşa. Belə ki, mən heç bir bəyənir bilirik midterms düşünmək, lakin ilk viktorina, 15 oktyabr edir oktyabr bu həftə başlayır. Belə ki, tez ola bilər gözləniləndən daha bütün edir. Belə ki qarovul off atılan deyilik Mən oh ki, növbəti həftə bölmə qeyd Sizin viktorina gələn həftə, mən düşündüm Mən daha çox bir az vermək istədiyiniz İndi bir rəhbərləri. 

Belə ki, problem set, sayı üç. Insanlar oxumaq necə maraq spec? OK. Biz bir neçə var. Kind aşağı sonuncu lakin həftə OK. Mən bu gözəl idi bilirik. Belə ki, Out ayırın. Mütləq həyata almaq sonra Bu gün ən azı spec oxumaq yüklənərkən kimi cəhd distribution kodu və çalışan İlk ilkin kimi Onlar xahiş ki, bir şey. Biz istifadə Çünki distribution kodu və kitabxana biz yalnız --It yalnız using-- etdik ki, biz bu pset etdik ikinci dəfə, crazy şey ola bilər Sizin cihaz ilə, və siz tapmaq istəyirəm həyata indi sonra qarşı. 

Cümə axşamı gecə və ya əgər çünki Çərşənbə gecə və nədənsə Sizin cihaz yalnız deyil kitabxana ilə almaq istəyirsinizsə və ya paylanması ilə kodu, deməkdir ki, hətta kodlaşdırma bunu başlamaq bilməz. Siz kontrol edə bilərsiniz, çünki Bu işləri görmək üçün. Sizin mý deyil biləcəklər tərtib görmek üçün. Siz erkən olanların qayğı istəyirəm həftə, siz hələ mənə e-poçt bilər və ya digər TFS biri, və biz o sabit əldə edə bilərsiniz. O Çünki məsələlər siz dayandırmaq gedir heç bir real irəliləyiş. Bu, bir səhv kimi deyil Siz yalnız cür atlayabilirsiniz. Siz məsələləri olan edirsinizsə sizin cihaz və ya distribution kodu, siz həqiqətən qəbul almaq istəyirəm sonra tez daha çox qayğı. Belə ki, hətta siz həqiqətən mý deyilik əgər kodlaşdırma başlamaq paylanması download kodu, spec oxumaq, əmin olun hər şey var çalışır. OK? Yalnız bunu edə bilərsiniz, mən asan olacaq həyatlarını söz verirəm. Və yəqin ki, olacaq İndi sağ bunu? OK. Belə ki, hər hansı bir sualınız? Hər hansı bir logistik şey? Hər kəs yaxşı? OK. 

Həmin üçün Disclaimer Siz oda və online. Mən keçmək üçün çalışırıq gedirəm cihaz PowerPoint arasında Biz gedirik, çünki bəzi coding bunu etmək anonim məşhur tələbi ilə bu gün təklif poll Mən keçən həftə göndərdi. Belə ki, biz bəzi coding məşğul olacaq. Belə ki, uşaqlar da istəyirsinizsə Sizin texnikası up yanğın, və bir e-poçt almış olmalıdır nümunə fayl ilə, mənə. Bunu etmək üçün çekinmeyin. 

Beləliklə, biz haqqında danışmaq olacaq Ayıklama olan gdb. Bu sizə kömək olacaq cür anlamaq şeyi kodu yanlış gedir. Bu, həqiqətən addım üçün yalnız bir yol var kodu vasitəsilə bunun kimi, və dəyişənlərin çap edə biləcəklər və ya faktiki neler başlıq proqram ayələri altında yalnız çalışan, bu faulting kimi, və siz heç bir fikir kimi istəyirik nə yalnız burada oldu. Mən uğursuz nə line bilmirəm. Bu yanlış getdi harada bilmirəm. Belə ki, gdb ilə sizə kömək edir. Ayrıca, istəsəniz bəli davam və 61, Bu, həqiqətən, həqiqətən olacaq sizin ən yaxşı dostu, mən sizə deyə bilər səbəb Mən sinif gedirəm, çünki. 

Biz ikili baxmaq olacaq axtarış, uşaqlar xatırlayıram əgər böyük telefon kitab misal sinif tamaşa. Biz həyata, və olacaq bir az daha vasitəsilə gəzinti, və sonra dörd vasitəsilə olacaq Bubble olan müxtəlif növ, Seçilməsi, Taxmaq, və Birleştirme. Cool. Belə ki, mən qeyd gdb kimi, bir ayıklama edir. Və bu böyük növü var şeylər, böyük funksiyaları və ya əmrləri Siz gdb ərzində istifadə və mən gəzmək ki, Siz ikinci bu bir demo vasitəsilə. 

Belə ki, bu deyil mücərrəd qalmaq olacaq. Mən cəhd və beton kimi etmək lazımdır uşaqlar üçün mümkün. Belə ki, qırmaq. Bu da fasilə olacaq kimi bir sıra olan , proqram bir xətt təmsil və ya bir funksiyası olar. Belə ki, əsas qırmaq demək əgər, Bu, əsas da dayandırmaq və funksiyası vasitəsilə gəzmək edək. 

Eyni zamanda, bəzi xarici varsa Swap və ya Cube kimi fəaliyyət, biz ötən həftə baxdı ki. Bu bir fasilə demək, proqram xit zaman, ki, Bu sizin üçün gözləmək lazımdır nə demək. Bu, yalnız belə icra əvvəl həqiqətən funksiyası daxilində addım bilər və neler oldu. Belə ki, Next, yalnız üzərində skips növbəti line, funksiyaları üzərində gedir. Addım. Bu bütün kiçik mücərrəd. Belə ki, yalnız onların vasitəsilə çalıştırmak üçün gedirəm, ancaq ikinci istifadə onları görmək lazımdır. 

Bir funksiyası daxil Addım. Kimi mən deyirdim, Swap ilə, olduğu kimi Siz həqiqətən istəyirik kimi imkan verir kimi fiziki daxilində gücləndirməklə, o dəyişənlərin siz mess, çap Onlar nə, neler oldu. Siyahı sözün yalnız çap edəcək ətraf kodunu. Belə ki, siz cür unutmaq əgər Siz proqram olduğu, və ya merak etdiyiniz nə ətrafında neler bu yalnız bir seqment çap edəcək onun ətrafında beş və ya altı xətləri istəyirəm. Belə ki, siz yönümlü bilər Siz harada haqqında. 

Bəzi dəyişən çap. Belə ki, əsas kimi varsa Sezar, biz baxmaq lazımdır ki. Siz hər hansı bir anda Çap Açar demək olar. Dəyəri belə nə deyim ki, bəlkə haradasa yol boyunca, Sizin əsas yazılmaması. Siz, həqiqətən, çünki demək olar həqiqətən dəyər müşahidə edə bilərsiniz. 

Yerli, yalnız izləri yerli dəyişənlərin. Belə ki, zaman bir loop etdiyiniz, və yalnız oh, kimi görmək istəyirik. Mənim nədir? Bu əsas dəyəri nədir Mən burada başlamaq ki? Bu nöqtədə mesaj nədir? Bu, yalnız bütün çap edəcək o, belə ki, siz fərdi yoxdur Print I. Print Mesaj, deyirlər. Print Key. Və sonra göstərin. Hansı ki, yoxdur sizin kimi proqramı vasitəsilə addım, Bu yalnız əmin etmək lazımdır Bəzi dəyişən tapılanlar hər nöqtədə. Belə ki, siz --it var also-- qısa harada cür Siz oh kimi davam yoxdur. Print Key ya çap I. Bu, yalnız sizin üçün bunu avtomatik olaraq. 

Belə ki, ki, biz gedirik Bu gedir necə. Mən cəhd və keçid gedirəm mənim cihaz üzərində. Mən bunu edə bilərsiniz əgər baxın. Bütün. Biz yalnız güzgü olacaq. Crazy şey yoxdur Mənim laptop zaten. OK. Bu bir olmalıdır. Bu, belə kiçik deyil. Biz bunu edə bilərsiniz əgər in nəzər salaq. 

OK. Alice açıq-aydın mübarizə Burada yalnız bir az, ancaq bir MOMENTO almaq lazımdır. OK. Biz yalnız bu artırmaq niyyətindəyik. OK. Hər kəs cür ki, görmək edə bilərəmmi? Bəlkə bir az? Mən bunu bir az kiçik bilirik. Siz çox anlamaq bilməz bu böyük etmək üçün necə. Hər kəs bilir. Hər kəs daha böyük etmək üçün necə bilir? OK. Biz bununla gəzmək olacaq. Yalnız çünki zaten etməz ki, uşaqlar lazımdır kod var. 

Hansı daha vacibdir burada terminal edir. Və biz niyə bu qədər kiçik burada var? Parametrlər. Oh. True Ike. Bu necə oldu? Orada. Ki, hər kəs üçün daha yaxşı deyilmi? OK ,. Cool. 

Bir CS etdiyiniz zaman Bilirsiniz class texniki çətinliklər the-- cür hissəsi Belə ki, bu sil. OK. Belə ki, burada hissəsində, biz burada idi. Caesar bir yürütülebilir fayl. Mən bunu. Belə ki, gdb ilə həyata bir şey ki, yalnız yürütülebilir faylları üzərində işləyir. Belə ki, bir DOTSY run bilməz. Siz, həqiqətən, etmək lazımdır Sizin kodu tərtib əmin, və bu, həqiqətən run bilər ki. 

Bu deyil, əgər Belə ki, əmin olun tərtib, tərtib almaq, ki cür vasitəsilə çalıştırabilirsiniz. Belə ki, gdb başlamaq üçün, bütün etmək, Gloria növü gdb, və sonra yalnız istədiyiniz fayl. Mən həmişə Sezar orfoqrafik səhv. Amma əmin etmək istəyirəm bir yürütülebilir ildən, ti nin dot flash ki, siz olacaq deməkdir CSI siz icra olacaq çalıştırmak üçün Bu ayıklama ilə və ya faylları. OK. Belə ki, siz almaq nə hədyan bu cür. Bu ayıklama yalnız hər şeyi var. Siz, həqiqətən, yoxdur indi bu barədə narahat. Gördüyünüz kimi, biz bu var açıq parens, ÜDM, yaxın parens, və yalnız cür kimi görünür Bizim command line, sağ? 

Belə ki, biz do-- nə istəyirəm --So, Ilk şey Biz seçmək istəyirəm bir yer pozmaq. Belə ki, bir səhv var Bu Caesar proqram Hesab edirəm ki, təqdim ki, biz tapmaq olacaq. Bu daxil edir ki, bu nə Bütün caps Barfoo, və nədənsə Bu yalnız tərk A. dəyişmir tək, doğru hər şey mi lakin ikinci məktubu A dəyişməz olaraq qalır. Belə ki, biz cəhd olacaq və ki, niyə anlamaq. Belə ki, ilk şey adətən Siz gdb başlamaq zaman etmək istəyirəm pozmaq harada həyata rəqəm deyil. 

Belə ki, Sezar olduqca qısa proqramdır. Biz yalnız sağ, bir funksiyası var? Sezar funksiyası nə idi? Yalnız bir funksiyası, Main doğru var? Əsas funksiyası bütün proqramları üçün. Əgər əsas olmasaydı, mən bilər narahat az indi ola, lakin mən bütün var Main idi ümid edirik. Belə ki, nə biz nə edə bilərik bilər yalnız kimi, Main pozub. Belə ki, OK, deyir. Biz orada breakpoint bir müəyyən. 

Belə ki, xatırlamaq indi şey Caesar edir bir command line arqument hüququ alır və biz hər yerdə hələ ki, həyata yoxdur. Belə ki, nə zaman Siz, həqiqətən, run getmək Bu proqram, siz etdiyiniz hər hansı bir proqram gdb çalışan command line lazımdır arqumentlər, siz daxil olacaq zaman ilk yayınlanmaya başlar. Belə ki, bu halda, biz nə Üç açarı ilə Run. Və həqiqətən başlayacaq. 

Burada görmək Belə ki, biz RC 2 bərabər deyil. Belə ki, uşaqlar bütün varsa Mən göndəriləcək ki, fayl ki, kimi ki, görürsünüz ilk line, bizim əsas funksiyası, sağ? Biz görmek üçün yoxlanılması dəlilləri doğru sayı. Belə ki, siz merak edirsinizsə RC doğru əgər, Yalnız Print RC kimi bir şey edə bilərsiniz. RC olan iki biz doğru nə gözlənilir, nə? 

Belə ki, biz növbəti getmək bilər, vasitəsilə davam edir. Belə ki, biz bəzi əsas var. Və biz əsas çap edə bilərsiniz ki, doğru deyil əmin olun. Maraqlı. Olduqca biz gözlənilir nə. Belə ki, bir şey həyata keçirmək üçün də gdb ilə, Siz, həqiqətən, hit qədər deyil ki, Next, siz yalnız gördüm ki, xətt həqiqətən icra edilir. Belə ki, bu halda Key hələ təyin olunmayıb. Belə ki, Key bəzi zibil dəyəri Siz orada altındakı görmək. Mənfi $ 120-- --It nin bir milyard və bir şey tək şeyi doğru? Biz gözlənilir ki, Key deyil. Amma biz sonra Next hit, və əgər biz cəhd və Print əsas, bu üç var. 

Hər kəs ki? Belə ki, bir şey almaq əgər kimi istəyirik ki, gözləyin. Bu tamamilə səhv, mən bilmirəm Mən bütün istəyirəm, çünki bu baş necə bir sıra təyin olunur etməli, dəyişən, çap cəhd Sonrakı vuruş cəhd ki, işləyir, əgər yenidən və görürük. Yalnız həyata olacaq, çünki həqiqətən, sizin sonra bir şey təyin Next edib. Hər kəs mənada? Uh huh? 

HOPARLÖR 2: zaman təsadüfi nömrələri ki, nə deməkdir? 

HOPARLÖR 1: Bu yalnız təsadüfi deyil. Bu, sadəcə zibil var. Bu, yalnız bir şey var ki, kompüter təsadüfi təyin edəcək. Cool. Belə ki, indi biz vasitəsilə hərəkət, və belə ki, indi biz bu düz mətn GetString var. Belə ki, mənə yalnız təqdim edək nə Biz burada növbəti hit zaman baş verəcək. Bizim gdb hüququ, yox? Ki, GetString, çünki indi icra olunur, sağ? Biz gördükdə, düz mətn bərabərdir GetString, açıq parens və parens, və biz Next hit ki, var həqiqətən, indi edam. Belə ki, bunun üçün gözləyir daxil bir şey us. 

Belə ki, biz daxil bizim ərzaq olacaq olan Mən sizə dedim kimi uğursuz oldu nə və yalnız olduğunu deyir kapandı ki, icra tamamladı bracket bu deməkdir ki, loop həyata mövcud. Mən ki, biz, indi Next hit bilər, və Siz Caesar tanış bütün istəyirik, Bunu etmək üçün gedən, bu xətt nə edir. Int I 0 bərabərdir üçün bu, N bərabərdir Strlen, düz mətn, və sonra Mən n, mən, üstəgəl, üstəgəl azdır. Edəcəyimiz bu loop nədir? Sizin mesajı açın. Cool. Belə ki, bunu başlamaq edək. 

Belə ki, bu vəziyyət olmalıdır ilk bir, uyğun? Bu bir B varsa, bu düz mətn I. Biz var Bizim yerli haqqında məlumat əldə edə bilərsiniz. Belə ki, mən sıfır və altı əgər biz gözləyirik və bizim əsas üç. Mənada ki, bütün, sağ? Həmin nömrələr bütün məhz onlar olmalıdır. Belə ki, zümzümə? HOPARLÖR 3: Mən mina üçün təsadüfi nömrələri. HOPARLÖR 1: Bəli, biz --we yoxlamaq bilər ikinci bu barədə söhbət edə bilərsiniz. Amma bu əldə olmalıdır. Beləliklə, biz bir kapital varsa Ilk bir B, Bu vəziyyət doğru, onu tutmaq lazımdır? Biz Next hit əgər Belə ki, görürük Bu Əgər həqiqətən icra edən. Siz aşağıdakı edirsinizsə Sizin kodu boyunca, burada bu xətt, burada düz mətn I Bu hesab ilə əvəz olunur, yalnız əgər icra vəziyyəti düzgün mı? 

Gdb yalnız sizə göstərmək niyyətindədir faktiki icra olunur ki, hər şeyi. Əgər bu şərt yerinə əgər Belə ki, bu yalnız növbəti line keçmək olacaq. OK? Belə ki, biz var. Bu bracket bu deməkdir indi loop həyata bağladı. Belə ki, yenidən başlamaq olacaq. Just kimi. Belə ki, biz məlumat əldə edə bilərsiniz ki, burada yerli haqqında və biz ilk olduğunu görəcəksiniz məktub, sağ dəyişib? Bu olmalıdır kimi, indi E var. Belə ki, biz davam edə bilərsiniz. 

Və biz bu çek var. Bu çek sağ, işləmək lazımdır? Bu dəyişdirilməlidir A. var irəli üç məktublar. Amma, biz hiss əgər fərqli bir şey almaq. Burada bu halda qədər ki, bu tutuldu Bu, və bu xətt, edam Bizim B. redaktə Lakin, burada bu halda, biz yalnız atlandı ki, var, və [getdi? L SIFF. ?] Belə ki, bir şey var olur. Nə ki, izah edir ki, biz burada tutmaq lazımdır bilirik ki, lakin bu deyil. Hər kəs nə görmək edə bilərəmmi bizim problem uyğundur? Bu, çox dəqiqə şey. Və siz də kodu baxmaq bilər. Bu da nə line unutmaq xətt var orada da ancaq [Işitilemez] var. Bəli? 

HOPARLÖR 4: Bu çox böyük var səhifə kitab oxumaq əgər. HOPARLÖR 1: Məhz. Belə ki, ayıklama demək deyil bilər ki, ancaq ayıklama bir xətt aşağı əldə edə bilər Siz fəaliyyət deyil bilirik. Və bəzən, xüsusilə sonra dövr, zaman Bir yüz, bir ilə məşğul olduğunuz bir neçə yüz kodu xətləri, və siz Bu uğursuz oldu harada bilmirəm, bu bunu bir yoldur. Belə ki, biz səhv tapdım. Siz fayl düzeltmek bilər və sonra, yenidən run bilər və hər şey mükəmməl işləmək olardı. Və ən böyük şey Bu OK, kimi görünə bilər. Bəli. Cool. Siz aradığınız nə bilirdi. Belə ki, siz nə bilirdi. 

Gdb çünki super faydalı ola bilər bütün bu şeylər çap edə bilərsiniz ki, deyil. Bu, çox faydalı printf artıq var. Necə bir çox istifadə printf hesabatları kimi bir səhv, sağ olduğu anlamaq üçün? Belə ki, bu, siz deyil geri davam etmək lazımdır, və şərh kimi Printf, və ya, həyata şərh və anlamaq nə Siz çap edilməlidir. Bu, həqiqətən, yalnız imkan verir vasitəsilə addım şeyi çap Siz olacaq kimi, belə ki, siz Onlar real vaxt dəyişdirmək necə müşahidə, proqram kimi çalışır. 

Və bu bir az sürer alışma bit. Mən yalnız cür məsləhətdir onu bir az incidir olan indi üçün. Siz artıq bir saat sərf əgər gələn həftə necə gdb istifadə öyrənmək, Siz özünüzü xilas edəcək sonra çox vaxt. Və sanki. biz demək Bu insanların hər il, Mən gəldiyində və Mən xatırlayıram sinif, mən gözəl olacaq, kimi idi. No. Pset 6 gəldi və mən kimi, mən mý öyrənmək alıram Mən çünki gdb istifadə etmək necə burada neler bilirik. 

Siz çox vaxt əgər Belə ki, kiçik proqramlar istifadə Siz olacaq ki, iş kimi, iş kimi bir şey ilə Bu kimi VISIONARE. Siz əlavə təcrübə istəyirsinizsə, mən əminəm Mən arabası proqramları ilə gəlmək bilər Isterseniz üçün debug. 

Amma yalnız bir vaxt əgər almaq üçün onu istifadə, yalnız ilə ətrafında oynamaq, həqiqətən yaxşı xidmət edəcək. Və həqiqətən biri o şeyi ki, siz yalnız cəhd, və əlləri çirkli almaq Siz, həqiqətən, anlamaq əvvəl ilə. Mən, həqiqətən, yalnız bir dəfə başa Mən bu debug şeyi idi və bir fikir var çox gözəl var necə tez deyil, gec debug. OK. Cool. Mən bu cür kimi bilirik gdb bir qəza kurs, və mən mütləq əldə işləyəcək bu böyük növbəti dəfə baxmaq. Cool. 

Belə ki, biz geri PowerPoint getmək əgər. Bu iş gedir? Awh. Bəli. OK. Belə ki, heç hər hansı bir ehtiyac varsa o yenə siyahısı var. Belə ki Binary Search, hər kəs Davudun böyük tamaşa xatırlayır yarısında telefon kitab Ses. Mən, həqiqətən, almaq deyil Artıq telefon kitab, siz harada kimi çünki bu gün telefon kitab almaq? Mən, həqiqətən, bilmirəm. Bu Binary Search. Hər kəs xatırlayıram varmı İkili Axtar işləyir? Hər kəs bütün? Bəli? HOPARLÖR 5: Siz izlə siz yarım baxmaq ki əsaslanaraq, olacaq, və digər yarısı qurtarmaq. 

HOPARLÖR 1 Məhz. Belə ki, Binary Search, o EA cür --we Bu bölmək və fəth zəng etmək istəyirəm. Belə ki, siz edəcəyik nə Siz ortasında baxmaq lazımdır Bu oyunları əgər siz görəcəksiniz nə üçün aradığınız. Bu deyil, onda siz cəhd anlamaq, onu tərk etmək niyyətindədir yarım və ya sağ yarım. Siz arıyorsanız Belə ki, bu ola bilər alfabetik ki bir şey, Siz oh, bax. Allison M əvvəl gəlir? Bəli. Belə ki, biz olacaq birinci yarısında baxmaq. 

Yoxsa nömrələri ilə kimi ola bilər. Ki, bir şey edə bilərsiniz müqayisə, bu sıralaması edə bilər. Siz ikili axtarış istifadə edə bilərsiniz. Belə ki, hər kəs bu xatırlayıram graph və ya bu nədir? Bu asimptotik mürəkkəblik var. Belə ki, bu graph yalnız nə qədər təsvir kimi bir problemi həll etmək üçün götürür Siz şeyin sayını artırmaq ki, istifadə edirik. 

Belə ki, biz xətti vaxt olan N, var. Qədər olan iki üzərində N, əgər yaxşı, hələ super sürətli artır. Və sonra biz olan giriş nə biz ikili axtarış hesab. Biz fark etsəniz, sizin problem kimi çox və daha böyük olur Bu sizi zaman həll etmək üçün həqiqətən ki, çox artırmaq deyil. Bu müqayisə kimi burada əvvəlində. Siz OK, kimi istəyirik. Şey burada həqiqətən deyil olsun biz istifadə bir, ancaq, bir milyon bir milyard çıxmaq. Siz some-- --you're tapmaq üçün çalışırıq bir ot tayası bir iynə tapmaq üçün çalışırıq. 

Mən sizə bu problemi istəyirəm edirəm. Bu mürəkkəbliyi deyil istəyirəm xətti, çünki bütün üçün Sizin mý vasitəsilə axtarış bilirik Hər bir fərdi iynə, ot şey, Sizin iynə axtarmaq üçün çalışırıq. Və mənim fikrimcə çox əyləncə deyil. Mən sürətli kimi. Mən səmərəli istəyirəm. Və Çalışqan tələbələr sizə uşaqlar, siz asan iş bilirik var deyil, çətindir növü şey necə Bu alqoritmlər edə bilərsiniz. 

Belə ki, biz gəzmək olacaq yalnız bir sürətli Məsələn vasitəsilə. Mən sizə uşaqlar olmalıdır düşünürəm Binary Search bir tərəfdən, lakin halda hər kəs bir az qeyri-səlis, onu gücləndirmək istəyirik, biz yalnız getmək olacaq burada bir nümunə ilə. Əgər Belə ki, biz aradığınız array yeddi ehtiva edir. 

Belə ki, biz nə ilk şey sağ, ortasında baxmaq? Və həmçinin kodlaşdırma olacaq Yalnız ikinci ikili axtarış. Belə ki, fun olacaq. Beləliklə, biz baxmaq orta kiçik Diziler 3. 3 7 bərabər varmı? Deyil. Bu altı var. Belə ki, daha az və ya yeddi daha? Az. Bəli. Nice iş uşaqlar. Mən olmalıdır kimi hiss konfet, çünki mən meydançaları onu atmaq istəyirəm. Mən gələn həftə gedirəm budur. Bu kəskin uşaqlar davam edəcək. 

Belə ki, biz tullamaq İlk yarı, sağ? Bu az idi. biz hər şeyi bilirik ki, sol tərəfində az olacaq nə Biz, həqiqətən, aradığınız. Belə ki, heç bir ehtiyac var var buna diqqət. Yalnız bu barədə unutmaq. Belə ki, indi biz sağ tərəfdən baxmaq, və biz orada orta baxmaq və indi doqquz var. Belə ki, 9 That --Everyone? Biz istəyirik nə daha böyük sağ üçün axtarırsınız? Belə ki, biz atmaq olacaq sağ üz hər şey. Kimi. İndi biz bir ilə tərk edirik. Beləliklə, biz yoxlamaq, bu nə biz aradığınız? edir. Biz nə istədiyini tapdı. Beləliklə, biz tamamlayın. Bilinear axtar. 

Və, biz hiss əgər Orada yeddi giriş idi. Bu, yalnız üç dəfə kimi götürdü ancaq bir milyard kimi edirik, əgər, Sizlərin neçə addımlar edəcəyini bilirik biz dörd milyard şeyi olsa almaq? Hər hansı bir guesses? 32 var. Bir şey tapmaq üçün 32 addımlar bir dörd milyard Çünki iki səlahiyyətləri element array. Belə ki, iki, 32 üçün dörd milyard edir. 

Belə ki, olduqca crazy necə də etdiyiniz addımlar kifayət qədər kiçik bir sıra kimi bir şey tapmaq üçün dörd milyard elementləri. Ki, qeyd ki, biz istəyirik Bu kod gedir belə ki, uşaqlar həqiqətən bilərsiniz cür necə bu işləri görmək. Bütün sağ, uşaqlar kod bilər. Mən sizə uşaqlar imkan gedirəm bir az danışmaq. Olan siz ətrafında insanlar bilmək alın kimsə son bölməsində istədi. 

Belə ki, siz ətrafında insanların tanış. Bir az danışmaq. Və Mən sizə istəyirəm uşaqlar indi yalnız pseudocode bir kontur yaratmaq üçün cəhd edin. OK? Whoa. Mən sizə uşaqlar istədiyiniz bütün istəyirik yalnız bu halda, doldurmaq niyyətindədir. Mən bu yuxarı qoymuşuq və aşağı həddi olan başlanğıcını təmsil bizim serialın və sonu. Və həqiqətən gedir loop vasitəsilə anlamaq nə biz bu isə loop ərzində edirik. 

Siz yazaraq anlamaq bilər, belə ki, mən hallar nə orada bir ipucu ki, biz burada var? Siz anlamaq istəyirsinizsə Belə ki, hallarda, biz bu pseudocode edəcək sonra biz, həqiqətən, onlara kod lazımdır. Və olacaq, mən ümid edirəm ki, lazımdır, hesab edirəm ki, gözləmək çox bir az daha asan ola bilər. , Bu çox kodu deyil, çünki həqiqətən, həqiqətən, sərin. 

Mm-hm? 

TƏLƏBƏ: [Işitilemez]? Öğretim: Bəli. Bir şey var idi ortasında tapmaq üçün. 

TƏLƏBƏ: Belə ki, istifadə edə bilərsiniz. OK. 

Öğretim: Perfect. Belə ki, biz nə etmək lazımdır ilk şey. Belə ki, orta tapmaq. Böyük. Belə ki, bir fikir var ki, necə biz bilər həqiqətən kodu ilə orta tapmaq? 

TƏLƏBƏ: Bəli. 2 n? Öğretim: Belə ki, n 2 üzərində. Belə ki, xatırlayıram bir şey ki, Sizin yuxarı və aşağı həddi dəyişir. Biz hissəsi constricting saxlamaq serialın biz üçün arıyorsanız. Belə ki, n 2 yalnız işləyəcək ilk şey üçün biz. Belə ki, nəzərə yuxarı və aşağı alaraq, necə ki, orta element əldə edə bilər? Biz orta istəyirəm, çünki yuxarı və aşağı, sağ arasında? Mm-hm? 

TƏLƏBƏ: [işitilemez]. 

Öğretim: Beləliklə, biz bir orta var. Və üst plus 2-dən aşağı olacaq. Awesome. Biz orada getmək. Bir xətt aşağı. Siz uşaqlar üçün yol var. Belə ki, indi biz bizim var orta, biz nə istəyirik? Yalnız ümumi. Siz kod yoxdur. Bəli. TƏLƏBƏ: [Işitilemez]? Öğretim: Belə ki, plus siz etdiyiniz çünki iki arasında orta tapmaq Onlardan. Belə ki, xeyirxah onlara hesab əgər Bu tərəfdən də artan, Siz yanaşma kimi bu barədə düşünmək orta, bu kimi istəyirəm. Əgər Beləliklə, siz hər tərəfində idi orta və biz 5 və 7 kimi var. Siz onları birlikdə əlavə 12 almaq, siz 2 bölmək, 6. 

Bəzən çətindir ki, işləyir izah, lakin Siz iş əgər nümunə bəzən, Bu əgər anlamaq kömək lazımdır Bu müsbət və ya mənfi olmalıdır. Bəli. 

TƏLƏBƏ: [Işitilemez] tam ortasında onlar bir halda idi əgər kiçik ədəd bir çox var və böyük bir sayı kimi? 

Öğretim: Belə ki, sizə lazım olan bütün serialın orta. Belə ki, əgər siz kiçik ədəd bir dəstə idi və sonra bir həqiqətən böyük sayı sonunda, bu məsələ deyil. Bütün məsələ ki, onlar yalnız sıralanır edirik orta baxmaq istəyirəm Bu array hələ istəyirik, çünki yarısı sizin problem dilimleme. Cool. Belə ki, indi biz var ki, orta, biz növbəti nə etməliyəm? 

TƏLƏBƏ: karşılaştırın. Öğretim: The müqayisə. Value_wanted Belə orta müqayisə. Cool. Belə ki, biz burada görmək biz burada qədər istəyirsinizsə bu dəyər. Bu bir sıra saxla. Belə ki, orta indeksi aiddir. Beləliklə, biz orta dəyərləri etmək istəyirəm. Əgər siz unutmayın , ikiqat bərabər müqayisə. Siz tək sen bərabərdir nə yalnız redesign gedir, və sonra, əlbəttə, bu Istədiyiniz dəyəri olacaq. Belə ki, yoxdur. 

Beləliklə, biz görmek olacaq orta dəyərlər Biz istəyirik dəyərinə bərabərdir. Aşırma unutmayın. Dropbox getmək lazımdır. Beləliklə, biz bu halda nə etməliyəm? Biz qayıtmaq istəyirəm nə varsa? Biz demək çalışırıq. 

TƏLƏBƏ: off yazdırın. 

Öğretim: Bəli, biz off çap etmək istəmirəm. Belə ki, burada bir bool, biz belə doğru və ya yalan qayıtmaq istəyirəm. Biz bu sayı, deyərək edirik bir [? RRA? ?] Bu Belə ki, biz yalnız doğru qayıdın. Mən doğru sehr bilər. 

TƏLƏBƏ: Niyə sıfır geri deyil? Öğretim: ola bilər Belə ki, Siz istəyirdi əgər sıfır qayıtmaq. Lakin bu halda, çünki funksiyası bir bool qaytarır, biz doğru və ya yalan ya qayıtmaq lazımdır. TƏLƏBƏ: zaman etdiyiniz , boolean ifadə deyərək siz onu yalan bərabər müəyyən edə bilər? Mən demək istəyirəm, əgər bu vəziyyətdə Like yuxarı yalan bərabərdir kimi, görüşüb deyil. Yalnız əgər anlamaq edəcək digər tərəfdən yalan qoymaq? Öğretim: Bəli. Belə ki, həqiqətən əgər Heç bir şey bunu kimi yuxarı və ya aşağı, ki, doğru və ya yalan qaytarır və bu həqiqətən pis stil demək bərabərdir doğru və ya bərabərdir bərabərdir yalan bərabərdir. Siz nəticəsində istifadə etmək istəyirəm Sizin çek kimi özü kimi. Mən istəyirdim nə. Mən istəyirdim nə var. Xahiş edirik sizin halda belə bir şey haqqında kimi c bu edin. 

Beləliklə, biz int əsas (void) varsa və bu kimi bir şey. Yuxarı olduqda və siz Siz etdiyiniz və bəzi daxil Siz edə bilərsiniz əgər xahiş bu kimi bir şey? Right? TƏLƏBƏ: Mən çalışır Bu [Işitilemez] etmək. It's-- Çünki Öğretim: Sağ. Belə ki, bu doğru, yalan olmaq istəyirsiniz? TƏLƏBƏ: Bəli. Öğretim: bu halda Belə ki, Bu doğru deyil, əgər icra etmək istəyirik. Belə ki, orada nə sərin şey bu. Belə ki, nida xatırlayıram point şeyi inkar? Bu [Işitilemez] deyil deməkdir deyir. Biz yalnız baxmaq əgər Belə ki, Burada bu hissəsi, siz had ki, qiymətləndirir demək yalan siz istədiyiniz kimi. Yalan deyil doğru olan bu icra deməkdir. Ki, hissi edirmi? TƏLƏBƏ: Bəli. Öğretim: Awesome. OK. Belə ki, biz yalnız qayıtmaq bilər bu halda doğru. Belə ki, indi biz digər iki var bu halda hallarda. Bizim iki digər hallarda hansılardır? Yalnız bu yolu edək. Belə ki, başqa ilə başlamaq edək əgər ortada dəyərlər Biz istəyirik dəyəri azdır. Belə ki, ortada dəyəri az biz aradığınız ki, dəyəri daha. 

Belə ki, bound olan edirsiniz biz yeniləmək istəyirəm edirəm? Yuxarı və ya aşağı? Upper? Serialın Belə ki, yan Biz baxaraq gedir? 

TƏLƏBƏ: Aşağı. 

Öğretim: Biz gedirik Sol axtarır. Az dəyəri az belə, əgər başqa. Burada orta dəyəri So biz istədiyiniz nə azdır. Belə ki, biz almaq istəyirəm bizim serialın sağ. Beləliklə, biz olacaq Bizim aşağı bound yeniləmə. Beləliklə, biz bizim aşağı redesign lazımdır. Və aşağı olmalıdır nə düşünürsünüz? TƏLƏBƏ: orta dəyər? Öğretim: Belə ki, orta dəyər TƏLƏBƏ: Plus 1. Öğretim: --plus 1. Niyə hər kəs mənə deyə bilərsiniz ki, plus 1 var? 

TƏLƏBƏ: [? Heç bir dəyəri?] daha çox bərabərdir. 

Öğretim: Sağ. Biz artıq bilirik ki, çünki Bizim orta dəyəri bərabər deyil Bu və biz onu istisna etmək istəyirəm bütün sonrakı axtarış. Ki plus 1, bu unutsanız qeyri-müəyyən loop kimi olacaq. Və yalnız bir tutuldu olacaq sonsuz loop və sonra segfault lazımdır və hər şeyi pis gedin. Belə ki, həmişə deyilik əmin olun dəyəri, o cümlədən yalnız baxdı. Beləliklə, biz bir plus 1 qayğı. 

Belə ki, indi biz son vəziyyət var təhlükəsizlik naminə həmişə mən Siz dəyəri, əgər başqa, burada kontrol edə bilərsiniz orta dəyəri daha böyükdür biz istəyirik. Biz istəyirik ki, deməkdir sol yarısı. Belə ki, bir biz yeniləmək üçün gedir? Upper. Və bərabər gedən bu nədir? Orta mənfi 1, çünki Əlbəttə, biz istəyirik biz deyilik ki, əmin etmək daha orta dəyəri baxaraq. Və sonra biz bunu var. Vəssalam. Yəni bütün ikili axtarış edir. Bu doğru, pis deyil? Bu 10 xətt kimi ağ kosmik ilə kodu. Belə ki, çox güclü, çox faydalı, siz daha sonra psets biri istifadə ola bilər. Bəlkə bu bir, lakin sonra. Belə ki, onu öyrənmək. Onu sevirəm. Bu, siz müalicə edəcək. Belə ki, hər hansı bir yoxdur binar axtarış suallar? Bəli. 

TƏLƏBƏ: bu önemli mi Sizin n hətta və ya tək olub? 

Öğretim: Xeyr Biz orta üçün tökmə Çünki bir int, bu yalnız kəsmək edəcək. Bir tam qalmaq və belə olacaq nəticədə hər şey vasitəsilə düzmək. Belə ki, narahat yoxdur. Hər kəs yaxşı? Awesome. Cool. Belə ki, uşaqlar bu var. Slideshow. Biz söhbət kimi, mən bilirəm David mürəkkəbliyi runtimes qeyd. 

Belə ki, ən yaxşı halda, yalnız var biz daimi vaxt zəng bir. Ki, ola bilər niyə hər kəs mənə deyə bilərsiniz? Ki, ssenari hansı növü səbəb olacaq? Mm-hm. 

TƏLƏBƏ: [Işitilemez] first-- Öğretim: Orta olan Belə ki, biz gələn ilk element, sağ? Belə bir bir sıra və ya nə biz yalnız aradığınız ortasında tam dab olmaq olur. Belə ki, ən yaxşı işi var. Siz yəqin ki, real problemlər daxil deyil almaq tez-tez [Işitilemez] çatmaq üçün gedir. Nə bizim ən pis halda haqqında? Bizim ən pis halda log n. Və bütün nə var mən danışdı ki, iki şey səlahiyyətləri. 

Belə ki, ən pis halda, demək ki, Biz aşağı sıra doğramaq idi ki, Bu bir bir element qədər. Belə ki, yarım onu ​​doğramaq idi biz bəlkə bilər kimi bir çox dəfə. Bu log n, çünki nə var Yalnız iki bölünməsi saxlamaq. Belə fərziyyələr, hər şeyi sizə Əgər edirsinizsə bilmək lazımdır ikili axtarış istifadə etmək niyyətindədir. Sizin elementləri sıralanır olmalıdır. Onlar sıralanır olmalıdır ki, yalnız yol var siz edə əgər bilirik bunun yarısını atmaq. 

Bu jumbled bag olsaydı və nömrələr siz, deyərək edirik OK, Mən orta yoxlamaq üçün gedirəm sayı və mən arıyorum sayı az, yalnız gedirəm özbaşına bir yarım atmaq. Siz əgər bilmək deyil sizin digər yarısı nömrələri. Sizin siyahısı sıralanır var. Eləcə də, bu ola bilər irəlidə bir az gedir, ancaq təsadüfi daxil olmaq lazımdır. Siz lazımdır yalnız ki, orta element gedin. Axır varsa bir şey vasitəsilə və ya əlavə addımlar atır ki, orta element almaq üçün, Bu log n artıq, çünki deyil Siz onu daha çox iş əlavə edirik. Və bu bir az edəcək iki həftə daha çox mənada, lakin mən yalnız cür, müqəddimə istədi Sizlərin nə bir fikir vermək gəlib. Amma o iki əhəmiyyətli fərziyyələr Bir ikili siyahısı üçün lazımdır. Bu sıralanır əmin olun. Ki, böyük bir var Siz indi uşaqlar. Və biz daxil edə bilərsiniz Bizim növ istirahət. Belə ki, dörd sorts-- bubble, durub, seçilməsi, və birləşməsi. Onlar sərin cür edirik. Sizlərin CS 124 almaq istəsəniz, Siz növ bütün növ öyrənmək lazımdır. Və bir XKCD fan əgər orada həqiqətən cool komik haqqında həqiqətən təsirsiz növ kimi mən yüksək baxmaq üçün gedir gəlir. Onlardan biri çaxnaşma növ kimi olan kimi, heç bir oh, təsadüfi array qayıtmaq deyil. Kapatma sistemi. Buraxın. Belə ki, geeky yumor həmişə yaxşıdır. 

Belə ki, hər kəs cür yadda deyil yalnız ümumi bir fikir kimi bubble sort necə. Yadınızdadırsa? 

TƏLƏBƏ: Bəli. 

Öğretim: Bunun üçün getmək. 

TƏLƏBƏ: Siz olacaq Belə ki, bu böyük, onda siz iki dəyişdirmək. 

Öğretim: Mm-hm. Məhz. Belə ki, yalnız vasitəsilə təkrarlamaq. Siz iki ədəd yoxlamaq. Bir əvvəl böyük olur sonra bir çox, Siz yalnız ki, onları dəyişdirmək bu yolla ali nömrələri bütün siyahısı sonuna bubble qədər və bütün aşağı nömrələri bubble aşağı. 

O sərin sizə uşaqlar göstərmək mi Video çeşidlənməsi səs effekti? Bu sərin növü var. Robert yalnız dediyi kimi, alqoritm belə yalnız siyahısını addım ki, qonşu dəyərləri dəyişdirmə onlar üçün deyil əgər. Və sonra yalnız təkrar saxlamaq qədər hər hansı svopları yoxdur. Belə ki, pis deyil, sağ? Belə ki, biz yalnız burada tez misal var. Belə ki, bu sort gedir sifariş artan onlara. Beləliklə, biz ilk vasitəsilə getmək zaman zaman, biz səkkiz baxmaq və altı açıq-aydın deyil üçün, biz onları dəyişdirmək. 

Belə ki, növbəti bir nəzər. Səkkiz və qaydada dörd deyil. Onları dəyişdirmək. Və sonra səkkiz və iki, onları dəyişdirmək. Biz orada getmək. Belə ki, ilk pass sonra, bilirik ki, ən böyük sayı bütün yol olacaq yalnız çünki üst daim olacaq başqa hər şey daha və yalnız bubble olacaq orada sonuna bütün yol qədər. Ki, hər kəs üçün əhəmiyyət kəsb edir mu? Cool. 

Beləliklə biz ikinci pass baxmaq. Six və dörd, keçid. Six və iki keçid. Və indi biz üçün bir neçə şey var. Hər pass üçün Belə ki, biz Bütün siyahısını etmək, bilirik ki, bir çox nömrələri kimi sonunda sıralanır olacaq. Beləliklə, biz bir üçüncü pass etmək, bir svop edir. Və sonra dördüncü biz sıfır yuvası var, keçir. Və belə ki, biz bilirik ki, bizim array sıralanır edilmişdir. 

Və böyük bubble sırala ilə bir şey. Biz bilirik ki, ki, sıfır svopları var ki, hər şey deməkdir tam üçün deyil. Biz yoxlamaq necə növü var. Beləliklə, biz də bubble kod gedir sort həmçinin pis deyil. Bunların heç biri ki, pis. Mən bir az qorxudan görünə bilər bilirik. Mən gəldiyində mən bilirəm sinif, hətta mən üçün dərs oldu İlk dəfə keçən il, Mən kimi, mən bu necə etməliyəm etdi? Bu nəzəriyyə əhəmiyyət kəsb edir, lakin biz, həqiqətən, bu necə etməliyəm? Mən də getmək istəyirəm nə burada uşaqlar ilə kod vasitəsilə. Mən bir pseudocode var Sizlərin bu dəfə üçün. Belə ki, kimi mind bu saxlamaq biz artıq keçid üzrəyik. Beləliklə, biz bir counter var ki, Bizim svopları tutar biz əmin etmək lazımdır, çünki biz kontrol edirik ki. Və biz bütün array təkrarlamaq biz yalnız bu misal ilə kimi. Bu element əvvəl çox olarsa, biz olduğunuz sonra element, biz onları dəyişdirmək və biz arttırmayı counter, biz dəyişdirmək kimi tezliklə çünki biz counter bildirmek istəyirəm. Hər hansı suallar? Something burada gülməli görünür. TƏLƏBƏ: sıfır counter müəyyən etməyin Siz loop vasitəsilə getmək hər zaman? Siz davam etməyin hər dəfə geri sıfır? Öğretim: Mütləq. Belə ki, nə olur, biz buradan getmək edir. Belə isə, bu xatırlayırsınız Fail olmadan bir dəfə icra edəcək. Belə ki, müəyyən olacaq sıfıra bərabər counter, sonra onun vasitəsilə təkrarlamaq olacaq. Vasitəsilə iterates kimi, Bu counter yeniləyir. Bu counter yeniləyir kimi, bunu zaman, Bu serialın sonunda əldə zaman, Bizim siyahı sıralanır deyil, əgər, counter yeniləndi olacaq. 

Belə ki, o vəziyyətini yoxlayır və OK, sıfırdan counter böyükdür deyir. Əgər, bir daha bunu. Siz zaman ki, yenidən istəyirəm keçmək, counter sıfıra bərabərdir. Bir sıralanır keçmək əgər array, heç bir dəyişikliklər Bu uğursuz, və siz sıralanır siyahısını geri. Ki, hissi verir mu? TƏLƏBƏ: bir az güc It. Öğretim: OK. Hər hansı digər varsa gəlir ki, sual. Bəli. 

TƏLƏBƏ: Nə funksiyası elementləri dəyişdirmə üçün olacaq? 

Öğretim: Belə ki, biz, həqiqətən, yaza bilərsiniz biz indi doğru olacaq ki. Cool. Ki, qeyd, belə ki, Alison gedir geri cihaz keçid. Bu fun olacaq. Və biz gözəl var burada bubble sırala şey. Mən artıq velosiped etdi array vasitəsilə. Biz svopları var ki, sıfıra bərabərdir. Beləliklə, biz qonşu dəyişdirmək istəyirəm elementləri onlar üçün həyata əgər. Belə ki, ilk şey biz lazımdır bizim array vasitəsilə təkrarlamaq olunur yoxdur. 

Belə ki, necə biz güc düşünürsünüz bizim array vasitəsilə təkrarlamaq? Biz və i 0 bərabərdir. Biz i az olmaq istəyirəm n minus 1 minus k daha. Mən ikinci izah edəcəyik. Belə ki, bu bir optimizasyon burada olduğu, Mən hər ötürməsindən sonra bildirib necə yadda Bu array vasitəsilə biz nə on-- olduğunu bilirik 

Belə ki, bir ötürməsindən sonra biz Bu çeşidlənir bilirik. Iki keçdikcə sonra biz bilirik bütün bu çeşidlənir ki. Üç ötürmədən sonra ki, çeşidlənir bilirik. Yol Mən iterating alıram burada array vasitəsilə, yalnız getmək üçün əmin edilməsi olunur biz bilirik nə ilə çeşidlənməmiş edir. OK? Bu yalnız bir optimizasyon var. Siz yalnız naively yazmaq bilər hər şey vasitəsilə iterating, yalnız uzun olacaq. Bu dörd loop ilə var bir gözəl optimallaşdırılması biz hər tam sonra bilirik, çünki burada array vasitəsilə iteration, Burada hər tam loop kimi, biz bilirik Bu elementlərin bir daha sonunda sıralanır. 

Beləliklə, biz bu barədə narahat yoxdur. Ki, hər kəs üçün əhəmiyyət kəsb edir mu? Sərin az oyun? Bu halda, əgər belə biz vasitəsilə iterating edirik biz yoxlamaq istəyirəm bilirik ki, array n və n + 1 üçün var. OK. Belə ki, burada pseudocode var. Biz yoxlamaq istəyirəm array n və n + 1 üçün var. Beləliklə, biz nə ola bilər? Bəzi şərti olacaq. Bu əgər olacaq. 

TƏLƏBƏ: array n varsa array n plus 1 az. Öğretim: Mm-hm. Yaxşı, az və ya daha çox. TƏLƏBƏ: böyükdür. Sonra biz onları dəyişdirmək istəyirik. Məhz. Belə ki, indi biz nə almaq Onlara dəyişdirmə üçün mexanizm? Beləliklə, biz bu qısa yolu ilə getdi, svop funksiyası bir növü keçən həftə. Hər kəs işləyib necə yadda varmı? Beləliklə, biz yalnız sağ, onlara redesign bilməz? Onlardan biri itirilmiş olacaq, çünki. Dedik əgər sonra B B və bərabər A bərabər, onların hər ikisi birdən B. yalnız bərabərdir 

Beləliklə, biz nə var, nə biz ki, bir müvəqqəti dəyişən var bizim müddət bir keçirəcək biz dəyişdirmə prosesi istəyirik. Belə ki, nə biz, biz bir int lazımdır edir Siz təyin edə bilərsiniz to-- temp bərabər hansı bir siz yalnız istədiyiniz Siz it-- takip əmin olun saxlamaq bu halda, mən gedirəm array n plus 1 təyin. Belə ki keçirmək niyyətində nə dəyəri ikinci blok edir biz aradığınız ki. 

Və biz getmək bilər, biz nə edə bilər irəli və REASSIGN array n plus 1, biz bilirik, çünki saxlanılır ki, dəyəri var. Bu da böyük biridir Siz əgər hər şeyə mən bilmirəm Siz iki keçid əgər tapa məsələlər idi kod xətləri birdən şeylər işləyib. Sifariş CS çox vacibdir. Belə ki, diaqram etmək şeyi əgər mümkündürsə kimi nə həqiqətən baş verir. Belə ki, indi biz gedirik , array n plus 1 redesign biz bilirik, çünki saxlanılır ki, dəyəri var. 

Və biz array ki atayabilirsiniz n və ya bu halda array i ilə. Çox çox dəyişənlər. OK. Belə ki, indi biz adına etdik array i plus 1 sıra i nə bərabər. Və indi biz geri getmək bilər və nə array i təyin? Hər kəs? 

TƏLƏBƏ: 10. 

Öğretim: 10. Məhz. Və son bir şey. Biz indi dəyişdirildikdə varsa, biz nə etmək lazımdır? Bir şey nədir ki, demək olacaq biz bu proqramı dayandırmaq əgər? Nə biz ki, bizə deyir bir sıralanır siyahısı var? Biz hər hansı svopları ifa deyil varsa, sağ? Svopları əgər bərabərdir Bu sonunda sıfır. Belə ki, zaman biz kimi, svop çıxış yalnız burada idi, biz svopları yeniləmək istəyirəm. Mən var idi bir sual əvvəllər Siz əvəzinə sıfır və ya bir istifadə və doğru və ya yalan. Və burada nə var. Belə ki, bu əgər svopları deyir. Svopları sıfır, əgər Belə ki, həmişə mən That almaq mənim həqiqətləri və falses qarışdırılır. Biz qiymətləndirmək istəyirəm doğru və bu deyil. Sıfır əgər Belə ki, o, yalan var. Bir ilə inkar əgər [? bang?] Bu doğru olur. Belə ki, bu xətt icra. 

Həqiqətlər və yalan və adet sıfır və olanları crazy almaq. Yalnız yavaş-yavaş gəzmək əgər onun vasitəsilə mənada edəcək. Amma nə bu kiçik var kodu bit burada yoxdur. Belə ki, bu görmek üçün yoxlayır Biz hər hansı svopları etdik. Belə ki, bir şey başqa əgər var sıfır, bu, yalan olacaq və bütün şey yenidən həyata olacaq. Cool? 

TƏLƏBƏ: break nə edir? 

Öğretim: yalnız Break loop sizi pozur. Bu halda ki, belə ki, yalnız proqram başa istəyirəm və yalnız ki Sizin sıralanır siyahısı var. TƏLƏBƏ: Amazing. Öğretim: Üzgünüm? TƏLƏBƏ: Çünki əvvəl sıfır yazılı üzərində 1 yazılı istifadə ki təqdim ki, iş və ya deyil. 

Öğretim: Bəli. Belə ki, sıfır və ya 1 qayıda bilər. Bu halda, çünki biz həqiqətən deyilik funksiyası ilə bir şey bunu, biz yalnız qırmaq istəyirəm. Biz, həqiqətən, bu barədə qayğı yoxdur. Brake də əgər yaxşı həyata qırılma üçün istifadə Dörd loops və şərtlər ki, Siz icra saxlamaq istəmirəm. Bu, sadəcə onlardan götürür. Bu nüans şey bir az var. Var kimi hiss edirəm əl yelləyən bir çox, kimi tezliklə bu öyrənmək lazımdır. 

Lakin tezliklə bu barədə öyrənmək lazımdır. Mən söz verirəm. OK. Yəni hər kəs bubble cür almaq deyil? Çox pis deyil. Vasitəsilə təkrarlamaq, svop şeyi istifadə temp dəyişən, və biz bütün var müəyyən edirik? Cool. Awesome. OK. Geri PowerPoint. Ümumi Hər hansı bir sualınız haqqında bu günə qədər? Cool. Mm-hm. 

TƏLƏBƏ: [Işitilemez] adətən əsas int. Bu ki, var, siz var? 

Öğretim: Beləliklə, biz yalnız aradığınız yalnız faktiki çeşidlənməsi alqoritm edir. Siz ərzində olsaydı daha böyük bir proqram kimi, Bir int əsas haradasa olardı. Harada asılı olaraq Bu alqoritm istifadə, Bu nə müəyyən olardı tərəfindən geri qaytarılır. Amma bizim halda, biz ciddi istəyirik əslində bu necə baxır bir sıra vasitəsilə təkrarlamaq. Belə ki, biz bu barədə narahat olmayın. 

Belə ki, biz ən yaxşı halda söhbət və Binar axtarış üçün ən pis ssenari. Belə ki, nə üçün də vacibdir Bizim növ hər biri üçün. Belə ki, nə düşünürsünüz pis deyil bubble sırala halda uzunluğu? Siz uşaqlar saxla? 

TƏLƏBƏ: N minus 1. Öğretim: N minus 1. Belə ki, var deməkdir n minus 1 müqayisə. Belə ki, həyata bir şey ilk iteration ki, biz müqayisə keçmək Bu two-- ki 1 var. Bu iki, üç, dörd. Belə ki, bir iteration sonra biz artıq dörd müqayisə var. Mən uzunluğu və n söhbət alıram. N müqayisə sayı təmsil neçə elementləri bir funksiyası kimi olduq. OK? 

Beləliklə, biz vasitəsilə getmək, biz dörd var. Bildiyiniz növbəti dəfə biz deyil bu qayğı var. Biz, bu iki müqayisə Bu iki, bu iki, və biz optimallaşdırılması olmasaydı yazdığı dörd loop, zaten burada müqayisə olunacaq. Belə ki, olardı array vasitəsilə run və n müqayisə etmək n dəfə, hər dəfə biz, çünki Bu sort bir şey axır. 

Və biz axır hər dəfə Bu array, biz n müqayisə etmək. Belə ki, bu bizim iş deyil həqiqətən n, kvadrat çox pis bizim çünki son daxil biz dörd idi deməkdir əgər milyard elementləri, bu Bizə dörd milyard etmək niyyətindədir əvəzinə 32 kvadrat. Belə ki, ən yaxşı iş, lakin bəzi şeylər üçün, Siz ərzində əgər siz bilirsiniz, elementləri müəyyən bir sıra bubble sırala istifadə üçün gözəl ola bilər. 

OK. Belə ki, indi ən yaxşı halda iş nədir? TƏLƏBƏ: Zero? Və ya 1? 

Öğretim: Belə ki, 1 ki bir müqayisə ola bilər. Right. 

TƏLƏBƏ: N minus 1? 

Öğretim: Belə ki, Bəli. Belə ki, n minus 1. Siz n kimi bir anlayış var zaman minus 1, biz yalnız yuxulamaq edirlər Siz çünki biz yalnız n demək these-- hər bir cüt hər müqayisə. Belə ki, 1 n olacaq minus olan biz Biz yalnız təxminən n demək ediyorum. Siz uzunluğu ilə məşğul olduğunuz zaman, hər şey bərabərdir edir. Kimi uzun eksponent kimi doğru, olduqca yaxşı deyilik. 

Biz ilə məşğul necə. Ən yaxşı halda n edir ki, belə ki, , siyahısı artıq çeşidlənir o deməkdir ki, və biz bütün vasitəsilə çalışır və sıralanır yoxlayın. Cool. Bütün hüquqlar. Burada görmək ki, biz yalnız bir neçə qrafik var. Belə ki, n kvadrat. Fun. Çox olaraq görürük n daha pis, və log 2n daha pis, çox. Və sonra da log logs daxil almaq. Və 124 almaq, siz almaq crazy kimi olan log ulduz kimi. Əgər istəyirsinizsə Belə ki, axtarış log star. Bu cür əyləncə var. Beləliklə, biz bu böyük chart var. Bir rəhbərləri up, bu gözəl chart var Çünki biz orta müddətli siz bu lesitinlər xahiş uzun. Belə ki, yalnız bir rəhbərləri up, bu var, sizin Sizin gözəl istifadə etmək hesabatı orta-müddətli var. Beləliklə, biz yalnız bubble sırala baxdı. Ən pis halda, n, n ən yaxşı halda kvadrat. Və biz digər baxmaq olacaq. 

Və yalnız bilərsiniz kimi həqiqətən də yoxdur ki, bir biz niyə nəzərə almaq lazımdır ki birləşmə sort edir. Belə ki, biz getmək olacaq Növbəti bir burada seçim sort. Hər kəs necə yadda varmı seçim sort işləyib? Bunun üçün getmək. 

TƏLƏBƏ: Əsasən keçmək Sifariş və yeni siyahısını yaratmaq. Və elementləri qoyulması etdiyiniz kimi da, doğru yerdə onlara qoymaq yeni siyahısı. 

Öğretim: Belə səsləri durub sort kimi daha çox. Amma həqiqətən yaxın deyilik. Onlar çox oxşar istəyirik. Hətta mən onlara bəzən qarışdırılır almaq. Mən kimi idi bu bölmədə əvvəl, gözləyin. OK. Belə ki, istədiyiniz nə nə, seçim sortudur Siz hesab edə bilər yolu bu və yol haqqında Mən əminəm almaq üçün cəhd etmək onlara keçir ki, qarışdırılır və seçir kiçik sayı və Sizin siyahısı əvvəlində ki qoyur. Bu ilk spot ilə svopları. Onlar, həqiqətən, mənim üçün bir nümunə var. Awesome. Belə ki, yalnız bir yol it-- seçim düşünmək sort, kiçik dəyər seçin. Və biz olacaq Məsələn axır Çünki kömək edəcək ki, Mən visuals həmişə kömək edirəm. Beləliklə, biz bir şey ilə başlamaq tamamilə çeşidlənməmiş edir. Qırmızı, çeşidlənməmiş olunacaq yaşıl sıralanır. Bu, bütün ikinci mənada edəcək. 

Beləliklə, biz vasitəsilə getmək və biz təkrarlamaq sonuna əvvəldən. Və biz OK, 2, demək Bizim kiçik sayı. Beləliklə, biz 2 almaq olacaq və biz olacaq bizim serialın qarşısında hərəkət Bu, çünki kiçik sayı, biz var. Belə ki, burada nə var. Bu, sadəcə bu iki dəyişdirmək olacaq. Belə ki, indi biz bir sıralaması hissəsi və çeşidlənməmiş hissəsi. Və yadda yaxşı nə var Seleksiya sort haqqında biz yalnız seçilməsi edirik çeşidlənməmiş hissəsi. 

Sıralanır hissəsi yalnız tək buraxın. Mm-hm? 

TƏLƏBƏ: nə bilmək necə müqayisə olmadan kiçik array hər digər dəyər. Öğretim: Bu müqayisə edir. Biz bunu atlandı kimi. Bu ümumi yalnız ümumi edir. Bəli. Biz Mən kodu yazarkən Siz daha məmnun olacaq. Amma siz ilk bu saxlamaq kiçik kimi element. Siz müqayisə və siz OK, bu kiçik, demək? Bəli. Onu saxlamaq. Burada kiçik? No? 

Bu, kiçik deyil Sizin dəyəri redesign. Və çox xoşbəxt olacaq Biz kod vasitəsilə getmək zaman. Beləliklə, biz vasitəsilə getmək, biz sonra onu dəyişdirmək biz bu çeşidlənməmiş hissəsi baxmaq. Beləliklə, biz üç out seçin olacaq. Biz onu qoymaq olacaq sıralanır hissəsinin sonu. Və biz yalnız bunu saxlamaq olacaq bunu, və bunu ki,. Belə ki, burada pseudocode bizim növüdür. Biz ikinci burada bu qədər kod lazımdır. Lakin yalnız bir şey gəzmək yüksək səviyyədə vasitəsilə. Siz getmək olacaq i n minus 2 0 bərabərdir. Ki, bir optimallaşdırma var. Bu barədə çox narahat etməyin. Beləliklə, siz deyirdilər. Yaqub deyirdi ki, necə ki, biz bizim minimum nə takip? Necə bilirik? Biz müqayisə etmək bizim siyahıda hər şey. 

Belə ki, minimum i bərabərdir. Yalnız bu halda deyən oldu Bizim minimum dəyər index. Belə ki, o vasitəsilə təkrarlamaq olacaq j i plus 1 bərabərdir və gedir. Beləliklə, biz artıq bilirik ki, ki, bizim ilk element var. Biz özü müqayisə etmək lazım deyil. Belə ki, biz növbəti müqayisə başlamaq i plus 1 n niyə bir olan minus 1, olan orada serialın sonu. Və biz array əgər bildirib j, array min azdır sonra biz harada redesign bizim minimum göstəricilərindəndir. 

Və min kimi, i bərabər deyil burada biz burada artıq geri idi. Biz ilk bu nə zaman, belə ki, istəyirəm. Bu halda, bu başlamaq olardı sıfır, bu iki olan son bilər. Belə ki, min sonunda i bərabər deyil. Bizə bilirik ki, imkan verir biz onları dəyişdirmək lazımdır. Mən konkret misal kimi hiss Bu daha çox kömək edəcək. Mən sizə uşaqlar bu qədər kod lazımdır İndi mən daha yaxşı olacaq edirəm. 

Sorts ki, yol işləmək üçün edirlər yalnız onları görmək üçün tez-tez daha yaxşıdır. Beləliklə, biz nə etmək istəyirəm nə biz ilk kiçik istəyirəm serialda öz mövqeyini element. Məhz Yaqub deyirdi nə. Siz elə saxlamaq lazımdır. Beləliklə, biz burada başlamaq olacaq serialın üzərində iterating. Biz demək olacaq bizim yalnız başlamaq üçün ilk biridir. Beləliklə, biz int üçün gedir kiçik I array bərabərdir. 

Belə bir şey, hər xəbər bu loop həyata zaman, biz birlikdə bir addım daha başlayır. Biz başlamaq zaman biz bu biri baxmaq. Biz vasitəsilə təkrarlamaq Növbəti dəfə, bu bir başlanğıc edirik və bu, bizim kiçik dəyər təyin. Belə ki, bubble sırala çox oxşar Biz harada bir keçid sonra, Bu son element çeşidlənir. Seçim növ ilə, yalnız qarşı deyil. 

Hər pass, biz bilirik ki, ilk çeşidlənir. Ikinci ötürməsindən sonra, bu ikinci sıralanır. Və siz slide nümunələri ilə gördüm kimi, bizim sıralanır hissəsi yalnız artan saxlayır. Belə ki, bizim kiçik bir yaradılması serialların i, bütün bunu constricting nə Biz belə baxırıq sayı minimuma endirmək üçün müqayisələrin biz. Ki, hər kəs üçün mənada edirmi? Siz vasitəsilə run lazımdır, daha yavaş və ya müxtəlif sözləri? Mən xoşbəxtəm. OK. 

Beləliklə, biz saxlanılması edirik bu nöqtədə dəyəri, lakin biz də indeksi saxlamaq istəyirəm. Belə ki, biz saxlamaq olacaq kiçik mövqeyi yalnız i olacaq bir. Belə ki, indi Jacob məmnun. Biz saxlanılır şeylər var. İndi biz vasitəsilə baxmaq lazımdır serialın çeşidlənməmiş hissəsi. Bu halda bu, belə bizim çeşidlənməmiş olardı. Bu i. OK. 

Belə ki, nə biz nə olacaq bir loop üçün olacaq. Sizə lazım zaman bir sıra vasitəsilə təkrarlamaq, Fikrinizi bir loop üçün getmək bilər. Bəzi int k üçün belə biz nə düşünürsünüz bərabərdir k ilə başlamaq üçün bərabər gedir? Bu, bizim kiçik kimi müəyyən nə dəyəri və biz bunu müqayisə etmək istəyirəm. Biz onu müqayisə etmək istəyirsiniz? Bu doğru, bu növbəti bir olacaq? Beləliklə, biz başlatılmış k istəyirəm i plus 1 başlamaq üçün. 

Və biz bu halda k istəyirəm ki, biz Artıq ölçüsü burada saxlanılır, belə ki, biz yalnız ölçüsü istifadə edə bilərsiniz. Size serialın ölçüsü olan. Və biz yalnız istəyirik bir hər zaman k yeniləmə. Cool. Belə ki, indi biz tapmaq lazımdır Burada kiçik element. Beləliklə, biz vasitəsilə təkrarlamaq, biz demək istəyirəm ki, əgər k array Bizim kiçik dəyər azdır Biz, həqiqətən, olduğunuz bu nə takip saxlanılması kiçik burada sonra biz redesign istəyirəm bizim kiçik dəyər nə. 

Bu oh, biz istəyirik, o deməkdir ki, Burada vasitəsilə iterating. Nə dəyəri burada deyil bizim kiçik şey. Biz bunu istəmirik. Biz redesign istəyirik. Biz bunu reassigning istəyirsinizsə Belə ki, nə Siz burada bu kodu ola bilər mi? Biz redesign istəyirəm kiçik və mövqeyi. Belə ki, indi kiçik nədir? TƏLƏBƏ: Array k. Öğretim: Array k. Və mövqeyi indi nə edir? Göstəriciləri nədir Bizim kiçik dəyər? Bu, sadəcə k edir. Array k, k, onlar uyğun. Belə ki, redesign istəyirdi. Və biz kiçik tapıldı sonra loop üçün bu sonunda belə burada biz gördük nə bizim kiçik dəyəri nə, belə ki, biz yalnız dəyişdirmək. Bu halda, kimi demək kiçik dəyəri burada deyil. Bu, bizim kiçik dəyəri nə. 

Biz yalnız olan, burada dəyişdirmək istəyirəm nə altındakı svop funksiyası biz yalnız yazdığı etdi birlikdə bir neçə dəqiqə əvvəl. Belə ki, tanış baxmaq lazımdır. Və sonra yalnız təkrarlamaq edəcək vasitəsilə bütün yol çatana qədər Siz o deməkdir ki, sonuna çeşidlənməmiş ki, sıfır elementləri var və başqa hər şey sıralanır edilmişdir. Mənada etmək? Daha konkret Bir az? Kod yardım? 

TƏLƏBƏ: bir ölçüsü üçün, heç vaxt həqiqətən müəyyən və ya dəyişdirmək, necə bilir? 

Öğretim: Belə ki, bir şey int ölçüsü burada qeyd. Beləliklə, biz bu sort-- cür deyərək edirik bu bir funksiyası var iki halda seçim sort, bu keçdi funksiyası ilə. Bu qəbul edilmişdir, əgər Belə ki, , siz bir şey olardı serialın uzunluğu ilə kimi və ya vasitəsilə təkrarlamaq olardı uzunluğu tapmaq üçün. Amma bu keçdi, çünki , biz yalnız istifadə edə bilərsiniz. Siz yalnız istifadəçi güman bir etibarlı ölçüsü verdi həqiqətən təmsil array ölçüsü. Cool? 

Sizlərin bu ilə hər hansı bir problem varsa, və ya daha çox təcrübə kodlaşdırma növ istəyirəm Öz, siz olmalıdır study.cs50 gedin. Bu aracıdır. Onlar checker var ki, Siz həqiqətən yaza bilərsiniz. Onlar pseudocode yoxdur. Onlar daha çox video və slaydlar Mən burada istifadə, o cümlədən. Siz hələ bir hiss edirsinizsə Belə ki, az qeyri-səlis ki, cəhd edin. Həmişə olduğu kimi, o, mənim üçün danışmaq gəlir. Sual? 

TƏLƏBƏ: Siz deyərək ölçüsü əvvəl müəyyən olunur? Öğretim: Bəli. Size əvvəllər müəyyən edilir burada funksiyası bəyannamə. Belə ki, qəbul edilmişdir ki, güman istifadəçi tərəfindən, və sadəlik xatirinə, biz güman olacaq istifadəçi bizə doğru ölçüsü verdi. Cool. Belə ki, seçim sort var. Uşaqlar, bu gün bir çox öyrənmək bilirik. Bu bölüm üçün sıx data var. Belə ki, gedirik durub növ getmək üçün. 

OK. Belə ki, əvvəl biz nə etmək lazımdır burada uzunluğu təhlili. , Ən yaxşı halda belə Mən sizə göstərdi verilən masa artıq mən cür üz verdi. Amma yaxşı halda uzunluğu, biz nə düşünürsünüz? Hər şey sıralanır. N kvadrat. Hər kəs bir izahat var Sizcə niyə? 

TƏLƏBƏ: Siz through-- müqayisə edirik Öğretim: Sağ. Siz vasitəsilə müqayisə edirik. Hər iteration, hətta baxmayaraq biz bir bu decrementing edirik Əgər hələ də aradığınız hər şey kiçik bir tapa bilərsiniz. Belə ki, hətta ən kiçik dəyər , başında burada Siz hələ müqayisə edirik başqa hər şey qarşı Bu kiçik şey əmin üçün. Belə ki, keçən çıxacağıq təxminən n dəfə kvadrat. Bütün hüquqlar. Və ən pis halda nə var? Siz olacaq, çünki Həmçinin n kvadrat Eyni proseduru edirik. Bu halda, seçimi belə sort bir şey var biz də nə gözlənilir, uzunluğu zəng. Belə ki, başqaları, biz yalnız bilirik yuxarı və aşağı həddi. Necə crazy asılı olaraq bizim siyahısı və ya necə çeşidlənməmiş bu, Onlar n və ya n kvadrat arasında dəyişir. Biz bilmirik. 

Amma seçim sort eyni çünki pis və ən yaxşı halda, ki, bizə deyir giriş nə olursa olsun cür tamamilə olsun, var sıralanır və ya tamamilə bu, sıralanır geri eyni miqdarda almaq niyyətindədir. Bu halda belə, əgər Bizim masa xatırlayıram, Bu, həqiqətən bir dəyəri var idi ki, Bu iki növ, yoxdur olan gözlənilir iş deyil. Beləliklə, biz bilirik zaman ki, biz seçim sort run, Bu təmin edir bir kvadrat n vaxt axır. Heç bir dəyişkənlik yoxdur. Bu, sadəcə gözlənilir. Və yenə, siz öyrənmək istəyirsinizsə daha Bahar CS 124 almaq. Bütün hüquqlar. Biz bu bir gördüm. Cool. Belə ki, durub sırala. Və yəqin ki, gedirəm Bu vasitəsilə etmek üçün. Mən sizə uşaqlar kod olmayacaq. Biz yalnız onun vasitəsilə gəzmək lazımdır. Belə ki, durub sırala növüdür Seçim Sıralama oxşar ki, biz də bir çeşidlənməmiş var və serialın hissəsi sıralanır. 

Amma nə müxtəlif ki biz bir ilə getmək kimi, biz yalnız nə sıra almaq bizim çeşidlənməmiş növbəti edir və düzgün sort Bizim sıralanır array. Bir misal daha mənada etmək lazımdır. Belə ki, hər şey çeşidlənməmiş kimi başlayır, yalnız seçim sort ilə kimi. Və biz bu sort olacaq biz olduğu kimi sifariş artan. Ilk pass belə biz ilk dəyəri almaq və biz OK, siz demək İndi özünüz bir siyahısı. 

Bir siyahısı Çünki Özünüz, siz sıralanır. Bu olmaq üçün təbrik Bu array ilk element. Siz artıq öz sıralanır edirik. Belə ki, indi biz bir sıralaması və çeşidlənməmiş array. Belə ki, indi biz ilk almaq. Burada arasında olur və burada, biz demək ki, OK, biz baxmaq olacaq bizim çeşidlənməmiş serialın ilk dəyəri və biz girişi üçün olacaq onun sıralanır array düzgün yer. 

Beləliklə, biz 5 almaq biz nə və biz 5, 3-dən böyük, OK, demək belə ki, biz yalnız sağ daxil ki, sağ üçün. Biz yaxşı edirik. Beləliklə biz növbəti bir getmək. Və biz 2 almaq. Biz OK, 2 az, demək 3-dən, belə ki, biz bilirik ki, var Bu da olmalıdır İndi bizim siyahısı ön. Belə ki, nə biz, biz aşağı 3 və 5 təkan edir və biz ilk yuvasına 2 hərəkət. Beləliklə, biz yalnız onu daxil edirik Bu olmalıdır düzgün yer. 

Sonra baxmaq bizim Növbəti bir, biz 6 deyirlər. OK, 6 daha böyükdür Bizim sıralanır array hər şey, belə ki, biz yalnız sonunda onu tag. Və sonra biz 4 baxmaq. 4 6 azdır, az deyil 5-dən lakin 3-dən çox var. Beləliklə, biz yalnız sağ daxil edin 3 və 5 arasında orta. Belə ki, bir az etmək üçün daha konkret bit, burada növ nə fikir. Hər çeşidlənməmiş element üçün, biz burada sıralanır hissəsi müəyyən edir. 

Belə ki, mind saxlamaq çeşidlənir və çeşidlənməmiş, biz vasitəsilə və rəqəm axır var Bu sıralanır array uyğun olduğu. Və biz dəyişkən ilə daxil onun sağ aşağı elementləri. Və sonra biz yalnız saxlamaq biz qədər vasitəsilə iterating tamamilə sıralanır siyahısı var İndi sıfır olduğu çeşidlənməmiş edir və sorted tutur bizim siyahısı bütövlükdə. Belə ki, daha belə şeylər etmək daha konkret, biz pseudocode var. 

Belə ki, əsasən i üçün n minus 1 0 bərabər, ki, serialın yalnız uzunluğu var. Biz bərabər bir element var ilk array və ya ilk göstəriciləri. Biz bərabər j seçin. J daha çox isə belə sıfır və array, j minus 1 Bu daha böyükdür element, bütün bunu edir əmin edir Sizin j həqiqətən təmsil serialın çeşidlənməmiş hissəsi. 

Hələ şeyi var isə belə sort və j minus bir nə That üçün Bu element onun var? J burada müəyyən heç vaxt. Bu annoying növü var. OK. Zaten. Belə ki, j minus 1, kontrol edirik Əvvəl element. Siz OK, element, deyərək edirik Mən imkan am-- yerdə əvvəl həqiqətən bu cəlb edir. Belə ki, bu deyək ikinci pass kimi. Belə ki, i bərabər olacaq 1, burada edir. 

Belə ki, i 1-bərabər olacaq. Bu, 2, 4, 5, 6, 7 olacaq. Bütün hüquqlar. Bu halda belə bizim element 4 bərabər olacaq. Və biz ki, bəzi j var 1 bərabər olacaq. Oh, j decrementing olunur. Ki, nə var. Belə ki, j i bərabərdir, belə ki, bu nə deyərək, biz irəli hərəkət kimi ki, biz yalnız əmin edirik biz artıq deyilik ki, biz çalışdığınız zaman bu şəkildə indeksasiyası bizim sıralanır siyahısına şeyi daxil etmək üçün. 

Belə ki, j, bu halda 1-bərabər olduqda və belə array j minus 1 one-- array j minus ki, əgər Bu halda 2 element daha çox, sonra bütün bu edir şeyi aşağı sürüşür. Bu halda, array j minus bir So 2 olan array sıfır olacaq. 2, 4-dən böyük deyil bu icra etmir. Belə ki, shift aşağı hərəkət etmir. Nə burada nə yalnız aşağı sıralanır array hərəkət. Bu halda, faktiki olaraq, biz do-- bilər bu 3 edək. Beləliklə, biz vasitəsilə gəzmək əgər Bu misal, biz burada indi istəyirik. Bu çeşidlənir. Bu çeşidlənməmiş edir. Cool? Belə ki, i ki, 2 bərabərdir Bizim element 3 bərabərdir. Və j 2 bərabərdir. Belə ki, biz və baxmaq OK, array j minus biridir, demək element daha çox biz aradığınız ki? Və cavab doğru yes? 4 3 və j daha böyükdür 2, bu kodu icra. 

Belə ki, indi biz bir sıra nə 2, burada, biz onları dəyişdirmək. Beləliklə, biz yalnız OK, array, demək 2 indi 3 olacaq. Və j bərabər gedir 1 olan j minus 1. Ki, dəhşətli, lakin Sizlərin fikir almaq. J indi 1 bərabərdir. Və array j yalnız olacaq 4 olan element, bərabər. Mən bir şey silinə I verməməli və ya miswrote bir şey, ancaq uşaqlar fikir almaq. 

Bu n da hərəkət. Bu idi sonra əgər, bu loop ki daha və OK, j indi 1, demək olardı. Və array j minus 1 indi 2. 2 bizim element azdır? No? Yəni biz o deməkdir ki, Bu element daxil Bizim sıralanır array düzgün spot. Sonra biz bu edə bilərsiniz və biz demək, OK, sıralanır array burada. Və bu sayı 6 və olacaq kimi, OK, bu sayı 6 az? No? Cool. Biz yaxşıyıq. 

Daha bunu. Biz 7 deyirlər. Sonda 7-dən az sıralanır array? No. Beləliklə, biz yaxşıyıq. Belə ki, bu sıralanır olardı. Əsasən bütün bu yoxdur Bu Anlık deyərək olunur ilk element Sizin çeşidlənməmiş array, gedir harada anlamaq Sizin sıralanır array. Və bu, yalnız qayğı svopları bunu. Siz əsasən yalnız dəyişdirmə edirik qədər sağ spot var. Vizual image sen ki, bunu hər şeyi aşağı hərəkət. 

Belə ki, yarım bubble kimi sort-esque var. Iş 50 oldu. Mən çalışıram gəlir öz Bu kod. Hər hansı məsələlər və ya etmək istəyirsinizsə bir durub sırala üçün nümunə kodu görmək, xahiş edirik Mənə bildirin. Mən ətrafında həmişə edirəm. Belə ki, ən pis halda iş və ən yaxşı halda iş. Siz oğlan Mən artıq masa gördüm Bu kvadrat və n edir, həm də n, göstərdi. 

Belə ki cür danışdıq nə off gedir bizim əvvəlki növləri ilə haqqında pis halda iş deyil ki, əgər tamamilə çeşidlənməmiş, bu n dəfə bütün müqayisə etmək lazımdır. Biz müqayisə bir çox Bu sırayla əgər çünki, Biz OK, bu demək olacaq , bu yaxşıdır, eyni və bu müqayisə olacaq birinci qarşı geri daşınacaq. Və biz doğru almaq kimi quyruq sonunda, biz , müqayisə, və hər şeyə qarşı müqayisə. 

Belə ki, olan qədər başa təxminən n kvadrat. O zaman doğru varsa Siz yaxşı istəyirik, 2, OK, deyirlər. 3, 2 ilə müqayisədə edirik. Siz yaxşı istəyirik. 4, yalnız quyruq müqayisə. Siz yaxşı istəyirik. 6, gözəl istəyirik, quyruq müqayisə. Belə ki, hər spot üçün artıq var, əgər sıralanır, bir müqayisə edirik. Belə ki, yalnız n var. Və biz yaxşı halda uzunluğu var, çünki n və n pis halda uzunluğu kvadrat, biz heç nə gözlənilir, uzunluğu var. 

Bu, yalnız asılıdır var siyahısı xaos. Və yenə başqa graph və digər masa. Növ arasında fərqlər belə. Mən yalnız vasitəsilə breeze gedirəm, mən Biz geniş söhbət etdiyiniz kimi hiss nə onlar bütün növ haqqında fərqlənə və birlikdə keçid. Belə ki, sort son biridir birləşmə Mən sizə uşaqlar doğdu edilir. Biz olduqca rəngarəng şəkil var. Belə ki, sort bir recursive alqoritmi daxil. Belə ki, uşaqlar bilirik nə bir recursive funksiyası? 

Hər kəs demək istəyirəm? Siz cəhd etmək istəyirsiniz? Belə ki, bir recursive funksiyası yalnız özü çağırır ki, bir funksiyası. Belə ki, uşaqlar tanış olduqda Fibonacci ardıcıllığı ilə, çünki recursive hesab edir Siz əvvəlki iki almaq və onlara birlikdə əlavə növbəti bir almaq üçün. Belə ki recursive, Mən həmişə fikirləşirəm bir spiral kimi recursion belə ki, onu aşağı spiral kimi istəyirik. Amma bu yalnız bir funksiyası var ki, özü çağırır. 

Və, həqiqətən, həqiqətən, tez mən ki, kimi görünür nə göstərmək olar. Biz baxmaq əgər burada belə recursive, bu Bu recursive yol bir sıra üzərində yekunlaşdırmaq üçün. Belə ki, bütün biz ki, biz məbləğ funksiyası var bir ölçüsü və bir sıra edir ki məbləği. Və qeyd əgər, ölçüsü bir hər zaman decrements. Və bunu bütün x bərabərdir əgər sıfır əgər belə serialın ölçüsü sıfır qaytarır sıfır bərabərdir. 

Əks halda bu yekunlaşdırır Serialın son element, və sonra bir məbləğ edir serialın qalan. Belə ki, yalnız aşağı qırılma kiçik və daha kiçik problemlər daxil. Uzun hekayə qısa, recursion, özü çağırır ki, fəaliyyət göstərir. Ki, bu həyata var, bütün əgər, ki, bir recursive funksiyası nə var. Siz 51 alsaq, çox olacaq, Recursion ilə çox rahat. Bu, həqiqətən sərin var. Bu kimi at mənada etdi 3-AM bir gecə. Və mən, nə kimi idi Mən bu istifadə heç vaxt? 

Əsasən, birləşmə sort Belə ki, nə etmək olur ki, var edir qırmaq və onu qırmaq niyyətində Bu yalnız bir elementləri qədər aşağı. Vahid elementləri düzmək üçün asandır. Biz görürük. Bir element varsa, bu artıq sıralaması hesab. N elementləri daxil, belə ki, n az 2 olduqda, yalnız deməkdir, çünki qayıtmaq biz gördük kimi 0 və ya 1 ya var. Həmin sorted elementlər hesab edilir. 

Əks halda yarım onu ​​qıra. Ikinci sort, ilk yarım sort yarım, sonra onları birlikdə birləşməsi. Niyə birləşmə sort deyirlər. Bu düzmək lazımdır, belə ki, biz burada var. Beləliklə, biz onlara olan saxlamaq Bu array ölçüsü 1 qədər. Bu, 1 zaman, biz yalnız qayıtmaq bu bir sorted array, çünki, və bu sorted array edir ki, var sıralanır array, biz bütün sıralanır edirik. Beləliklə biz nə biz Onlara birlikdə birləşmə başlayın. 

Belə ki, yol bilərsiniz birləşmə haqqında düşünmək Yalnız kiçik aradan qaldırılması alt serialların hər sayı və yalnız ortaya array üçün əlavə. Belə ki, əgər biz zaman, burada baxmaq bu dəsti 4, 6 və 1 var. Biz bu daxil etmək istədiyiniz zaman, biz bu ilk iki baxmaq və biz 1 kiçik, OK, demək, ön gedir. 4 və 6, müqayisə etmək heç bir şey yoxdur Bu, yalnız sonunda onu tag üçün. 

Biz bu iki birləşdirmək zaman, biz yalnız , bu iki kiçik birini belə ki, 1 var. İndi biz almaq bu iki, belə ki, 2 kiçik. Bu iki, 3 kiçik. Bu iki, 4, 5, 6 kiçik. Belə ki, yalnız bu off çekme edirik. Onlar var, çünki əvvəllər sıralanır, Yalnız bir var müqayisə var hər zaman. Burada daha çox kodu, yalnız nümayəndəliyi. Belə ki, orta başlamaq və Siz sort sol və sağ və sonra yalnız daxil. 

Və biz kodu yoxdur üçün burada daxil. Amma, yenə də, siz getmək əgər 50 təhsil, orada olacaq. Əks halda mənə danışmaq gəlmək Siz əgər yenə qarış. Belə ki, burada sərin şey ki, yaxşı haldır, ən pis halda, gözlənilən iş , n bütün daxil olan biz daha yaxşıdır Bizim növ istirahət üçün görülür. Biz gördük n kvadrat etdik və həqiqətən nə biz böyük olan, n log n burada almaq. 

Ki, nə qədər yaxşı baxın. Belə bir gözəl curve. Belə ki, daha səmərəli. Əgər edə bilmirsinizsə, istifadə birləşmə sort. Bu zaman qənaət edəcək. Sonra yenə biz dediyi kimi, əgər Siz bu aşağı bölgədə aşağı edirik ki, etmir qədər fərq. Siz minlərlə almaq və giriş minlərlə, siz mütləq bir istəyirəm daha səmərəli alqoritm. Bütün Və yenə bizim sevimli masa Siz uşaqlar bu gün öyrəndim ki növ. 

Mən bir sıx gün oldu bilirik. Bu mütləq niyyətində deyil Sizin pset ilə sizə kömək edir. Amma yalnız bir disclaimer etmək istəyirəm ki, bölmədə yalnız psets deyil. Bütün bu material ədalətli Sizin midterms üçün oyun. Və CS ilə davam edə də əgər, Bu həqiqətən əhəmiyyətli əsasları var ki, bilmək lazımdır. Belə ki, bir neçə gün olacaq az daha pset yardım, lakin bəzi həftə olacaq daha çox faktiki content super görünə bilər indi sizin üçün faydalı, Davam əgər mən söz verirəm çox, çox faydalı olacaq. 

Belə ki bölüm üçün var. Tel Down. Mən bir dəqiqə ərzində bunu. Amma siz gedin. Mən donuts və ya konfet olacaq. Allergik hər kəs edir yolu ilə bir şey? Yumurta və süd. Belə ki, donuts heç bir var? OK. Bütün hüquqlar. Chocolate heç? Starburst. Starbursts yaxşı. OK. Biz olacaq Sonra növbəti həftə Starburst. Mən almaq lazımdır nə. Siz uşaqlar böyük bir həftə var. Spec oxuyun. 

Əgər hər hansı bir sualınız varsa, Mənə bildirin. Pset iki notları olmalıdır Cümə axşamı tərəfindən həyata. Hər hansı bir sualınız varsa, Mən bir şey pilləli haqqında və ya niyə yol bir şey pilləli , mənə eməktub göndərin idi, mənə danışmaq gəlir. Mən bir az dəli, bu deyiləm həftə, amma söz verirəm Mən hələ 24 saat ərzində cavab verəcəyik. Belə ki, böyük bir həftə, hər kəs. Sizin pset Uğurlar.