>> SPEAKER 1: Hey everyone!
Selamat datang kembali ke bagian.
Sangat senang melihat begitu banyak dari Anda berdua di sini, dan semua orang yang menonton secara online.
Jadi, sebagai Selamat datang biasa kembali.
Saya harap Anda semua memiliki yang indah akhir pekan, penuh istirahat, relaksasi.
Itu indah kemarin.
Jadi, saya harap Anda menikmati alam bebas.
>> Jadi pertama beberapa pengumuman.
Grading.
Jadi, sebagian besar dari Anda harus mendapatkan sebuah email dari saya tentang Pset Scratch Anda,
serta gradasi untuk Pset 1.
Jadi, hanya beberapa hal.
Pastikan untuk menggunakan check50 di style50.
Ini dimaksudkan untuk menjadi sumber daya untuk kalian,
untuk memastikan bahwa Anda mendapatkan poin sebanyak yang Anda bisa
tanpa sia-sia kehilangan mereka.
Jadi, hal-hal seperti gaya sangat penting.
Kita akan lepas landas untuk itu.
Beberapa dari Anda mungkin sudah melihat bahwa dari Pset Anda.
Dan check50 hanya cara yang sangat mudah untuk memastikan
bahwa kita benar-benar kembali apa perlu kembali ke pengguna,
dan bahwa segala sesuatu bekerja dengan baik.
>> Pada catatan kedua, pastikan Anda meng-upload hal-hal ke folder yang benar.
Itu membuat hidup saya hanya sedikit lebih sulit
jika Anda meng-upload Pset 2 ke Pset 1 karena ketika saya men-download hal-hal,
mereka tidak men-download dengan benar.
Dan aku tahu itu miring sedikit dalam suatu sistem untuk membiasakan diri,
tetapi hanya menjadi super hati-hati, jika hanya untuk saya,
sehingga ketika Anda mendapatkan email di seperti 2:00 dan aku grading.
Jika tidak menyebabkan saya harus melihat semua sekitar untuk Pset Anda.
Keren.
>> Aku tahu itu lebih awal, tapi aku benar-benar mendapat lengah
oleh esai itu karena hari Jumat ini, bahwa profesor saya hanya suka, oh yeah.
Ingat, Anda memiliki esai tempo pada Jumat.
Jadi, saya tahu tidak ada yang suka untuk berpikir tentang ujian tengah semester,
tapi kuis pertama Anda adalah pada 15 Oktober, yang Oktober mulai minggu ini.
Jadi, mungkin lebih cepat dari yang Anda harapkan semua.
Sehingga Anda tidak dilemparkan lengah ketika Saya menyebutkan bagian minggu depan yang oh,
kuis minggu berikutnya, saya pikir Saya akan memberikan Anda sedikit lebih
dari kepala sampai sekarang.
>> Jadi, masalah Anda mengatur, nomor tiga.
Bagaimana orang telah membaca spec keluar dari rasa ingin tahu?
OK.
Kami punya beberapa.
Jenis turun dari lalu minggu tapi itu OK.
Aku tahu itu keluar indah.
Jadi Break Out.
Pasti setelah Anda selesai hari ini membaca spec setidaknya
coba seperti men-download Kode distribusi dan berjalan
seperti awal pertama hal yang mereka meminta Anda untuk.
Karena kita menggunakan Kode distribusi dan perpustakaan
bahwa kita hanya pernah using-- --Itu hanya kedua kalinya kami sudah melakukan Pset ini,
hal-hal gila bisa terjadi dengan alat Anda,
dan Anda ingin menemukan bahwa keluar sekarang dibandingkan nanti.
>> Karena jika itu Kamis malam atau itu Rabu malam dan untuk beberapa alasan
alat Anda hanya tidak ingin menjalankan dengan perpustakaan
atau dengan distribusi kode, yang berarti
Anda bahkan tidak dapat mulai melakukan coding.
Karena Anda tidak dapat memeriksa untuk melihat apakah ia bekerja.
Anda tidak akan dapat untuk melihat apakah mengkompilasi.
Anda ingin mengurus mereka di awal minggu itu, ketika Anda masih bisa email saya
atau salah satu dari TF lainnya, dan kita bisa mendapatkan mereka tetap.
Karena mereka adalah isu-isu yang akan menghentikan Anda
dari membuat kemajuan nyata.
Ini tidak seperti salah satu bug, yang Anda dapat hanya jenis melewatkan.
Jika Anda mengalami masalah dengan Anda alat atau kode distribusi,
Anda benar-benar ingin mendapatkan yang diambil peduli lebih awal daripada kemudian.
Jadi bahkan jika Anda tidak benar-benar gonna mulai coding, download distribusi
kode, membaca spec, pastikan semuanya bekerja di sana.
OK?
Jika Anda hanya dapat melakukan itu, saya berjanji hidup Anda akan lebih mudah.
Dan Anda mungkin akan untuk melakukannya sekarang kan?
OK.
Jadi, pertanyaan di sana?
Setiap hal logistik?
Semua orang baik?
OK.
>> Disclaimer bagi Anda di kamar dan online.
Aku akan mencoba untuk beralih antara PowerPoint di alat
karena kita akan menjadi melakukan beberapa coding
hari ini oleh permintaan populer dari anonim jajak pendapat saran saya mengirimkan minggu lalu.
Jadi, kita akan melakukan beberapa coding.
Jadi, jika kalian juga ingin untuk menjalankan peralatan Anda,
dan Anda harus punya email dari saya, dengan contoh file.
Jangan ragu untuk melakukan itu.
>> Jadi, kita akan berbicara tentang GDB, yang merupakan debugger.
Ini akan membantu Anda jenis mencari tahu di mana
hal-hal yang tidak beres dalam kode Anda.
Ini benar-benar hanya satu cara bagi Anda untuk melangkah melalui kode Anda seperti itu terjadi,
dan mampu mencetak variabel atau melihat apa yang sebenarnya terjadi
di bawah tenda ayat program Anda hanya berjalan, itu seperti faulting,
dan Anda seperti, tidak tahu apa yang baru saja terjadi di sini.
Aku tidak tahu apa garis itu gagal.
Aku tidak tahu di mana itu salah.
Jadi, GDB akan membantu Anda dengan itu.
Juga, jika Anda memutuskan untuk terus ya, dan mengambil 61,
itu akan benar-benar, benar-benar akan Anda sahabat, karena aku dapat memberitahu Anda
karena aku akan melalui kelas itu.
>> Kita akan melihat biner pencarian, yang jika kalian ingat
besar buku telepon contoh tontonan dari kelas.
Kami akan menerapkan itu, dan berjalan melalui itu sedikit lebih,
dan kemudian kita akan melalui empat berbagai macam, yaitu Bubble,
Seleksi, penyisipan, dan Merge.
Keren.
Jadi, GDB seperti yang saya sebutkan, adalah debugger.
Dan ini adalah jenis besar hal, fungsi besar atau perintah
yang Anda gunakan dalam GDB, dan saya akan berjalan Anda melalui demo itu dalam hitungan detik.
>> Jadi, ini bukan hanya akan tinggal abstrak.
Saya akan mencoba dan membuatnya sebagai beton mungkin bagi kalian.
Jadi, istirahat.
Itu baik akan istirahat seperti, beberapa nomor, yang
merupakan garis dalam program Anda, atau Anda dapat nama fungsi.
Jadi, jika Anda mengatakan istirahat utama, itu akan berhenti di utama,
dan membiarkan Anda berjalan melalui fungsi tersebut.
>> Demikian juga, jika Anda memiliki beberapa eksternal berfungsi seperti Swap atau Cube,
bahwa kita melihat pekan lalu.
Jika Anda mengatakan melanggar salah satu dari mereka, setiap kali program Anda memukul itu,
itu akan menunggu Anda untuk memberitahu apa yang harus dilakukan.
Sebelum itu hanya akan mengeksekusi sehingga Anda benar-benar bisa melangkah di dalam fungsi
dan melihat apa yang terjadi.
Jadi, Next, hanya melompat di atas baris berikutnya, berjalan di atas fungsi.
Langkah.
Ini semua adalah abstrak kecil.
Jadi, aku hanya akan berjalan melalui mereka, tetapi Anda akan melihat mereka digunakan dalam satu detik.
>> Masuki fungsi.
Jadi seperti yang saya katakan, seperti dengan Swap, itu akan
memungkinkan Anda untuk benar-benar seolah-olah Anda seperti fisik melangkah di dalam,
Anda bisa main dengan variabel, cetak tahu apa yang mereka, lihat apa yang terjadi.
Daftar harfiah akan hanya mencetak out kode sekitarnya.
Jadi, jika Anda jenis lupa di mana Anda berada dalam program Anda,
atau Anda bertanya-tanya apa yang terjadi di sekitarnya,
ini hanya akan mencetak segmen dari seperti lima atau enam baris di sekitarnya.
Jadi, Anda dapat mendapatkan berorientasi tentang di mana Anda berada.
>> Mencetak beberapa variabel.
Jadi, jika Anda memiliki kunci seperti di Caesar, bahwa kita akan melihat.
Anda dapat mengatakan Cetak Key pada titik apapun.
Ini akan memberitahu Anda apa nilai begitu itu, mungkin di suatu tempat di sepanjang jalan,
Anda menimpa kunci Anda.
Anda benar-benar bisa mengatakan bahwa karena Anda benar-benar dapat mengamati nilai tersebut.
>> Dalam penduduk setempat, hanya cetakan out variabel lokal Anda.
Jadi, kapan Anda berada dalam satu lingkaran, dan Anda hanya ingin melihat seperti, oh.
Apa saya?
Apa nilai kunci ini bahwa saya menginisialisasi sini?
Apa pesan pada saat ini?
Itu hanya akan mencetak semua dari mereka, sehingga Anda
tidak perlu secara individual mengatakan, Print I. Print Pesan.
Cetak Key.
Dan kemudian Tampilan.
Apa yang dilakukan adalah seperti yang Anda langkah melalui program ini,
itu hanya akan memastikan bahwa itu menampilkan beberapa variabel tertentu
di setiap titik.
Sehingga Anda also-- --Itu adalah jenis jalan pintas mana
Anda tidak harus terus seperti, oh.
Cetak Key atau Print I. Itu hanya otomatis akan melakukannya untuk Anda.
>> Jadi, dengan itu, kita akan untuk melihat bagaimana ini berjalan.
Aku akan mencoba dan beralih ke alat saya.
Lihat apakah saya bisa melakukan ini.
Semua.
Kami hanya akan cermin itu.
Tidak ada yang gila di laptop saya anyways.
OK.
Hal ini perlu menjadi satu ini.
Ini sangat kecil.
Mari kita lihat apakah kita bisa melakukan ini.
>> OK.
Alice jelas berjuang di sini hanya sedikit,
namun kami akan mendapatkannya di momento.
OK.
Kami hanya akan meningkatkan ini.
OK.
Dapatkah orang semacam melihat bahwa?
Mungkin sedikit?
Aku tahu itu agak kecil.
Anda tidak bisa mencari tahu bagaimana membuat ini lebih besar.
Jika ada yang tahu.
Apakah ada yang tahu bagaimana membuatnya lebih besar?
OK.
Kita akan roll dengan itu.
Tidak peduli lagian karena itu hanya itulah kode yang kalian harus
memiliki.
>> Apa yang lebih penting adalah terminal sini.
Dan kita miliki di sini Mengapa begitu kecil?
Pengaturan.
Oh.
Benar Ike.
Bagaimana ini?
Keluar dari sana.
Apakah itu baik bagi semua orang?
OK ,.
Keren.
>> Anda tahu ketika Anda berada di CS kesulitan teknis kelas
adalah jenis bagian dari the-- Jadi, mari kita membersihkan ini.
OK.
Jadi, di sini, di bagian, yang kami punya di sini.
Caesar adalah file eksekusi.
Jadi saya membuatnya.
Jadi, satu hal yang perlu disadari dengan GDB adalah bahwa ia hanya bekerja pada file yang dapat dieksekusi.
Jadi, Anda tidak dapat menjalankannya pada dotsy a.
Anda harus benar-benar membuat memastikan bahwa kode Anda mengkompilasi,
dan bahwa hal itu dapat benar-benar dijalankan.
>> Jadi, pastikan bahwa jika tidak kompilasi, mendapatkannya untuk mengkompilasi,
sehingga Anda dapat jenis berjalan melalui itu.
Jadi, untuk memulai GDB, semua yang Anda lakukan, Gloria Jenis GDB, dan kemudian hanya
mengajukan yang Anda inginkan.
Saya selalu misspell Caesar.
Tapi Anda ingin memastikan karena itu dieksekusi,
ti itu dot kilat sehingga berarti Anda akan
untuk menjalankan CSI Anda akan mengeksekusi ini file baik dengan debugger.
OK.
Jadi, Anda melakukan itu, Anda mendapatkan semacam ini omong kosong.
Hanya saja semua hal tentang debugger.
Anda tidak benar-benar harus khawatir tentang hal itu sekarang.
Dan seperti yang Anda lihat, kami punya ini parens terbuka, PDB, parens dekat,
dan hanya jenis terlihat seperti baris perintah kita, kan?
>> Jadi, apa yang ingin kita do-- --So, Hal pertama
adalah kita ingin memilih tempat untuk memecahkannya.
Jadi, ada satu bug dalam program Caesar ini
bahwa saya memperkenalkan, bahwa kita akan mencari tahu.
Itu Apa yang dilakukannya adalah dibutuhkan input Barfoo dalam semua topi, dan untuk beberapa alasan
itu tidak mengubah A. Itu hanya daun sendiri, Apakah segala sesuatu yang lain benar,
tapi surat kedua A tetap tidak berubah.
Jadi, kita akan mencoba dan mencari tahu mengapa itu.
Jadi, hal pertama yang Anda biasanya ingin melakukan setiap kali Anda mulai pada GDB
adalah mencari tahu di mana untuk memecahkannya.
>> Jadi Caesar adalah program yang cukup singkat.
Kami hanya memiliki satu fungsi, kan?
Apa fungsi kita di Caesar?
Hanya ada satu fungsi, hak Main?
Utama adalah fungsi untuk semua program Anda.
Jika Anda tidak memiliki Main, aku mungkin menjadi sedikit khawatir sekarang,
tapi saya harap Anda semua memiliki Main di sana.
Jadi, apa yang bisa kita lakukan adalah kita bisa hanya istirahat Main, begitu saja.
Jadi, ia mengatakan, OK.
Kami menetapkan satu breakpoint kami di sana.
>> Jadi, sekarang hal yang perlu diingat adalah Caesar mengambil satu perintah argumen baris yang tepat
dan kami tidak melakukan hal itu di mana saja belum.
Jadi, apa yang Anda lakukan adalah ketika Anda benar-benar pergi untuk menjalankan
program, program apapun yang Anda berjalan di GDB yang perlu baris perintah
argumen, Anda akan masukan ketika Anda pertama kali mulai menjalankannya.
Jadi, dalam hal ini, kita lakukan Jalankan dengan kunci tiga.
Dan itu benar-benar akan dimulai.
>> Jadi, jika Anda lihat di sini, kita memiliki Jika RC tidak sama dengan 2.
Jadi, jika kalian semua memiliki bahwa file yang saya dikirim up
Anda akan melihat bahwa itu seperti baris pertama fungsi utama kita, kan?
Ini memeriksa untuk melihat apakah kita memiliki jumlah argumen yang benar.
Jadi, jika Anda bertanya-tanya jika RC benar,
Anda dapat melakukan sesuatu seperti Print RC.
RC adalah dua, yaitu apa yang kita harapkan, kan?
>> Jadi, kita bisa pergi berikutnya, dan terus melalui.
Jadi, kami memiliki beberapa kunci di sana.
Dan kita dapat mencetak kunci kami untuk memastikan itu benar.
Menarik.
Tidak cukup apa yang kami harapkan.
Jadi, satu hal untuk mewujudkan dengan GDB juga, adalah
bahwa itu tidak sampai Anda benar-benar memukul Berikutnya, bahwa garis yang baru saja Anda lihat
benar-benar dijalankan.
Jadi, dalam hal ini Key belum ditetapkan belum.
Jadi, Key adalah beberapa nilai sampah yang Anda lihat di bawah sana.
Negatif $ 120-- --Itu ini satu miliar dan sesuatu hal yang aneh kan?
Ini bukan kunci yang kami harapkan.
Tetapi jika kita memukul Berikutnya, lalu kita mencoba dan tombol Print, itu tiga.
>> Semua orang melihat itu?
Jadi, jika Anda mendapatkan sesuatu bahwa Anda seperti, tunggu.
Ini benar-benar salah, dan saya tidak tahu
bagaimana ini akan terjadi karena semua yang saya inginkan lakukan adalah menetapkan nomor, variabel,
mencoba memukul Selanjutnya, coba pencetakan lagi, dan melihat apakah yang bekerja.
Karena itu hanya akan mengeksekusi dan benar-benar menetapkan sesuatu setelah Anda
tekan Next.
Masuk akal untuk semua orang?
Uh huh?
>> SPEAKER 2: Ketika Anda acak nomor apa artinya?
>> SPEAKER 1: Ini hanya acak.
Ini hanya sampah.
Ini hanya sesuatu yang Anda komputer secara acak akan menetapkan.
Keren.
Jadi, sekarang kita dapat bergerak melalui, dan sebagainya sekarang kita memiliki ini GetString teks biasa.
Jadi, biarkan aku hanya memperkenalkan apa akan terjadi ketika kita memukul Berikutnya sini.
GDB kami jenis menghilang, kan?
Itu karena GetString sekarang mengeksekusi, kan?
Jadi, ketika kita melihat teks biasa sama GetString, parens terbuka dan parens,
dan kita memukul Selanjutnya, yang memiliki sebenarnya dieksekusi sekarang.
Jadi, itu menunggu kita masukan sesuatu.
>> Jadi, kita akan masukan makanan kami yang adalah apa itu gagal seperti yang saya katakan
dan bahwa hanya mengatakan bahwa itu selesai mengeksekusi, yang ditutup
braket berarti itu keluar dari lingkaran itu.
Jadi, kita bisa tekan Next, dan sekarang, karena saya yakin kita semua sudah familiar dari Caesar,
ini, apa baris ini akan dilakukan.
Ini untuk Int I sama dengan 0, N sama Strlen, teks biasa, dan kemudian
Saya kurang dari n, I, ditambah, plus.
Apa lingkaran ini akan dilakukan?
Buka pesan Anda.
Keren.
Jadi, mari kita mulai melakukan hal itu.
>> Jadi, harus kondisi ini cocok, untuk pertama kita?
Jika itu adalah B, itu teks biasa I. Kami dapat memperoleh informasi tentang penduduk setempat kami.
Jadi, saya adalah nol, dan jika enam, yang kami berharap, dan kunci kami adalah tiga.
Semua yang masuk akal, kan?
Angka-angka itu semua persis apa yang mereka seharusnya.
Jadi, bersenandung?
SPEAKER 3: Saya memiliki nomor acak untuk tambang.
SPEAKER 1: Yah, kita bisa check-- --Kami dapat chatting tentang bahwa dalam satu detik.
Tapi Anda harus mendapatkan ini.
Jadi, jika kita memiliki modal B untuk pertama kami,
Kondisi ini harus menangkapnya, kan?
Jadi, jika kita memukul Selanjutnya, kita lihat bahwa Jika ini benar-benar dijalankan.
Karena jika Anda mengikuti bersama dalam kode Anda,
baris ini di sini, di mana teks biasa saya diganti dengan aritmatika ini,
hanya mengeksekusi jika Jika Kondisi yang tepat yang benar?
>> GDB hanya akan menampilkan hal-hal yang benar-benar melaksanakan.
Jadi jika kondisi Jika ini tidak terpenuhi, itu hanya akan melompat ke baris berikutnya.
OK?
Jadi, kita mendapati bahwa.
Braket ini berarti itu ditutup keluar dari lingkaran itu sekarang.
Jadi, itu akan mulai lagi.
Hanya seperti itu.
Jadi, kita bisa mendapatkan info tentang penduduk setempat kami di sini,
dan kita melihat bahwa pertama kami surat telah berubah, kan?
Sekarang E, sebagaimana mestinya.
Jadi, kita dapat melanjutkan.
>> Dan kami memiliki cek ini.
Dan cek ini harus bekerja, kan?
Ini A. Ini harus diubah tiga huruf depan.
Tetapi jika Anda melihat, kita mendapatkan sesuatu yang berbeda.
Jadi dalam hal ini di sini, itu tertangkap itu, dan baris ini dieksekusi,
yang dimodifikasi kami B. Tapi, dalam hal ini di sini,
kita mendapati bahwa itu hanya melewatkan itu, dan pergi ke [itu? L SIFF. ?]
Jadi sesuatu yang terjadi di sana.
Apa yang memberitahu Anda adalah bahwa, kita tahu bahwa itu harus menangkap sini,
tapi tidak.
Dapatkah orang melihat apa yang kami Masalah ini sejalan itu?
Ini adalah hal yang sangat menit.
Dan Anda juga bisa melihat kode Anda.
Ini juga line-- melupakan apa garis itu di besar-- tapi itu di [tidak terdengar].
Ya?
>> SPEAKER 4: Ini pada lebih besar dari Halaman jika Anda membacanya di buku.
SPEAKER 1: Tepat.
Jadi, debugger tidak tahu Anda itu, tapi debugger
bisa membuat Anda turun ke saluran Anda tahu tidak berfungsi.
Dan kadang-kadang, ketika terutama kemudian di semester, ketika
Anda sedang berhadapan dengan seratus, ratus beberapa baris kode, dan Anda
tidak tahu di mana itu gagal, ini adalah cara yang bagus untuk melakukannya.
Jadi, kami menemukan bug kami.
Anda dapat memperbaikinya dalam file Anda, dan kemudian Anda bisa menjalankannya lagi,
dan semuanya akan bekerja dengan sempurna.
Dan yang terbesar adalah ini dapat tampak seperti, OK.
Ya.
Keren.
Kau tahu apa yang Anda cari.
Jadi, Anda tahu apa yang harus dilakukan.
>> GDB dapat super membantu karena Anda dapat mencetak semua hal yang Anda
tidak.
Ini jauh lebih berguna daripada printf.
Berapa banyak dari Anda menggunakan seperti pernyataan printf
untuk mencari tahu di mana bug itu, kan?
Jadi, dengan ini, Anda tidak harus terus kembali,
dan seperti komentar di Printf, atau komentar dari,
dan mencari tahu apa Anda harus mencetak.
Ini benar-benar hanya memungkinkan Anda untuk langkah melalui, mencetak hal-hal
karena Anda akan melalui, jadi, Anda dapat mengamati bagaimana mereka berubah secara real time,
sebagai program anda berjalan.
>> Dan itu tidak mengambil sedikit sedikit membiasakan diri.
Saya akan sangat menyarankan hanya jenis menjadi sedikit frustrasi dengan itu
untuk sekarang.
Jika Anda menghabiskan satu jam di atas minggu depan belajar bagaimana menggunakan GDB,
Anda akan menghemat begitu banyak waktu di kemudian hari.
Dan secara harfiah. kita memberitahu ini untuk orang setiap tahun,
dan saya ingat ketika saya mengambil kelas, aku seperti, aku akan baik-baik saja.
Nomor
Pset 6 datang dan aku seperti, aku akan belajar
bagaimana menggunakan GDB karena saya tidak melakukan tahu apa yang terjadi di sini.
>> Jadi jika Anda meluangkan waktu sehingga menggunakannya pada program yang lebih kecil
bahwa Anda akan menjadi bekerja, seperti bekerja
melalui sesuatu seperti Visionare, seperti ini.
Atau jika Anda ingin latihan ekstra, saya yakin Aku bisa datang dengan program buggy,
bagi Anda untuk men-debug jika Anda ingin.
>> Tetapi jika Anda hanya mengambil beberapa waktu untuk mendapatkan digunakan untuk itu, hanya bermain-main dengan hal itu,
itu benar-benar akan melayani Anda dengan baik.
Dan itu benar-benar salah satu dari hal-hal yang baru saja Anda
harus mencoba, dan mendapatkan tangan Anda kotor dengan, sebelum Anda benar-benar memahaminya.
Aku benar-benar hanya mengerti sekali Aku harus men-debug hal dengan itu,
dan itu jauh lebih baik untuk memiliki gagasan tentang bagaimana debug lebih awal daripada kemudian.
OK.
Keren.
Aku tahu itu jenis seperti kursus kilat di GDB,
dan saya pasti akan bekerja untuk mendapatkan ini untuk terlihat lebih besar waktu berikutnya.
Keren.
>> Jadi, jika kita kembali ke PowerPoint kami.
Apakah ini akan berhasil?
Awh.
Ya.
OK.
Jadi, jika Anda pernah membutuhkan semua mereka lagi, ada daftar.
Cari begitu Binary, yang semua orang ingat tontonan besar David
merobek buku telepon di setengah.
Saya tidak benar-benar mendapatkan buku telepon lagi,
karena seperti di mana Anda mendapatkan buku-buku telepon hari ini?
Aku benar-benar tidak tahu.
The Binary Search.
Apakah ada yang ingat bagaimana Binary Search bekerja?
Siapapun sama sekali?
Ya?
SPEAKER 5: Anda tahu kapan Anda melihat di mana setengah
itu akan di, Berdasarkan itu, dan menyingkirkan setengah lainnya.
>> SPEAKER 1 Persis.
Jadi, Binary Search, itu jenis a-- --Kami suka menyebutnya membagi dan menaklukkan.
Jadi, apa yang akan Anda lakukan adalah Anda akan melihat di tengah,
dan Anda akan melihat apakah itu cocok apa yang Anda cari.
Dan jika tidak, maka Anda mencoba untuk mencari tahu, apakah akan dibiarkan
setengah atau setengah benar.
Jadi, mungkin ini jika Anda sedang mencari sesuatu yang menurut abjad,
Anda lihat, oh.
Apakah Allison datang sebelum M?
Ya.
Jadi, kita akan melihat babak pertama.
>> Atau bisa juga seperti dengan angka.
Apa pun yang Anda bisa bandingkan, dapat diurutkan.
Anda dapat menggunakan pencarian biner pada.
Jadi, ada yang ingat ini grafik atau apa ini?
Ini Kompleksitas Asymptotic.
Jadi, grafik ini hanya menjelaskan berapa lama
membawa Anda untuk memecahkan masalah karena Anda meningkatkan jumlah hal-hal
yang Anda gunakan.
>> Jadi, kita memiliki N, yang merupakan waktu linier.
Jika N lebih dari dua, yang sedikit lebih baik, masih tumbuh super cepat.
Dan kemudian kami telah Login, yang apa yang kita anggap Binary Search.
Jika kita perhatikan, sebagai masalah Anda mendapat banyak dan jauh lebih besar,
waktu yang dibutuhkan Anda untuk memecahkannya tidak benar-benar meningkat banyak.
Ini seperti sebanding di sini di awal.
Kau seperti, OK.
Apa pun di sini tidak benar-benar penting yang mana yang kita gunakan,
tapi Anda keluar untuk satu juta, satu miliar.
Anda mencoba untuk menemukan --you're some-- berusaha mencari jarum di tumpukan jerami.
>> Saya pikir Anda ingin masalah ini.
Anda ingin kompleksitas ini, tidak linier karena untuk semua Anda
tahu akan Anda dapat mencari melalui setiap jarum individu, hal jerami,
mencoba untuk mencari jarum Anda.
Dan itu tidak terlalu menyenangkan menurut pendapat saya.
Saya suka cepat.
Saya suka efisien.
Dan siswa sebagai pekerja keras Anda orang ini, Anda tahu bekerja lebih cerdas,
bukan lebih keras jenis hal, bagaimana Anda dapat membuat algoritma ini.
>> Jadi, kita akan berjalan melalui hanya contoh cepat.
Saya pikir kalian harus memiliki tangan pada Binary Search,
tetapi dalam kasus ada yang sedikit fuzzy, ingin memperkuat itu,
kita akan hanya pergi melalui contoh di sini.
Jadi, kita cari jika array berisi tujuh.
>> Jadi, hal pertama yang kita lakukan adalah terlihat di tengah, kan?
Dan juga Anda akan coding Pencarian biner hanya dalam hitungan detik.
Jadi, itu akan menyenangkan.
Jadi kita melihat di tengah array kecil 3.
Apakah 3 sama 7?
Tidak.
Ini enam.
Jadi, apakah itu kurang dari atau lebih besar dari tujuh?
Kurang dari.
Ya.
Bagus job guys.
Aku merasa aku seperti aku harus memiliki permen karena saya
ingin membuangnya keluar ke meter.
Itu yang akan saya lakukan minggu depan.
Ini akan membuat kalian tajam.
>> Jadi, kita buang jauh-jauh babak pertama, kan?
itu kurang dari.
kita tahu bahwa segala sesuatu di sisi kiri
akan menjadi kurang dari apa kita benar-benar mencari.
Jadi, tidak perlu untuk memperhatikan itu.
Lupakan saja.
Jadi, sekarang kita melihat sisi kanan kami, dan kami melihat tengah sana,
dan sekarang sembilan.
Jadi, 9 is-- --Everyone?
Lebih besar dari apa yang kita cari, kan?
Jadi, kita akan melemparkan segala sesuatu ke kanan.
Seperti itu.
Sekarang, semua kami pergi dengan adalah satu.
Jadi kita periksa, satu ini apa kita cari? itu.
Kami menemukan apa yang kita inginkan.
Jadi kita sudah selesai.
Bilinear Search.
>> Dan jika Anda perhatikan, kita memiliki tujuh input ada.
Hanya kami butuh seperti tiga kali, tetapi jika Anda melakukan seperti miliar,
kalian tahu berapa banyak langkah itu akan mengambil jika kita memiliki empat miliar hal?
Setiap tebakan?
Ini 32.
32 langkah untuk menemukan sesuatu dalam empat miliar
elemen array karena kekuasaan dua.
Jadi dua adalah 32, adalah empat miliar.
>> Bagaimana begitu cukup gila kau masih dalam seperti jumlah yang cukup kecil dari langkah-langkah
untuk menemukan sesuatu di empat miliar elemen.
Jadi pada catatan, kami tidak akan kode ini
sehingga kalian benar-benar bisa jenis melihat bagaimana ini bekerja.
Baiklah, jadi kalian dapat kode.
Aku akan membiarkan kalian berbicara untuk sedikit.
Kenali orang di sekitar Anda, yang apa yang orang inginkan dari bagian terakhir.
>> Jadi mengenal orang-orang di sekitar Anda.
Bicara untuk sedikit.
Dan semua yang saya inginkan dari Anda orang sekarang hanya
mencoba untuk membuat garis besar pseudocode.
OK?
Whoa.
Semua yang saya inginkan dari kalian adalah Anda hanya akan mengisi dalam kasus ini sementara.
Jadi saya telah menetapkan ini atas dan batas bawah yang
mewakili awal dan akhir array kita.
Dan Anda akan benar-benar loop melalui dan mencari tahu
apa yang kita lakukan dalam while loop ini.
>> Jadi jika Anda dapat mengetahui out-- Saya memiliki petunjuk besar-- apa kasus
yang kita miliki di sini?
Jadi jika Anda ingin mengetahui kasus, kita akan pseudo mereka
dan kemudian kita benar-benar akan kode mereka.
Dan itu akan menjadi, saya berpikir, mudah-mudahan itu akan
menjadi sedikit lebih mudah dari yang Anda harapkan.
Karena itu bukan kode banyak, sebenarnya, yang benar-benar keren.
>> Mm-hm?
>> SISWA: [tak terdengar]?
INSTRUKTUR: Ya.
Ada sesuatu untuk menemukan di tengah.
>> SISWA: Jadi kita bisa menggunakan itu.
OK.
>> INSTRUKTUR: Perfect.
Jadi itulah hal pertama yang perlu kita lakukan.
Jadi menemukan tengah.
Besar.
Jadi Anda memiliki gagasan tentang bagaimana kita mungkin benar-benar menemukan tengah dengan kode?
>> SISWA: Ya.
n lebih dari 2?
INSTRUKTUR: Jadi n lebih dari 2.
Jadi, satu hal yang perlu diingat adalah bahwa batas atas dan bawah Anda.
Kami terus konstriksi bagian dari array yang kita cari untuk.
Jadi n lebih dari 2 hanya akan bekerja untuk hal pertama yang kita lakukan.
Jadi mengambil atas dan bawah ke rekening, bagaimana kita bisa mendapatkan elemen tengah?
Karena kami ingin tengah antara atas dan bawah, kanan?
Mm-hm?
>> SISWA: [tak terdengar].
>> INSTRUKTUR: Jadi kita memiliki beberapa tengah.
Dan itu akan menjadi bagian atas ditambah lebih rendah lebih dari 2.
Mengagumkan.
Di sana kami pergi.
Satu ke bawah garis.
Kalian berada di jalan.
Jadi sekarang kita memiliki kita tengah, apa yang kita ingin lakukan?
Hanya secara umum.
Anda tidak harus kode itu.
Ya.
SISWA: [tak terdengar]?
INSTRUKTUR: Jadi ditambah karena Anda menemukan rata-rata antara dua
dari mereka.
Jadi jika Anda menganggap mereka sebagai jenis peningkatan di dari sisi,
berpikir tentang hal ini saat Anda mendekati tengah, Anda ingin seperti itu.
Jadi jika Anda berada di kedua sisi tengah, dan kami punya seperti 5 dan 7.
Ketika Anda menambahkan mereka bersama-sama Anda mendapatkan 12, Anda membagi dengan 2, adalah 6.
>> Kadang-kadang sulit untuk menjelaskan mengapa yang bekerja,
tetapi jika Anda bekerja melalui contoh kadang-kadang,
itu akan membantu Anda mengetahui apakah itu harus plus atau minus.
Ya.
>> SISWA: [tidak terdengar] persis di tengah
jika mereka memiliki kasus di mana ada banyak nomor yang lebih kecil
dan seperti sejumlah besar?
>> INSTRUKTUR: Jadi semua yang Anda butuhkan adalah tengah array.
Jadi jika Anda memiliki sekelompok angka kecil dan kemudian satu nomor yang benar-benar besar
pada akhirnya, itu tidak masalah.
Yang penting adalah bahwa mereka diurutkan, Anda hanya
ingin melihat tengah array karena Anda masih
mengiris masalah Anda di setengah.
Keren.
Jadi sekarang kita memiliki tengah, apa yang kita lakukan selanjutnya?
>> SISWA: Bandingkan.
INSTRUKTUR: The bandingkan.
Jadi bandingkan menengah ke value_wanted.
Keren.
Jadi Anda lihat di sini kita memiliki nilai ini kami ingin di sini.
Ingat ini adalah array.
Jadi menengah mengacu pada indeks.
Jadi kami ingin melakukan nilai-nilai menengah.
Jangan lupa jika Anda ingin untuk membandingkan, ganda sederajat.
Anda melakukan satu sama kau hanya akan menetapkan kembali,
dan kemudian, tentu saja, itu akan menjadi nilai yang Anda inginkan.
Jadi jangan lakukan itu.
>> Jadi kita akan melihat apakah nilai-nilai di tengah
adalah sama dengan nilai yang kita inginkan.
Jangan lupa kawat gigi Anda.
Dropbox harus pergi.
Jadi apa yang kita lakukan dalam kasus ini?
Jika itu apa yang kita ingin kembali?
Kami mencoba untuk mengatakan.
>> SISWA: Cetak off.
>> INSTRUKTUR: Yah, kita tidak ingin mencetak.
Jadi ini adalah bool sini, jadi kami ingin kembali benar atau salah.
Kami katakan, adalah nomor ini sebuah [? RRA? ?] Jadi jika,
kita hanya mengembalikannya benar.
Jika saya bisa mengeja benar.
>> SISWA: Mengapa Anda tidak akan kembali nol?
INSTRUKTUR: Jadi Anda bisa kembali nol jika Anda inginkan.
Tapi dalam kasus ini karena fungsi kita mengembalikan bool,
kita perlu kembali bisa benar atau salah.
SISWA: Saat Anda mengatakan ekspresi boolean,
dapat Anda mengaturnya sama dengan palsu?
Seperti jika saya ingin mengatakan, jika kondisi ini tidak terpenuhi, seperti tersebut diatas sama palsu.
Apakah akan mengerti jika Anda hanya menempatkan palsu di sisi lain?
INSTRUKTUR: Ya.
Jadi sebenarnya jika Anda pernah melakukan sesuatu
seperti adalah atas atau lebih rendah, yang mengembalikan benar atau salah
dan itu adalah gaya benar-benar buruk untuk katakanlah sama sama benar atau sederajat
sama palsu.
Anda ingin menggunakan hasil tersebut sebagai dirinya sebagai cek Anda.
Tidak apa yang saya inginkan.
Itulah apa yang saya inginkan.
Jadi dalam kasus Anda bertanya tentang sesuatu seperti menyimpan ini dalam c.
>> Jadi jika kita memiliki int main (void) dan sesuatu seperti ini.
Dan Anda miliki jika adalah atas dari beberapa masukan dan Anda
menanyakan apakah Anda dapat melakukan sesuatu seperti ini?
Benar?
SISWA: Saya mencoba untuk melakukannya [tidak terdengar].
Karena jika it's--
INSTRUKTUR: Benar.
Jadi, Anda ingin hal ini menjadi salah, kan?
SISWA: Ya.
INSTRUKTUR: Jadi dalam hal ini Anda ingin mengeksekusi jika itu tidak benar.
Jadi hal yang keren yang Anda lakukan ada ini.
Jadi ingat seru Titik meniadakan hal-hal?
Dikatakan [tak terdengar] berarti tidak.
Jadi jika kita melihat hanya bagian ini di sini, Anda lebih
mengatakan bahwa mengevaluasi ke palsu seperti yang Anda inginkan.
Tidak salah memang benar yang berarti ini akan mengeksekusi.
Apakah itu masuk akal?
SISWA: Ya.
INSTRUKTUR: Awesome.
OK.
Jadi kita hanya bisa kembali benar dalam kasus ini.
Jadi sekarang kita memiliki dua lainnya kasus dalam kasus ini.
Apa dua kasus kami yang lain?
Mari kita melakukannya dengan cara ini.
Jadi mari kita mulai dengan yang lain jika nilai-nilai di tengah
kurang dari nilai yang kita inginkan.
Jadi nilai kita di tengah kurang dari nilai yang kita cari.
>> Jadi yang terikat apakah Anda pikir kita ingin memperbarui?
Atas atau bawah?
Atas?
Jadi sisi mana dari array kita akan melihat?
>> SISWA: Semakin rendah.
>> INSTRUKTUR: Kita kita akan untuk melihat kiri.
Jadi lain jika sedikit nilai kurang.
Jadi nilai tengah Anda di sini kurang dari apa yang kita inginkan.
Jadi kami ingin mengambil sisi kanan array kita.
Jadi kita akan memperbarui batas bawah kami.
Jadi kita akan menetapkan kembali lebih rendah kami.
Dan bagaimana menurutmu lebih rendah harus?
SISWA: Nilai tengah?
INSTRUKTUR: Jadi value-- tengah
SISWA: Ditambah 1.
INSTRUKTUR: --plus 1.
Bisa ada yang bilang saya mengapa kami memiliki itu ditambah 1?
>> SISWA: [? Tidak ada nilai?] lebih sama dengan itu.
>> INSTRUKTUR: Benar.
Karena kita sudah tahu bahwa nilai tengah kami tidak sama dengan
dan kami ingin mengecualikan itu dari semua pencarian berikutnya.
Jika Anda lupa bahwa ditambah 1, ini akan seperti lingkaran tanpa batas.
Dan Anda hanya akan terjebak dalam infinite loop dan kemudian Anda akan segfault
dan hal-hal buruk.
Jadi selalu pastikan bahwa Anda tidak termasuk nilai yang baru saja Anda
memandang.
Jadi kita berhati-hati itu dengan ditambah 1.
>> Jadi sekarang kita memiliki kondisi terakhir kami yang saya selalu demi keamanan
Anda dapat memeriksa di sini, lain jika nilai pada tengah lebih besar dari nilai
kita inginkan.
Itu berarti bahwa kita ingin setengah tangan kiri.
Jadi mana yang akan kita update?
Atas.
Dan apakah yang satu ini akan sama?
Tengah minus 1 karena, Tentu saja, kami ingin
untuk memastikan bahwa kita tidak melihat bahwa nilai tengah lagi.
Dan kemudian kami memilikinya.
Itu saja.
Itu semua pencarian biner adalah.
Ini tidak terlalu buruk, kan?
Hal ini seperti 10 baris kode dengan spasi.
Jadi sangat kuat, sangat berguna, Anda akan akan menggunakannya di salah satu psets Anda nanti.
Mungkin tidak satu ini, tapi nanti.
Jadi mempelajarinya.
Love it.
Ini akan memperlakukan Anda dengan baik.
Jadi tidak ada yang punya pertanyaan pada pencarian biner?
Ya.
>> SISWA: Apa itu penting apakah n Anda bahkan atau ganjil?
>> INSTRUKTUR: No.
Karena kita melemparkannya ke tengah sebagai int, itu hanya akan memotong itu.
Sehingga akan tetap integer dan akan akhirnya memilah-milah semuanya.
Jadi Anda tidak perlu khawatir tentang itu.
Semua orang baik?
Mengagumkan.
Keren.
Jadi, kalian punya ini.
Slideshow.
Jadi seperti yang kita bicarakan, saya tahu David menyebutkan runtimes kompleksitas.
>> Jadi dalam kasus terbaik, itu hanya satu, yang kita sebut waktu yang konstan.
Bisa ada yang bilang saya mengapa yang mungkin?
Apa jenis skenario apakah itu memerlukan?
Mm-hm.
>> SISWA: [tak terdengar] first--
INSTRUKTUR: Jadi tengah menjadi elemen pertama yang kita datang ke, kan?
Jadi baik array satu atau apapun yang kita sedang mencari hanya
kebetulan smack setetes di tengah.
Jadi itu yang terjadi yang terbaik.
Anda masuk ke masalah nyata, mungkin tidak akan mencapai [tak terdengar] yang sering.
Bagaimana dengan kasus terburuk kami?
Kasus terburuk kami adalah log n.
Dan yang ada hubungannya dengan keseluruhan kekuatan dari dua hal yang saya bicarakan.
>> Jadi dalam kasus terburuk itu berarti bahwa kita harus memotong array turun
sampai itu unsur satu.
Jadi kami harus menebang setengah sebanyak yang kita bisa.
Itulah mengapa log n karena Anda hanya terus membagi dua.
Jadi asumsi, hal yang perlu tahu jika Anda pernah
akan menggunakan pencarian biner.
Elemen Anda harus dipilah.
Mereka harus diurutkan karena itulah satu-satunya cara Anda
dapat tahu apakah Anda mampu untuk membuang setengah dari itu.
>> Jika Anda memiliki tas campur aduk ini angka dan kau mengatakan,
OK, aku akan memeriksa tengah jumlah dan nomor yang saya cari
kurang dari itu, aku hanya akan untuk sewenang-wenang membuang satu setengah.
Anda tidak akan tahu jika Anda angka dalam setengah lainnya.
Daftar Anda harus diurutkan.
Selain itu, ini mungkin akan maju sedikit,
tetapi Anda harus memiliki akses acak.
Anda harus dapat langsung pergi ke elemen tengah.
Jika Anda harus melintasi melalui sesuatu
atau membawa Anda langkah tambahan untuk sampai ke elemen tengah,
itu tidak log n lagi karena Anda menambahkan lebih banyak pekerjaan ke dalamnya.
Dan ini akan membuat sedikit lebih masuk akal dalam dua minggu,
tapi aku hanya jenis ingin pengantar, memberikan kalian gambaran tentang apa yang
untuk datang.
Tapi mereka adalah dua asumsi penting
yang Anda butuhkan untuk daftar biner.
Pastikan itu diurutkan.
Itulah yang besar untuk kalian sekarang.
Dan pada bahwa kita dapat masuk ke sisa macam kami.
Jadi empat gelembung sorts--, penyisipan, seleksi, dan gabungan.
Mereka semua agak dingin.
Jika kalian memutuskan untuk mengambil CS 124, Anda akan belajar tentang segala macam macam.
Dan jika Anda seorang penggemar XKCD, ada adalah tentang komik benar-benar keren
seperti macam benar-benar tidak efektif, yang saya sangat menyarankan Anda akan melihat.
Salah satunya adalah seperti panik semacam, yang seperti, oh tidak, kembali acak array.
Sistem Shutdown.
Tinggalkan.
Jadi humor culun selalu baik.
>> Jadi tidak ada yang ingat jenis seperti hanya ide umum
bagaimana bubble sort bekerja.
Kau ingat?
>> SISWA: Ya.
>> INSTRUKTUR: Pergi untuk itu.
>> SISWA: Jadi Anda akan melalui dan jika itu lebih besar, maka Anda menukar dua.
>> INSTRUKTUR: Mm-hm.
Tepat.
Jadi Anda hanya iterate melalui.
Anda memeriksa dua nomor.
Jika salah satu sebelum lebih besar daripada yang setelah itu,
Anda hanya swap mereka sehingga dalam cara ini semua nomor yang lebih tinggi
gelembung menjelang akhir daftar dan semua angka yang lebih rendah gelembung bawah.
>> Apakah dia menunjukkan kalian cool efek suara menyortir Video?
Ini agak dingin.
Jadi seperti Robert hanya mengatakan, algoritma bahwa Anda hanya melangkah melalui daftar,
swapping nilai-nilai yang berdekatan jika mereka tidak dalam rangka.
Dan kemudian hanya terus mengulangi sampai Anda tidak melakukan swap.
Jadi tidak buruk, kan?
Jadi kita hanya memiliki contoh cepat di sini.
Jadi ini akan mengurutkan mereka dalam urutan menaik.
Jadi ketika kita pergi melalui pertama waktu, kita melihat melalui delapan
dan enam jelas tidak dalam rangka, kita swap mereka.
>> Jadi melihat yang berikutnya.
Delapan dan empat tidak dalam urutan.
Swap mereka.
Dan kemudian delapan dan dua, swap mereka.
Di sana kami pergi.
Jadi setelah lulus pertama Anda, Anda tahu bahwa jumlah terbesar Anda
akan menjadi semua jalan di bagian atas karena itu hanya
akan terus-menerus lebih besar dari segala sesuatu yang lain
dan itu hanya akan gelembung up semua jalan ke ujung sana.
Apakah itu masuk akal untuk semua orang?
Keren.
>> Jadi kita melihat lulus kedua kami.
Enam dan empat, switch.
Enam dan dua, switch.
Dan sekarang kami memiliki beberapa hal dalam rangka.
Jadi untuk setiap pass yang kita membuat melalui seluruh daftar kami,
kita tahu bahwa seperti itu banyak nomor pada akhirnya akan telah disortir.
Jadi kita lakukan lulus ketiga, yang merupakan salah satu swap.
Dan kemudian pada keempat kami lulus, kita memiliki nol slot.
Dan kita tahu bahwa kita Array telah disortir.
>> Dan itu adalah besar hal dengan bubble sort.
Kita tahu bahwa ketika kita memiliki nol swap, yang
berarti bahwa segala sesuatu adalah secara lengkap.
Ini semacam bagaimana kita memeriksa.
Jadi kita juga akan kode gelembung semacam yang juga tidak terlalu buruk.
Tak satu pun dari ini adalah bahwa buruk.
Aku tahu mereka bisa tampak sedikit menakutkan.
Aku tahu ketika saya mengambil kelas, bahkan ketika saya
mengajar kelas untuk pertama kalinya tahun lalu,
Aku seperti, bagaimana saya melakukan ini?
Masuk akal dalam teori, tetapi bagaimana kita benar-benar melakukan ini?
Itulah sebabnya aku juga ingin berjalan melalui kode dengan kalian di sini.
Jadi saya memiliki pseudocode sebuah untuk kalian saat ini.
Jadi hanya ingatlah ini sebagai kami tidak akan transisi berakhir.
Jadi kita memiliki beberapa counter yang melacak swap kita,
karena kita perlu memastikan bahwa kita memeriksa itu.
Dan kita iterate seluruh array seperti yang kita hanya melakukan dengan contoh ini.
Jika elemen sebelum lebih besar dari unsur setelah mana kita berada di,
kita swap mereka dan kami kenaikan kami kontra karena segera setelah kami bertukar,
kami ingin membiarkan counter kami tahu itu.
Ada pertanyaan di sana?
Sesuatu tampaknya lucu di sini.
SISWA: Apakah Anda mengatur counter ke nol setiap kali Anda pergi melalui loop?
Apakah Anda tidak terus kembali ke nol setiap kali?
INSTRUKTUR: Belum tentu.
Jadi apa yang terjadi adalah kita pergi ke sini.
Begitu juga saat, ingat, ini akan mengeksekusi sekali tanpa gagal.
Jadi itu akan mengatur kontra sama dengan nol,
maka itu akan beralih melalui.
Seperti iterates melalui, itu akan memperbarui counter.
Seperti update counter, bila dilakukan, ketika itu mencapai akhir dari array,
jika daftar kami belum disortir, counter akan telah diperbarui.
>> Jadi cek kondisi dan berkata, OK, adalah kontra besar dari nol.
Jika ya, lakukan lagi.
Anda ingin me-reset sehingga ketika Anda pergi melalui, counter sama dengan nol.
Jika Anda pergi melalui diurutkan array, tidak ada perubahan,
ini gagal, dan Anda mengembalikan daftar diurutkan.
Apakah itu masuk akal?
SISWA: Ini mungkin dalam sedikit.
INSTRUKTUR: OK.
Jika ada yang lain Pertanyaan yang muncul.
Ya.
>> SISWA: Apa yang akan fungsi bagi swapping elemen?
>> INSTRUKTUR: Jadi kita benar-benar bisa menulis bahwa jika kita akan ke kanan sekarang.
Keren.
Maka pada catatan itu, Alison akan untuk beralih kembali ke alat.
Ini akan menyenangkan.
Dan kami memiliki bagus kami bubble sort hal di sini.
Jadi saya sudah melakukan bersepeda melalui array.
Kami memiliki swap kami yang sama dengan nol.
Jadi kita ingin menukar berdekatan elemen jika mereka rusak.
Jadi, hal pertama yang perlu kita lakukan adalah iterate melalui array kita.
>> Jadi bagaimana Anda pikir kita mungkin iterate melalui array kita?
Kami memiliki untuk dan i sama dengan 0.
Kami ingin saya menjadi kurang dari n minus 1 dikurangi k.
Dan saya akan menjelaskan bahwa dalam satu detik.
Jadi ini adalah optimasi di sini di mana, ingat bagaimana aku mengatakan setelah setiap lulus
melalui kami array yang tahu bahwa apa pun yang on--
>> Jadi setelah satu lulus kami tahu bahwa ini diurutkan.
Setelah dua melewati kita tahu bahwa semua ini diurutkan.
Setelah tiga lewat kami tahu yang diurutkan.
Jadi cara saya iterasi melalui array sini,
adalah itu pastikan untuk hanya pergi melalui apa yang kita tahu adalah tidak disortir.
OK?
Itu hanya sebuah optimasi.
Anda bisa menulis itu naif hanya iterasi melalui segala sesuatu,
itu hanya akan memakan waktu lebih lama.
Dengan empat lingkaran ini itu hanya optimasi bagus
karena kita tahu bahwa setelah setiap penuh iterasi melalui array sini,
seperti setiap lingkaran penuh di sini, kita tahu bahwa satu lagi dari unsur-unsur
akan diurutkan di akhir.
>> Jadi kita tidak perlu khawatir tentang mereka.
Apakah itu masuk akal untuk semua orang?
Itu sedikit trik keren?
Jadi dalam hal ini, jika kita iterasi melalui,
kita tahu bahwa kita ingin memeriksa apakah Array n dan n ditambah 1 adalah dalam rangka.
OK.
Jadi, inilah pseudocode.
Kami ingin memeriksa apakah array n dan n ditambah 1 adalah dalam rangka.
Jadi apa yang kita miliki di sana?
Ini akan menjadi beberapa bersyarat.
Ini akan menjadi jika.
>> SISWA: Jika array n adalah kurang dari array yang n ditambah 1.
INSTRUKTUR: Mm-hm.
Nah, kurang dari atau lebih besar dari.
SISWA: Lebih besar dari.
Kemudian kita ingin menukar mereka.
Tepat.
Jadi sekarang kita masuk ke apa mekanisme untuk swapping mereka?
Jadi kami pergi melalui singkat ini, jenis fungsi pertukaran pekan lalu.
Apakah ada yang ingat bagaimana ia bekerja?
Jadi kita tidak bisa hanya menetapkan kembali mereka, kan?
Karena salah satu dari mereka akan tersesat.
Jika kita mengatakan A sama dengan B dan kemudian B sama dengan A, semua tiba-tiba keduanya
hanya sama dengan B.
>> Jadi apa yang harus kita lakukan adalah kita memiliki variabel sementara itu
akan mengadakan salah satu dari kita sementara kami sedang dalam proses swapping.
Jadi apa yang kita miliki adalah kita akan memiliki beberapa int suhu sama to-- Anda dapat menetapkan
ke mana yang Anda inginkan, hanya pastikan Anda melacak itu--
sehingga dalam kasus ini, aku akan menetapkan ke berbagai n ditambah 1.
Sehingga akan terus apapun Nilai adalah dalam blok kedua
bahwa kita sedang melihat.
>> Dan kemudian bisa kita lakukan adalah kita bisa pergi depan dan array yang Reassign n ditambah 1,
karena kita tahu kita memiliki nilai yang disimpan.
Ini juga salah satu besar things-- Saya tidak tahu apakah ada di antara kalian
memiliki masalah di mana jika Anda beralih dua baris kode tiba-tiba hal-hal bekerja.
Order sangat penting dalam CS.
Jadi, pastikan Anda diagram hal-hal jika mungkin
seperti apa yang sebenarnya terjadi.
Jadi sekarang kita akan menetapkan kembali susunan n ditambah 1,
karena kita tahu kita memiliki nilai yang disimpan.
>> Dan kita dapat menetapkan bahwa array n atau dalam hal ini berbagai i.
Terlalu banyak variabel.
OK.
Jadi sekarang kita sudah ditugaskan kembali array yang i ditambah 1 untuk sama apa yang ada di berbagai i.
Dan sekarang kita dapat kembali dan menetapkan susunan i apa?
Siapa?
>> SISWA: 10.
>> INSTRUKTUR: 10.
Tepat.
Dan satu hal lagi.
Jika kita telah bertukar sekarang, apa yang perlu kita lakukan?
Apa satu hal yang akan memberitahu kita
jika kita pernah mengakhiri program ini?
Apa memberitahu kita bahwa kita memiliki daftar diurutkan?
Jika kita tidak melakukan apapun swap, kan?
Jika swap sama dengan nol pada akhir ini.
Jadi, setiap kali Anda melakukan swap, seperti yang kita hanya melakukan di sini, kami ingin memperbarui swap.
Dan aku tahu ada pertanyaan sebelumnya tentang dapat Anda
menggunakan nol atau satu daripada dari benar atau salah.
Dan itulah yang ini tidak di sini.
Jadi ini mengatakan jika tidak swap.
Jadi, jika swap adalah nol, yang is-- saya selalu mendapatkan kebenaran dan kesalahan-kesalahan saya campur aduk.
Kami ingin kita untuk mengevaluasi untuk benar dan tidak.
Jadi jika itu nol, maka itu palsu.
Jika Anda meniadakan itu dengan [? Bang?] menjadi benar.
Jadi baris ini dijalankan.
>> Kebenaran dan palsu dan angka satu dan nol gila.
Hanya jika Anda berjalan perlahan-lahan melalui itu akan masuk akal.
Tapi itulah yang sedikit ini sedikit kode di sini tidak.
Jadi ini memeriksa untuk melihat telah kita lakukan setiap swap.
Jadi jika apa-apa selain nol, itu akan menjadi palsu
dan semuanya adalah akan mengeksekusi lagi.
Keren?
>> SISWA: Apa istirahat lakukan?
>> INSTRUKTUR: Break hanya istirahat Anda keluar dari loop.
Jadi dalam hal ini akan hanya ingin mengakhiri program
dan Anda akan hanya memiliki daftar diurutkan.
SISWA: Amazing.
INSTRUKTUR: Maaf?
SISWA: Karena sebelumnya kami digunakan ditulis 1 lebih ditulis nol
untuk menyajikan bahwa jika yang akan bekerja atau tidak.
>> INSTRUKTUR: Ya.
Sehingga Anda dapat kembali nol atau 1.
Dalam hal ini, karena kita tidak benar-benar melakukan apa-apa dengan fungsi,
kami hanya ingin istirahat.
Kami tidak benar-benar peduli tentang hal itu.
Rem juga baik jika itu digunakan untuk melanggar
dari empat loop atau kondisi yang Anda tidak ingin terus mengeksekusi.
Itu hanya akan membawa Anda keluar dari mereka.
Itu adalah sedikit dari hal nuansa.
Aku merasa seperti ada banyak melambaikan tangan,
seperti Anda akan belajar tentang hal ini segera.
>> Tapi Anda akan belajar tentang hal ini segera.
Aku berjanji.
OK.
Jadi tidak semua orang mendapatkan bubble sort?
Tidak terlalu buruk.
Iterate melalui, hal Swap menggunakan variabel temp, dan kami sudah siap di sana?
Keren.
Mengagumkan.
OK.
Kembali ke PowerPoint.
Ada pertanyaan secara umum tentang ini sejauh ini?
Keren.
Mm-hm.
>> SISWA: [tak terdengar] int main biasanya.
Apakah Anda harus memiliki untuk ini?
>> INSTRUKTUR: Jadi kami hanya mencari hanya di algoritma sorting yang sebenarnya.
Jika Anda punya itu dalam seperti program yang lebih besar,
Anda akan memiliki tempat utama int.
Tergantung di mana Anda menggunakan algoritma ini,
itu akan menentukan apa yang dikembalikan oleh itu.
Tapi untuk kasus kami, kami benar-benar melihat bagaimana hal ini benar-benar
iterate melalui array.
Jadi kita tidak khawatir tentang hal itu.
>> Jadi kami berbicara tentang kasus terbaik dan skenario kasus terburuk untuk pencarian biner.
Jadi itu juga penting untuk dilakukan bahwa untuk setiap macam kami.
Jadi apa yang menurut Anda adalah yang terburuk kasus runtime dari bubble sort?
Kalian ingat?
>> SISWA: N minus 1.
INSTRUKTUR: N minus 1.
Jadi itu berarti ada n minus 1 perbandingan.
Jadi satu hal yang harus disadari adalah bahwa pada iterasi pertama,
kita pergi melalui, kita membandingkan two-- ini jadi itu 1.
Kedua, tiga, empat.
Jadi setelah satu iterasi kita telah memiliki empat perbandingan.
Ketika saya sedang berbicara tentang runtime dan n.
N merupakan jumlah perbandingan sebagai fungsi dari berapa banyak elemen
kami.
OK?
>> Jadi kami pergi melalui, kita memiliki empat.
Lain kali Anda tahu kami tidak harus mengurus ini.
Kami membandingkan dua ini, kedua, kedua,
dan jika kita tidak memiliki optimasi yang dengan empat lingkaran yang saya tulis,
Anda akan membandingkan di sini anyways.
Jadi, Anda harus dijalankan melalui array
dan membuat perbandingan n n kali, karena setiap kali kita
menjalankan melalui itu kita semacam satu hal.
>> Dan setiap kali kita jalankan melalui array, kita membuat perbandingan n.
Jadi runtime kami untuk ini adalah sebenarnya n kuadrat, yang
jauh lebih buruk dalam kami log end karena
berarti jika kita memiliki empat miliar elemen, itu
akan membawa kita empat miliar squared bukan 32.
Jadi bukan runtime terbaik, tapi untuk beberapa hal,
Anda tahu, jika Anda dalam jarak tertentu dari elemen
bubble sort mungkin baik untuk digunakan.
>> OK.
Jadi sekarang apa yang terjadi runtime terbaik?
SISWA: Zero?
Atau 1?
>> INSTRUKTUR: Jadi 1 akan menjadi salah satu perbandingan.
Tepat.
>> SISWA: N minus 1?
>> INSTRUKTUR: Jadi, ya.
Jadi n minus 1.
Setiap kali Anda memiliki konsep seperti n minus 1, kita cenderung untuk hanya drop off
dan kami hanya mengatakan n karena Anda memiliki untuk membandingkan masing-masing these-- masing-masing pasangan.
Jadi akan n minus 1, yang kami kita hanya akan mengatakan kira-kira n.
Ketika Anda sedang berhadapan dengan runtime, segala sesuatu adalah dalam mendekati.
Selama eksponen benar, kau cukup baik.
>> Begitulah cara kita menghadapinya.
Sehingga kasus terbaik adalah n, yang berarti bahwa daftar tersebut sudah diurutkan,
dan semua yang kita lakukan dijalankan melalui dan memeriksa bahwa itu diurutkan.
Keren.
Baik.
Jadi seperti yang Anda lihat di sini, kita hanya memiliki beberapa grafik lebih.
Jadi n kuadrat.
Fun.
Jauh lebih buruk daripada n seperti yang kita lihat, dan jauh, jauh lebih buruk daripada log 2n.
Dan kemudian Anda juga masuk ke log log.
Dan Anda mengambil 124, Anda masuk ke seperti bintang log, yang seperti orang gila.
Jadi jika Anda tertarik, lookup log star.
Ini semacam menyenangkan.
Jadi kita memiliki grafik yang besar ini.
Hanya kepala up, ini grafik indah untuk memiliki
untuk jangka menengah Anda karena kami lama untuk meminta Anda menipis ini.
Jadi hanya kepala sampai, memiliki ini pada Anda jangka menengah pada bagus lembar contekan Anda
di sana.
Jadi kami hanya melihat bubble sort.
Kasus terburuk, n kuadrat, kasus terbaik, n.
Dan kita akan melihat orang lain.
>> Dan seperti yang Anda lihat, satu-satunya salah satu yang benar-benar baik
adalah semacam penggabungan, yang akan kita masuk ke mengapa.
Jadi kita akan pergi ke berikutnya satu di sini-jenis pilihan.
Apakah ada yang ingat bagaimana Temukan semacam bekerja?
Pergi untuk itu.
>> SISWA: Pada dasarnya melalui perintah dan membuat daftar baru.
Dan seperti Anda meletakkan elemen di, menempatkan mereka di tempat yang tepat
dalam daftar baru.
>> INSTRUKTUR: Sehingga suara lebih seperti insertion sort.
Tapi kau benar-benar dekat.
Mereka sangat mirip.
Bahkan aku mendapatkan mereka bercampur kadang-kadang.
Sebelum bagian ini aku seperti, menunggu.
OK.
Jadi apa yang ingin Anda lakukan adalah semacam seleksi,
cara yang dapat Anda pikirkan tentang hal itu dan cara
Saya memastikan bahwa saya mencoba untuk tidak mendapatkan mereka bercampur, itu berjalan melalui
dan memilih nomor terkecil dan
menempatkan bahwa pada awal daftar.
Hal swap dengan tempat itu pertama.
Mereka benar-benar memiliki sebuah contoh bagi saya.
Mengagumkan.
Jadi hanya cara untuk memikirkan pilihan itu-- semacam, pilih nilai terkecil.
Dan kita akan dijalankan melalui contoh
yang saya pikir akan membantu karena Saya pikir visual selalu membantu.
Jadi kita mulai dengan sesuatu yang benar-benar dipisahkan.
Red akan disortir, hijau akan diurutkan.
Itu semua akan masuk akal dalam satu detik.
>> Jadi kita pergi melalui dan kita iterate dari awal sampai akhir.
Dan kita katakan, OK, 2 adalah nomor terkecil kami.
Jadi kita akan mengambil 2 dan kita akan untuk memindahkannya ke depan array kita
karena itu adalah Jumlah terkecil yang kita miliki.
Jadi itulah apa ini lakukan di sini.
Ini hanya akan menukar kedua.
Jadi sekarang kami telah a diurutkan bagian dan bagian yang tidak dipisahkan.
Dan apa yang baik untuk diingat tentang seleksi semacam
adalah kita hanya memilih dari bagian yang tidak dipisahkan.
>> Bagian diurutkan Anda biarkan saja.
Mm-hm?
>> SISWA: Bagaimana cara mengetahui apa yang terkecil tanpa membandingkannya
untuk setiap nilai lain dalam array.
INSTRUKTUR: Itu membandingkannya.
Kami suka melewatkan itu.
Ini adalah keseluruhan hanya umum.
Ya.
Ketika kita menulis kode saya yakin Anda akan lebih puas.
Tapi Anda menyimpan ini pertama unsur sebagai terkecil.
Anda membandingkan dan Anda mengatakan, OK, itu lebih kecil?
Ya.
Menyimpannya.
Berikut adalah lebih kecil?
Tidak ada?
>> Ini adalah terkecil Anda, menetapkan kembali ke nilai Anda.
Dan Anda akan jauh lebih bahagia ketika kita pergi melalui kode.
Jadi kita pergi melalui, kita swap, jadi kemudian kita melihat bagian disortir ini.
Jadi kita akan memilih tiga.
Kita akan meletakkannya di di akhir bagian diurutkan kami.
Dan kita hanya akan terus melakukan bahwa, melakukan hal itu, dan melakukan hal itu.
Jadi ini semacam kami pseudocode sini.
Kami akan kode itu di sini dalam satu detik.
Tetapi hanya sesuatu untuk berjalan melalui pada tingkat tinggi.
Anda akan pergi dari i sama dengan 0 untuk n minus 2.
Itu optimasi lain.
Jangan khawatir terlalu banyak tentang hal itu.
Jadi seperti yang Anda katakan.
Seperti Yakub berkata, bagaimana kita melacak apa minimum kami adalah?
Bagaimana kita tahu?
Kami harus membandingkan segala sesuatu dalam daftar kami.
>> Jadi minimal sama dengan i.
Ini hanya mengatakan dalam kasus ini indeks nilai minimum kami.
Jadi itu akan beralih melalui dan pergi dari j sama dengan i ditambah 1.
Jadi kita sudah tahu bahwa itu elemen pertama kami.
Kita tidak perlu membandingkannya dengan dirinya sendiri.
Jadi kita mulai membandingkannya dengan berikutnya salah satu yang mengapa itu i ditambah 1 sampai n
minus 1, yang merupakan akhir array sana.
Dan kami mengatakan jika array di j kurang dari array yang min,
maka kita menetapkan kembali di mana indeks minimum kami adalah.
>> Dan jika min tidak sama dengan i, seperti di mana kami kembali ke sini.
Jadi seperti ketika kami pertama kali melakukan satu ini.
Dalam hal ini, itu akan mulai nol, itu akan berakhir menjadi dua.
Jadi min tidak akan sama i pada akhirnya.
Itu memungkinkan kita tahu bahwa kita perlu swap mereka.
Aku merasa seperti contoh konkret akan membantu lebih dari ini.
Jadi saya akan kode ini dengan kalian sekarang dan saya pikir itu akan lebih baik.
>> Macam cenderung bekerja seperti itu dalam itu sering lebih baik hanya untuk melihat mereka.
Jadi apa yang ingin kita lakukan adalah pertama kita ingin terkecil
elemen dalam posisinya dalam array.
Persis apa yang dikatakan Jacob.
Anda perlu untuk menyimpan yang entah bagaimana.
Jadi kita akan mulai di sini iterasi array.
Kita akan mengatakan itu kami pertama hanya untuk memulai dengan.
Jadi kita akan memiliki int terkecil sama dengan berbagai at i.
>> Jadi satu hal untuk melihat, setiap lingkaran waktu ini dijalankan,
kita mulai satu langkah lebih jauh.
Ketika kita mulai kita melihat yang satu ini.
Lain kali kita iterate melalui, kita mulai di satu ini
dan menetapkan nilai terkecil kami.
Jadi itu sangat mirip dengan bubble sort di mana kita tahu bahwa setelah satu lulus,
Unsur terakhir ini diurutkan.
Dengan pemilihan jenis, itu justru sebaliknya.
>> Pada setiap lulus, kita tahu bahwa yang pertama diurutkan.
Setelah lulus kedua, kedua akan diurutkan.
Dan seperti yang Anda lihat dengan contoh slide, bagian kami diurutkan hanya terus tumbuh.
Jadi dengan menetapkan satu terkecil kami untuk array i, semua yang dilakukannya
adalah konstriksi apa kita sedang melihat sehingga
untuk meminimalkan jumlah perbandingan kita buat.
Apakah itu masuk akal untuk semua orang?
Apakah Anda perlu saya untuk menjalankan melalui itu lagi lambat atau dengan kata yang berbeda?
Saya senang untuk.
OK.
>> Jadi kita menyimpan nilai pada saat ini,
tapi kami juga ingin menyimpan indeks.
Jadi kita akan menyimpan posisi terkecil
satu, yang hanya akan menjadi i.
Jadi sekarang Yakub puas.
Kami memiliki hal-hal yang tersimpan.
Dan sekarang kita perlu melihat melalui bagian disortir dari array.
Jadi dalam hal ini ini akan disortir kami.
Ini adalah i.
OK.
>> Jadi apa yang kita akan lakukan akan menjadi untuk loop.
Setiap kali Anda perlu iterate melalui sebuah array,
pikiran Anda bisa pergi ke untuk loop.
Jadi untuk beberapa int k equals-- apa yang kita pikirkan
k akan sama untuk memulai dengan?
Ini adalah apa yang kita ditetapkan sebagai terkecil kami nilai dan kami ingin membandingkannya.
Apa yang kita ingin membandingkannya dengan?
Ini akan menjadi salah satu berikutnya ini, kan?
Jadi kami ingin k diinisialisasi untuk i ditambah 1 untuk memulai.
>> Dan kami ingin k dalam hal ini kita sudah memiliki ukuran yang tersimpan di sini,
jadi kami hanya bisa menggunakan ukuran.
Ukuran menjadi ukuran array.
Dan kami hanya ingin memperbarui k per satu setiap kali.
Keren.
Jadi sekarang kita perlu menemukan elemen terkecil sini.
Jadi jika kita iterate melalui, kita ingin mengatakan, jika array di k
kurang dari value-- terkecil kami ini adalah di mana kita benar-benar
melacak apa yang di sini-terkecil
maka kita ingin menetapkan kembali apa nilai terkecil kita.
>> Ini berarti bahwa, oh, kami iterasi melalui sini.
Apapun nilai di sini adalah tidak hal terkecil kami.
Kami tidak ingin itu.
Kami ingin menetapkan kembali.
Jadi jika kita pemindahan itu, apa yang dilakukan Anda berpikir mungkin dalam kode ini di sini?
Kami ingin menetapkan kembali terkecil dan posisi.
Jadi apa yang terkecil sekarang?
SISWA: Array k.
INSTRUKTUR: Array k.
Dan apa posisi sekarang?
Apa indeks nilai terkecil kita?
Hanya saja k.
Jadi Array k, k, mereka cocok.
Jadi kita ingin menetapkan kembali itu.
Dan kemudian setelah kami menemukan terkecil kami, sehingga pada akhir ini untuk loop
di sini kami telah menemukan apa yang terkecil kami Nilai adalah, jadi kami hanya swap.
Dalam hal ini, seperti mengatakan kami Nilai terkecil adalah di sini.
Ini adalah nilai terkecil kita.
>> Kami hanya ingin menukar sini, yang apa fungsi swap yang di bagian bawah
lakukan, yang kita hanya menuliskan bersama-sama beberapa menit yang lalu.
Jadi harus tampak akrab.
Dan kemudian itu hanya akan iterate melalui sampai mencapai semua jalan
sampai akhir, yang berarti bahwa Anda memiliki nol elemen yang unsorted
dan segala sesuatu yang lain telah disortir.
Masuk akal?
Sedikit lebih konkret?
Kode bantuan?
>> SISWA: Untuk ukuran, Anda tidak pernah benar-benar mendefinisikannya atau mengubahnya,
bagaimana cara tahu?
>> INSTRUKTUR: Jadi satu hal untuk perhatikan di sini adalah ukuran int.
Jadi kami katakan dalam semacam sort-- ini adalah fungsi dalam case-- itu
selection sort, itu berlalu dengan fungsi.
Jadi, jika tidak disahkan , Anda akan melakukan sesuatu
seperti dengan panjang array atau Anda akan iterate melalui
untuk menemukan panjang.
Tetapi karena itu berlalu di, kita hanya bisa menggunakannya.
Anda hanya berasumsi bahwa pengguna memberi Anda ukuran yang valid yang
sebenarnya merupakan ukuran array Anda.
Keren?
>> Jika kalian memiliki masalah dengan ini atau ingin lebih banyak latihan coding macam
Anda sendiri, Anda harus pergi ke study.cs50.
Ini alat.
Mereka memiliki checker yang Anda benar-benar dapat menulis.
Mereka melakukan pseudocode.
Mereka memiliki lebih banyak video dan slide termasuk yang saya gunakan di sini.
Jadi jika Anda masih merasa agak kabur, mencoba yang keluar.
Seperti biasa, datang bicara padaku juga.
Pertanyaan?
>> SISWA: Apakah Anda mengatakan Ukuran yang didefinisikan sebelumnya?
INSTRUKTUR: Ya.
Ukuran yang sebelumnya didefinisikan up di sini di deklarasi fungsi.
Jadi Anda menganggap bahwa itu sudah berlalu dalam oleh pengguna, dan untuk mudahnya,
kita akan berasumsi bahwa pengguna memberi kami ukuran yang benar.
Keren.
Jadi itu semacam seleksi.
Guys, aku tahu kita belajar banyak hari ini.
Ini adalah data yang padat untuk bagian.
Maka dengan itu, kita akan untuk pergi ke insertion sort.
>> OK.
Jadi sebelum itu harus kita lakukan analisis runtime kami di sini.
Jadi dalam kasus terbaik, diberikan karena saya menunjukkan Anda
tabel saya sudah jenis beri tahu.
Tapi kasus runtime terbaik, apa yang kita pikirkan?
Semuanya diurutkan.
N kuadrat.
Ada yang punya penjelasan mengapa menurut Anda?
>> SISWA: Kau membandingkan through--
INSTRUKTUR: Benar.
Anda membandingkan melalui.
Pada setiap iterasi, meskipun kita decrementing ini dengan satu,
Anda masih mencari melalui segalanya untuk menemukan satu yang terkecil.
Jadi bahkan jika nilai terkecil Anda di sini di awal,
Anda masih membandingkannya terhadap segala sesuatu yang lain
untuk memastikan itu adalah hal terkecil.
Jadi Anda akan berakhir berjalan melalui kira-kira n kuadrat kali.
Baik.
Dan apa kasus terburuk?
Juga n kuadrat karena Anda akan untuk melakukan itu prosedur yang sama.
Jadi dalam hal ini, pilihan semacam memiliki sesuatu
bahwa kita juga panggilan runtime yang diharapkan.
Jadi dalam orang lain, kita hanya tahu batas atas dan bawah.
Tergantung pada seberapa gila daftar atau bagaimana unsorted itu,
mereka bervariasi antara n atau n kuadrat.
Kita tidak tahu.
>> Tetapi karena pilihan jenis memiliki sama terburuk dan kasus terbaik, yang memberitahu kita bahwa
Jenis tidak peduli apa input yang kita miliki, apakah itu benar-benar
diurutkan atau benar-benar membalikkan diurutkan, itu
akan mengambil jumlah waktu yang sama.
Jadi dalam hal ini, jika Anda ingat dari meja kami,
itu benar-benar memiliki nilai yang dua jenis ini tidak memiliki,
yang merupakan runtime diharapkan.
Jadi kita tahu bahwa setiap kali kita menjalankan semacam seleksi,
itu dijamin menjalankan waktu n kuadrat.
Tidak ada variabilitas sana.
Hanya saja diharapkan.
Dan, sekali lagi, jika Anda ingin belajar lebih, mengambil CS 124 di musim semi.
Baik.
Kami telah melihat yang satu ini.
Keren.
Semacam Jadi penyisipan.
Dan aku mungkin akan untuk merintis melalui ini.
Aku tidak akan memiliki kalian kode itu.
Kami hanya akan berjalan melalui itu.
Jadi insertion sort adalah jenis dari mirip dengan selection sort
dalam bahwa kita memiliki kedua unsorted dan diurutkan bagian dari array.
>> Tapi apa yang berbeda adalah bahwa seperti yang kita pergi melalui satu per satu,
kami hanya mengambil nomor apapun adalah berikutnya dalam unsorted kami,
dan benar semacam itu ke array diurutkan kami.
Ini akan lebih masuk akal dengan sebuah contoh.
Jadi semuanya dimulai sebagai disortir, hanya suka dengan pilihan semacam.
Dan kita akan menyelesaikan masalah ini dalam urutan menaik seperti yang kita telah.
Jadi pada lulus pertama kami kita mengambil nilai pertama
dan kita katakan, OK, Anda sekarang dalam daftar sendiri.
>> Karena Anda berada dalam daftar sendiri, Anda diurutkan.
Selamat untuk menjadi elemen pertama dalam array ini.
Anda sudah diurutkan semua pada Anda sendiri.
Jadi sekarang kami telah a diurutkan dan sebuah array disortir.
Jadi sekarang kita ambil yang pertama.
Apa yang terjadi antara sini dan di sini adalah bahwa kita berkata,
OK, kita akan melihat nilai pertama dari array disortir kami
dan kita akan masukan dalam nya tempat yang benar dalam array diurutkan.
>> Jadi apa yang kita lakukan adalah kita mengambil 5 dan kita katakan, OK, 5 lebih besar dari 3,
jadi kami hanya memasukkan benar di sebelah kanan itu.
Kita baik.
Jadi kami pergi ke satu kami berikutnya.
Dan kita mengambil 2.
Kita berkata, OK, 2 kurang dari 3, jadi kita tahu bahwa itu
perlu di depan daftar kami sekarang.
Jadi apa yang kita lakukan adalah kita mendorong 3 dan 5 ke bawah dan kami pindah 2 ke slot pertama.
Jadi kami hanya memasukkan ke tempat yang benar seharusnya.
>> Kemudian kita melihat kami berikutnya, dan kita katakan 6.
OK, 6 lebih besar dari segala sesuatu dalam array diurutkan kami,
jadi kami hanya tag pada akhir.
Dan kemudian kita melihat 4.
4 kurang dari 6, itu kurang dari 5 tapi itu lebih besar dari 3.
Jadi kami hanya masukkan langsung ke tengah-tengah antara 3 dan 5.
Jadi untuk membuat sedikit sedikit lebih konkret,
di sini adalah jenis yang ide apa yang terjadi.
Jadi untuk setiap elemen disortir, kita menentukan di mana di bagian diurutkan
itu.
>> Jadi mengingat disortir dan disortir,
kita harus melintasi melalui dan angka tahu di mana cocok dalam array diurutkan.
Dan kita masukkan dengan menggeser elemen di sebelah kanan bawah.
Dan kemudian kami terus iterasi melalui sampai kita
memiliki daftar benar-benar diurutkan mana disortir sekarang nol
dan diurutkan memakan keseluruhan daftar kami.
Jadi, sekali lagi, untuk membuat sesuatu yang lebih konkret, kita memiliki pseudocode.
>> Jadi pada dasarnya untuk i adalah sama dengan 0 sampai n minus 1,
itu hanya panjang array kami.
Kami memiliki beberapa unsur yaitu sebesar array pertama atau indeks pertama.
Kami menetapkan j sama dengan itu.
Jadi sementara j lebih besar dari nol dan array, j minus 1
lebih besar dari elemen, sehingga semua yang melakukan
adalah memastikan bahwa j Anda benar-benar mewakili
bagian disortir dari array.
>> Jadi sementara masih ada hal-hal untuk memilah dan j minus satu is-- apa
adalah elemen nya?
J tidak pernah didefinisikan di sini.
Ini agak menjengkelkan.
OK.
Anyways.
Jadi j minus 1, Anda sedang memeriksa elemen sebelum.
Anda mengatakan, OK, adalah elemen sebelum mana pun aku am-- mari
benar-benar menarik ini.
Jadi, mari kita mengatakan ini adalah seperti pada lulus 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 unsur kami dalam hal ini akan menjadi sama dengan 4.
Dan kami memiliki beberapa j yang akan sama dengan 1.
Oh, j decrementing.
Itulah apa itu.
Jadi j sama dengan saya, jadi apa ini katakan adalah bahwa kita bergerak maju,
kami hanya memastikan bahwa kita tidak lebih dari
pengindeksan dengan cara ini ketika kita mencoba untuk memasukkan sesuatu ke dalam daftar diurutkan kami.
>> Jadi, ketika j sama dengan 1 dalam kasus ini dan Array j dikurangi satu-- sehingga berbagai j dikurangi 1
adalah 2 di case-- ini kalau itu lebih besar dari elemen,
maka semua ini adalah melakukan bergeser segalanya.
Jadi dalam hal ini, berbagai j minus satu akan Array nol, yaitu 2.
2 tidak lebih besar dari 4, jadi ini tidak mengeksekusi.
Jadi pergeseran tidak bergerak ke bawah.
Apa yang dilakukan di sini hanya bergerak array diurutkan ke bawah.
Dalam hal ini, sebenarnya, kita bisa do-- mari kita membuat 3 ini.
Jadi jika kita berjalan melalui dengan contoh ini, kami sekarang di sini.
Hal ini diurutkan.
Hal ini tidak dipisahkan.
Keren?
Jadi saya sama dengan 2, sehingga Elemen kami adalah sama dengan 3.
Dan j kami adalah sama dengan 2.
Jadi kita melihat melalui dan kami mengatakan, OK, adalah array yang j minus satu
lebih besar dari elemen bahwa kita sedang melihat?
Dan jawabannya adalah ya, kan?
4 lebih besar dari 3 dan j adalah 2, sehingga kode ini dijalankan.
>> Jadi sekarang apa yang kita lakukan array di 2, jadi di sini, kita swap mereka.
Jadi kita hanya mengatakan, OK, susunan pada 2 sekarang akan menjadi 3.
Dan j akan sama j minus 1, yang adalah 1.
Itu mengerikan, tapi kalian mendapatkan ide.
J sekarang sama dengan 1.
Dan berbagai j hanya akan menjadi sama dengan elemen kami, yang 4.
Aku terhapus sesuatu yang saya tidak seharusnya memiliki atau sesuatu miswrote,
tapi kalian mendapatkan ide.
>> Bergerak di n.
Dan kemudian jika ini, itu akan loop lagi dan itu akan berkata, OK, j adalah 1 sekarang.
Dan berbagai j minus 1 sekarang 2.
Apakah 2 kurang dari elemen kami?
Tidak ada?
Itu berarti bahwa kita sudah dimasukkan unsur ini
di tempat yang benar dalam array diurutkan kami.
Kemudian kita bisa mengambil ini dan kita katakan, OK, array diurutkan kami di sini.
Dan itu akan mengambil nomor ini 6 dan menjadi seperti, OK, adalah 6 kurang dari angka ini?
Tidak ada?
Keren.
Kami baik-baik.
>> Melakukannya lagi.
Kita mengatakan 7.
Adalah 7 kurang dari akhir array diurutkan kita?
Nomor
Jadi kita baik-baik saja.
Jadi ini akan diurutkan.
Pada dasarnya semua ini tidak adalah itu mengatakan take
elemen pertama dari Array unsorted Anda,
mencari tahu di mana ia pergi dalam array diurutkan Anda.
Dan ini hanya membutuhkan perawatan swap untuk melakukan itu.
Anda pada dasarnya hanya swapping sampai itu di tempat yang tepat.
Gambar visual adalah bahwa Anda bergerak semuanya turun dengan melakukan itu.
>> Jadi seperti setengah bubble sort-esque.
Periksa studi 50.
Saya sangat merekomendasikan mencoba kode ini pada Anda sendiri.
Jika Anda memiliki masalah apapun atau Anda ingin lihat contoh kode untuk jenis penyisipan,
tolong beritahu saya.
Aku selalu sekitar.
Jadi kasus terburuk runtime dan kasus runtime terbaik.
Sebagai pria yang Anda lihat dari meja saya sudah menunjukkan Anda, itu baik n kuadrat dan n.
>> Jadi semacam pergi dari apa yang kita bicarakan tentang dengan macam kami sebelumnya, terburuk
kasus runtime adalah bahwa jika itu benar-benar unsorted,
kita harus membandingkan semua kali n ini.
Kami melakukan banyak perbandingan karena jika itu dalam urutan terbalik,
kita akan mengatakan, OK, ini adalah sama, ini baik,
dan yang satu ini harus dibandingkan terhadap yang pertama untuk dipindahkan kembali.
Dan seperti yang kita dapatkan terhadap ujung ekor, kita harus
untuk membandingkan, membandingkan, dan membandingkan terhadap segala sesuatu.
>> Jadi akhirnya menjadi sekitar n kuadrat.
Jika benar maka Anda mengatakan, OK, 2, kau baik.
3, Anda dibandingkan dengan 2.
Anda baik.
4, Anda hanya dibandingkan dengan ekor.
Anda baik.
6, dibandingkan dengan ekor, kau baik-baik saja.
Jadi untuk setiap titik jika sudah diurutkan, Anda membuat satu perbandingan.
Jadi itu hanya n.
Dan karena kita memiliki kasus runtime terbaik n dan kasus runtime terburuk n
kuadrat, kami tidak memiliki runtime yang diharapkan.
>> Itu hanya tergantung pada kekacauan daftar kami di sana.
Dan lagi, lain grafik dan tabel lain.
Jadi perbedaan antara macam.
Aku hanya akan angin melalui, saya merasa seperti kami sudah bicara secara ekstensif
tentang bagaimana mereka semua jenis dari beragam dan menghubungkan bersama.
Jadi menggabungkan semacam ini yang terakhir Aku akan membuat Anda bosan orang dengan.
Kami memiliki gambaran yang cukup berwarna-warni.
Jadi menggabungkan semacam merupakan algoritma rekursif.
Jadi kalian tahu apa fungsi rekursif adalah?
>> Siapapun ingin mengatakan?
Anda ingin mencoba?
Jadi fungsi rekursif hanya fungsi yang memanggil dirinya sendiri.
Jadi jika kalian sudah familiar dengan deret Fibonacci,
yang dianggap rekursif karena Anda mengambil dua sebelumnya
dan menambahkan mereka bersama-sama untuk mendapatkan satu berikutnya.
Jadi rekursif, saya selalu berpikir rekursi sebagai seperti spiral
sehingga Anda seperti spiral ke dalamnya.
Tapi itu hanya fungsi yang menyebut dirinya.
>> Dan, sebenarnya, benar-benar cepat saya dapat menunjukkan apa yang terlihat seperti.
Jadi rekursif sini, jika kita melihat, ini adalah cara rekursif untuk jumlah lebih dari satu array.
Jadi semua yang kita lakukan adalah kita memiliki fungsi sum
sum yang mengambil ukuran dan array.
Dan jika Anda perhatikan, ukuran decrements per satu setiap kali.
Dan semua hal ini adalah jika x sama dengan zero-- jadi jika ukuran array
sama dengan zero-- ia mengembalikan nol.
>> Selain itu sums ini elemen terakhir dari array,
dan kemudian mengambil sejumlah sisa array.
Jadi itu hanya memecahnya masalah kecil dan lebih kecil.
Singkat cerita, rekursi, fungsi yang memanggil dirinya sendiri.
Jika itu semua yang Anda keluar dari ini, itulah yang fungsi rekursif adalah.
Jika Anda mengambil 51, Anda akan menjadi sangat, sangat nyaman dengan rekursi.
Ini sangat keren.
Masuk akal pada seperti 03:00 satu malam.
Dan aku seperti, mengapa aku tak pernah menggunakan ini?
>> Jadi untuk merge sort, pada dasarnya apa yang akan lakukan adalah itu
akan memecahnya dan istirahat bawah sampai itu elemen hanya satu.
Unsur-unsur tunggal yang mudah untuk menyortir.
Kita melihat bahwa.
Jika Anda memiliki satu elemen, itu sudah dianggap diurutkan.
Jadi pada masukan dari elemen n, jika n kurang dari 2,
hanya kembali karena itu berarti itu 0 atau 1 seperti yang kita lihat.
Mereka dianggap elemen diurutkan.
>> Jika tidak istirahat menjadi dua.
Urutkan babak pertama, memilah kedua setengah, dan kemudian menggabungkan mereka bersama-sama.
Mengapa ini disebut merge sort.
Jadi kita miliki di sini kita akan mengurutkan ini.
Sehingga kita tetap memiliki mereka sampai ukuran array 1.
Jadi ketika itu 1, kita hanya kembali karena ini adalah array diurutkan,
dan ini adalah array diurutkan, dan itu array diurutkan, kita semua diurutkan.
Jadi apa yang kita lakukan adalah kita mulai menggabungkan mereka bersama-sama.
>> Jadi cara Anda dapat berpikir tentang penggabungan adalah
Anda hanya menghapus lebih kecil jumlah masing-masing sub array
dan hanya menambahkan ke array muncul.
Jadi jika Anda melihat di sini, ketika kita memiliki set ini kami memiliki 4, 6, dan 1.
Ketika kita ingin menggabungkan ini, kita melihat ini pertama dua
dan kita katakan, OK, 1 lebih kecil, ia pergi ke depan.
4 dan 6, tidak ada untuk membandingkan untuk, hanya tag pada akhir.
>> Ketika kita menggabungkan kedua, kami hanya mengambil salah satu yang lebih kecil dari dua,
jadi 1.
Dan sekarang kita mengambil lebih kecil dari dua, jadi 2.
Lebih kecil dari dua, 3.
Lebih kecil dari dua, 4, 5, 6.
Jadi Anda hanya menarik dari ini.
Dan karena mereka sudah telah diurutkan sebelumnya,
Anda hanya memiliki satu perbandingan setiap waktu di sana.
Jadi kode lebih di sini, hanya representasi.
Jadi Anda mulai dari tengah dan Anda semacam kiri dan kanan
dan kemudian Anda hanya gabungkan.
>> Dan kita tidak memiliki kode untuk menggabungkan di sini.
Tapi, sekali lagi, jika Anda pergi pada mempelajari 50, itu akan berada di sana.
Jika tidak datang bicara padaku jika Anda masih bingung.
Jadi hal yang keren di sini adalah bahwa kasus terbaik, kasus terburuk, dan runtime yang diharapkan
semua dalam log n, yang jauh lebih baik daripada kita sudah
terlihat untuk sisa macam kami.
Kami telah melihat n kuadrat dan apa yang kita benar-benar
mendapatkan di sini adalah n log n, yang sangat bagus.
>> Lihatlah betapa jauh lebih baik itu.
Seperti kurva bagus.
Jadi jauh lebih efisien.
Jika Anda pernah bisa, gunakan menggabungkan semacam.
Ini akan menghemat waktu Anda.
Kemudian lagi, seperti yang kita katakan, jika Anda turun di daerah yang lebih rendah ini,
itu tidak membuat banyak perbedaan.
Anda bangun untuk ribuan dan ribuan input,
Anda pasti ingin algoritma yang lebih efisien.
Dan, sekali lagi, meja yang indah kami semua macam yang kalian pelajari hari ini.
>> Jadi saya tahu itu merupakan hari yang padat.
Hal ini belum tentu akan untuk membantu Anda dengan pset Anda.
Tapi aku hanya ingin membuat disclaimer Bagian yang tidak hanya tentang psets.
Semua bahan ini adil game untuk ujian tengah semester Anda.
Dan juga jika Anda melanjutkan dengan CS, ini adalah fundamental sangat penting
bahwa Anda akan perlu tahu.
Jadi beberapa hari akan menjadi sedikit pset bantuan lebih lanjut,
tetapi beberapa minggu akan konten jauh lebih aktual
yang mungkin tidak tampak Super berguna bagi Anda sekarang,
tapi aku berjanji jika Anda terus pada akan sangat, sangat berguna.
>> Jadi itu saja untuk bagian.
Ke kawat.
Aku melakukannya dalam satu menit.
Tapi ada Anda pergi.
Dan saya akan memiliki donat atau permen.
Apakah ada yang alergi terhadap apa-apa, by the way?
Telur dan susu.
Jadi donat adalah tidak?
OK.
Baik.
Chocolate ada?
Starburst.
Starbursts baik.
OK.
Kita akan memiliki Starburst minggu depan kemudian.
Itulah yang akan saya dapatkan.
Kalian memiliki minggu yang besar.
Membaca spec Anda.
>> Let me know jika Anda memiliki pertanyaan.
Pset dua kelas harus kepada Anda pada hari Kamis.
Jika Anda memiliki pertanyaan tentang bagaimana saya dinilai sesuatu
atau mengapa saya dinilai sesuatu cara saya tidak, silakan email saya, datang bicara padaku.
Aku ini gila sedikit Minggu, tapi aku berjanji
Saya masih akan menjawab dalam waktu 24 jam.
Jadi memiliki minggu yang besar, semua orang.
Good luck pada pset Anda.