SPEAKER 1: Hei semua orang! Selamat kembali ke bahagian. Sangat senang melihat begitu ramai di antara anda berdua di sini, dan semua orang yang menonton online. Jadi, seperti biasa selamat datang kembali. Saya harap anda semua telah tinggal yang indah hujung minggu, penuh dengan rehat, istirahat. Itu indah daripada kemarin. Jadi, saya berharap anda menikmati alam bebas. Jadi pertama beberapa pengumuman. Penilaian. Jadi, kebanyakan kamu harus mendapatkan satu email dari saya tentang Serangga Scratch anda, dan juga kadar untuk Serangga 1. Jadi, hanya beberapa perkara. Pastikan anda menggunakan check50 di style50. Ini dimaksudkan untuk menjadi sumber untuk kalian, memastikan bahawa anda mendapat sebagai mata sebanyak yang anda boleh sia-sia tanpa kehilangan mereka. Jadi, hal-hal seperti gaya sangat penting. Kita akan mengambil kira untuk itu. Sebahagian daripada anda mungkin sudah melihat bahawa dari Serangga anda. Dan check50 hanyalah cara yang sangat mudah untuk memastikan bahawa kita benar-benar kembali apa perlu dikembalikan kepada pengguna, dan semua yang bekerja dengan baik. Dalam perkembangan yang kedua, pastikan anda memuat naik perkara ke folder yang betul. Ia menjadikan hidup saya hanya sedikit lebih sukar jika anda memuat naik Serangga Serangga 2 ke 1 kerana apabila saya memuat turun perkara-perkara, mereka tidak turun dengan betul. Dan saya tahu itu miring sedikit dalam satu sistem untuk membiasakan diri, tetapi hanya menjadi super berhati-hati, jika hanya untuk saya, supaya apabila anda mendapat e-mel di seperti 2:00 dan saya grading. Jika tidak menyebabkan saya perlu melihat di sekitar untuk Serangga anda. Sejuk. Aku tahu itu lebih awal, tetapi saya sama sekali tak lengah oleh satu esei itu karena Jumaat ini, yang profesor saya hanya suka, oh yeah. Ingat, anda mempunyai esei kerana pada hari Jumaat. Jadi, saya tahu tidak ada orang suka untuk berfikir tentang ujian tengah semester, tetapi kuiz pertama anda adalah pada 15 Oktober, Oktober ini yang bermula minggu ini. Jadi, ia mungkin lebih cepat dari yang Anda harapkan adalah semua. Supaya anda tidak dibuang dalam keadaan tidak bersedia apabila Saya menyebut seksyen minggu depan yang oh, kuiz minggu depan anda, saya fikir Saya akan memberikan anda sedikit lebih dari kepala sekarang. Jadi, masalah anda ditetapkan, nombor tiga. Bagaimana orang telah membaca spec daripada rasa ingin tahu? OK. Kami mendapat pasangan. Jenis turun dari lepas minggu tetapi tidak apa-apa. Saya tahu itu keluar indah. Jadi Break. Sudah pasti selepas anda mendapatkan dilakukan hari ini membaca spec anda sekurang-kurangnya cuba seperti memuat turun kod pengedaran dan berjalan seperti permulaan pertama hal yang mereka meminta anda. Oleh kerana kita menggunakan kod pengedaran dan perpustakaan bahawa kita hanya telah using-- --Ini hanya kali kedua kami telah melakukan Serangga ini, perkara gila boleh berlaku dengan alat anda, dan anda ingin mencari yang keluar sekarang berbanding nanti. Kerana jika itu malam Khamis atau itu Rabu malam dan untuk sebab-sebab tertentu alat anda hanya tidak ingin menjalankan dengan perpustakaan atau dengan taburan kod, yang cara Anda tidak boleh mula melakukan coding. Kerana anda tidak boleh menyemak untuk melihat jika ia berfungsi. Anda tidak akan dapat untuk melihat jika ia menyusun. Anda mahu untuk menjaga mereka di awal minggu itu, ketika anda masih boleh e-mel saya atau salah satu daripada TF yang lain, dan kita boleh mendapatkan orang-orang yang tetap. Kerana mereka adalah isu-isu yang akan menghalang anda daripada membuat apa-apa kemajuan yang nyata. Ini tidak seperti satu bug, yang Anda boleh hanya jenis melewatkan. Jika anda menghadapi masalah dengan anda perkakas atau kod pengedaran, Anda benar-benar mahu untuk mendapatkan yang diambil mengurus lebih awal daripada kemudian. Jadi, walaupun anda tidak benar-benar gonna mulai coding, muat turun pengedaran kod, baca spec, memastikan segala-galanya yang bekerja di sana. OK? Jika anda hanya boleh melakukan itu, saya menjanjikan kehidupan anda akan menjadi lebih mudah. Dan supaya anda mungkin akan untuk melakukannya dengan betul sekarang kan? OK. Jadi, mana-mana soalan di sana? Hal-hal logistik? Semua orang yang baik? OK. Penafian bagi Anda di dalam bilik dan dalam talian. Saya akan cuba untuk menukar antara PowerPoint pada alat kerana kita akan cuba membuat beberapa coding hari ini oleh permintaan popular daripada tanpa nama cadangan jajak pendapat saya dihantar minggu lepas. Jadi, kita akan melakukan beberapa coding. Jadi, jika anda lelaki juga mahu untuk menjalankan peralatan anda, dan anda harus sudah mendapat e-mel dari saya, dengan contoh file. Sila berasa bebas untuk berbuat demikian. Jadi, kita akan bercakap tentang GDB, yang debugger. Ia akan membantu anda jenis memikirkan di mana hal-hal yang tidak baik di dalam kod anda. Ia benar-benar hanya satu cara bagi Anda untuk melangkah melalui kod anda kerana ia berlaku, dan mampu untuk mencetak pembolehubah atau melihat apa yang sebenarnya berlaku di bawah tenda ayat program anda hanya berjalan, ia seperti faulting, dan anda seperti, tidak tahu apa yang baru saja terjadi di sini. Saya tidak tahu apa yang talian itu gagal. Saya tidak tahu di mana ia pergi salah. Jadi, GDB akan membantu anda dengan itu. Juga, jika anda membuat keputusan untuk terus ya, dan mengambil 61, ia akan benar-benar, benar-benar menjadi anda kawan baik, sebab saya boleh memberitahu anda kerana saya akan melalui kelas itu. Kita akan melihat binari carian, yang jika kalian ingat contoh buku telefon besar cermin mata dalam kelas. Kami akan melaksanakan itu, dan berjalan melalui yang lebih sedikit, dan kemudian kita akan melalui empat macam yang berbeda, yang gelembung, Pemilihan, Pemasukan, dan Gabung. Sejuk. Jadi, GDB seperti yang saya sebutkan, adalah debugger. Dan ini adalah jenis yang besar perkara, fungsi besar atau perintah yang anda gunakan dalam GDB, dan saya akan berjalan Anda melalui demo dalam satu saat. Jadi, ini bukan sahaja akan tinggal abstrak. Saya akan cuba dan menjadikannya sebagai konkrit mungkin bagi kalian. Jadi, istirahat. Ia sama ada akan istirahat seperti ini, cukup banyak, yang merupakan garis dalam program anda, atau anda boleh nama fungsi. Jadi, jika anda mengatakan memecahkan utama, ia akan berhenti di utama, dan membiarkan anda berjalan melalui fungsi itu. Demikian juga, jika anda mempunyai beberapa luaran berfungsi seperti Tukar atau Cube, yang kita melihat pada minggu lepas. Jika anda mengatakan memecahkan salah satu dari mereka, setiap kali program anda sebagai rumah anda itu, ia akan menunggu untuk anda beritahu apa yang perlu dilakukan. Sebelum itu hanya akan melaksanakan sehingga Anda sebenarnya boleh melangkah di dalam fungsi dan melihat apa yang sedang berlaku. Jadi, Seterusnya, hanya melompat ke atas baris berikutnya, berjalan di atas fungsi. Langkah. Ini semua adalah abstrak sedikit. Jadi, aku hanya akan berjalan melalui mereka, tetapi anda akan melihat mereka digunakan dalam satu saat. Melangkah ke fungsi. Jadi seperti yang saya katakan, seperti dengan Swap, ia akan membolehkan anda untuk benar-benar seolah-olah anda seperti fizikal melangkah di dalam, anda boleh main-main dengan variabel, mencetak tahu apa yang mereka, lihat apa yang berlaku. Senarai akan benar-benar hanya mencetak daripada kod di sekitarnya. Jadi, jika anda jenis lupa mana anda berada dalam program anda, atau anda tertanya-tanya apa yang berlaku di sekitarnya, ini hanya akan mencetak segmen dari seperti lima atau enam baris di sekitarnya. Jadi, anda boleh mendapatkan berorientasi kira-kira di mana anda berada. Mencetak beberapa pembolehubah. Jadi, jika anda mempunyai kunci seperti di Caesar, yang kita akan melihat. Anda boleh mengatakan Cetak utama pada bila-bila. Ia akan memberitahu anda apa nilai yang begitu itu, mungkin di suatu tempat di sepanjang jalan, Anda menimpa kunci anda. Anda benar-benar boleh mengatakan bahawa kerana Anda benar-benar boleh melihat nilai tersebut. Dalam penduduk tempatan, hanya cetakan daripada pembolehubah tempatan anda. Jadi, bila-bila masa anda dalam satu lingkaran, dan anda hanya ingin melihat seperti, oh. Apa yang saya saya? Apa nilai utama ini yang saya memulakan di sini? Apa pesan itu pada ketika ini? Ini hanya akan mencetak semua dari mereka, supaya anda tidak perlu secara individu berkata, Cetak I. Cetak mesej. Cetak Utama. Dan kemudian Paparkan. Apa yang dilakukan adalah kerana anda langkah melalui program ini, ia hanya akan memastikan bahawa itu menampilkan beberapa variabel tertentu pada setiap titik. Supaya anda also-- --Ini Ini jenis pintasan di mana anda tidak perlu terus berjalan seperti, oh. Cetak Kunci atau Cetak I. Ia hanya secara automatik akan melakukannya untuk anda. Jadi, dengan itu, kita akan untuk melihat bagaimana ini pergi. Saya akan cuba dan beralih kepada alat saya. Lihat jika saya boleh melakukan hal ini. Semua. Kami hanya akan cermin itu. Tidak ada yang gila di laptop saya anyways. OK. Ini perlu menjadi satu ini. Ia amat kecil. Mari kita lihat apakah yang boleh kita lakukan ini. OK. Alice jelas berjuang di sini hanya sedikit, tetapi kita akan mendapatkannya dalam momento. OK. Kami hanya akan meningkat ini. OK. Bolehkah semua orang jenis lihat itu? Mungkin sedikit? Aku tahu itu agak kecil. Anda tidak boleh agak memikirkan bagaimana untuk membuat ini lebih besar. Jika ada yang tahu. Adakah sesiapa yang tahu bagaimana untuk membuat ia lebih besar? OK. Kami akan melancarkan dengan itu. Tidak kira anyways kerana ia hanya itulah kod yang kalian harus mempunyai. Apa yang lebih penting adalah terminal itu di sini. Dan kami ada di sini Mengapa begitu kecil? Tetapan. Oh. Ike benar. Bagaimana ini? Keluar dari sana. Apakah yang lebih baik untuk semua orang? OK ,. Sejuk. Anda tahu apabila anda berada dalam CS masalah teknikal kelas adalah jenis sebahagian daripada the-- Jadi, mari kita jelas ini. OK. Jadi, di sini, di bahagian, yang kami di sini. Caesar adalah fail boleh laku. Jadi saya membuat ia. Jadi, satu perkara untuk merealisasikan dengan GDB adalah yang hanya bekerja pada fail boleh laku. Jadi, anda tidak boleh menjalankannya pada dotsy a. Anda perlu benar-benar membuat memastikan bahawa kod anda mengkompilasi, dan bahawa ia sebenarnya boleh dijalankan. Jadi, pastikan bahawa jika ia tidak menyusun, dapatkan ia untuk mengkompilasi, supaya anda jenis boleh berjalan melaluinya. Jadi, untuk memulakan GDB, semua yang anda lakukan, Gloria jenis GDB, dan kemudian hanya fail yang anda mahu. Saya selalu salah mengeja Caesar. Tetapi anda ingin memastikan karena itu laksana, titik kilat ti supaya bermakna anda akan untuk menjalankan CSI anda akan melaksanakan file ini sama ada dengan debugger. OK. Jadi, anda melakukan itu, anda akan mendapat seperti ini omong kosong. Ia hanya kira-kira tiap-tiap sesuatu penyahpepijat. Anda tidak benar-benar perlu bimbang tentang hal itu sekarang. Dan seperti yang anda lihat, kita mempunyai ini parens terbuka, KDNK, parens dekat, dan hanya jenis kelihatan seperti baris arahan kita, kan? Jadi, apa yang kita mahu do-- --So, Perkara pertama yang adalah kita ingin memilih tempat untuk memecahkannya. Jadi, ada satu bug dalam program ini Caesar bahawa saya memperkenalkan, yang kita akan mencari tahu. Ini Apa yang dilakukannya adalah ia mengambil input Barfoo dalam semua topi, dan untuk sebab-sebab tertentu itu tidak mengubah A. Ia hanya meninggalkan itu sahaja, Apakah segala sesuatu yang lain yang benar, tetapi huruf kedua A tetap tidak berubah. Jadi, kita akan cuba memikirkan mengapa itu. Jadi, perkara pertama yang anda biasanya ingin melakukan setiap kali anda mula pada GDB adalah mencari tahu di mana untuk memecahkannya. Jadi Caesar adalah program yang cukup singkat. Kami hanya mempunyai satu fungsi, kan? Apakah fungsi kita di Caesar? Hanya ada satu fungsi, hak utama? Utama adalah fungsi untuk semua program anda. Jika anda tidak mempunyai Utama, saya mungkin menjadi sedikit bimbang sekarang, tetapi saya berharap anda semua memiliki Utama di sana. Jadi, apa yang kita boleh lakukan ialah kita boleh hanya memecahkan Utama, begitu saja. Jadi, ia mengatakan, OK. Kami menetapkan satu titik pecah yang kami ada. Jadi, hal yang perlu diingat adalah Caesar mengambil satu perintah argumen baris kanan dan kami tidak melakukan hal itu di mana-mana lagi. Jadi, apa yang anda lakukan adalah apabila Anda benar-benar pergi untuk menjalankan program ini, apa-apa program yang anda berjalan dalam GDB yang perlu baris perintah hujah, anda akan input saat pertama kali menjalankannya. Jadi, dalam hal ini, kami Main dengan kunci tiga. Dan ia benar-benar akan bermula. Jadi, jika anda lihat di sini, kami mempunyai Jika RC tidak sama dengan 2. Oleh itu, jika kalian semua mempunyai fail yang saya dihantar sehingga Anda akan melihat bahawa itu seperti yang baris pertama fungsi utama kita, kan? Ia memeriksa untuk melihat jika kita mempunyai nombor yang betul bagi hujah. Jadi, jika anda bertanya-tanya jika RC adalah benar, Anda dapat melakukan sesuatu seperti Cetak RC. RC adalah dua, iaitu apa yang kita harapkan, bukan? Jadi, kita boleh pergi depan, dan terus melalui. Jadi, kita mempunyai beberapa kunci di sana. Dan kita boleh mencetak utama kami memastikan itu benar. Menarik. Tidak cukup apa yang kita harapkan. Jadi, satu perkara untuk merealisasikan dengan GDB juga, adalah bahawa ia bukan sehingga anda benar-benar memukul Selanjutnya, bahawa garis yang anda hanya melihat benar-benar dijalankan. Jadi, dalam hal ini Key belum ditetapkan lagi. Jadi, kunci adalah beberapa nilai sampah yang anda lihat di bawah sana. Negatif $ 120-- --Ini ini satu bilion dan perkara-perkara yang aneh bukan? Ia bukan yang utama yang kita harapkan. Tetapi jika kita tekan Next, dan kemudian kita mencuba dan kunci Cetak, itu tiga. Semua orang melihat itu? Jadi, jika anda mendapat sesuatu bahawa anda seperti, tunggu. Ini benar-benar salah, dan aku tidak tahu bagaimana ini akan berlaku kerana semua yang saya mahu lakukan adalah memberikan nombor telefon, variabel, cuba memukul Seterusnya, cuba percetakan lagi, dan melihat apakah yang bekerja. Kerana ia hanya akan melaksanakan dan sebenarnya menetapkan sesuatu selepas anda tekan Next. Masuk akal untuk semua orang? Eh eh? SPEAKER 2: Apabila anda rawak nombor apa artinya? SPEAKER 1: Ia hanya secara rawak. Ia hanya sampah. Ia hanya sesuatu yang anda komputer secara rawak akan menetapkan. Sejuk. Jadi, kita boleh bergerak melalui, dan sebagainya sekarang kita mempunyai GetString teks biasa. Jadi, saya hanya memperkenalkan apa akan berlaku apabila kita tekan Next sini. GDB kami semacam hilang, kan? Ini kerana GetString kini melaksanakan, bukan? Jadi, ketika kita melihat teks biasa sama GetString, parens terbuka dan parens, dan kita memukul Seterusnya, yang mempunyai sebenarnya dilaksanakan sekarang. Jadi, ia menunggu kita untuk memasukkan sesuatu. Jadi, kita akan input makanan kami yang apa itu gagal seperti yang saya katakan dan hanya mengatakan bahawa itu selesai melaksanakan, yang ditutup braket berarti itu keluar daripada gelung itu. Jadi, kita boleh tekan Next, dan sekarang, yang saya pasti anda semua biasa dari Caesar, ini adalah, apa baris ini akan lakukan. Ini untuk Int saya sama dengan 0, N sama Strlen, teks biasa, dan kemudian Saya kurang daripada n, saya, ditambah, ditambah. Apa yang gelung ini akan lakukan? Buka mesej anda. Sejuk. Jadi, mari kita mulai melakukan hal itu. Jadi, sekiranya keadaan ini sesuai, untuk yang pertama kita? Jika ia merupakan satu B, itu teks biasa I. Kami boleh mendapatkan maklumat mengenai penduduk tempatan kami. Jadi, saya adalah sifar, dan jika enam, yang kita harapkan, dan utama kami adalah tiga. Semua yang masuk akal, bukan? Nombor-nombor tersebut adalah semua apa yang mereka perlu. Jadi, bersenandung? SPEAKER 3: Saya nombor rawak untuk saya. SPEAKER 1: Baik, kami boleh check-- --Kami boleh berbual tentang itu dalam satu saat. Tetapi anda harus mendapatkan ini. Jadi, jika kita mempunyai modal yang B untuk yang pertama kami, keadaan ini harus menangkapnya, bukan? Jadi, jika kita memukul Seterusnya, kita lihat bahawa Jika ini benar-benar dijalankan. Kerana jika anda sedang mengikuti bersama-sama dalam kod anda, talian ini di sini, di mana teks biasa saya diganti dengan aritmetik ini, hanya dijalankan jika Jika keadaan yang tepat betul? GDB hanya akan menunjukkan kepada anda perkara-perkara yang benar-benar melaksanakan. Oleh itu, jika keadaan Jika ini tidak dipenuhi, itu hanya akan melangkau ke baris seterusnya. OK? Jadi, kita harus itu. Kurungan Ini bermakna ia menutup gelung itu sekarang. Jadi, ia akan bermula sekali lagi. Begitu sahaja. Jadi, kita boleh mendapatkan maklumat kira-kira penduduk tempatan kita di sini, dan kita melihat bahawa kita yang pertama surat telah berubah, kan? Sekarang E, seperti yang diharapkan. Jadi, kita boleh meneruskan. Dan kami mempunyai cek ini. Dan pemeriksaan ini harus bekerja, bukan? Ini A. Ia perlu ditukar tiga surat ke hadapan. Tetapi jika anda perhatikan, kita mendapatkan sesuatu yang berbeza. Jadi dalam hal ini di sini, ia tertangkap itu, dan sebagainya baris ini dilaksanakan, yang diubahsuai B. kami Tetapi, dalam hal ini di sini, yang kita ada bahawa ia hanya melewatkan itu, dan pergi ke [yang? L SIFF. ?] Jadi sesuatu yang terjadi di sana. Apa yang memberitahu anda adalah bahawa, kita tahu bahawa ia harus menangkap sini, tetapi ia bukan. Sesiapa sahaja boleh melihat apa yang kami masalah ini sejalan itu? Ia satu perkara yang sangat minit. Dan anda juga boleh melihat kod anda. Ia juga line-- lupa apa garis itu di besar-- tetapi ia dalam [terdengar]. Ya? SPEAKER 4: Ada di yang lebih besar dari Halaman jika anda membacanya dalam buku ini. SPEAKER 1: Tepat sekali. Jadi, debugger tidak tahu anda itu, tetapi debugger boleh membawa anda ke garis Anda tahu tidak berfungsi. Dan kadang-kadang, apabila terutama kemudian pada semester, apabila Anda sedang berhadapan dengan seratus, ratus beberapa baris kod, dan anda tidak tahu di mana ia gagal, ini merupakan cara terbaik untuk melakukannya. Jadi, kami menemukan bug. Anda boleh memperbaikinya dalam fail anda, dan kemudian anda boleh berjalan lagi, dan semuanya akan bekerja dengan sempurna. Dan yang paling besar adalah ini boleh kelihatan seperti, OK. Yeah. Sejuk. Anda tahu apa yang anda cari. Jadi, anda tahu apa yang perlu dilakukan. GDB dapat super berguna kerana anda boleh mencetak semua hal yang anda tidak. Ini jauh lebih berguna daripada printf. Berapa ramai daripada anda menggunakan seperti pernyataan printf untuk memikirkan di mana bug itu, bukan? Jadi, dengan ini, anda tidak melakukan perlu terus kembali, dan suka mengulas di Printf, atau mengulas keluar, dan mencari tahu apa Anda perlu mencetak. Ini sebenarnya hanya membolehkan anda langkah melalui, mencetak perkara seperti yang anda akan melalui, jadi, anda boleh bagaimana mereka berubah dalam masa sebenar, sebagai program anda berjalan. Dan ia mengambil sedikit sedikit untuk membiasakan diri. Saya sangat akan mengesyorkan hanya jenis menjadi sedikit kecewa dengan itu untuk sekarang. Jika anda menghabiskan satu jam selama minggu depan belajar bagaimana menggunakan GDB, Anda akan menyelamatkan diri begitu banyak masa di kemudian hari. Dan benar-benar. kami adalah orang- ini kepada orang-orang setiap tahun, dan saya ingat ketika saya mengambil kelas, aku seperti, saya akan baik-baik. Tidak. Serangga 6 datang dan saya seperti, aku akan belajar bagaimana menggunakan GDB kerana saya tidak tahu apa yang sedang berlaku di sini. Jadi, jika anda mengambil masa yang begitu menggunakannya pada program yang lebih kecil bahawa anda akan menjadi kerjakan, seperti bekerja melalui sesuatu seperti Visionare, seperti ini. Atau jika anda mahu amalan tambahan, saya yakin Saya boleh datang dengan program kereta, untuk anda untuk debug jika anda suka. Tetapi jika anda hanya mengambil sedikit masa untuk mendapatkan digunakan untuk itu, hanya bermain-main dengan itu, ia benar-benar akan melayani anda dengan baik. Dan ia benar-benar salah satu daripada perkara-perkara yang anda hanya perlu mencuba dan mendapatkan tangan anda kotor dengan, sebelum anda benar-benar memahaminya. Saya benar-benar hanya difahami sekali Saya terpaksa perkara debug dengan itu, dan ia adalah jauh lebih baik untuk mempunyai idea tentang cara debug lebih awal daripada kemudian. OK. Sejuk. Aku tahu itu jenis seperti kursus kilat dalam GDB, dan saya pasti akan bekerja pada mendapatkan ini untuk melihat waktu yang lebih besar akan datang. Sejuk. Jadi, jika kita kembali ke PowerPoint kami. Adakah ini akan berfungsi? Awh. Ya. OK. Jadi, jika anda memerlukan apa-apa dari mereka lagi, ada senarai. Search sehingga Perduaan, yang semua orang ingat cermin mata besar Daud merobek buku telefon pada separuh. Saya tidak benar-benar mendapatkan buku telefon lagi, kerana seperti mana yang anda mendapatkan buku-buku telefon hari ini? Saya benar-benar tidak tahu. Search Binary. Apakah ada yang ingat bagaimana Binary Search kerja-kerja? Siapa pun? Ya? SPEAKER 5: Anda tahu bila Anda melihat yang setengah ia akan berada dalam, Berdasarkan itu, dan menyingkirkan separuh yang lain. SPEAKER 1 Tepat. Jadi, Cari Perduaan, itu agak a-- --Kami suka menyebutnya membahagi dan menakluk. Jadi, apa yang anda akan lakukan adalah Anda akan melihat di tengah-tengah, dan anda akan melihat apakah itu sesuai apa yang anda cari. Dan jika tidak, maka anda cuba untuk memikirkan, apakah akan dibiarkan setengah atau separuh benar. Jadi, mungkin ini jika anda sedang mencari sesuatu yang menurut abjad, Anda lihat, oh. Adakah Allison datang sebelum M? Ya. Jadi, kita akan melihat separuh masa pertama. Atau ia boleh menjadi seperti dengan nombor. Apa sahaja yang anda boleh membandingkan, ia boleh disusun. Anda boleh menggunakan carian dedua pada. Jadi, ada yang ingat ini grafik atau apa ini? Ini Kerumitan asimptot. Jadi, grafik ini hanya menerangkan berapa lama membawa anda untuk menyelesaikan masalah kerana anda meningkatkan jumlah perkara yang anda gunakan. Jadi, kita mempunyai N, yang merupakan masa linear. Jika N lebih dari dua, yang sedikit yang lebih baik, masih tumbuh super cepat. Dan kemudian kami Masuk, yang apa yang kita anggap Cari Perduaan. Kalau kita lihat, sebagai masalah anda mendapat banyak dan lebih besar, masa yang diperlukan anda untuk menyelesaikannya tidak benar-benar meningkat banyak. Ia seperti yang setanding di sini pada mulanya. Kau seperti, OK. Apa-apa sahaja di sini tidak benar-benar penting yang mana yang kita gunakan, tetapi anda keluar untuk satu juta, bilion. Anda sedang cuba untuk mencari --you're some-- cuba mencari jarum di tumpukan jerami. Saya fikir anda mahu masalah ini. Anda mahu kerumitan ini, tidak linear kerana untuk semua anda tahu akan anda mencari melalui jarum individu, sesuatu dari rumput kering, cuba mencari jarum anda. Dan itu bukan yang turut pada pendapat saya. Saya suka cepat. Saya suka cekap. Dan pelajar sebagai pekerja keras anda Orang-orang ini, anda tahu bekerja lebih cerdas, bukan lebih keras hal jenis, bagaimana anda dapat membuat algoritma ini. Jadi, kita akan berjalan melalui hanya contoh cepat. Saya rasa anda semua perlu mempunyai tangan pencarian Binary, tetapi dalam kasus orang adalah sedikit kabur, ingin agar lebih kuat, kita akan hanya pergi melalui contoh di sini. Jadi, kita cari jika array mengandungi tujuh. Jadi, perkara pertama yang kita lakukan adalah melihat di tengah-tengah, kan? Dan juga anda akan coding Cari Perduaan hanya dalam satu saat. Jadi, ia akan menjadi seronok. Jadi kita lihat dalam array sedikit pertengahan 3. Adakah 3 sama dengan 7? Tidak. Ini enam. Jadi, adalah kurang daripada atau lebih daripada tujuh? Kurang daripada. Ya. Nice job guys. Saya rasa saya seperti saya harus mempunyai gula-gula kerana saya ingin membuangnya ke dalam meter. Ia adalah apa yang saya akan lakukan minggu depan. Ini akan membuat kalian tajam. Jadi, kita buang jauh-jauh babak pertama, kan? itu kurang dari. kita tahu segala-galanya yang pada yang sebelah kiri akan menjadi kurang daripada apa yang kita benar-benar cari. Jadi, tidak ada keperluan untuk memberi perhatian kepadanya. Lupakan saja. Jadi, kita melihat di sebelah kanan kami, dan kita melihat pertengahan di sana, dan sekarang ini sembilan. Jadi, 9 is-- --Everyone? Lebih besar daripada apa yang kita cari, kan? Jadi, kita akan membuang segala sesuatu ke kanan. Seperti itu. Sekarang, semua kami pergi dengan adalah satu. Oleh itu, kita semak, adakah ini satu apa yang kami cari? ia adalah. Kami mendapati apa yang kita inginkan. Oleh itu, kita sudah selesai. Bilinear Cari. Dan jika anda perhatikan, kita mempunyai tujuh input di sana. Ia hanya membawa kami seperti tiga kali, tetapi jika anda lakukan seperti bilion, kalian tahu berapa banyak langkah-langkah yang akan mengambil jika kita mempunyai empat bilion-tiap sesuatu? Mana-mana tekaan? Ini 32. 32 langkah-langkah untuk mencari sesuatu dalam empat bilion elemen array kerana kuasa dua. Jadi kedua-duanya adalah 32, adalah untuk empat bilion. Bagaimana begitu cantik gila anda masih berada dalam seperti jumlah yang cukup kecil langkah-langkah untuk mencari sesuatu di empat bilion elemen. Maka pada masa yang sama, kami akan kode ini jadi kalian benar-benar dapat jenis melihat bagaimana ini bekerja. Baiklah, jadi kalian dapat kode. Saya akan membiarkan kalian bercakap untuk sedikit. Mengenal orang-orang di sekeliling anda, yang apa yang orang inginkan dari bagian terakhir. Jadi untuk mengenal orang-orang di sekeliling anda. Bercakap untuk sedikit. Dan semua yang saya inginkan dari anda orang sekarang hanya cuba untuk membuat garis besar pseudokod. OK? Tunggu dulu. Apa yang saya mahu dari anda semua adalah anda hanya akan mengisi dalam kes semasa ini. Jadi saya telah menetapkan atas ini dan batas bawah yang mewakili permulaan dan akhir array kita. Dan anda akan benar-benar loop melalui dan memikirkan apa yang kita lakukan dalam loop selama ini. Jadi jika anda boleh mencari out-- saya mempunyai Petunjuk besar-- apakah kes-kes yang kita ada di sini? Jadi, jika anda ingin mengetahui kes, kami akan pseudokod mereka dan kemudian kita akan benar-benar memberi kod kepada mereka. Dan ia akan menjadi, saya berfikir, mudah-mudahan ia bakal menjadi sedikit lebih mudah daripada yang anda harapkan. Oleh kerana ia tidak bahawa kod banyak, sebenarnya, yang benar-benar sejuk. Mm-hm? PELAJAR: [didengar]? PENGAJAR: Ya. Ada sesuatu untuk mencari di tengah-tengah. PELAJAR: Jadi kita boleh menggunakannya. OK. PENGAJAR: Perfect. Jadi itulah perkara pertama yang perlu kita lakukan. Jadi mencari tengah-tengah. Besar. Jadi adakah anda mempunyai idea tentang bagaimana kita mungkin benar-benar menemukan tengah dengan kod? PELAJAR: Ya. n lebih dari 2? PENGAJAR: Jadi n lebih dari 2. Jadi, satu hal yang perlu diingat adalah bahawa batas atas dan bawah Anda. Kami terus mengecutkan bahagian array kami sedang mencari untuk. Jadi n lebih dari 2 hanya akan bekerja untuk perkara pertama yang kami lakukan. Jadi mengambil atas dan bawah kira, bagaimana mungkin kita mendapatkan bahwa unsur menengah? Kerana kita mahu tengah antara atas dan bawah, kan? Mm-hm? PELAJAR: [didengar]. PENGAJAR: Oleh itu, kita mempunyai beberapa menengah. Dan ia akan menjadi lebih rendah atas ditambah lebih dari 2. Awesome. Di sana kami pergi. Satu baris ke bawah. Kalian dalam perjalanan anda. Jadi sekarang kita mempunyai kita pertengahan, apa yang kita mahu lakukan? Hanya pada umumnya. Anda tidak perlu memberi kod itu. Ya. PELAJAR: [didengar]? PENGAJAR: Jadi itu ditambah kerana anda mencari purata antara kedua-dua daripada mereka. Jadi, jika anda menganggap mereka sebagai jenis peningkatan dalam dari sisi, berfikir tentang hal itu sebagai pendekatan tengah-tengah, anda mahu seperti itu. Jadi, jika anda berada di kedua sisi menengah, dan kami mempunyai seperti 5 dan 7. Apabila anda menambah mereka bersama-sama anda mendapatkan 12, anda membahagi dengan 2, adalah 6. Kadang-kadang ia sukar untuk menjelaskan mengapa yang bekerja, tetapi jika anda bekerja dengan contoh kadang-kadang, ia akan membantu anda memahami jika ia perlu tambah atau tolak. Ya. PELAJAR: [didengar] betul-betul di tengah-tengah jika mereka mempunyai kes di mana ada banyak dari jumlah yang lebih kecil dan seperti satu jumlah yang besar? PENGAJAR: Jadi semua yang anda perlukan adalah tengah array. Jadi, jika anda telah mempunyai banyak bilangan yang kecil dan kemudian satu nombor benar-benar besar pada akhirnya, ia tidak mengapa. Apa yang penting ialah bahawa mereka disusun, anda hanya ingin melihat pertengahan array kerana anda masih mengiris masalah anda pada separuh. Sejuk. Jadi sekarang kita mempunyai pertengahan, apa yang kita lakukan seterusnya? PELAJAR: Bandingkan. PENGAJAR: The membandingkan. Jadi membandingkan tengah untuk value_wanted. Sejuk. Jadi anda lihat di sini kita mempunyai nilai ini kita mahu di sini. Ingat ini adalah array. Jadi tengah merujuk kepada indeks. Oleh itu, kita ingin melakukan nilai-nilai tengah. Jangan lupa jika anda mahu untuk membandingkan, sama dengan dua kali ganda. Anda boleh melakukan satu sama anda hanya akan menetapkan kembali, dan kemudian, tentu saja, itu akan menjadi nilai yang anda mahu. Jadi, jangan lakukan itu. Jadi kita akan melihat apakah nilai-nilai yang di tengah-tengah adalah sama dengan nilai yang kami mahu. Jangan lupa kawat gigi anda. Dropbox harus pergi. Jadi apa yang kita lakukan dalam hal ini? Jika ia adalah apa yang kita mahu untuk kembali? Kami katakan. PELAJAR: Cetak off. PENGAJAR: Kami tidak mahu mencetak. Jadi, ini adalah bool di sini, jadi kami mahu kembali benar atau salah. Kami katakan, adalah nombor ini sebuah [? RRA? ?] Oleh itu, jika ia adalah, kita hanya mengembalikannya benar. Jika saya boleh mengeja benar. PELAJAR: Mengapa tidak anda kembali sifar? PENGAJAR: Jadi, anda boleh kembali sifar jika anda mahu. Tetapi dalam kes ini kerana fungsi kita kembali bool, kita perlu kembali sama ada benar atau salah. PELAJAR: Apabila anda mengatakan ungkapan boolean, anda boleh menetapkan ia sama dengan salah? Seperti jika saya ingin mengatakan, jika keadaan ini tidak dipenuhi, seperti atas adalah sama dengan yang salah. Adakah ia akan memahami jika anda hanya menempatkan palsu di sebelah yang lain? PENGAJAR: Ya. Jadi sebenarnya jika anda pernah melakukan sesuatu seperti adalah atas atau lebih rendah, yang mengembalikan benar atau salah dan itu gaya sebenarnya buruk untuk katakan sama sama benar atau sama dengan sama dengan yang salah. Anda ingin menggunakan hasil itu sebagai dirinya sebagai cek. Tidak apa yang saya mahu. Itu yang saya mahu. Jadi, dalam kes anda bertanya tentang sesuatu seperti menyimpan ini dalam c. Jadi, jika kita mempunyai int main (void) dan sesuatu seperti ini. Dan jika anda mempunyai adalah atas input beberapa dan anda menanyakan apakah yang boleh anda lakukan sesuatu seperti ini? Betul? PELAJAR: Saya cuba untuk melakukannya [terdengar]. Kerana jika it's-- PENGAJAR: Benar. Jadi, anda mahu ini adalah palsu, bukan? PELAJAR: Ya. PENGAJAR: Jadi dalam hal ini anda mahu ia untuk melaksanakan jika ia tidak benar. Jadi perkara yang sejuk yang anda lakukan ada ini. Jadi ingat seru titik meniadakan tiap sesuatu? Dikatakan [terdengar] tidak bermakna. Oleh itu, jika kita melihat hanya bahagian ini di sini, Anda lebih mengatakan bahawa untuk menilai palsu seperti yang anda mahu ia. Tidak palsu benar yang bermakna ini akan melaksanakan. Adakah ini masuk akal? PELAJAR: Ya. PENGAJAR: Awesome. OK. Jadi kita hanya boleh kembali benar dalam kes ini. Jadi sekarang kita mempunyai dua lain kes dalam kes ini. Apakah dua kes kami yang lain? Mari kita melakukannya dengan cara ini. Jadi mari kita mulakan dengan yang lain jika nilai-nilai di tengah-tengah adalah kurang daripada nilai yang kami mahu. Jadi nilai kita di tengah-tengah adalah kurang daripada nilai yang kami cari. Jadi yang terikat yang anda fikir kita mahu update? Atas atau bawah? Atas? Jadi pihak mana array kita akan melihat? PELAJAR: yang lebih rendah. PENGAJAR: Kami akan kita untuk melihat sebelah kiri. Jadi lain jika kita terlalu kurang. Jadi nilai tengah anda di sini adalah kurang daripada apa yang kita inginkan. Oleh itu, kita ingin mengambil kanan array kita. Oleh itu, kita akan mengemaskini batas bawah kami. Jadi kita akan menyerahhakkan semula yang lebih rendah kami. Dan apa yang anda berfikir yang lebih rendah seharusnya? PELAJAR: Nilai menengah? PENGAJAR: Jadi value-- tengah PELAJAR: Plus 1. PENGAJAR: --plus 1. Bolehkah sesiapa beritahu saya mengapa kita ada yang ditambah 1? PELAJAR: [? Tidak ada nilai?] lebih sama dengan itu. PENGAJAR: Benar. Kerana kita sudah tahu bahawa nilai menengah kita tidak sama dengan dan kami mahu ia tidak termasuk daripada semua carian berikutnya. Jika anda terlupa bahawa campur 1, ini akan seperti gelung tanpa batas. Dan anda hanya akan terperangkap dalam gelung tak terhingga dan kemudian anda akan segfault dan sesuatu yang buruk. Jadi selalu memastikan bahawa anda tidak termasuk nilai yang anda hanya memandang. Oleh itu, kita berhati-hati itu dengan ditambah 1. Jadi sekarang kita mempunyai keadaan terakhir kami yang saya selalu demi keamanan anda boleh menyemak di sini, lain jika nilai-pada tengah adalah lebih besar daripada nilai yang kita mahu. Ini bermakna bahawa kita mahu separuh kiri. Jadi mana yang kita akan mengemas kini? Atas. Dan apa yang satu ini akan sama? Tengah tolak 1 kerana, sudah tentu, kita mahu memastikan bahawa kita tidak melihat bahawa nilai pertengahan lagi. Dan kemudian kita ada. Itu saja. Itu sahaja carian binari adalah. Ia bukan yang buruk, benar? Ia seperti 10 baris kod dengan ruang putih. Jadi sangat kuat, sangat berguna, anda akan akan menggunakannya di salah satu pşet anda kemudian. Mungkin tidak yang satu ini, tetapi kemudian. Jadi mempelajarinya. Sukakannya. Ini akan melayan anda dengan baik. Jadi tidak ada yang punya soalan pada carian binari? Ya. PELAJAR: Apa itu penting sama ada anda adalah n genap atau ganjil? PENGAJAR: No. Kerana kita membuangnya ke tengah seperti int, ia hanya akan memotong ia. Jadi ia akan kekal integer dan akan akhirnya menyusun melalui semua. Jadi anda tidak perlu bimbang tentang itu. Semua orang yang baik? Awesome. Sejuk. Jadi, kalian mendapat ini. Tayangan slaid. Jadi seperti yang kita bercakap tentang, saya tahu Daud disebutkan runtimes kerumitan. Jadi dalam kes ini, ia hanya satu, yang kita panggil masa yang sama. Bolehkah sesiapa beritahu saya mengapa yang mungkin? Apakah jenis senario akan yang memerlukan? Mm-hm. PELAJAR: [didengar] first-- PENGAJAR: Jadi tengah yang yang Elemen pertama ini dapat kita, kan? Jadi baik pelbagai satu atau apa sahaja yang kami cari hanya kebetulan memukul dab di tengah-tengah. Jadi itu yang terjadi terbaik. Anda masuk ke dalam masalah sebenar, mungkin tidak akan mencapai [terdengar] yang sering. Bagaimana pula dengan kes kami yang paling teruk? Kes kami terburuk adalah log n. Dan yang ada hubungannya dengan keseluruhan kuasa dua perkara yang saya bercakap tentang. Jadi dalam hal yang paling teruk ia bermakna bahawa kami terpaksa memotong pelbagai ke bawah sehingga unsur satu. Jadi kami terpaksa memotong ke bawah pada separuh sebanyak yang mungkin kami bisa. Itulah mengapa ia log n kerana Anda hanya terus membahagikan dengan dua. Jadi andaian, perkara yang anda perlu tahu jika anda pernah akan menggunakan carian dedua. Unsur-unsur anda harus diurutkan. Mereka perlu disusun kerana itulah satu-satunya cara yang anda boleh tahu jika anda mampu untuk membuang setengah dari itu. Jika anda mempunyai beg bercampur aduk ini nombor dan kau mengatakan, OK, saya akan memeriksa tengah jumlah dan bilangan yang saya cari adalah kurang dari itu, aku hanya akan untuk sewenang-wenangnya membuang satu setengah. Anda tidak akan tahu jika anda nombor pada separuh yang lain. Senarai anda harus diurutkan. Selain itu, ini mungkin pergi ke depan sedikit, tetapi anda perlu mempunyai akses rawak. Anda perlu dapat langsung pergi ke elemen menengah. Jika anda mempunyai untuk melintasi melalui sesuatu atau ia akan membawa anda langkah-langkah tambahan untuk sampai ke elemen tengah, ia tidak log n lagi kerana anda menambah lebih banyak kerja ke dalamnya. Dan ini akan membuat sedikit arti yang lebih dalam dua minggu, tetapi saya hanya jenis mahu pengantar, memberikan kalian idea tentang apa yang yang akan datang. Tetapi mereka adalah dua andaian penting yang anda perlukan untuk daftar binari. Pastikan itu disusun. Itu salah satu yang besar untuk kalian sekarang. Dan pada yang kita dapat masuk ke sisa macam kami. Jadi empat gelembung sorts--, penyisipan, pemilihan, dan gabungan. Mereka semua jenis sejuk. Jika kalian membuat keputusan untuk mengambil CS 124, Anda akan belajar tentang pelbagai macam. Dan jika anda seorang penggemar XKCD, ada adalah tentang komik yang menyeronokkan! seperti macam benar-benar berkesan, yang saya sangat menyarankan anda akan melihat. Salah seorang daripada mereka adalah seperti semacam panik, yang adalah seperti, oh tidak, kembali pelbagai rawak. Sistem shutdown. Tinggalkan. Jadi humor culun selalu baik. Jadi tidak ada yang ingat jenis seperti hanya idea umum bagaimana semacam gelembung berfungsi. Anda masih ingat? PELAJAR: Ya. PENGAJAR: Pergi untuk itu. PELAJAR: Jadi, anda akan melalui dan jika ia lebih besar, maka anda menukar dua. PENGAJAR: Mm-hm. Tepat. Jadi anda hanya beralih melalui. Anda memeriksa dua nombor. Jika yang sebelumnya lebih besar daripada yang selepas itu, Anda hanya menukar mereka supaya dalam cara ini semua nombor yang lebih tinggi meluap menjelang akhir senarai dan semua jumlah yang lebih rendah gelembung bawah. Adakah dia menunjukkan kalian sejuk kesan bunyi menyortir video? Ia adalah jenis sejuk. Supaya Robert hanya berkata, algoritma bahawa anda hanya langkah melalui senarai, menukar nilai-nilai yang berdekatan jika mereka tidak teratur. Dan kemudian hanya terus mengulangi sehingga anda tidak membuat sebarang pertukaran. Jadi tidak buruk, kan? Oleh itu, kita hanya mempunyai satu contoh yang cepat di sini. Jadi ini akan menyusun mereka dalam urutan menaik. Oleh itu, apabila kita pergi melalui pertama masa, kita melihat melalui lapan dan enam yang jelas tidak dalam rangka, kita menukar mereka. Jadi melihat satu depan. Lapan dan empat tidak teratur. Swap mereka. Dan kemudian lapan dan dua, swap mereka. Di sana kami pergi. Jadi setelah pertama anda, anda tahu bahawa jumlah terbesar anda akan menjadi sepanjang jalan di bahagian atas kerana ia hanya akan terus-menerus lebih besar daripada segala sesuatu yang lain dan ia hanya akan gelembung sehingga sampai ke akhir di sana. Adakah ini masuk akal untuk semua orang? Sejuk. Jadi kita melihat pas kedua kami. Enam dan empat, suis. Enam dan dua, suis. Dan sekarang kita mempunyai beberapa perkara dalam rangka. Jadi untuk setiap pas yang kita membuat melalui semua senarai kami, kita tahu bahawa seperti yang banyak nombor pada akhirnya akan sudah diselesaikan. Jadi kita lulus ketiga, yang merupakan salah satu swap. Dan kemudian pada keempat kami lulus, kita mempunyai sifar slot. Dan dengan itu kita tahu bahawa kita array sudah disusun. Dan itu adalah besar perkara dengan semacam gelembung. Kita tahu bahawa apabila kita mempunyai swap sifar, yang bermakna segala sesuatu yang adalah dalam rangka lengkap. Ini semacam bagaimana kita memeriksa. Oleh itu, kita juga akan memberi kod gelembung semacam yang juga tidak terlalu buruk. Tiada seorang pun daripada ini adalah yang buruk. Saya tahu bahawa mereka boleh kelihatan sedikit menakutkan. Saya tahu apabila saya mengambil kelas, walaupun saya mengajar kelas untuk kali pertama tahun lalu, Aku seperti, bagaimana saya boleh melakukan ini? Ia masuk akal dalam teori, tetapi bagaimana kita benar-benar melakukan ini? Oleh sebab itulah saya juga ingin berjalan melalui kod dengan kalian di sini. Jadi saya mempunyai satu pseudokod untuk kalian kali ini. Jadi, ingatlah ini sebagai kami akan beralih ke atas. Oleh itu, kita mempunyai beberapa kaunter yang menjejaki swap kami, kerana kita perlu memastikan bahawa kami sedang memeriksa itu. Dan kita beralih seluruh array kerana kami hanya melakukan dengan contoh ini. Jika elemen yang sebelum ini lebih besar daripada elemen setelah di mana kita berada, kita swap mereka dan kita kenaikan kami kaunter kerana sebaik sahaja kami menukar, Kami menulis untuk memberitahu kaunter kami tahu itu. Mana-mana soalan di sana? Sesuatu kelihatan lucu di sini. PELAJAR: Apakah anda menetapkan kaunter untuk sifar setiap kali anda pergi melalui loop? Adakah anda tidak terus kembali kepada sifar setiap kali? PENGAJAR: Tidak semestinya. Jadi apa yang berlaku ialah kita pergi ke sini. Begitu juga semasa, ingat, ini akan melaksanakan sekali tanpa gagal. Jadi ia akan menetapkan kaunter sama dengan nol, kemudian ia akan beralih melalui. Sebagai iterates melalui, itu akan memperbarui kaunter. Seperti update kaunter, ketika selesai, apabila ia sampai ke penghujung array, jika senarai tidak disusun, kaunter akan telah dikemaskini. Jadi kemudian ia memeriksa keadaan dan ia berkata, OK, adalah tidak lebih besar daripada sifar. Jika ya, melakukannya sekali lagi. Anda mahu menetapkan semula supaya apabila anda melalui, kaunter adalah sama dengan sifar. Jika anda pergi melalui diurutkan array, tidak ada perubahan, ini gagal, dan anda kembali senarai disusun. Adakah ini masuk akal? PELAJAR: Ia mungkin dalam sedikit. PENGAJAR: OK. Jika ada apa-apa yang lain pertanyaan yang muncul. Ya. PELAJAR: Apa yang akan fungsi adalah untuk menukar unsur-unsur? PENGAJAR: Oleh itu, kita sebenarnya boleh menulis bahawa jika kita akan ke kanan sekarang. Sejuk. Maka pada masa yang sama, Alison akan untuk beralih kembali ke perkakas. Ia akan menjadi seronok. Dan kita mempunyai baik kami hal semacam gelembung sini. Jadi saya sudah melakukan berbasikal melalui array. Kami mempunyai swap kami bahawa adalah sama dengan sifar. Oleh itu, kita ingin menukar berdekatan elemen jika mereka rusak. Jadi perkara pertama yang kita perlu lakukan adalah beralih melalui array kita. Jadi bagaimana anda rasa kami mungkin beralih melalui array kita? Kami ada untuk dan saya sama dengan 0. Kami mahu saya menjadi kurang dari n tolak 1 tolak k. Dan saya akan menjelaskan bahawa dalam satu saat. Jadi, ini adalah pengoptimuman di sini di mana, ingat bagaimana saya berkata selepas setiap lulus melalui kita array tahu bahawa apa pun yang on-- Jadi, selepas satu lulus kami tahu bahawa ini disusun. Selepas dua pas kita tahu bahawa semua ini disusun. Selepas tiga penerbangan yang kita tahu yang disusun. Jadi cara yang saya iterasi melalui array di sini, adalah ia memastikan hanya pergi melalui apa yang kita tahu adalah tidak dipisahkan. OK? Itu hanya pengoptimuman. Anda boleh menulis secara naif hanya iterasi melalui segala-galanya, ia hanya akan mengambil masa yang lama. Dengan gelung empat itu hanya pengoptimuman baik kerana kita tahu bahawa selepas setiap penuh lelaran melalui array di sini, seperti setiap gelung penuh di sini, kita tahu yang satu lagi elemen-elemen ini akan disusun di akhir. Oleh itu, kita tidak perlu bimbang tentang mereka. Adakah ini masuk akal untuk semua orang? Itu helah sedikit sejuk? Jadi, dalam hal ini, jika kami iterasi melalui, kita tahu bahawa yang kita inginkan untuk memeriksa jika pelbagai n dan n ditambah 1 adalah teratur. OK. Jadi, inilah pseudocode. Kami ingin memeriksa jika array n dan n ditambah 1 adalah teratur. Jadi apa yang kita ada di sana? Ia akan menjadi beberapa bersyarat. Ini akan menjadi jika. PELAJAR: Jika array n adalah kurang daripada pelbagai n campur 1. PENGAJAR: Mm-hm. Nah, kurang daripada atau lebih besar dari. PELAJAR: Lebih besar dari. Kemudian kita ingin menukar mereka. Tepat. Jadi sekarang kita masuk ke dalam apa mekanisme untuk menukar mereka? Oleh itu, kita telah melalui secara ringkas ini, sejenis fungsi swap minggu lepas. Apakah ada yang masih ingat bagaimana ia bekerja? Oleh itu, kita tidak boleh hanya menetapkan kembali mereka, kan? Oleh kerana salah seorang daripada mereka akan hilang. Jika kita mengatakan A sama dengan B, kemudian B adalah sama dengan A, semua tiba-tiba kedua-dua mereka hanya sama dengan B. Jadi apa yang harus kita lakukan adalah kita mempunyai variabel sementara itu akan memegang salah satu dari sementara kita kami dalam proses menukar. Jadi apa yang kita ada adalah kita akan mempunyai beberapa int suhu adalah sama supaya- anda boleh menetapkan kepada mana-mana satu yang anda mahu, hanya pastikan anda menjejaki itu-- sehingga dalam hal ini, saya akan menetapkan ke pelbagai n campur 1. Jadi itu akan memegang apa sahaja nilai adalah dalam blok kedua bahawa kita sedang melihat. Dan kemudian kita boleh lakukan ialah kita boleh pergi ke depan dan pelbagai menyerahhakkan semula n campur 1, kerana kita tahu bahawa kita mempunyai nilai yang disimpan. Ini juga salah satu besar things-- Saya tidak tahu sesiapa di antara kamu mempunyai isu-isu di mana jika anda menghidupkan dua baris kod tiba-tiba perkara yang bekerja. Perintah ini sangat penting dalam CS. Jadi, pastikan anda diagram hal-hal jika boleh mengenai apa yang sebenarnya berlaku. Jadi sekarang kita akan menetapkan kembali pelbagai n campur 1, kerana kita tahu bahawa kita mempunyai nilai yang disimpan. Dan kita boleh menetapkan bahwa untuk pelbagai n atau dalam hal ini pelbagai i. Terlalu banyak pembolehubah. OK. Pelbagai Jadi sekarang kita telah ditugaskan semula i ditambah 1 untuk sama apa yang ada di pelbagai i. Dan sekarang kita boleh kembali dan menetapkan pelbagai saya untuk apa? Sesiapa sahaja? PELAJAR: 10. PENGAJAR: 10. Tepat. Dan satu hal. Jika kita telah bertukar sekarang, apa yang kita perlu buat? Apakah perkara yang salah perkara yang berlaku untuk memberitahu kita jika kita pernah menamatkan program ini? Apa yang memberitahu kita bahawa kita mempunyai senarai yang disusun? Jika kita tidak melakukan apa-apa pertukaran, kan? Jika pertukaran adalah sama dengan sifar pada akhir ini. Jadi, setiap kali anda melakukan pertukaran, seperti yang kita hanya lakukan di sini, kita mahu untuk mengemaskini swap. Dan saya tahu ada pertanyaan sebelumnya tentang boleh anda menggunakan sifar atau salah satu daripada dari benar atau salah. Dan itulah apa yang dilakukan di sini. Jadi ini mengatakan, jika tak swap. Jadi jika swap adalah sifar, yang is-- saya selalu mendapatkan kebenaran saya dan kesalahan-kesalahan saya bercampur. Kami mahu kita menilai kepada benar dan ia bukan. Jadi, jika itu sifar, maka itu salah. Jika anda menafikan ia dengan [? bang?] ia menjadi kenyataan. Demikian maka baris ini dijalankan. Kebenaran dan yang salah dan sifar dan orang-orang gila. Hanya jika anda perlahan-lahan berjalan melaluinya ia akan masuk akal. Tapi itulah yang kecil ini sedikit kod di sini tidak. Jadi ini memeriksa untuk melihat yang telah kita lakukan apa-apa swap. Jadi, jika itu apa-apa selain sifar, ia akan menjadi palsu dan perkara ini adalah akan melaksanakan lagi. Cool? PELAJAR: Apa istirahat lakukan? PENGAJAR: Break hanya memecahkan kamu dari gelung. Jadi dalam hal ini ia akan hanya suka mengakhiri program dan anda akan hanya mempunyai senarai disusun anda. PELAJAR: Amazing. PENGAJAR: Saya minta maaf? PELAJAR: Oleh kerana sebelum ini kita digunakan bertulis 1 lebih ditulis nol membentangkan bahawa jika yang akan bekerja atau tidak. PENGAJAR: Ya. Jadi, anda boleh kembali sifar atau 1. Dalam kes ini, kerana kita tidak benar-benar melakukan apa-apa dengan fungsi tersebut, kami hanya mahu ia untuk memecahkan. Kami tidak benar-benar mengambil berat tentang hal itu. Brek juga baik jika ia digunakan untuk melanggar empat gelung atau syarat-syarat yang Anda tidak mahu untuk menjaga melaksanakan. Ia hanya akan membawa anda keluar dari mereka. Ini adalah sedikit hal nuansa. Aku merasa seperti ada banyak melambaikan tangan, seperti anda akan belajar tentang perkara ini tidak lama lagi. Tetapi anda akan belajar tentang perkara ini tidak lama lagi. Aku janji. OK. Jadi tidak semua orang mendapatkan semacam gelembung? Tidak terlalu buruk. Beralih melalui, hal-hal swap menggunakan suhu berubah-ubah, dan kami sudah siap di sana? Sejuk. Awesome. OK. Kembali ke PowerPoint. Apa-apa soalan secara umum mengenai setakat ini? Sejuk. Mm-hm. PELAJAR: [didengar] int utama biasanya. Adakah anda perlu mempunyai bahawa untuk ini? PENGAJAR: Oleh itu, kita hanya mencari hanya pada algoritma sorting sebenar. Jika anda mempunyai ia dalam seperti program yang lebih besar, Anda akan memiliki tempat utama int. Bergantung kepada di mana anda menggunakan algoritma ini, ia akan menentukan apa yang dipulangkan olehnya. Tetapi bagi kes kami, kami tidak ketat melihat bagaimana ini sebenarnya beralih melalui array. Oleh itu, kita tidak bimbang tentang hal itu. Jadi kita bercakap tentang hal terbaik dan senario kes terburuk untuk carian binari. Jadi ia juga penting untuk dilakukan bahwa untuk setiap macam kami. Jadi apa yang anda fikir adalah yang paling teruk kes runtime semacam gelembung? Anda semua masih ingat? PELAJAR: N tolak 1. PENGAJAR: Tiada tolak 1. Ini bermakna terdapat n tolak 1 perbandingan. Jadi, satu perkara yang perlu sedar ialah bahawa pada lelaran pertama, kita pergi melalui, kita bandingkan ini two-- jadi itu 1. Kedua-dua, tiga, empat. Jadi selepas satu lelaran kami sudah mempunyai empat perbandingan. Apabila saya bercakap tentang masa jalanan dan n. N mewakili bilangan perbandingan sebagai fungsi dari berapa banyak elemen kita ada. OK? Oleh itu, kita pergi melalui, kami mempunyai empat. Masa seterusnya yang anda tahu kita tidak melakukan harus mengurus ini. Kita bandingkan kedua-dua, kedua-dua, kedua-dua, dan jika kita tidak mempunyai pengoptimuman yang dengan gelung empat yang saya tulis, Anda akan membandingkan di sini anyways. Jadi, anda perlu dijalankan melalui array dan membuat perbandingan n n kali, kerana setiap kali kita dijalankan melalui itu kita semacam satu perkara. Dan setiap kali kami berjalan melalui array, kita buat n perbandingan. Jadi runtime kami untuk ini adalah sebenarnya n kuasa dua, yang jauh lebih buruk kita log akhir kerana itu ertinya jika kita mempunyai empat bilion elemen, itu akan membawa kita empat bilion kuasa dua bukan 32. Jadi tidak runtime yang terbaik, tetapi untuk beberapa hal, Anda tahu, jika anda dalam jarak tertentu dari unsur-unsur semacam gelembung mungkin baik untuk digunakan. OK. Jadi sekarang apa yang mana-mana yang terbaik runtime? PELAJAR: Zero? Atau 1? PENGAJAR: Jadi 1 akan menjadi salah satu perbandingan. Betul. PELAJAR: N tolak 1? PENGAJAR: Jadi, ya. Jadi n tolak 1. Setiap kali anda mempunyai konsep seperti n tolak 1, kita cenderung untuk hanya menjatuhkannya dan kami hanya mengatakan n kerana anda mempunyai untuk membandingkan setiap these-- setiap pasangan. Jadi ia akan menjadi n tolak 1, yang kita kita hanya akan mengatakan adalah lebih kurang n. Ketika anda sedang berhadapan dengan runtime, semuanya dalam lebih kurang. Selama eksponen adalah betul, kau cukup baik. Itulah cara kita menghadapinya. Supaya mana-mana yang terbaik adalah n, yang bermakna bahawa senarai itu sudah disusun, dan semua yang kita lakukan adalah menjalankan melalui dan pastikan ia disusun. Sejuk. Baik. Jadi seperti yang anda lihat di sini, kita hanya mempunyai beberapa lebih grafik. Jadi n kuasa dua. Fun. Jauh lebih buruk daripada n seperti yang kita lihat, dan jauh, jauh lebih buruk daripada log 2n. Dan kemudian anda juga masuk ke dalam log log. Dan anda mengambil 124, anda masuk ke dalam seperti bintang log, yang seperti gila. Jadi, jika anda berminat, bintang log pencarian. Ia adalah jenis yang menyeronokkan. Jadi kita mempunyai grafik yang hebat ini. Hanya kepala naik, ini grafik yang indah untuk mempunyai selama tempoh pertengahan anda kerana kami lama untuk meminta anda menipis ini. Jadi hanya kepala, memiliki ini pada anda jangka menengah pada contekan baik anda ada. Oleh itu, kita hanya melihat semacam gelembung. Kes terburuk, n kuasa dua, kes terbaik, n. Dan kita akan melihat yang lain. Dan seperti yang anda boleh lihat, satu-satunya salah satu yang benar-benar baik adalah gabungan semacam, yang kita akan masuk ke mengapa. Jadi, kita akan pergi ke satu jenis pilihan di sini-depan. Apakah ada yang masih ingat bagaimana pemilihan jenis bekerja? Pergi untuk itu. PELAJAR: Pada dasarnya melalui pesanan dan membuat senarai baru. Dan seperti yang anda meletakkan unsur-unsur dalam, meletakkan mereka di tempat yang betul dalam senarai baru. PENGAJAR: Supaya suara lebih seperti jenis sisipan. Tetapi anda benar-benar dekat. Mereka sangat mirip. Walaupun saya dicampuradukkan kadang-kadang. Sebelum seksyen ini aku seperti, menunggu. OK. Jadi apa yang anda mahu lakukan adalah jenis pemilihan, cara yang anda boleh berfikir mengenainya dan cara Saya memastikan saya tidak cuba untuk mendapatkan dicampuradukkan, adakah ia akan melalui dan ia memilih jumlah yang paling kecil dan ia meletakkan bahawa pada awal senarai anda. Ia menukar dengan yang tempat pertama. Mereka benar-benar mempunyai satu contoh untuk saya. Awesome. Jadi hanya satu cara untuk memikirkan pemilihan itu-- macam, pilih nilai yang paling kecil. Dan kita akan dijalankan melalui contoh yang saya fikir akan membantu kerana Saya rasa visual sentiasa membantu. Oleh itu, kita bermula dengan sesuatu yang yang benar-benar tidak dipisahkan. Merah akan menjadi tidak dipisahkan, hijau akan diurutkan. Semuanya akan masuk akal di saat. Oleh itu, kita melalui dan kita beralih dari awal hingga akhir. Dan kita berkata, OK, 2 adalah jumlah yang paling kecil kami. Jadi, kita akan mengambil 2 dan kita akan untuk memindahkannya ke hadapan array kita kerana itu adalah jumlah paling kecil yang kita ada. Jadi itulah yang ini lakukan di sini. Ini hanya akan menukar dua. Jadi sekarang kita telah yang disusun bahagian dan satu bahagian yang tidak dipisahkan. Dan apa yang baik untuk diingat mengenai jenis pilihan adalah kita hanya memilih dari bahagian yang tidak dipisahkan. Bahagian yang diurutkan anda biarkan. Mm-hm? PELAJAR: Bagaimana ia tahu apa yang yang paling kecil tanpa membandingkannya untuk setiap nilai lain dalam array. PENGAJAR: Itu membandingkannya. Kami suka melewatkan itu. Ini hanyalah umum secara keseluruhan. Yeah. Apabila kita menulis kod saya pasti anda akan lebih berpuas hati. Tetapi anda menyimpan ini pertama sebagai unsur yang paling kecil. Anda membandingkan dan anda berkata, OK, adalah lebih kecil? Ya. Menyimpannya. Di sini adalah lebih kecil? Tidak? Ini adalah yang paling kecil anda, menetapkan kembali ke nilai anda. Dan anda akan lebih gembira apabila kita melalui kod. Oleh itu, kita pergi melalui, kita tukar, jadi kemudian kita melihat bahagian yang tidak dipisahkan ini. Jadi, kita akan memilih tiga daripada. Kami akan meletakkannya di di akhir bahagian diurutkan kami. Dan kita hanya akan terus melakukan itu, melakukan hal itu, dan melakukan hal itu. Jadi, ini adalah semacam kami pseudo di sini. Kami akan memberi kod itu di sini dalam satu saat. Tetapi hanya sesuatu untuk berjalan melalui pada tahap yang tinggi. Anda akan pergi daripada i sama dengan 0 ke n tolak 2. Itu pengoptimuman lain. Jangan bimbang terlalu banyak tentang hal itu. Jadi seperti yang anda katakan. Sebagai Yakub berkata, bagaimana kita menjejaki apa yang minimum kami adalah? Bagaimana kita tahu? Kami perlu membandingkan segala-galanya dalam senarai kami. Jadi sekurang-kurangnya sama dengan saya. Ia hanya mengatakan dalam hal ini indeks nilai minimum kami. Demikian maka ia akan beralih melalui dan pergi dari j sama i ditambah 1. Oleh itu, kita sudah tahu bahawa itulah elemen pertama kami. Kita tidak perlu untuk membandingkannya dengan sendiri. Oleh itu, kita mula membandingkannya dengan yang akan datang salah satu yang adalah mengapa ia i ditambah 1 hingga n tolak 1, yang merupakan akhir array sana. Dan kita berkata jika array di j adalah kurang dari pelbagai min, maka kita menetapkan kembali di mana indeks minimum kami adalah. Dan jika min tidak sama dengan saya, sebagai di mana kami kembali ke sini. Jadi seperti ketika kita mula-mula melakukan satu ini. Dalam kes ini, ia akan bermula pada sifar, ia akan berakhir menjadi dua. Jadi min tidak akan sama saya pada akhirnya. Yang membolehkan kita tahu bahawa kita perlu untuk menukar mereka. Saya rasa seperti contoh yang konkrit akan membantu lebih dari ini. Jadi saya akan kode atas ini dengan kalian sekarang dan saya fikir ia akan menjadi lebih baik. Macam cenderung bekerja dengan cara itu dalam itu sering lebih baik hanya untuk melihat mereka. Jadi apa yang kita ingin lakukan adalah pertama kita mahu yang paling kecil elemen dalam kedudukannya dalam array. Tepat apa Yakub berkata. Anda perlu untuk menyimpan yang entah bagaimana. Jadi kita akan bermula di sini iterasi array. Kita akan mengatakan itu kami yang pertama hanya bermula dengan. Oleh itu, kita akan mempunyai int yang paling kecil adalah sama dengan pelbagai di i. Jadi, satu perkara yang perlu melihat, setiap masa lingkaran ini dijalankan, kita mulai satu langkah lebih jauh. Apabila kita mula kita melihat yang satu ini. Lain kali kita beralih melalui, kita mulai pada satu ini dan menetapkan nilai yang paling kecil kami. Jadi ia adalah hampir sama dengan semacam gelembung di mana kita tahu bahawa selepas satu pas, elemen terakhir ini disusun. Dengan jenis pemilihan, itu sebaliknya. Pada setiap pas, kita tahu bahawa yang pertama disusun. Setelah lulus kedua, yang kedua akan diurutkan. Dan seperti yang anda lihat pada contoh slaid, bahagian disusun kami hanya terus berkembang. Jadi dengan menetapkan satu yang paling kecil kami kepada barisan saya, semua yang dilakukannya adalah mengecutkan apa kita sedang melihat supaya untuk mengurangkan bilangan perbandingan yang kita buat. Adakah ini masuk akal untuk semua orang? Adakah anda memerlukan saya untuk menjalankan melalui yang lagi lambat atau dalam kata yang lain? Saya gembira. OK. Jadi kita menyimpan nilai pada masa ini, tapi kami juga ingin untuk menyimpan indeks. Jadi, kita akan untuk menyimpan kedudukan yang paling kecil satu, yang hanya akan menjadi i. Jadi sekarang Yakub berpuas hati. Kami memiliki hal-hal yang disimpan. Dan sekarang kita perlu melihat melalui bahagian yang tidak dipisahkan dari array. Jadi dalam hal ini ini akan unsorted kami. Ini adalah i. OK. Jadi apa yang kita akan lakukan akan menjadi untuk satu lingkaran. Bila-bila masa anda perlu beralih melalui array, fikiran anda boleh pergi ke untuk satu lingkaran. Jadi untuk beberapa int k equals-- apa yang kita berfikir k akan sama untuk memulakan dengan? Inilah yang kita tetapkan sebagai yang paling kecil kami nilai dan kami mahu membandingkannya. Apa yang kita mahu membandingkannya dengan? Ia akan menjadi salah satu yang akan datang ini, kan? Oleh itu, kita mahu k yang akan dimulakan ke i ditambah 1 untuk memulakan. Dan kami ingin k dalam hal ini kita sudah saiz disimpan di sini, jadi kami hanya boleh menggunakan saiz. Saiz yang saiz array. Dan kami hanya mahu mengemaskini k per satu setiap kali. Sejuk. Jadi sekarang kita perlu mencari unsur yang paling kecil di sini. Jadi jika kita beralih melalui, kami ingin mengatakan, jika array di k kurang dari value-- terkecil kita ini adalah di mana kita benar-benar mencatat apa yang sini-yang paling kecil maka kita ingin menetapkan kembali apa nilai yang paling kecil kita. Ini bermakna, oh, kami tidak iterasi melalui sini. Apa sahaja nilai di sini adalah bukan perkara yang paling kecil kami. Kita tidak mahu itu. Kami ingin menetapkannya semula. Jadi jika kita pemindahan itu, apa yang anda berfikir seperti di dalam kod ini di sini? Kami ingin menetapkan kembali terkecil dan kedudukan. Jadi apa yang paling kecil ini? PELAJAR: Array k. PENGAJAR: Array k. Dan apakah kedudukan ini? Apa indeks bagi nilai yang paling kecil kita? Hanya saja k. Jadi pelbagai k, k, mereka cocok. Jadi kita ingin untuk menetapkan kembali itu. Dan kemudian selepas kami mendapati yang paling kecil kami, sehingga pada akhir ini untuk gelung di sini kita telah memperoleh apa yang paling kecil kami nilai adalah, jadi kita tukar. Dalam kes ini, seperti mengatakan kami nilai yang paling kecil adalah di sini. Ini adalah nilai yang paling kecil kami. Kami hanya ingin tukar di sini, yang apa fungsi pertukaran di bahagian bawah lakukan, yang kita hanya menuliskan bersama-sama beberapa minit yang lalu. Jadi ia perlu kelihatan biasa. Dan kemudian ia hanya akan beralih melalui hingga mencapai semua jalan hingga akhir, yang bermakna anda mempunyai sifar unsur-unsur yang tidak dipisahkan dan segala sesuatu yang lain telah disusun. Masuk akal? Sedikit lebih kukuh? Kod ini membantu? PELAJAR: Untuk saiz, anda tidak benar-benar menetapkan atau mengubahnya, bagaimana cara mengetahui? PENGAJAR: Jadi, satu perkara yang perlu perhatikan di sini adalah saiz int. Oleh itu, kita katakan dalam jenis sort-- ini adalah fungsi dalam case-- itu jenis pilihan, ia berlalu masuk dengan fungsi. Jadi, jika ia tidak disahkan masuk, anda akan melakukan sesuatu seperti dengan panjang array atau anda akan beralih melalui untuk mencari panjang. Tetapi oleh kerana ia diluluskan dalam, kami hanya boleh menggunakannya. Anda hanya menganggap bahawa pengguna memberikan anda saiz yang sah yang sebenarnya mewakili saiz array Anda. Cool? Jika anda mempunyai sebarang masalah dengan ini atau mahu lebih banyak latihan coding macam pada anda sendiri, anda perlu pergi ke study.cs50. Ini alat. Mereka mempunyai pemeriksa yang Anda benar-benar boleh menulis. Mereka pseudokod. Mereka mempunyai lebih banyak video dan slaid termasuk yang saya gunakan di sini. Jadi, jika anda masih merasa agak kabur, cuba yang keluar. Seperti biasa, datang bercakap dengan saya juga. Soalan? PELAJAR: Adakah anda mengatakan yang saiz yang sebelum ini ditakrifkan? PENGAJAR: Ya. Saiz sebelum ini ditakrifkan sehingga sini dalam akuan fungsi. Jadi anda menganggap bahawa ia telah diluluskan pada oleh pengguna, dan untuk mudahnya, kita akan menganggap bahawa pengguna memberi kami saiz yang betul. Sejuk. Jadi itulah jenis pemilihan. Guys, saya tahu kita belajar banyak hari ini. Ini adalah data yang padat untuk bahagian. Maka dengan itu, kita akan untuk pergi ke jenis sisipan. OK. Jadi sebelum itu kami perlu lakukan analisis runtime kami di sini. Jadi dalam kes ini, diberikan kerana saya menunjukkan anda jadual saya sudah jenis beri tahu. Tetapi kes terbaik runtime, apa yang kita fikir? Semuanya disusun. N kuasa dua. Ada yang punya penjelasan mengapa anda berfikir? PELAJAR: Anda membandingkan through-- PENGAJAR: Benar. Anda membandingkan melalui. Pada setiap lelaran, walaupun kami decrementing ini dengan satu, Anda masih mencari melalui segala-galanya untuk mencari satu yang paling kecil. Jadi, walaupun nilai yang paling kecil anda di sini di awal, Anda masih membandingkannya terhadap segala sesuatu yang lain memastikan ia adalah perkara yang paling kecil. Jadi, anda akan berakhir dengan berjalan melalui kira-kira n kali kuasa dua. Baik. Dan apa yang mana-mana yang paling teruk? Juga n kuasa dua kerana anda akan yang akan melakukan prosedur yang sama. Jadi dalam hal ini, pemilihan semacam sesuatu bahawa kami juga menyeru runtime yang diharapkan. Jadi pada orang lain, kita hanya tahu batas-batas bawah dan atas. Bergantung kepada bagaimana kita gila daftar atau bagaimana unsorted itu, mereka berbeza-beza antara n atau n kuasa dua. Kita tidak tahu. Tetapi oleh kerana jenis pemilihan mempunyai yang sama paling teruk dan kes terbaik, yang memberitahu kita bahawa tidak kira jenis input apa yang kita mempunyai, sama ada ia benar-benar disusun atau benar-benar membalikkan disusun, itu akan mengambil jumlah yang sama. Jadi dalam hal ini, jika anda ingat dari meja kami, ia sebenarnya mempunyai nilai yang kedua-dua macam tidak punya, yang runtime diharapkan. Jadi kita tahu bahawa setiap kali kami menjalankan jenis pemilihan, itu dijamin menjalankan kuasa dua n masa yang. Tidak ada kebolehubahan di sana. Hanya saja yang diharapkan. Dan, sekali lagi, jika anda mahu belajar lebih, mengambil CS 124 di musim semi. Baik. Kami telah melihat yang satu ini. Sejuk. Semacam Jadi penyisipan. Dan Aku mungkin akan untuk merintis melalui ini. Saya tidak akan mempunyai anda semua kode itu. Kami hanya akan berjalan melaluinya. Jadi semacam penyisipan adalah jenis dari serupa dengan jenis pilihan kerana kami mempunyai satu unsorted dan disusun sebahagian daripada array. Tetapi apa yang berbeza ialah seperti yang kita pergi melalui satu per satu, kita hanya mengambil apa jumlah yang berikutnya dalam unsorted kami, dan benar mengatasinya ke dalam array diurutkan kami. Ia akan lebih masuk akal dengan satu contoh. Jadi semuanya bermula sebagai tidak dipisahkan, hanya suka dengan jenis pilihan. Dan kita akan menyelesaikan masalah ini di urutan menaik seperti yang kita telah. Maka pada kami pertama berlalu kita mengambil nilai pertama dan kita berkata, OK, anda sekarang dalam senarai sendiri. Kerana anda berada dalam senarai sendiri, anda disusun. Tahniah kerana menjadi Elemen pertama dalam array ini. Anda sudah menyusun semua sendiri. Jadi sekarang kita telah yang disusun dan pelbagai yang tidak dipisahkan. Jadi sekarang kita mengambil pertama. Apa yang berlaku antara sini dan di sini ialah kita mengatakan, OK, kita akan melihat Nilai pertama array unsorted kami dan kita akan input dalam nya tempat yang benar dalam array diurutkan. Jadi apa yang kita lakukan adalah kita mengambil 5 dan kita kata, OK, 5 adalah lebih besar dari 3, jadi kami hanya memasukkan dengan betul di sebelah kanan itu. Kami baik. Jadi kami pergi ke salah satu yang akan datang. Dan kita mengambil 2. Kami berkata, OK, 2 kurang dari 3, jadi kita tahu bahawa ia perlu berada di depan senarai kami sekarang. Jadi apa yang kita lakukan adalah kita menolak 3 dan 5 ke bawah dan kita bergerak 2 ke slot pertama. Jadi kami hanya memasukkan ke tempat yang betul yang sepatutnya. Kemudian kami melihat kami yang berikutnya, dan kita katakan 6. OK, 6 adalah lebih besar daripada segala-galanya dalam array diurutkan kami, jadi kita tag ke akhirnya. Dan kemudian kita melihat 4. 4 adalah kurang dari 6, itu kurang daripada 5 tetapi ia lebih besar dari 3. Jadi kita hanya masukkan terus ke dalam tengah di antara 3 dan 5. Jadi untuk membuat yang sedikit sedikit lebih konkrit, di sini adalah jenis yang idea dari apa yang berlaku. Jadi untuk setiap unsur yang tidak dipisahkan, kami menentukan di mana di bahagian diurutkan ia adalah. Jadi dengan mengambil kira disusun dan tidak dipisahkan, kita perlu melintasi melalui dan angka di mana ia sesuai dalam array diurutkan. Dan kita masukkannya dengan menggeser unsur-unsur di sebelah kanan bawah. Dan kemudian kita terus iterasi melalui sehingga kita mempunyai senarai yang sama sekali disusun di mana tidak dipisahkan kini sifar dan diurutkan memakan keseluruhannya dari senarai kami. Jadi, sekali lagi, untuk membuat sesuatu yang lebih konkrit, kami mempunyai pseudo. Jadi, pada asasnya adalah untuk i sama dengan 0 ke n tolak 1, itu hanya panjang array kami. Kami mempunyai beberapa elemen yang sama dengan array pertama atau indeks pertama. Kami menetapkan j sama dengan itu. Oleh itu, sambil j adalah lebih besar daripada sifar dan array, j tolak 1 adalah lebih besar daripada elemen, sehingga semua yang melakukan adalah memastikan bahawa j anda benar-benar mewakili bahagian yang tidak dipisahkan dari array. Jadi sementara masih ada perkara-perkara untuk menyusun dan j minus one is-- apa adalah elemen yang dia? J tidak pernah ditakrifkan di sini. Ini semacam menjengkelkan. OK. Anyways. Jadi j tolak 1, anda sedang menyemak elemen sebelumnya. Anda katakan, OK, adalah elemen yang sebelum di mana sahaja aku am-- mari kita benar-benar menarik ini. Jadi, bila ini seperti di celah kedua kami. Jadi saya akan menjadi sama 1, yang ada di sini. Jadi saya akan menjadi sama dengan 1. Ini akan menjadi 2, 4, 5, 6, 7. Baik. Jadi elemen kami dalam hal ini akan menjadi sama dengan 4. Dan kami mempunyai beberapa j itu akan menjadi sama dengan 1. Oh, j decrementing. Itulah apa yang ada. Jadi j sama dengan saya, jadi apa ini katakan adalah bahawa seperti yang kita bergerak ke hadapan, kami hanya memastikan bahawa kita tidak lebih mengindeks cara ini apabila kita cuba memasukkan sesuatu ke dalam senarai disusun kami. Oleh itu, apabila j sama dengan 1 dalam kes ini dan pelbagai j tolak satu-- sehingga pelbagai j tolak 1 adalah 2 dalam case-- ini jika itu lebih besar daripada elemen, maka semua ini adalah melakukan beralih segalanya. Jadi dalam hal ini, pelbagai j minus one akan pelbagai sifar, yang 2. 2 tidak lebih besar dari 4, jadi ini tidak melaksanakan. Jadi peralihan tidak bergerak ke bawah. Apa yang dilakukan di sini adalah hanya bergerak array diurutkan anda ke bawah. Dalam kes ini, sebenarnya, kita boleh do-- mari kita membuat 3. Jadi jika kita berjalan melalui dengan contoh ini, kita sekarang di sini. Ini disusun. Ini adalah tidak dipisahkan. Cool? Jadi saya adalah sama dengan 2, jadi unsur kita adalah sama dengan 3. Dan j kami adalah sama dengan 2. Oleh itu, kita melihat melalui dan kami berkata, OK, adalah pelbagai j minus one lebih besar daripada unsur yang kita lihat? Dan jawapannya adalah ya, bukan? 4 adalah lebih besar dari 3 dan j adalah 2, sehingga kod ini dijalankan. Jadi sekarang apa yang kami lakukan array di 2, jadi di sini, kita menukar mereka. Oleh itu, kita hanya berkata, OK, pelbagai pada 2 kini akan menjadi 3. Dan j akan sama j tolak 1, iaitu 1. Itu mengerikan, tetapi kalian mendapat idea. J kini sama dengan 1. Dan pelbagai j hanya akan menjadi sama dengan elemen kita, yang 4. Saya dipadam sesuatu yang saya tidak boleh mempunyai atau sesuatu miswrote, tapi kalian mendapat idea. Ia bergerak pada n. Dan kemudian jika ini, ia akan loop sekali lagi dan ia akan berkata, OK, j adalah 1 sekarang. Dan pelbagai j tolak 1 sekarang 2. Adalah kurang daripada 2 elemen kita? Tidak? Ini bermakna bahawa kita telah dimasukkan elemen ini di tempat yang betul dalam array diurutkan kami. Maka kita boleh mengambil ini dan kita berkata, OK, array diurutkan kami ada di sini. Dan ia akan mengambil nombor ini 6 dan seperti, OK, adalah 6 kurang dari angka ini? Tidak? Sejuk. Kami baik-baik. Melakukannya sekali lagi. Kami mengatakan 7. Adalah kurang dari 7 akhir array diurutkan kita? Tidak. Oleh itu, kita baik-baik saja. Jadi ini akan diurutkan. Pada dasarnya semua ini tidak adalah ia mengatakan mengambil unsur pertama pelbagai unsorted anda, mencari tahu di mana ia pergi dalam array diurutkan anda. Dan ini hanya mengambil penjagaan swap untuk melakukan itu. Anda pada dasarnya hanya menukar sehingga ia di tempat yang betul. Imej visual adalah bahawa anda bergerak segala sesuatu ke bawah dengan melakukan itu. Jadi seperti setengah bubble sort-esque. Semak kajian 50. Saya sangat mengesyorkan cuba kode ini sendiri. Jika anda mempunyai masalah atau anda mahu lihat contoh kod untuk jenis penyisipan, sila maklumkan kepada saya. Saya selalu sekitar. Jadi yang paling teruk kes runtime dan kes terbaik runtime. Seperti yang anda melihat seorang lelaki dari meja saya sudah menunjukkan anda, ia kedua-dua kuasa dua n dan n. Sungguh baik pergi daripada apa yang kita bercakap mengenai dengan macam kami sebelum ini, yang paling teruk kes runtime adalah bahawa jika ia benar-benar unsorted, kita perlu membandingkan semua ini n masa. Kami melakukan banyak seluruh perbandingan kerana jika ia dalam urutan terbalik, kita akan berkata, OK, ini adalah sama, ini adalah baik, dan yang satu ini perlu dibandingkan terhadap orang pertama yang dipindahkan kembali. Dan seperti yang kita mendapatkan arah hujung ekor, kita mempunyai untuk membandingkan, membandingkan, dan membandingkan terhadap segala-galanya. Sehingga akhirnya menjadi kira-kira n kuasa dua. Jika benar maka anda berkata, OK, 2, kau baik. 3, anda dibandingkan dengan 2. Kau baik. 4, anda hanya dibandingkan dengan ekor. Kau baik. 6, berbanding dengan ekor, anda baik-baik saja. Jadi untuk setiap tempat jika sudah disusun, anda membuat satu perbandingan. Jadi itu hanya n. Dan kerana kita mempunyai kes runtime terbaik n dan kes runtime paling teruk n kuasa dua, kita tidak mempunyai masa jalanan yang diharapkan. Ia hanya bergantung kepada huru-hara dalam senarai kami di sana. Dan sekali lagi, satu lagi graf dan jadual lain. Jadi perbezaan antara macam. Saya hanya akan angin melalui, saya berasa seperti kita telah berbincang secara meluas tentang bagaimana mereka semua jenis berbeza-beza dari dan link bersama-sama. Jadi bergabung sort adalah yang terakhir Saya akan melahirkan kalian dengan. Kami mempunyai gambar yang cantik berwarna-warni. Jadi menggabungkan semacam adalah algoritma rekursif. Jadi jangan kalian tahu apa yang fungsi rekursif adalah? Sesiapa pun mahu katakan? Anda mahu mencuba? Jadi fungsi rekursif hanya fungsi yang memanggil dirinya sendiri. Oleh itu, jika kalian kenal dengan jujukan Fibonacci, yang dianggap rekursif kerana Anda mengambil dua sebelumnya dan menambah mereka bersama-sama untuk mendapatkan satu di sebelah anda. Jadi rekursif, saya selalu berfikir rekursi sebagai seperti lingkaran jadi anda seperti ini semakin ke dalamnya. Tetapi ia hanya satu majlis yang menyebut dirinya. Dan, benar-benar, benar-benar cepat saya dapat menunjukkan apa yang kelihatan seperti. Jadi rekursif di sini, kalau kita lihat, ini adalah cara rekursif untuk jumlah lebih array. Jadi semua yang kita lakukan adalah kita mempunyai fungsi penjumlahan jumlah wang itu mengambil ukuran dan array. Dan jika anda perhatikan, saiz pengurangan per satu setiap kali. Dan semua hal ini adalah jika x sama dengan zero-- jadi jika saiz array adalah sama dengan zero-- itu kembali sifar. Jika tidak, jumlah ini elemen terakhir dari array, dan kemudian mengambil sejumlah sisa array. Jadi ia hanya memecahkannya ke dalam masalah yang lebih kecil dan lebih kecil. Singkat cerita, rekursi, fungsi yang memanggil dirinya. Jika itu semua yang anda keluar dari ini, itulah yang fungsi rekursif. Jika anda mengambil 51, anda akan mendapat sangat, sangat selesa dengan rekursi. Ia benar-benar sejuk. Masuk akal pada seperti 03:00 satu malam. Dan aku seperti, mengapa yang saya tidak pernah menggunakan ini? Jadi untuk gabungan semacam, pada dasarnya apa yang ia akan lakukan ialah ia akan memecahnya dan pecah ke bawah sehingga ia hanya satu elemen. Unsur-unsur tunggal yang mudah untuk menyusun. Kita lihat bahawa. Jika anda mempunyai salah satu elemen, itu sudah dianggap diurutkan. Maka pada masukan n unsur, jika n adalah kurang daripada 2, hanya kembali kerana cara yang itu sama ada 0 atau 1 seperti yang kita lihat. Mereka yang dianggap unsur-unsur diurutkan. Jika tidak pecah menjadi dua. Susun separuh pertama, menyusun kedua setengah, dan kemudian menggabungkan mereka bersama-sama. Mengapa ia dipanggil gabungan semacam. Jadi kami ada di sini kami akan menyusun ini. Oleh itu, kita tetap memiliki mereka sehingga saiz array adalah 1. Oleh itu, apabila ia adalah 1, kita hanya kembali kerana ini adalah array diurutkan, dan ini adalah array diurutkan, dan itulah array diurutkan, kami semua disusun. Jadi maka apa yang kita lakukan adalah kita mulai menggabungkan mereka bersama-sama. Jadi cara yang anda boleh berfikir tentang penggabungan adalah Anda hanya menghapus kecil jumlah setiap sub tatasusunan dan hanya menambahkan ke array muncul. Jadi, jika anda lihat di sini, apabila kita mempunyai set ini kita ada 4, 6, dan 1. Apabila kita ingin menggabungkan ini, kita melihat kedua pertama dan kita berkata, OK, 1 adalah lebih kecil, ia pergi ke depan. 4 dan 6, ada apa-apa untuk membandingkan untuk, hanya tag ke akhirnya. Apabila kita menggabungkan kedua, kita hanya mengambil salah satu yang lebih kecil dari kedua orang ini, jadi ia adalah 1. Dan kini kita mengambil lebih kecil dari kedua orang ini, jadi 2. Lebih kecil dari kedua-dua, 3. Lebih kecil dari kedua-dua, 4, 5, 6. Jadi anda hanya menarik dari ini. Dan kerana mereka telah telah disusun sebelum ini, Anda hanya mempunyai satu perbandingan setiap waktu di sana. Kod Jadi lebih lanjut di sini, perwakilan adil. Jadi anda akan bermula pada tengah-tengah dan Anda semacam kiri dan kanan dan kemudian anda hanya menggabungkan mereka. Dan kita tidak mempunyai kod untuk bergabung di sini. Tetapi, sekali lagi, jika anda pergi ke atas mengkaji 50, ia akan berada di sana. Jika tidak datang bercakap dengan saya jika anda masih keliru. Jadi perkara yang menarik di sini adalah bahawa hal terbaik, kes terburuk, dan runtime dijangka semua dalam log n, yang adalah jauh lebih baik daripada kita sudah dilihat untuk sisa macam kami. Kami telah melihat n kuasa dua dan apa yang kita sebenarnya mendapatkan di sini adalah n log n, yang besar. Lihatlah betapa jauh lebih baik itu. Seperti keluk baik. Jadi jauh lebih efisien. Jika anda boleh, penggunaan menggabungkan semacam. Ini akan menjimatkan masa anda. Kemudian lagi, seperti yang kita katakan, jika Anda turun di rantau yang lebih rendah, ia tidak membuat yang banyak perbezaan. Anda akan mendapat sehingga beribu-ribu dan beribu-ribu input, Anda pasti mahu algoritma yang lebih cekap. Dan, sekali lagi, meja yang indah kami semua macam yang anda semua tahu hari ini. Jadi saya tahu ia pernah ada hari yang padat. Ini belum tentu akan untuk membantu anda dengan Serangga anda. Tetapi saya hanya ingin membuat penafian seksyen itu bukan hanya tentang pşet. Semua bahan ini adalah adil permainan untuk ujian tengah semester anda. Dan juga jika anda melakukan melanjutkan dengan CS, ini adalah asas-asas yang sangat penting yang anda perlu tahu. Jadi beberapa hari akan menjadi Serangga kecil bantuan lanjut, tetapi beberapa minggu akan kandungan banyak lagi sebenarnya yang mungkin tidak kelihatan super berguna untuk anda sekarang, tapi aku berjanji jika anda terus atas akan menjadi sangat, sangat berguna. Jadi itu sahaja untuk bahagian. Ke kawat. Aku melakukannya dalam masa satu minit. Tetapi ada anda pergi. Dan aku akan donat atau gula-gula. Apakah orang alah kepada apa-apa, dengan cara itu? Telur dan susu. Jadi donat adalah tidak? OK. Baik. Coklat tidak? Starburst. Starbursts baik. OK. Kita akan mempunyai Starburst minggu depan itu. Itu yang saya akan mendapatkan. Kalian mempunyai minggu yang besar. Baca spec anda. Beritahu saya jika anda mempunyai sebarang soalan. Serangga dua gred harus kepada anda pada hari Kamis. Jika anda mempunyai sebarang pertanyaan tentang bagaimana saya dinilai sesuatu atau mengapa saya dinilai sesuatu cara saya tidak, sila e-mel saya, datang bercakap dengan saya. Saya ini gila sedikit minggu, tetapi saya berjanji Saya masih akan membalas dalam masa 24 jam. Jadi mempunyai minggu yang besar, semua orang. Nasib baik pada Serangga anda.