>> HOPARLÖR 1: Hey everyone!
Bölümüne hoş geldiniz.
Burada hem çok görmek sevindim, ve çevrimiçi izliyor herkes.
Yani, her zamanki karşılama arkası gibi.
Hepinize güzel olduğunu umuyoruz geri kalanı tam haftasonu, gevşeme.
Dün dışarı güzeldi.
Yani, ben dışarıda zevk umuyoruz.
>> Duyurular yüzden ilk bir çift.
Puanlama.
Yani, sizin en kazanılmış olması gereken bir Kazı Kazan PSET hakkında benden e-posta,
yanı sıra Pset 1 notlandırma.
Yani, sadece bir kaç şey.
Style50 içinde check50 kullandığınızdan emin olun.
Bunlar olması gerekiyordu Sizin için kaynaklar,
Eğer alıyorsanız emin olmak için Mümkün olduğunca çok puan
gereksiz onları kaybetmeden.
Yani, tarzı gibi şeyler çok önemlidir.
Biz bunun için kapalı almaya gidiyoruz.
Bazılarınız zaten olabilir senin PSET o fark ettim.
Ve check50 bir olduğunu emin olmak için gerçekten kolay yolu
biz aslında dönen konum ne kullanıcıya iade edilmeleri gerekiyor,
ve her şeyin düzgün çalışıyor.
>> İkinci not, emin olun sizin Doğru klasöre şeyler yükleyerek.
Bu benim hayatımı sadece bir yapar biraz daha zor
Eğer PSET 1 içine Pset 2 yüklerseniz Ben şeyler indirmek zaman çünkü,
onlar doğru indirmek yok.
Ve ben biraz sakat olduğunu biliyorum Bir sistemde alışmak için,
ama sadece süper Dikkatli, sadece benim için eğer,
böylece e-posta alıyoruz zaman gibi 02:00 de ve ben sınıflandırma değilim.
Eğer ben bakmak zorunda neden tüm etrafında Pset için.
Serin.
>> Ben erken olduğunu biliyorum, ama ben tamamen gafil çekilen
Bu Cuma nedeniyle olduğunu bir deneme, bu kadar Benim profesör oh yeah, tıpkı edildi.
Unutmayın, bir var Cuma günü nedeniyle deneme.
Yani, ben kimsenin seviyor biliyorum ara sınav hakkında düşünmek,
ancak ilk yarışması, 15 Ekim'de ise hangi Ekim Bu hafta başlıyor.
Yani, er olabilir Eğer beklenenden daha hepsi.
Böylece nöbet sırasında atılır değil Ben, ah önümüzdeki haftaki bölümü söz
senin yarışması önümüzdeki hafta, ben düşündüm Ben daha sana biraz verirdim
Şimdi bir kafaları.
>> Peki, senin sorunun set, üç numara.
İnsanlar okudum nasıl meraktan spec?
TAMAM MI.
Biz bir çift var.
Tür aşağı son gelen Bu ancak bir hafta Tamam.
Ben güzel oldu biliyorum.
Yani Break Out.
Kesinlikle halletmek sonra Bugün en azından senin spec okumak
indirme gibi deneyin Dağıtım kodu ve koşu
ilk ilk gibi onlar sizden bir şey.
Kullandığımız Çünkü Dağıtım kodu ve bir kütüphane
biz sadece --O sadece bu using-- oldum Bu PSET yaptık ikinci kez,
çılgın şeyler olabilir Cihazla birlikte,
ve bunu bulmak istiyorum dışarı şimdi daha sonra karşı.
>> Perşembe gecesi ya da eğer Çünkü Çarşamba gecesi ve nedense
Cihazınız sadece değil kütüphane ile çalıştırmak istiyorum
veya dağıtımda Kod, araçlar olduğunu
hatta kodlama yapmaya başlayabilirsiniz olamaz.
Eğer kontrol edemez çünkü çalışıp çalışmadığını görmek için.
Sizin değil muktedir olacak derler olmadığını görmek için.
Erken olanlar dikkat çekmek istiyorum hafta, hala bana e-posta ne zaman
ya da diğer TF'lerin on, ve biz sabit olanlar alabilirsiniz.
Bu nedenle konular sizi durdurmak için gidiyoruz
Herhangi bir gerçek ilerleme yapmaktan.
O, bir hata gibi değil Eğer sadece tür üzerinde atlayabilirsiniz.
Eğer sorunları yaşıyorsanız sizin Cihaz veya dağıtım kodu,
Eğer gerçekten dikkat almak istiyorum er ya da geç bakımı.
Bu yüzden bile aslında gitmeyecek eğer kodlama başlar, dağıtım indir
Kod, spec okumak, emin olun her şey çalışıyor.
TAMAM MI?
Eğer sadece bunu yapabilirsiniz, ben kolay olacak hayatlarını söz veriyorum.
Ve böylece muhtemelen gidiyoruz Şu anda doğru yapmak?
TAMAM MI.
Yani, orada herhangi bir sorunuz var mı?
Herhangi bir lojistik şeyler?
Herkes iyi?
TAMAM MI.
>> Olanlar için Feragat Odaya ve çevrimiçi.
Ben geçmek için çalışıyor gidiyorum Cihazda PowerPoint arasında
gidiyoruz, çünkü Bazı kodlama yapıyor olmak
anonim popüler talebi bugün öneri anket Geçen hafta dışarı gönderdi.
Yani, bazı kodlama yapıyor olacak.
Yani, siz de isterseniz senin aletleri ateşlemek için,
ve bir e-posta var olmalıdır Bir örnek dosya ile, benden.
Bunu yapmak için çekinmeyin.
>> Peki, biz hakkında konuşmak için gidiyoruz Bir hata ayıklayıcı GDB.
Size yardım edecek tür durumlarda anlamaya
şeyler kodunuzda yanlış gidiyor.
Gerçekten adıma sadece bir yolu var kodunuzu bu oluyor gibi,
ve değişkenleri yazdırmak mümkün ya da aslında neler olduğunu görmek
kaput programı ayetler altında Sadece çalışan, bu faylanma gibi,
ve sen hiçbir fikri gibisin ne sadece burada oldu.
Ben başarısız hangi satır bilmiyorum.
Yanlış nereye gitti bilmiyorum.
Yani, GDB bu konuda size yardımcı oluyor.
Ayrıca, karar verirseniz evet devam ve 61 almak,
Gerçekten, gerçekten olacak senin En iyi arkadaşım, sana söyleyebilirim çünkü
Ben bu sınıfın içinden gidiyorum çünkü.
>> Biz ikili bakmak için gidiyoruz arama, siz hatırlarsanız
harika bir telefon defteri örneği sınıf gözlük.
Biz uygulama ve olacak biraz daha o yürürken,
ve sonra dört ile gidiyoruz Kabarcık farklı sıralar,
Seçim, Ekleme ve Birleştirme.
Serin.
Yani, bahsettiğim GDB gibi, bir ayıklama aracıdır.
Ve bu büyük türüdür şeyler, büyük fonksiyonlar ve komutlar
Eğer GDB içinde kullanmak ve ben yürüyeceğim ki Bir saniye içinde bunun bir demo ile.
>> Peki, bu sadece değil, soyut kalmak olacak.
Ben denemek ve beton gibi yapacağız Sizin için mümkün olduğunca.
Yani, kırmak.
Ya sonu olacak gibi, bazı sayı, hangi
, programınızda bir çizgi temsil ya da bir işlev adlandırabilirsiniz.
Yani, ana kırmak derseniz, o ana duracak
ve bu işlevi üzerinden geçelim.
>> Aynı şekilde, bazı dış varsa Swap veya Cube gibi işlev,
Geçen hafta baktı ki.
Eğer onlardan biri kırmak derseniz, Program vurur zaman, o
o sizin için bekleyeceğim ne yapacağını söyle.
Sadece bu kadar çalıştırır önce Aslında fonksiyonu içinde adım olabilir
ve neler bakın.
Yani, Sonraki, biraz üzerinde atlar Bir sonraki satır, fonksiyonları üzerinde gider.
Adım.
Bunların hepsi küçük soyut.
Yani, ben sadece içlerinden çalıştırmak için gidiyorum, ama bir saniye içinde kullanıma bunları görürsünüz.
>> Bir işlev adım.
Yani ben diyordum, Takas ile, it would gibi
aslında sen sanki izin gibi fiziksel içinde adım,
Bu değişkenler ile yapabilirsiniz karmaşa, baskı onlar ne, neler oluyor bakın.
Liste anlamıyla sadece basacaktır Çevredeki kod dışarı.
Yani, ne tür unutursanız Eğer programda nerede,
ya merak ediyorsanız ne etrafında oluyor
Bu sadece bir segment yazdırılır ve çevresinde beş veya altı hatları gibi.
Yani, odaklı alabilirsiniz nerede hakkında.
>> Bazı değişken yazdırın.
Yani, anahtar gibi varsa Sezar, biz bakacağız ki.
Sen herhangi bir noktada Yazdır Anahtarını söyleyebiliriz.
Değeri öylesine ne söyleyeceğim Bu, belki bir yerde yol boyunca,
Eğer anahtar overwrote.
Aslında çünkü söyleyebilirim aslında bu değeri gözlemleyebiliriz.
>> Halk olarak, sadece baskılar Yerel değişkenler dışarı.
Yani, her bir döngü içinde olduğunu, ve sadece, oh gibi görmek istiyorum.
Benim ben nedir?
Bu anahtar değeri nedir Ben burada başlatmak mı?
Bu noktada mesajı nedir?
Bu sadece tüm basacaktır Bunların, bu yüzden size o
tek gerekmez Baskı I. Baskı Mesaj, söylüyorlar.
Baskı Anahtarı.
Ve sonra görüntüler.
Ne o yapar senin gibidir Programın adım adım,
sadece bu kadar emin olacağım belli değişken görüntüleme
Her noktada.
Böylece siz --O var also-- Bir kısayol nerede tür
oh gibi devam etmek zorunda değilsiniz.
Baskı Anahtarı veya Baskı I. Sadece Senin için bunu otomatik olarak olur.
>> Peki, bu, biz gidiyoruz Bu nasıl gider görmek için.
Ben denemek ve anahtar gidiyorum Benim cihazın üzerinde.
Ben bunu görün.
Tüm.
Biz sadece bunu yansıtmak için gidiyoruz.
Çılgın bir şey yok Benim laptop durumda.
TAMAM MI.
Bu, tek olmalıdır.
Çok küçük.
Bunu yapabilirim görelim.
>> Tamam.
Alice açıkça mücadele Burada biraz,
ama biz bir momento onu alırsınız.
TAMAM MI.
Biz sadece bu artırmak için gidiyoruz.
TAMAM MI.
Herkes tür olduğunu görebilir miyim?
Belki biraz?
Ben biraz küçük olduğunu biliyorum.
Oldukça bilemiyorum Bu büyük yapmak nasıl.
Herkes bilir.
Herkes büyük yapmak nasıl biliyor mu?
TAMAM MI.
Biz onunla rulo gidiyoruz.
Sadece çünkü zaten Farketmez o çocuklar gerektiğini kodu
vardır.
>> Daha da önemlisi Burada terminal.
Ve biz neden bu kadar küçük burada var?
Ayarlar.
Ah.
Gerçek Ike.
Bu nasıl?
Oradan.
Bu herkes için daha iyi mi?
TAMAM MI ,.
Serin.
>> Eğer bir CS olduğunuzda biliyorum sınıf teknik zorluklar
Şeyin tür bir parçasıdır Yani, en bu temizleyin edelim.
TAMAM MI.
Yani, burada bölümünde, hangi biz burada vardı.
Sezar, bir yürütülebilir dosyadır.
Yani ben yaptım.
Yani, GDB ile gerçekleştirmek için bir şey o sadece yürütülebilir dosyalarda çalışır.
Yani, bir dotsy çalıştırmak edemez.
Aslında yapmak zorunda senin kodu derler emin olun,
ve aslında çalıştırılabilir.
>> Peki, eğer bu olmuyorsa emin olun derlemek, derlemek için olsun,
böylece tür içinden çalıştırabilirsiniz.
Yani, GDB başlatmak için, tüm yapmanız, Gloria tipi GDB, ve sonra sadece
İstediğiniz dosya.
Ben her zaman Sezar yanlış yazılan.
Ama emin olmak bir çalıştırılabilir beri,
ti en nokta flaş böylece Eğer gidiyoruz demektir
CSI yürütmek için gidiyoruz çalıştırmak için Bu hata ayıklayıcı ile ya dosyaları.
TAMAM MI.
Yani, o, sen alırım anlamsız bu tür.
Bu hata ayıklayıcı hakkında sadece her şeyi var.
Gerçekten gerek yok Şu anda bu konuda endişe.
Gördüğünüz gibi, biz bu var Açık Pars, GSYİH, yakın Pars,
ve sadece tür gibi görünüyor Bizim komut satırı, değil mi?
>> Peki, biz sanıyor- ne istiyor --Yani, Ilk şey
biz seçmek istiyoruz olduğunu Bir yerde bunu kırmak için.
Yani, bir hata var Bu Sezar programında
Ben, o tanıtmak biz öğrenmek için gidiyoruz.
O girdi sürer o neyi Tüm kapaklar Barfoo ve nedense
o sadece yaprakları A. değişmez tek başına, doğru her şey var
ancak ikinci mektup Bir değişmeden kalır.
Yani, biz denemek için gidiyoruz ve olduğunu anlamaya.
Yani, ilk şey genellikle Eğer GDB günü başlayacak her yapmak istiyorum
Bunu kırmak için nereye anlamaya olduğunu.
>> Peki Sezar oldukça kısa bir programdır.
Biz sadece doğru bir işlevi var?
Sezar bizim işlevi neydi?
Sadece bir fonksiyon, Ana hakkı var?
Ana bir fonksiyonudur Tüm programlar için.
Eğer Main yoktu, ben belki Bir endişeli biraz şimdi olacak,
ama hepsi orada Main vardı umuyoruz.
Peki, ne yapabiliriz biz yapabilirsiniz olduğunu Sadece bunun gibi, Main kırmak.
Yani, tamam, diyor.
Biz orada bizim kesme bir set.
>> Peki, hatırlamak şimdi bir şey Caesar tek bir komut satırı argümanı hakkını alır
ve biz her yerde henüz o yapmadım.
Yani, ne zaman olduğunu aslında çalıştırmak gitmek
Program, sen herhangi bir program GDB çalışan bu komut satırı ihtiyacı
argümanlar, girmek için gidiyoruz zaman ilk çalıştırmaya başlamak.
Yani, bu durumda, var Üç anahtar ile çalıştırın.
Ve aslında başlayacak.
Burada gördüğünüz takdirde >> Yani, biz var RC 2 eşit değilse.
Yani hepiniz varsa Ben dışarı gönderdi bu dosya
Eğer böyle olduğunu göreceksiniz İlk satır ana işlevi, değil mi?
Biz olup olmadığını görmek için kontrol ediyor argüman doğru sayısı.
Yani, merak ediyorsanız RC doğru olup olmadığını,
Sadece Baskı RC gibi bir şey yapabilirsiniz.
RC olan iki Biz doğru ne bekleniyor?
>> Peki, biz, ileri gidebilirsiniz ve içinden devam edin.
Yani, orada bazı anahtar var.
Ve bizim anahtar yazdırabilirsiniz Doğru olduğundan emin olmak için.
İlginç.
Değil tamamen ne bekleniyor.
Yani, bir şey fark Ayrıca GDB ile, bir
Aslında vurmak kadar olmadığını Sonraki, o sadece gördüm çizgi
Aslında yürütülür.
Yani, bu durumda Key Henüz atanmamış.
Yani, Key bazı çöp değeri Orada altta gördüğünüz.
Negatif $ 120-- --O en bir milyar ve bir şey garip şeyler değil mi?
Biz bekleniyor Anahtar değil.
Ama biz İleri'yi vurdu, ve eğer biz deneyin ve Yazdır tuşuna, bu üç var.
>> Herkes görüyoruz?
Yani, bir şey alırsanız Eğer gibi olduğunu, bekle.
Bu tamamen Yanlış, ben bilmiyorum
Ben hepsini istiyorum çünkü bu olacağını nasıl Bir numara atamak yapmak için, değişken,
yazdırmayı deneyin, ileri vurmak deneyin İşe yarayıp yaramadığını tekrar, ve bakın.
Sadece çalıştırmak için gidiyor çünkü aslında sonra bir şey atamak
İleri çarptı.
Herkese mantıklı?
Ha?
>> HOPARLÖR 2: Ne zaman rastgele sayılar ne demek?
>> HOPARLÖR 1: Sadece rastgele değil.
Sadece çöp var.
Sadece bir şey olduğunu, sizin Bilgisayar rastgele atar.
Serin.
Yani, şimdi biz aracılığıyla hareket, ve böylece edebilirsiniz Şimdi biz bu düz metin GetString var.
Yani, bana sadece tanıştırayım ne biz burada İleri vurduğunuzda olacak.
Bizim GDB tür sağ, kaybolur?
Bu getString çünkü var Şimdi yürütülüyor, değil mi?
Gördüğümüz Yani, düz metin eşittir GetString, açık Pars ve Pars,
ve biz ileri vurmak, o vardır Aslında şimdi idam.
Yani, o bekliyor Giriş şey bizi.
>> Peki, biz girişine bizim gıda gidiyoruz hangi Sana söylediğim gibi o başarısız ne olduğunu
ve bu sadece olduğunu söylüyor kapalı olduğu, yürütme bitmiş
braket bu demektir Bu döngünün dışına çıkmadan.
Ben Yani, biz, şimdi ileri vurmak, ve olabilir emin Sezar tanıdık tüm konum,
Bu yapacağımız bu çizgi ne olduğunu.
Int I 0 eşittir için It, N eşittir Strlen, düz metin, ve sonra
I, n, I, ayrıca, ayrıca daha azdır.
Yapacaksın bu döngü nedir?
Mesajınızı açın.
Serin.
Yani, bunu yaparken başlayalım.
>> Peki, bu durum gerekir Bizim ilki için, maç?
Bir B ise, bu düz metin I. Biz bulunuyor Bizim halk hakkında bilgi alabilirsiniz.
Yani, ben sıfır ve, altı ise hangi Beklediğimiz, ve bizim anahtar üçtür.
Mantıklı Bütün, değil mi?
Bu numaralar hepsi tam olarak ne olması gerektiği.
Yani, mırıldanır?
HOPARLÖR 3: Ben var maden için rastgele sayılar.
HOPARLÖR 1: Peki, biz --we check-- olabilir Bir saniyede bu konuda sohbet edebilirsiniz.
Ama bu almak olmalıdır.
Yani, biz bir sermaye varsa İlk bir B,
Bu durum doğru, onu yakalamak gerekir?
Biz İleri vurmak Yani, biz görmek Bu ise aslında yürütür söyledi.
Eğer takip ediyorsanız Çünkü kodunuzda birlikte,
Burada bu hat, nerede düz metin I Bu aritmetik ile değiştirilir,
Sadece If eğer yürütür durum doğru hakkı nedir?
>> GDB sadece size göstermek için gidiyor aslında yürütme şeyler.
Bu ise koşul yerine değildi eğer öyleyse, bu kadar Sadece bir sonraki satıra atlamak için gidiyoruz.
TAMAM MI?
Yani, biz var.
Bu braket bu demektir Şimdi bu döngünün dışında kapalı.
Yani, tekrar başlatmak için gidiyor.
Sadece böyle.
Yani, biz bilgi alabilirsiniz Burada bizim yerliler hakkında,
ve bizim ilk görüyoruz mektup, sağ değişti?
Olması gerektiği gibi, şimdi bir e var.
Yani, biz devam edebilirsiniz.
>> Ve biz bu onay var.
Ve bu onay sağ, çalışması gerekir?
It değiştirilmesi gerekir A. bulunuyor ileri üç harf.
Ama, biz fark ederseniz Farklı bir şey olsun.
Burada bu durumda yukarı Yani, o yakaladı o, ve böylece bu hat, idam
Bizim B. modifiye hangi Ancak burada, bu durumda,
biz sadece atlanır ki var, ve [gitti? L SIFF. ?]
Yani bir şey var oluyor.
Ne olduğunu söylüyor olduğunu, Biz burada yakalamak gerektiğini biliyorum
ama değil.
Herkes ne görebiliyor bizim Sorun bu hat var?
Çok dakikalık bir şey.
Ve ayrıca kod bakmak olabilir.
Ayrıca ne çizgi unutmak line-- var orada-- ama o [Inaudible] öyle.
Evet?
>> HOPARLÖR 4: Bu daha büyük üzerinde bulunuyor Sayfayı kitapta okursanız.
HOPARLÖR 1: Kesinlikle.
Yani, hata ayıklayıcı anlayamadı Bunu, ancak hata ayıklayıcı
Bir çizgiye aşağı alabilir Eğer çalışmıyor biliyorum.
Ve bazen, özellikle Daha sonra dönem içinde
Eğer yüz bir ile uğraşıyoruz birkaç yüz kod satırları, ve
o başarısız nerede bilmiyorum, bunu yapmak için harika bir yoldur.
Yani, bizim hata buldum.
Sen, senin dosyasında çözebilirsiniz ve sonra, tekrar çalıştırabilir
ve her şey mükemmel çalışacak.
Ve en büyük şey Bu tamam gibi görünebilir.
Evet.
Serin.
Sizin için ne arıyorsanız biliyordu.
Yani, ne yapacağını biliyordu.
>> GDB çünkü sen süper yararlı olabilir Bütün bunları yazdırabilirsiniz ki sen
olmaz.
Bu çok daha kullanışlı printf daha var.
Kaç kullandığınız bir printf tablolar gibi
Bir hata, haklıydı nerede olduğunu anlamaya?
Yani, bu, sen yok geri devam etmek zorunda,
ve yorumlama gibi Printf, ya da dışarı yorumlama
ve anlamaya ne Eğer baskı olmalıdır.
Bu aslında sadece size izin verir , adım adım şeyler yazdırmak
Eğer üzerinden gidiyoruz gibi, yani, sen yapabilirsiniz gerçek zamanlı olarak nasıl değiştiğini gözlemlemek,
Programınızın olarak çalışıyor.
>> Ve biraz sürer alışmak biraz.
Ben çok sadece tür tavsiye ederim onunla birlikte biraz sinirli olmak
şimdi için.
Eğer üzerinden bir saat harcamak Gelecek hafta nasıl GDB kullanmayı öğrenme,
kendinizi kurtaracak Daha sonra bu kadar zaman.
Ve tam anlamıyla. Biz haber Bu insanlar her yıl,
Ben aldı ve ben hatırlıyorum Sınıf, ben iyi olacak gibi oldu.
Hayır.
Pset 6 geldi ve ben gibi, ben öğreneceksin ediyorum
I do not çünkü GDB nasıl kullanılacağı Burada neler oluyor biliyor.
>> Bunu zaman alır Yani eğer küçük programlar üzerinde kullanabilirsiniz
olmak için gidiyoruz çalışma gibi, çalışan
gibi bir şey aracılığıyla Böyle Visionare.
Ekstra uygulama istiyorsanız Veya, eminim Ben, adamcağız programları ile gelebilir
Eğer isterseniz sizin için debug.
>> Ama sadece biraz zaman ayırın almak için Bunun için kullanılan, sadece onunla oynamak,
Gerçekten de size hizmet edecektir.
Ve bu gerçekten biri Bu işler o sadece
denemek zorunda, ve ellerinizi kirli olsun Eğer gerçekten anlamak önce, ile.
Ben gerçekten sadece bir kez anladım Ben, onunla hata ayıklama şeyler vardı
ve bunun bir fikrim yok çok daha güzel nasıl er geç ayıklamak için.
TAMAM MI.
Serin.
Ben bu tür benzeri biliyorum GDB bir kurs,
ve ben kesinlikle alma çalışacak Bu büyük bir dahaki sefere bakmak için.
Serin.
>> Peki, biz geri PowerPoint giderseniz.
Bu işe gidiyor?
Awh.
Evet.
TAMAM MI.
Yani, hiç herhangi bir ihtiyacınız olursa Bu tekrar, liste var.
Yani İkili Arama, hangi herkesin David büyük gözlük hatırlar
yarısında telefon rehberlerini müthiş.
Ben gerçekten alamadım Artık telefon kitaplar,
do you nerede gibi çünkü bu gün telefon kitapları olsun?
Ben gerçekten bilmiyorum.
İkili Arama.
Herkes hatırlıyor mu nasıl İkili Arama çalışmaları?
Herkes hiç?
Evet?
HOPARLÖR 5: zaman bilmek hangi yarısı bakmak
o dayanarak, olurdu, ve diğer yarısı kurtulmak.
>> HOPARLÖR 1 Kesinlikle.
Yani, İkili Arama, bunun bir-- tür --we bölmek ve fethetmek diyoruz.
Yani, yapacağım ne Eğer ortada bakarız
Eğer maç ve göreceksiniz ne için arıyoruz.
Eğer bu olmuyorsa, o zaman deneyin anlamaya, sola olacak
yarım veya sağ yarısı.
Eğer arıyorsanız Yani, bu olabilir alfabetik oluyor şeye,
oh, bakın.
Allison M önce mi geliyor?
Evet.
Yani, biz gidiyoruz İlk yarıda bak.
>> Yoksa numaraları ile benzeri olabilir.
Her şey o yapabilirsiniz karşılaştırmak, bu sıralanabilir.
Üzerinde ikili arama kullanabilirsiniz.
Yani, herkes bu hatırlamak grafiği ya da bu ne?
Bu asimptotik Karmaşıklık var.
Yani, bu grafik sadece ne kadar açıklar o
gibi bir sorunu çözmek için alır Eğer şeylerin sayısını artırmak
Bu kullandığınız.
>> Peki, biz doğrusal zaman N, var.
Hafifçe üzerinde iki N, varsa Daha iyi, hala süper hızlı büyür.
Ve sonra olan Girişi var ne İkili Arama düşünün.
Biz fark ederseniz, sizin sorun olarak çok ve çok daha fazla olur
o sizi zaman bunu çözmek için Gerçekten bu kadar artmaz.
Bu karşılaştırılabilir gibi Burada başında.
Tamam, gibisin.
Her şey burada gerçekten yok madde hangi kullandığımız bir,
ancak, bir milyon bir milyar çıkmak.
Sen some-- --you're bulmaya çalışıyoruz samanlıkta iğne bulmaya çalışıyor.
>> Ben bu sorunu istiyorum düşünüyorum.
Bu karmaşıklık, değil istiyorum lineer nedeniyle tüm sizin için
senin olacak aracılığıyla arıyor olması biliyorum her iğne, saman şey,
senin iğne aramaya çalışıyor.
Ve bu bence çok eğlenceli değil.
Ben hızlı seviyorum.
Ben verimli seviyorum.
Ve çalışkan öğrenciler size çocuklar, akıllıca çalışmak biliyorum, vardır
zor değil türü bir şey, nasıl Bu algoritmalar kadar yapabilirsiniz.
>> Peki, biz yürümeye gidiyoruz sadece hızlı bir örnek üzerinden.
Sizlerin olması gerektiğini düşünüyorum İkili Search bir el,
ancak durumda herkes biraz bulanık, bunu güçlendirmek istiyoruz,
biz sadece gitmek için gidiyoruz Burada bir örnek üzerinden.
Eğer Yani, biz arıyoruz Dizi yedi içerir.
>> Peki, biz ne ilk şey Doğru, ortada bak?
Ve ayrıca kodlama için gidiyoruz Sadece bir saniye İkili Arama.
Yani, eğlenceli olacak.
Yani biz bakmak Orta küçük diziler 3.
3 7 ile aynı mı?
Değil mi.
Altı var.
Bu yüzden, daha az olduğu veya yedi daha büyük?
Daha az.
Evet.
Güzel iş adamlar.
Ben gerektiğini gibi hissediyorum şeker var, çünkü ben
metre içine atmak istiyorum.
Ben önümüzdeki hafta yapacağım budur.
Bu keskin Sizi devam edecektir.
>> Peki, biz atmak İlk yarı, değil mi?
o daha az oldu.
biz her şeyi biliyoruz O sol tarafta
daha az olacak ne biz aslında arıyoruz.
Yani, gerek orada var buna dikkat.
Sadece unutun.
Yani, şimdi bizim sağ tarafına bakarsanız, ve biz, oraya orta bakmak
ve şimdi dokuz bulunuyor.
Böylece, 9 o-- --Everyone?
Biz ne konum Büyüktür Doğru, arıyor?
Yani, biz atmak için gidiyoruz sağa uzakta her şeyi.
Bu gibi.
Şimdi, hepimiz biridir kalacaksın.
Yani biz kontrol bu ne biz arıyoruz? öyle.
Biz ne istediğini bulundu.
Bu yüzden bitti.
Bilineer arayın.
>> Ve dikkat ederseniz, biz Orada yedi girişleri vardı.
Sadece, üç kez gibi götürdüler ama bir milyar gibi yapıyoruz,
Siz kaç adım it would biliyorum Biz dört milyar şeyler olsaydı almak?
Herhangi bir tahmin?
Bu 32 var.
Bir şey bulmak için 32 adım bir four milyar
Çünkü iki güçlerin unsuru dizisi.
Yani iki 32 dört milyar olduğunu.
>> Hala içinde olduğunu nasıl Yani oldukça çılgın adımlar oldukça küçük bir rakam gibi
bir şey bulmak için dört milyar elemanları.
Bu notu Yani, biz konum Bu kod gidiyor
böylece siz aslında can tür, bu nasıl çalıştığını görmek.
Pekala, siz kod böylece.
Size bir izin gidiyorum biraz konuşmak.
Olan çevrenizdeki insanları tanıyın ne kimse son bölümde istedik.
>> Yani çevrenizdeki insanları tanımak.
Biraz konuşmak.
Ve tüm Senden istiyorum adamlar şu anda sadece bir
pseudocode bir taslağını oluşturmaya çalışın.
TAMAM MI?
Vay.
Sizlerle istediğiniz tüm sen olduğunu Sadece bu süre durumda doldurmak için gidiyoruz.
Yani bu üst belirledik ve alt sınır olan
başlangıcını temsil Bizim dizinin ve bitiş.
Ve aslında olacak döngü yoluyla ve anlamaya
ne bu süre döngü içinde yapıyoruz.
Eğer bir konrtol anlamaya Yani eğer >> Ben var durumlar ne orada-- bir ipucu
biz burada var?
Eğer anlamaya istiyorsanız durumlarda, biz o yalancı kod olacak
ve sonra biz aslında onları kod olacak.
Ve o olacak, ben umarım olacak, düşünmek
beklediğinizden daha biraz daha kolay olacak.
, O kadar kod değil, çünkü Aslında, bu gerçekten iyidir.
>> Hı-hm?
>> ÖĞRENCİ: [duyulamaz]?
EĞİTMEN: Evet.
Bir şey vardı ortasında bulmak için.
>> ÖĞRENCİ: Yani bunu kullanabilirsiniz.
TAMAM MI.
>> ÖĞRETİM: Mükemmel.
Yani yapmamız gereken ilk şey.
Yani orta bulmak.
Büyük.
Yani bir fikrin var mı nasıl olabilir Aslında kodu ile orta bulmak?
>> ÖĞRENCİ: Evet.
2 üzerinde n?
EĞİTMEN: Yani n üzerinde 2.
Yani hatırlamak için bir şey olduğunu üst ve alt sınırları değiştirmek.
Biz kısmını daraltıcı devam Dizinin biz arıyoruz.
Yani n üzerinde 2 sadece çalışacak ilk şey için yapıyoruz.
Yani hesaba üst ve alt alarak, nasıl ki orta elemanı alabilirsiniz?
Biz orta istiyorum çünkü Üst ve alt, sağ arasında?
Mm-hm?
>> ÖĞRENCİ: [duyulamaz].
>> EĞİTMEN: Bu yüzden bazı orta var.
Ve üst artı 2 üzerinde düşük olacak.
Korku.
Biz oraya gitmek.
Bir satır aşağı.
Siz yolda.
Yani şimdi bizim var Orta, ne yapmak istiyorsun?
Sadece genel olarak.
Bunu kod gerekmez.
Evet.
ÖĞRENCİ: [duyulamaz]?
EĞİTMEN: Yani var artı çünkü İki arasındaki ortalama bulma
Bunların.
Yani siz bir tür onları düşünüyorsanız taraftan artan bir,
Eğer yaklaşım olarak düşünmek orta, böyle istiyorum.
Yani eğer siz iki tarafında vardı orta ve 5 ve 7 gibi şeyler göstermeleridir.
Size bunları birlikte eklediğinizde 12 olsun, sen 2 ile bölmek, 6.
>> Bazen zor çalıştığını açıklamak,
ama içinden çalışıyorsanız Bir örnek olarak, bazen
Eğer olmadığını anlamaya yardımcı olacak Bu artı ya da eksi olmalıdır.
Evet.
>> ÖĞRENCİ: [Duyulmaz] tam ortasında
nerede bir olgu olsaydı küçük sayılar çok şey var
ve büyük bir numarası gibi?
>> EĞİTMEN: Yani tüm ihtiyacınız Dizinin ortasıdır.
Yani küçük sayılar bir grup vardı ve sonra bir çok sayıda
sonunda, o önemli değil.
Bütün mesele olduğunu onlar, sadece sıralanır konum
ortasında bakmak istiyorum Dizi hala çünkü
yarısında sorununuzu dilimleme.
Serin.
Yani şimdi biz var Orta, biz şimdi ne yapacağız?
>> ÖĞRENCİ: öneririz.
EĞİTMEN: karşılaştırın.
Value_wanted Yani orta karşılaştırın.
Serin.
Yani biz burada görmek biz buraya istiyoruz bu değer.
Bu bir dizi olduğunu unutmayın.
Yani orta indeksi ifade eder.
Bu yüzden orta değerlerini yapmak istiyorum.
Eğer isterseniz unutmayın , çift eşittir karşılaştırmak için.
Sen tek sen eşittir yapmak sadece yeniden atamak olacak,
ve, tabii ki, bu kadar İstediğiniz değeri olacak.
Yani yapmayın.
>> Yani biz eğer görmek için gidiyoruz ortada değerler
İstediğimiz değerine eşittir.
Senin parantez unutma.
Dropbox gitmek gerekir.
Yani biz bu durumda ne yapmalıyım?
Biz dönmek istiyoruz buysa?
Biz söylemeye çalışıyoruz.
>> ÖĞRENCİ: off yazdırın.
>> ÖĞRETİM: Peki, biz kapalı baskı istemiyorum.
Yani bu burada bir bool, biz böylece doğru ya da yanlış dönmek istiyorum.
Biz bu sayı, söylüyorsun Bir [? RRA? ?] O yüzden eğer,
Biz sadece doğru döndürür.
Ben gerçek büyü edebilirsiniz.
>> ÖĞRENCİ: Neden sıfır dönmek olmaz?
EĞİTMEN: yapabildin Yani İsterseniz sıfır döndürür.
Ama bu durumda çünkü Fonksiyonumuzu bir bool döndürür
Biz doğru veya yanlış dönmek gerekiyor.
ÖĞRENCİ: Ne zaman sen boolean ifade söyleyerek
Eğer yanlış eşit ayarlayabilirsiniz?
Ben söylemek istiyorum, eğer bu durum böyle üst false eşittir gibi, bir araya geldi değil.
Sadece eğer anlayacaksınız diğer tarafta yanlış koymak?
EĞİTMEN: Evet.
Yani aslında sen eğer Hiç bir şey yapıyor
gibi üst ya da daha düşüktür, Bu doğru veya yanlış döndürür
ve aslında kötü tarzı diyelim eşit gerçek veya eşittir eşittir
Yanlış eşittir.
O sonuç kullanmak istiyorum senin çek olarak kendisi.
Ben istediğim gibi değil.
Ben istediğim buydu.
Soruyorsun sana durumunda Yani bir şey hakkında gibi c bu kaydedin.
>> Bu yüzden int main (void) varsa ve böyle bir şey.
Üst Ve eğer var sen ve bazı giriş
Yapabileceğiniz soran böyle bir şey?
Doğru?
ÖĞRENCİ: Ben çalışıyordum o [duyulamaz] yapmak.
Bu-- Çünkü eğer
EĞİTMEN: Sağ.
Yani bu doğru, yanlış olmak istiyorum?
ÖĞRENCİ: Evet.
EĞİTMEN: Bu durumda Yani bu doğru değil eğer çalıştırmak istiyorum.
Yani orada yapmak serin bir şey bu.
Yani ünlem hatırlıyorum nokta şeyleri olumsuzlar?
Bu [duyulamaz] anlamına gelir diyor.
Biz sadece bakmak Yani eğer Burada bu bölüm, şimdi etsen
Buna değerlendirir demek Yanlış siz istediğiniz gibi.
Yanlış değil doğru olduğu Bu yürütmek demektir.
Mantıklı mı?
ÖĞRENCİ: Evet.
EĞİTMEN: Korku.
TAMAM MI.
Yani biz sadece geri dönebilirler Bu durumda gerçek.
Yani şimdi diğer iki var Bu durumda olgu.
Bizim diğer iki olgu nedir?
Sadece bu şekilde yapalım.
Yani başka ile başlayalım eğer ortada değerler
İstediğimiz değerden daha azdır.
Yani ortada bizim değer az Aradığımız değerinden daha.
>> Yani bağlı olan do you Biz güncellemek istiyor düşünüyorsun?
Üst veya alt?
Üst?
Dizinin Yani hangi tarafı baktığımız olacak?
>> ÖĞRENCİ: düşük.
>> EĞİTMEN: Biz gidiyoruz vardır Soldaki bakıyor olması.
Az değer küçükse Yani başka.
Burada orta değer Yani bizim istediğimiz daha azdır.
Yani biz almak istiyoruz Bizim dizinin sağ tarafında.
Yani biz gidiyoruz Bizim alt sınır güncelleyin.
Bu yüzden bizim alt yeniden atamak olacak.
Ve daha düşük olmalı ne düşünüyorsunuz?
ÖĞRENCİ: Orta değeri var mı?
EĞİTMEN: Yani orta value--
ÖĞRENCİ: Artı 1.
EĞİTMEN: --plus 1.
Herkes bana neden söyleyebilir biz artı 1 var?
>> ÖĞRENCİ: [? Hiçbir değeri var mı?] ona daha eşittir.
>> ÖĞRETİM: Doğru.
Biz zaten biliyoruz çünkü Bizim orta değer eşit değil
o ve biz bunu dışlamak istiyorum sonraki tüm aramalardan.
Eğer bu artı 1, bu unutursanız süresiz döngü gibi olacak.
Ve sadece bir yakalanmış olacak sonsuz döngü ve sonra segfault edeceğiz
ve kötü şeyler gidin.
Yani her zaman değil emin olun değeri de dahil olmak üzere sadece
baktı.
Yani biz bir artı 1 ile dikkat çekmek.
>> Peki şimdi bizim son durum var Emniyet uğruna hangi hep
En değer else if, burada kontrol edebilirsiniz orta değerden büyüktür
İstediğimiz.
Yani istediğiniz anlamına gelir sol yarısı.
Yani hangisinin biz güncellemek için gidiyoruz?
Üst.
Ve eşit olacak bu nedir?
Orta eksi 1, çünkü Tabii, biz istiyoruz
Biz değiliz emin olmak için Yine o orta değerine bakarak.
Ve sonra biz buna sahip.
Işte bu.
Hepsi ikili arama konumdur.
Bu doğru, bu kötü değil mi?
Bu 10 çizgiler gibi Beyaz boşluk ile kodu.
Yani çok güçlü, çok kullanışlı, olacak senin sonraki psets biri bunu kullanıyor.
Belki bu bir, ama daha sonra.
Yani bunu öğrenmek.
Onu seviyorum.
Bu da koyacağız.
Yani herkes herhangi var mı İkili arama sorular?
Evet.
>> ÖĞRENCİ: önemli mi sizin n, tek veya çift olup olmadığını?
>> EĞİTMEN: Hayır
Biz orta döküm Çünkü bir int, sadece onu keser.
Bir tamsayı kalmak ve olacaktır bu yüzden olacak Sonunda her şeyi ile sıralamak.
Yani bu konuda endişelenmenize gerek yok.
Herkes iyi?
Korku.
Serin.
Yani, siz bu var.
Slayt gösterisi.
Bahsettiğimiz gibi Yani, ben biliyorum David karmaşıklık runtimes bahsetti.
En iyi durumda Yani >>, sadece var Biz sürekli zaman diyoruz biri.
Bu olabilir, neden kimse bana söyleyebilir?
Bu senaryoda ne tür gerektirecektir ki?
Mm-hm.
>> ÖĞRENCİ: [duyulamaz] birinci--
EĞİTMEN: Orta olmanın Yani biz gelen ilk unsur, değil mi?
Yani birinin bir dizi ya da ne olursa olsun biz sadece arıyoruz
ortasında şaplak dab olur.
Yani bizim en iyi durumda olduğunu.
Muhtemelen, gerçek sorunlar değil almak sık sık [duyulamaz] ulaşacak.
Ne bizim kötü durumda olacak?
Bizim en kötü durum günlük n.
Ve bu bütün ile ilgisi yoktur Ben hakkında konuştuk iki şey güçler.
>> Yani kötü durumda o anlamına gelecektir Biz aşağı dizi doğrayın zorunda
bu birinin bir unsuru kadar.
Bu yüzden ikiye devirmek zorunda biz belki olabilir gibi birçok kez.
Bu günlük n nedeni var bu yüzden Eğer sadece iki bölünerek tutun.
Yani varsayımlar, işler size Hiç iseniz bilmeniz gerekir
Bir ikili arama kullanmak için gidiyoruz.
Sizin elemanları sıralanması gerekir.
Onlar yüzünden sıralanmış olması tek yolu var
Eğer mümkün ise biliyorsunuz bunun yarısını dışarı atmak için.
>> Bu karışık bir çanta olsaydı ve numaraları size, söylüyorsun
Tamam, ben orta kontrol edeceğim numarası ve ben arıyorum numara
daha az olduğu, sadece gidiyorum keyfi yarısını dışarı atmak için.
Sen eğer bilemeyiz senin diğer yarısında numaralar.
Sizin liste sıralanır vardır.
Yanı sıra, bu olabilir Önümüzde biraz gidiyor,
ama rastgele erişim olması gerekir.
Sen edebilmek için gereken sadece Bu orta eleman gidin.
Eğer çapraz varsa bir şey aracılığıyla
ya da ekstra adımlar atıyor Bu orta elemana ulaşmak için,
log n artık çünkü değil bunu içine daha fazla iş ekliyoruz.
Ve bu biraz yapacak İki hafta içinde daha mantıklı,
ama ben sadece tür, önsöz istedi Size adamlar ne bir fikir vermek
gelmek.
Ama bu ikisi Önemli varsayımlar
Eğer bir ikili listesi için gereken.
Bu sıralama var emin olun.
Bunun için büyük biri Şu anda çocuklar.
Ve bu biz geçebiliriz Bizim türlü geri kalanı.
Yani dört sorts-- kabarcık, ekleme, seçme ve birleştirme.
Serin her türlü sensin.
Siz CS 124 almaya karar verirseniz, Eğer türlü her türlü öğreneceksiniz.
Ve bir XKCD hayranı iseniz, orada gerçekten harika bir çizgi hakkında
Gerçekten etkisiz türlü gibi hangi ben son derece bakmak için gidiş tavsiye.
Bunlardan biri panik tür gibi olan gibi, oh hayır, rastgele dizi dönüş olduğunu.
Kapatma sistemi.
Bırakın.
Yani geeky mizah her zaman iyidir.
>> Yani herkes tür hatırlıyor mu sadece genel bir fikir gibi
kabarcık sıralama nasıl çalıştığını.
Sen hatırlıyor musun?
>> ÖĞRENCİ: Evet.
>> EĞİTMEN: Go for it.
>> ÖĞRENCİ: Eğer üzerinden gidiyoruz Yani ve daha büyük ise, o zaman iki takas.
>> EĞİTMEN: Mm-hm.
Kesinlikle.
Yani sadece yineleme.
İki numaralarını kontrol.
Bir önceki büyükse daha sonra bir daha,
sadece o yüzden onları takas Bu şekilde daha yüksek sayılar tüm
Listenin sonuna doğru kabarcık ve tüm alt numaralar kabarcık aşağı.
>> Sana adamlar serin göstermek mi Videoyu sıralama ses efekti?
Bu serin tür.
Robert Az önce söylediğim gibi, algoritma Yani Sadece listede adım adım olduğu,
Bitişik değerleri takas onlar sırayla değilseniz.
Ve sonra sadece yinelenen tutmak kadar herhangi bir swapları yapmazlar.
Çok kötü değil, değil mi?
Yani biz sadece burada hızlı bir örnek var.
Yani bu sıralamak için gidiyor artan düzende onları.
Bu yüzden ilk gittiğinizde zaman, biz sekiz bakmak
ve altı besbelli değil sırayla, biz onları takas.
>> Yani bir sonraki bak.
Sekiz ve sırayla dört değil.
Onları değiştirin.
Ve sonra sekiz ve iki, onları takas.
Biz oraya gitmek.
Yani ilk geçişten sonra, sen Biliyorum ki senin büyük sayı
tüm yol olacak Sadece çünkü üstündeki
sürekli olacak her şeyin daha büyük
ve sadece kabarcık gidiyor Orada sonuna kadar tüm yol kadar.
Bu herkes için mantıklı mı?
Serin.
>> Öyleyse bizim ikinci geçişte bak.
Altı ve dört anahtar.
Altı ve iki anahtar.
Ve şimdi sırayla bir kaç şey var.
Her geçişte Yani biz bizim tüm liste üzerinden yapmak,
biz biliyoruz ki birçok sayılar gibi sonunda sıralanır olacaktır.
Bu yüzden üçüncü bir geçiş yapmak, hangisi takas olduğunu.
Ve sonra bizim dördüncü sıfır yuvası var, geçmek.
Ve böylece biz biliyoruz bizim Dizi sıralanır olmuştur.
>> Ve bu büyük kabarcık sıralama ile bir şey.
Biz biliyoruz ne zaman biz o , sıfır swap var
her şeyin anlamı tam sırası olduğunu.
Biz kontrol nasıl tür.
Bu yüzden de balonu kod gidiyoruz sıralama hangi da kötü değil.
Bunların hiçbiri o kötü.
Ben onlar biraz korkutucu görünebilir biliyorum.
Ben çekerken ben biliyorum sınıf, hatta zaman
için sınıf öğretiyordu İlk kez geçen yıl,
Ben gibi ben bunu nasıl yapabilirim ki?
Bu teoride mantıklı, ama biz aslında bu nasıl yaparsınız?
Hangi ben de yürümek istiyorum neden Burada sizinle kodu ile.
Yani bir pseudocode var Siz bu kez.
Yani sadece bunu aklınızdan çıkarmayın biz üzerinden geçiş üzereyiz.
Bu yüzden bazı sayaç var Bizim swap izler
Biz emin olmanız gerekir, çünkü biz kontrol ediyoruz ki.
Ve biz tüm dizi yineleme biz sadece bu örnek ile yaptığımız gibi.
Eleman önce daha büyükse biz olduğun yerde sonra eleman,
biz onları takas ve biz bizim, artırmak sayaç, biz takas kısa sürede çünkü
bizim sayaç bildirmek istiyorum.
Orada Herhangi bir sorunuz?
Bir şey buraya komik görünüyor.
ÖĞRENCİ: Eğer sıfıra sayacını musunuz Eğer döngü içinde gitmek her zaman?
Eğer devam etmeyin geri her zaman sıfıra?
EĞİTMEN: İlle.
Peki ne olur biz burada geçmesi olduğunu.
Yani olurken, bu hatırlıyorum kesintisi olmadan bir kez yürütülür.
Yani ayarlamak için gidiyor sıfıra eşit sayaç,
o zaman yineleme olacak.
Içinden dolaşır gibi, bu sayacı güncelleyecektir.
Bu sayacı güncellemeleri gibi, bu bitince, bu dizinin sonuna ulaşıldığında ne zaman,
Bizim liste sıralanır değil ise, sayaç güncellendi olacaktır.
>> Peki o zaman durumu kontrol eder ve Tamam, sıfırdan karşı büyüktür, diyor.
Eğer öyleyse, bunu tekrar.
Çok zaman sizi o sıfırlamak istiyorum geçmesi, sayaç sıfıra eşittir.
Eğer bir Sıralanmış geçmesi durumunda dizi, hiçbir şey değiştirir
Bu başarısız olur ve sıralanır listesini döndürür.
Bu mantıklı mı?
ÖĞRENCİ: biraz Ölebilirim Bu.
EĞİTMEN: Tamam.
Başka varsa çıkageldi soru.
Evet.
>> ÖĞRENCİ: Ne olur fonksiyonu elemanları takas için olabilir mi?
>> EĞİTMEN: Yani biz aslında yazabilirsiniz Şimdi sağa gidiyoruz eğer.
Serin.
Bu notu Yani, Alison gidiyor geri cihaza geçmek için.
Çok eğlenceli olacak.
Ve bizim hoş var Burada kabarcık sıralama şey.
Yani zaten bisiklet yaptım dizi üzerinden.
Bizim swapları var sıfıra eşittir.
Bu yüzden komşu takas etmek istiyorum elementler için dışarı iseniz.
Yani ilk şey gerekiyor Bizim dizi yineleyemezsiniz yoktur.
>> Peki biz olabilir sizce Bizim dizi boyunca yineleme?
Biz var ve ben 0 eşittir.
Biz ben daha az olmak istiyorum n eksi 1 eksi k'dan.
Ve ben bir saniye o anlatacağım.
Yani bu bir optimizasyon burada olduğu, Ben her geçişten sonra dedi nasıl hatırlıyor
Dizi biz yoluyla ne olursa olsun on-- olduğunu biliyorum
>> Yani bir geçişte sonra Bu sıralanır olduğunu biliyoruz.
İki paso sonra bildiğimiz Bütün bu sıralanır.
Üç geçiş sonra Bu sıralanır biliyorum.
Bu arada Yani yineleme ediyorum Burada dizi ile,
sadece gitmek emin yapıyor olduğunu Bildiğimiz ne ile sıralanmamış.
TAMAM MI?
Bu sadece bir optimizasyon var.
Sadece safça bunu yazabilirsiniz her şeyi ile yineleme,
sadece uzun sürer.
Bu dört döngü sayesinde var Sadece güzel bir optimizasyon
biz her tam sonra biliyorum çünkü Burada dizi ile yineleme,
Burada her tam döngü gibi, biz biliyoruz Bu elemanların bir kez daha bu
sonunda sıralanır.
>> Bu yüzden bu konuda endişelenmenize gerek yoktur.
Bu herkes için mantıklı mı?
Bu serin küçük hile?
Bu durumda, eğer öyleyse biz yineleme ediyoruz
biz kontrol etmek istediğini biliyorum Dizi n ve n artı 1 sıradadır.
TAMAM MI.
Yani burada pseudocode var.
Biz kontrol etmek istediğiniz dizi n ve n + 1 düzenindedir.
Yani biz orada ne olabilir?
Bazı koşullu olacak.
Bu bir if olacak.
>> ÖĞRENCİ: dizi n ise dizi n-plus 1 'den daha azdır.
EĞİTMEN: Hı-hı.
De, daha az ya da daha büyük olabilir.
ÖĞRENCİ: Büyüktür.
Sonra onları takas etmek istiyorum.
Kesinlikle.
Yani şimdi biz ne içine almak Bunları takas mekanizması?
Yani biz bu kısaca geçti, takas fonksiyonu bir tip geçen hafta.
Herkes nasıl çalıştığını hatırlıyor mu?
Yani biz sadece sağ, onları yeniden atamak değil mi?
Bunlardan biri kaybolmak Çünkü.
Dediğimiz Eğer bir sonra B'ye ve eşittir A eşittir, her ikisi de bir anda
B. sadece eşit
>> Peki yapmamız gereken ne ise bu geçici bir değişken var
bizimki bir süre birini tutmak için gidiyor Biz takas sürecinde konum.
Peki biz bazı int olacak olan Bunu atayabilirsiniz amaçlara yönelik geçici eşittir
hangisi için sadece, istediğiniz Eğer dökersin-- takip ediniz tutmak olun
yani bu durumda, ben gidiyorum dizi n-plus 1 olarak atayın.
Yani tutmak için gidiyor ne değeri ikinci blokta ise
Biz bakıyoruz ki.
>> Ve sonra biz yapabiliriz biz gidebiliriz olduğunu önde ve yeniden atamakta dizi n artı 1,
Biz biz biliyoruz çünkü depolanan bir değere sahiptir.
Bu aynı zamanda büyük biridir Senin varsa seyleri bilmiyorum
Eğer iki geçerseniz sorunları vardı kod satırları aniden şeyler çalıştı.
Sipariş CS çok önemlidir.
Yani emin olun diyagramı İşlerin mümkünse
olarak aslında ne oluyor.
Yani şimdi biz gidiyoruz , dizi n artı 1 olarak yeniden atamak
Biz biz biliyoruz çünkü depolanan bir değere sahiptir.
>> Ve biz dizi o atayabilirsiniz n veya bu durumda dizideki i.
Çok fazla değişken.
TAMAM MI.
Yani şimdi biz yeniden ettik dizi i artı 1 dizideki i ne eşit.
Ve şimdi geri gidebilir ve Neye dizi i atamak?
Herkes?
>> ÖĞRENCİ: 10.
>> ÖĞRETİM: 10.
Kesinlikle.
Ve son bir şey.
Şimdi bunu takas varsa, ne yapmamız gerekiyor?
Bir şey nedir bize söyleyecek
biz hiç bu programı sonlandırmak olur?
Ne biz söyler sıralı liste var?
Biz herhangi bir swapları yapmazsanız, değil mi?
Swap Eğer eşittir Bu sonunda sıfır.
Peki ne zaman biz gibi, bir takas yapmak sadece burada yaptım, biz swap güncellemek istiyoruz.
Ve ben orada olduğunu biliyorum bir Soru erken yaklaşık yapabilirsiniz
yerine sıfır veya bir kullanımı gerçek veya yanlış.
Ve bu burada ne var.
Yani bu değilse swapları diyor.
Swap sıfır, yani eğer ki hep ben bu-- olsun benim hakikatler ve benim falses karışık.
Biz bize değerlendirmek istiyoruz true ve değil.
Sıfır ise, o zaman bu yanlış.
Eğer bunu inkâr ederse [? patlama?] doğru olur.
Öyleyse bu hat yürütür.
>> Gerçek ve sahte ve sıfır ve olanlar deli olsun.
Sadece yavaş yürümek içinden mantıklı olacaktır.
Ama ne bu küçük bulunuyor kod bit burada yok.
Yani bu denetler biz herhangi bir swapları yaptık.
Bu yüzden bir şey yanında eğer var sıfır, sahte olacak
ve her şey olduğu Tekrar çalıştırmak için gidiyoruz.
Serin?
>> ÖĞRENCİ: molası ne yapar?
>> EĞİTMEN: sadece kırın döngü dışına kırılır.
Bu durumda olur Yani sadece programı bitirmek istiyorum
ve sadece olur senin sıralanmış listesi var.
ÖĞRENCİ: İnanılmaz.
EĞİTMEN: Üzgünüm?
ÖĞRENCİ: Çünkü biz daha önce sıfır yazılı üzerinde 1 yazılı kullanılan
eğer sunmak Bu işe ya da olmaz.
>> ÖĞRETİM: Evet.
Yani sıfır veya 1 dönebilirsiniz.
Bu durumda, çünkü biz aslında değiliz fonksiyonu ile bir şey yapıyor,
biz sadece kırmak istiyorum.
Biz gerçekten umurumda değil.
Fren da eğer iyi dışarı bozduğu için kullanılan
Dört döngü veya koşullardan Eğer yürütme tutmak istemiyorum.
Sadece onları dışarı götürür.
Bir nüans şey biraz var.
Var gibi hissediyorum el sallayarak bir sürü,
gibi yakında bu konuda öğreneceksiniz.
>> Ama yakında bu konuda öğreneceksiniz.
Söz veriyorum.
TAMAM MI.
Yani herkes kabarcık sıralama alır?
Çok kötü değil.
Yineleme, takas şeyler kullanarak geçici değişken ve hepimiz orada hazırsınız?
Serin.
Korku.
TAMAM MI.
Geri PowerPoint.
Genel olarak herhangi bir sorunuz hakkında bu kadar?
Serin.
Mm-hm.
>> ÖĞRENCİ: [duyulamaz] genellikle ana int.
Bunun için bu var var mı?
>> EĞİTMEN: Yani biz sadece aradılar Sadece gerçek sıralama algoritması ile.
Eğer içinde olsaydı Daha büyük bir program gibi,
Eğer bir int ana bir yerlerde olurdu.
Nereye bağlı Bu algoritmayı kullanmak,
ne var belirleyecek onun tarafından iade edilir.
Ama bizim durumumuzda için, biz kesinlikle konum aslında bu yapar nasıl bakıyor
Bir dizi boyunca yineleme.
Bu yüzden bu konuda endişelenmeyin.
>> Bu yüzden hakkında en iyi davayı konuşuyor edildi ve İkili arama için en kötü durum senaryoları.
Yani bunu yapmak için de önemlidir Bizim türlü her biri için söyledi.
Peki ne düşünüyorsun kötü kabarcık tür vaka zamanı?
Siz hatırlıyor musun?
>> ÖĞRENCİ: N eksi 1.
EĞİTMEN: N eksi 1.
Yani orada demektir n eksi 1 karşılaştırmalar.
Yani gerçekleştirmek için bir şey İlk yineleme o,
biz karşılaştırmak geçmesi Bu iki-- böylece 1 bu.
Bu iki, üç, dört.
Yani bir yineleme sonra Zaten dört karşılaştırmalar var.
Ne zaman çalışma zamanı ve n bahsediyorum.
N karşılaştırmalar sayısını temsil Kaç elemanlarının bir fonksiyonu olarak
sahibiz.
TAMAM MI?
>> Yani biz dört var, geçer.
Bildiğiniz dahaki sefere biz değil Bu dikkat çekmek gerekiyor.
Biz, bu iki karşılaştırmak Bu iki, bu iki,
ve biz bu optimizasyon yoktu Ben yazdım Dört döngü ile,
Eğer zaten burada karşılaştırarak olacaktır.
Yani olurdu dizi üzerinden çalıştırmak
ve n karşılaştırmalar yapmak n Zaman, her zaman çünkü biz
o tür bir şey, biz koşuyoruz.
>> Ve biz koşuyoruz her zaman Dizi, biz n karşılaştırmalar yapmak.
Yani bu bizim çalışma zamanı olduğunu Aslında n, kare hangi
çok kötü bizim çünkü sonu log
Biz dört vardı anlamına eğer milyar elemanları, bu kadar
dördümüz milyar almayı gidiyor yerine 32 kare.
Yani değil en iyi zamanı, ama bazı şeyler için,
Eğer içinde iseniz, biliyorsun elemanların belirli bir aralığı
kabarcık sıralama kullanmak iyi olabilir.
>> Tamam.
Yani şimdi iyi durumda çalışma zamanı nedir?
ÖĞRENCİ: Sıfır?
Veya 1?
>> EĞİTMEN: Yani 1 olur bir karşılaştırma olacak.
Sağ.
>> ÖĞRENCİ: N eksi 1?
>> ÖĞRETİM: Yani, evet.
Yani n eksi 1.
Eğer n gibi bir kavram var her zaman eksi 1, biz sadece onu düşüyorlar eğiliminde
Eğer var çünkü ve biz sadece n say these-- her çiftin her bir karşılaştırma.
Yani, 1 n olmak eksi hangi biz biz sadece yaklaşık n söyleyebilirim.
Eğer zamanı ile uğraşırken, Her şey yaklaşan içinde.
Sürece üs olarak Doğru, sen çok iyisin.
Biz onunla nasıl başa >> budur.
En iyi durumda, n geçirilir, böylece , liste zaten sıralanır anlamına gelir
ve yaptığımız tüm aracılığıyla çalıştırılır ve sıralanır oluyor olmadığını kontrol edin.
Serin.
Tamam.
Burada gördüğünüz gibi Yani, biz Sadece biraz daha grafikler var.
Yani n kare.
Eğlenceli.
Çok gördüğümüz gibi n daha kötü, ve Günlük 2n çok daha kötü, çok.
Ve o zaman da günlük günlükleri içine almak.
Ve 124 almak, içine almak deli gibi günlük yıldızı gibi.
Eğer ilgileniyorsanız Yani, arama günlüğü yıldızı.
Bu eğlenceli tür.
Yani biz bu büyük grafik var.
Sadece bir kafaları yukarı, bu bir harika grafik var
çünkü biz sizin orta vadede Size bu incelir sormak uzun.
Yani sadece bir kafaları yukarı, bu var senin senin güzel hile kağıda orta vadeli
orada.
Yani biz sadece kabarcık tür baktı.
En kötü durumda, n, n en iyi davayı kare.
Ve biz başkalarına bakmak için gidiyoruz.
>> Ve gördüğünüz gibi, sadece Gerçekten iyi yapar bir
biz neden içine alırsınız birleştirme sıralama vardır.
Yani biz gitmek için gidiyoruz Bir sonraki ötürü-- seçim sıralama.
Herkes nasıl hatırlıyor mu Seçim sıralama çalıştı?
Göreyim seni.
>> ÖĞRENCİ: Temelde geçmesi Bir düzen ve yeni bir liste oluşturmak.
Ve elemanları koyarak konum gibi olarak, doğru yere koyun
Yeni listede.
>> EĞİTMEN: Böylece sesler Ekleme tür gibi daha.
Ama gerçekten yakınsın.
Onlar çok benzer konum.
Hatta ben onları bazen karışık olsun.
Ben gibiydi bu bölümde önce, bekle.
TAMAM MI.
Yani istediğini yapmak, seçim tür
aklınıza gelebilecek yolu o ve yol hakkında
Eminim ben almak için denemek yapmak Onları o geçer ise, karışık
ve seçer küçük sayı ve
listenizin başında koyar.
Bu ilk nokta ile takas.
Onlar aslında benim için bir örnek var.
Korku.
Yani sadece bir yol bu-- seçim düşünmek sıralama, en küçük değeri seçin.
Ve biz gidiyoruz Bir örnek üzerinden çalıştırmak
Çünkü yardımcı olacaktır düşünüyorum Ben görseller her zaman yardımcı düşünüyorum.
Bu yüzden bir şey ile başlamak Bu tamamen sıralanmamış.
Kırmızı tasnifsiz olacak Yeşil sıralanır.
Her bir saniyede mantıklı olacaktır.
>> Bu yüzden geçmesi ve biz yineleme başından sonuna kadar.
Ve biz tamam, 2, demek Bizim küçük sayı.
Bu yüzden 2. almaya gidiyoruz ve biz gidiyoruz Bizim dizinin önüne taşımak için
o çünkü küçük sayı elimizde.
Yani bu burada ne yapıyor.
Sadece bu ikisini takas olacak.
Yani şimdi biz sıralamış bölüm ve bir sıralanmamış parçası.
Ve hatırlamak iyi ne Seçim tür hakkında
biz sadece seçme ediyoruz olduğunu ayıklanmamış parçası.
>> Eğer yalnız bırakmak sıralı bir parçası.
Mm-hm?
>> ÖĞRENCİ: ne o biliyor nasıldır karşılaştırmadan küçük
dizideki her bir değere yükseltilmektedir.
EĞİTMEN: O karşılaştırmak yapar.
Biz bunu atlanır seviyorum.
Bu genel sadece genel olduğunu.
Evet.
Biz Ben kod yazarken emin daha memnun olacağım.
Ama öncelikle bu depolamak küçük olarak eleman.
Sen karşılaştırmak ve Tamam, bu küçük, demek?
Evet.
Tutun.
İşte o küçük?
Hayır mı?
>> Bu, sizin küçüğüdür senin değere yeniden atayabilirsiniz.
Ve sen çok mutlu olacağım Biz kod geçmesi zaman.
Bu yüzden geçmesi, böylece o, takas Bu sıralanmamış kısmında bak.
Bu yüzden üç out seçmek için gidiyoruz.
Biz de onu koymak için gidiyoruz Bizim sıralı bölümünün sonu.
Ve biz sadece yapmaya devam edeceğiz yapıyor, ve bunu yaparken, o.
Yani bu burada pseudocode bizim türüdür.
Biz bir saniye burada o kadar kod olacak.
Ama sadece bir şey yürümek Yüksek düzeyde aracılığıyla.
Sen gitmek için gidiyoruz i n eksi 2 0 eşittir.
Bu başka bir optimizasyon var.
Bu konuda çok fazla endişe etmeyin.
Yani sen diyordun.
Yakup dediğim gibi, nasıl biz yapmak bizim asgari ne izlemek?
Nasıl biliyor musunuz?
Biz karşılaştırmak zorundayız Bizim listesinde her şeyi.
>> Yani asgari i eşittir.
Sadece bu durumda söylüyor bizim asgari değerin endeksi.
Yani o zaman yineleme gidiyor j i artı 1 eşittir gelen ve gider.
Yani biz zaten biliyoruz Bu bizim ilk unsur var.
Biz kendisine karşılaştırmak gerekmez.
Bu yüzden bir sonraki karşılaştırarak başlar i artı 1 n neden biri olan
eksi 1, olduğu Orada dizinin sonu.
Ve biz dizi de eğer dedi j, dizi dakikadan daha azdır
Sonra nereye yeniden atamak Bizim asgari endeksleri olduğunu.
>> Ve min gibi, i eşit değilse nerede biz buraya üzerindeydi.
Biz öncelikle bu bir yaptım Yani seviyorum.
Bu durumda, en başlayacak sıfır, bu iki olmak kadar sona erecekti.
Yani dk sonunda ben eşit olmaz.
Yani bize biliyor sağlar biz onları takas gerekir.
Ben somut bir örnek gibi hissediyorum Bu çok daha fazla yardımcı olacaktır.
Bu yüzden çocuklar bu kadar kod olacak şimdi ve ben daha iyi olacağım düşünüyorum.
>> Sıralar ki bu şekilde çalışmak eğilimindedir sadece onları görmek için sık sık daha iyi.
Yani biz yapmak istiyoruz ne biz ilk küçük istiyoruz
dizi içindeki bir konumda elemanı.
Tam Jacob ne dediğini.
Sen nasılsa saklamak gerekir.
Yani biz burada başlatmak için gidiyoruz dizi üzerinden yineleme.
Biz söylemek için gidiyoruz bizim Sadece başlamak için ilk.
Bu yüzden int sahip olacak küçük i de dizi eşittir.
>> Yani bir şey fark, her Bu döngü yürütür zaman,
biz birlikte bir adım daha ileri başlıyor.
Biz başlattığınızda bu bir bak.
Biz yineleme dahaki sefere, Bu bir de başlıyoruz
ve bizim en küçük değeri atama.
Yani kabarcık sıralama çok benzer Bildiğimiz nerede tek geçişte bundan sonra,
Bu son unsur sıralanır.
Seçim tür, tam tersi var.
>> Her geçişte, biz biliyoruz İlki sıralanır.
İkinci geçişte sonra, İkinci bir sıralanacaktır.
Ve slayt örneklerle gördüğümüz gibi, Bizim sıralanmış kısmı sadece büyümeye devam ediyor.
Yani bizim küçük birini ayarlayarak diziler i, tüm bu yapıyor
daraltıcı ne Biz böylece bakıyoruz
sayısını en aza indirmek için karşılaştırmalar biz yapmak.
Bu herkese mantıklı mı?
Yapılacak bu aracılığıyla çalıştırmak için bana ihtiyacın Tekrar yavaş veya farklı bir deyişle?
Ben mutluyum.
TAMAM MI.
>> Yani depolamak Bu noktada, bir değer,
ama biz de indeksi saklamak istiyorum.
Bu yüzden saklamak için gidiyoruz küçük pozisyonu
Sadece i olacak biri.
Şimdi Yakup memnun.
Biz saklanan şeyler var.
Ve şimdi biz bakmak gerekir Dizinin ayıklanmamış parçası.
Bu durumda, bu yüzden Bizim sıralanmamış olur.
Bu i.
TAMAM MI.
>> Peki yapacağız ne Bir döngü için olacak.
Size ihtiyaç duyarsan Bir dizi boyunca yineleme,
Aklını bir döngü için gidebiliriz.
Bazı int k Yani Biz ne düşünüyorsunuz equals--
k ile başlamak için eşit olacak?
Bu bizim küçük olarak ayarlandı ne değer ve biz bunu karşılaştırmak istiyorum.
Biz bunu karşılaştırmak ne istiyorsun?
Bu doğru, bu bir sonraki olacak?
Bu yüzden başlatılması için k istediğiniz i artı 1 başlatmak için.
>> Ve biz bu durumda k istiyoruz biz Zaten boyutu burada sakladığınız,
bu yüzden biz sadece boyutu kullanabilirsiniz.
Boyut dizinin boyutu olmak.
Ve biz sadece istiyoruz biri her seferinde k güncelleyin.
Serin.
Yani şimdi biz bulmalıyız Burada küçük elemanı.
Yani biz yineleme, biz söylemek istiyorum k dizisi
en küçük value-- daha azdır biz aslında olduğun yerde bu
ne kayıtlarını tutmak küçük ötürü--
sonra yeniden atamak istiyoruz Bizim en küçük değeri nedir.
>> Bu ah, biz konum anlamına gelir Burada yineleme.
Ne olursa olsun değer burada olduğunu bizim küçük şey.
Biz bunu istemiyoruz.
Biz bunu yeniden atamak istiyoruz.
Biz yeniden atama eğer Peki, ne yapmak Burada bu kodda olabileceğini düşünüyorum?
Biz yeniden atamak istiyoruz küçük ve konumu.
Peki şimdi küçük nedir?
ÖĞRENCİ: Dizi k.
EĞİTMEN: Dizi k.
Ve pozisyonu şimdi ne?
Indeksleri neler var Bizim küçük değeri?
Sadece k var.
Dizi k, k Yani, onlar kadar maç.
Yani biz yeniden atamak istedik.
Ve biz, bizim küçük bulundu, sonra sonra döngüsü için bu sonunda böylece
Burada biz bulduk ne bizim küçük değer, böylece biz sadece takas.
Bu durumda, gibi bizim, demek en küçük değeri burada olduğunu.
Bu bizim en küçük değerdir.
>> Biz sadece hangi burada takas etmek istiyorum ne altındaki bu takas fonksiyonu
biz sadece yazdığı, yaptım Birlikte birkaç dakika önce.
Bu yüzden tanıdık gelecektir.
Ve o zaman sadece yineleme olacak aracılığıyla tüm yol ulaşana kadar
Size demektir sonuna kadar sıralanmamış sıfır elemanlara sahip
ve her şey sıralanır olmuştur.
Mantıklı?
Daha somut Biraz?
Kod yardım?
>> ÖĞRENCİ: Bir boyutu için, asla gerçekten tanımlamak veya değiştirmek,
nasıl biliyor?
>> EĞİTMEN: Yani bir şey için int boyutu burada fark.
Yani biz bu sort-- tür söylüyorsun bu bir işlevi olduğunu case--
Seçim sıralama, o geçti oluyor fonksiyonu ile.
O geçti değildi Yani içinde, bir şey yapacağını
Dizinin uzunluğu gibi veya yineleme olur
uzunluğunu bulmak için.
Ama geçti çünkü olarak, biz sadece kullanabilirsiniz.
Sadece kullanıcı varsayalım Size geçerli bir boyut verdi
Aslında temsil hakkında dizisinin boyutu.
Serin?
>> Siz bu herhangi bir sorun varsa, veya daha fazla uygulama kodlama türlü istiyorum
kendi, sen-meli study.cs50 gidin.
Bu bir araçtır.
Onlar bir denetleyicisi var aslında yazabilirsiniz.
Onlar pseudocode yapmak.
Onlar daha fazla video ve slaytlar var Ben burada kullanmak olanlar da dahil olmak üzere.
Eğer hala hissettiğiniz Yani eğer Biraz bulanık, bu deneyin.
Her zaman olduğu gibi, çok konuş benimle gel.
Soru?
>> ÖĞRENCİ: Eğer söylüyorsun boyutu daha önce tanımlandığı gibidir?
EĞİTMEN: Evet.
Boyut önce yukarı tanımlanır Burada fonksiyon bildiriminde.
Yani o geçirilen oldu varsayalım kullanıcı tarafından ve basitlik aşkına,
Biz varsaymak için gidiyoruz Kullanıcı bize doğru boyutu verdi.
Serin.
Yani seçim nevi.
Beyler, ben bugün çok şey öğreniyorum biliyorum.
Bu bölüm için yoğun bir veri var.
Bununla Yani, biz gidiyoruz Ekleme tür gitmek için.
>> Tamam.
Yani daha önce yapmamız gereken Burada bizim zamanı analizi.
En iyi durumda Yani Seni gösterdi beri verilen
Tablo zaten ben tür onu ele verdi.
Ama en iyi durumda çalışma zamanı, ne düşünüyorsun?
Her şey sıralanır.
N kare.
Herkes bir açıklama var Sizce niçin?
>> ÖĞRENCİ: Sen through-- karşılaştırarak konum
EĞİTMEN: Sağ.
Sen aracılığıyla karşılaştırarak ediyoruz.
Her tekrarda, olsa biz tek bu azaltma konum
Hala aracılığıyla arıyor ediyoruz Her şey küçük olanı bulmak için.
Yani bile en küçük değeri başında burada
Hala karşılaştırarak konum her şeyin karşı
en küçük bir şey olduğundan emin olun.
Yani geçen bitireceğiz Yaklaşık n defa kare.
Tamam.
Ve en kötü durum nedir?
Eğer gidiyoruz çünkü Ayrıca n kare Aynı prosedür yapıyor.
Bu durumda, bir seçim yüzden sıralama şey vardır
biz de beklenen çalışma zamanı diyoruz ki.
Yani diğerleri, biz sadece biliyoruz alt ve üst sınırları.
Nasıl deli bağlı bizim Liste veya ne kadar sıralanmamış olduğunu,
onlar n veya n kare arasında değişmektedir.
Biz bilmiyoruz.
>> Ama seçim sıralama aynı çünkü En kötü ve en iyi durumda, o bize söyler
giriş ne olursa olsun biz tipi tamamen olsun, bilgisi
sıralanır veya tamamen bu kadar sıralanır ters
zaman aynı miktarda alacak.
Yani bu durumda, eğer Masamıza gelen hatırlıyorum,
aslında bir değeri vardı ki Bu iki türlü yok
hangi beklenen çalışma zamanı olduğunu.
Yani biz biliyoruz ne zaman ki Biz seçim sıralama çalıştırın,
o kadar garantili Bir n kare zamanı çalıştırın.
Orada hiçbir değişkenlik yoktur.
Sadece bekleniyor.
Ve yine, öğrenmek istiyorsanız daha İlkbahar CS 124 almak.
Tamam.
Biz bunu gördük.
Serin.
Yani yerleştirme sıralama.
Ve muhtemelen gidiyorum Bu yoluyla yangını.
Ben siz bunu kod olmaz.
Biz sadece bunun üzerinden yürümek gerekir.
Yani ekleme sıralama tür Seçim tür benzer
ki biz de bir sıralanmamış var ve dizinin parçası sıralanır.
>> Ama ne farklı olduğunu Biz tek tek geçmesi gibi,
biz sadece ne olursa olsun numara almak Bizim Sıralanmamış sonraki bir
ve doğru sıralamak Bizim sıralı diziye.
Bir örnek daha mantıklı olacak.
Yani her şey ayrımı yapılmamış diğer olarak başlar, Sadece seçim tür gibi.
Ve biz bu sıralamak için gidiyoruz Biz olmuştur olarak sipariş artan.
Bizim ilk geçişte Yani İlk değer alır
ve biz Tamam, sen demek, Şimdi kendiniz bir listede.
>> Bir listede Çünkü kendiniz, sen sıralanır.
Olmak için Tebrikler Bu dizideki ilk elemanı.
Siz zaten kendi tüm sıralanır ediyoruz.
Yani şimdi biz sıralamış ve bir sıralanmamış dizi.
Yani şimdi biz ilk almak.
Burada arasında olur ve burada, biz demek ki
Tamam, biz bakmak için gidiyoruz Bizim ayıklanmamış dizinin ilk değer
ve biz girişine gidiyoruz onun Sıralı dizide doğru bir yer.
>> Yani biz 5 almak ve biz ne Biz 5 3 büyüktür, tamam, demek
böylece biz sadece doğru yerleştirin Bunun sağında.
Biz iyiyiz.
Öyleyse bizim bir sonraki gitmek.
Ve biz take 2.
Biz tamam, 2 az, demek 3'ten, bu yüzden biliyorum öyle
olması gerekir Şimdi bizim listesinin ön.
Peki ne yapmamız aşağı 3 ve 5 itmek olduğunu ve biz o ilk yuvaya 2 taşıyın.
Yani biz sadece takarak konum olması gerektiği doğru yer.
>> Sonra bakmak bizim Bir sonraki, ve biz 6 söylüyorlar.
Yeterli, 6 daha büyüktür Bizim sıralı dizide her şeyi,
böylece biz sadece sonuna kadar onu etiketlemek.
Ve sonra 4 bakmak.
4, 6 dan daha azdır, daha az var: 5'ten ama 3'ten fazla var.
Yani biz sadece sağ takın 3 ve 5 arasında orta.
Yani biraz emin olmak için Daha somut bit,
Buradan tür ne fikri.
Her ayıklanmamış eleman Yani, biz nerede sıralı kısmında belirlemek
öyle.
>> Yani akılda tutarak sıralanır ve sıralanmamış,
biz aracılığıyla ve şekil hareket ettirmek zorunda o sıralı dizide uyuyor nereye.
Ve biz kaydırarak takın Bunun sağında aşağı unsurlar.
Ve sonra sadece tutmak biz gelene kadar yineleme
tamamen sıralanmış listesi var Şimdi sıfır burada sıralanmamış
ve sıralı kadar sürer Bizim listesinin tamamı.
Yani, yine, hatta şeyler yapmak için Daha somut biz pseudocode sahiptir.
>> Yani temelde i için n eksi 1 0 eşit,
bizim dizinin sadece uzunluğu var.
Biz eşit bazı eleman var İlk dizi ya da ilk endeksleri.
Biz eşit j ayarlayın.
J daha büyük ise yüzden sıfır ve dizi, j eksi 1
daha büyüktür eleman, tüm bu yüzden yapıyor
emin yapıyor senin j gerçekten temsil
Dizinin ayrıştırılmamış bölümü.
>> Hala şeyler varken Yani sıralamak ve j eksi bir ne bu-- için
eleman o mu?
J Burada tanımlanan asla.
Bu can sıkıcı tür.
TAMAM MI.
Neyse.
Yani j eksi 1, sen kontrol ediyoruz daha önce eleman.
Tamam, unsurdur, söylüyorsun Ben diyelim Ben-- yerde önce
Aslında bunu çizin.
Yani bu diyelim Bizim ikinci geçişte olduğu gibi.
Yani ben eşit olacak 1, hangi burada.
>> Yani ben 1'e eşit olacak.
Bu 2, 4, 5, 6, 7 olacaktır.
Tamam.
Bu durumda Yani bizim eleman 4 eşit olacak.
Ve biz bu biraz j var 1'e eşit olacak.
Ah, j azaltma olduğunu.
Yani budur.
Yani j i eşittir, bu nedenle bu nedir deyişi, biz ileriye taşımak gibi olduğunu
Biz sadece emin yapıyoruz Biz üzerinde değiliz ki
Biz çalışıyoruz bu şekilde endekslenmesi Bizim sıralanmış listeye şeyleri eklemek için.
>> Dolayısıyla j bu durumda 1 'e eşit olduğu zaman, yani dizi j eksi 1 Şehre dizi j eksi
bu ise, bu case-- 2 olduğu elemanın fazlaysa
sonra tüm bu yapıyor aşağı şeyler kayıyor.
Bu durumda, dizi j eksi bir Yani 2 dizi sıfır olurdu.
2, 4 daha büyük değildir bu nedenle bu idam değildir.
Yani vites aşağı hareket etmiyor.
Ne bu burada tıpkı bir aşağı sıralı dizi hareketli.
Bu durumda, gerçekten, biz sanıyor- olabilir Şimdi bu 3 yapalım.
Yani biz yürüyelim eğer Bu örnekte, biz şimdi burada değilsin.
Bu sıralanır.
Bu sıralanmamış.
Serin?
Bu yüzden, bu yüzden 2'ye eşittir Bizim eleman 3 'e eşittir.
Ve j O ile 2 eşittir.
Bu yüzden biz ve bakmak Tamam, dizi j eksi biri, demek
elemanının daha büyük Biz bakıyoruz ki?
Ve cevap hakkı, evet mi?
4 3 ve j daha büyüktür 2, bu nedenle bu kod yürütür.
>> Peki şimdi biz bir dizi ne 2, burada böylece, biz onları takas.
Yani biz sadece Tamam, dizi, demek 2 şimdi 3 olacak.
Ve j eşit olacak 1 j eksi 1.
Bu, korkunç ama Siz fikir olsun.
J şimdi 1'e eşittir.
Ve dizi j sadece olacak 4 bizim eleman, eşit.
Ben bir şey sildim ben olmamalı ya miswrote şey,
ama siz anladınız.
>> Bu n hareket.
Bu were sonra eğer Ve bu döngü olur Tekrar ve Tamam, j şimdi 1, söyleyebilirim.
Ve dizi j eksi 1 şimdi 2.
2 Bizim eleman daha az mı?
Hayır mı?
Yani biz ettik demektir Bu eleman takılı
Bizim sıralanmış diziye doğru nokta.
Sonra bu alabilir ve biz demek, Tamam, bizim sıralı dizi burada.
Ve bu sayı 6 almak ve olacaktır gibi, tamam, bu sayıdan daha az 6?
Hayır mı?
Serin.
Biz iyiyiz.
>> Tekrar yapın.
Biz 7 söylüyorlar.
Sonunda daha az 7 mi Bizim sıralı dizinin?
Hayır.
Bu yüzden iyiyiz.
Yani bu sıralama olacaktır.
Temelde tüm bu yapar o take söylüyor edilir
ilk elemanı senin sıralanmamış dizi,
nereye gittiğini anlamaya senin sıralı dizide.
Ve bu sadece ilgilenir swap yapmak.
Sen temelde sadece takas ediyoruz kadar doğru yerde var.
görsel resim sen olduğunu bunu yaparken her şeyi aşağı hareket.
>> Yani yarım kabarcık sıralama-vari gibi.
Çalışma 50 göz atın.
Ben çok çalışıyorum tavsiye Kendi bu kod.
Eğer herhangi bir sorun varsa veya isterseniz Bir ekleme sıralama için örnek kod bakın,
lütfen bana bildirin.
Ben her zaman etrafında değilim.
Yani en kötü durum zamanı ve en iyi durumda çalışma zamanı.
Eğer adam zaten tablodan gördüğümüz gibi o kare ve n oluyor hem de n, seni gösterdi.
>> Yani bir tür konuştuk ne gidiyor önceki türlü hakkında, kötü
durumda çalışma zamanı ise o tamamen sıralanmamış var,
bu n kez tüm karşılaştırmak zorundayız.
Biz karşılaştırmalar bir sürü yapmak Bu ters sırada ise, çünkü
biz Tamam, bu demek için gidiyoruz Bu iyi, aynı
ve bu karşılaştırıldığında gerekecektir İlk birine karşı geri taşınacak.
Ve biz doğru olsun Kuyruk ucu, biz var
, karşılaştırmak, ve her şeye karşı karşılaştırın.
>> Yani olmak biter Yaklaşık n kare.
O zaman doğru ise Eğer iyisin, 2, tamam, demek.
3, 2 olarak karşılaştırıldığında ediyoruz.
Iyisin.
4, sadece kuyruk karşılaştırın.
Iyisin.
6, sen iyisin, kuyruk karşılaştırın.
Yani her nokta için zaten var ise sıralanır, bir karşılaştırma yapıyoruz.
Yani sadece n var.
Ve biz en iyi durumda çalışma zamanı var çünkü n ve n bir kötü durumda çalışma zamanı
kare, hiçbir beklenen zamanını var.
>> Sadece bağlıdır Orada bizim listesinin kaos.
Ve yine, bir başka grafik ve başka bir tablo.
Türlü arasındaki farklar Yani.
Ben sadece esinti gidiyorum, ben biz yoğun konuştuk ettik gibi hissediyorum
nasıl her türlü hakkında bir farklılık ve birlikte bağlantı.
Yani sıralama sonuncusu birleştirme Ben sizi delik olacaktır.
Biz oldukça renkli bir resim var.
Yani sıralama yinelemeli bir algoritma olduğunu birleştirme.
Yani siz ne biliyor musun bir özyinelemeli işlevi nedir?
>> Herkes söylemek istiyorum?
Sen denemek ister misin?
Yani bir özyinelemeli fonksiyon sadece bir kendisini çağıran bir işlev.
Böylece siz aşina iseniz Fibonacci dizisi ile,
çünkü ardışık kabul var Eğer önceki iki almak
ve bunları birbirine ekleyin sonraki bir tane almak.
Yani özyinelemeli, ben hep düşünüyorum Bir spiral gibi özyineleme
böylece içine aşağı sarmal gibisin.
Ama sadece bir işlev bulunuyor Bu kendini çağırır.
>> Ve, aslında, gerçekten hızlı ben Bu neye benzediğini size gösterebilirim.
Biz bakarsanız burada çok özyinelemeli, bu özyinelemeli yolu bir dizi üzerinde toplanacak.
Yani hepimiz yapmak olduğunu Biz toplamı fonksiyonu var
Bir boyut ve bir dizi alır toplamı.
Ve dikkat ederseniz, boyut birer Zaman azalır.
Ve öyle her x eşitse olduğunu zero-- yani eğer dizinin büyüklüğü
sıfır döndürür zero-- eşittir.
>> Aksi takdirde bu özetliyor dizinin son elemanı,
ve daha sonra bir miktar alır Dizinin kalanı.
Yani sadece aşağı kırılıyor küçük ve daha küçük sorunlarla.
Uzun lafın kısası, yineleme, kendisini çağıran fonksiyon.
Bu, bu çıktı hepsi buysa, Bu bir özyinelemeli fonksiyon budur.
Eğer 51 alırsanız, çok alacak, yineleme ile çok rahat.
Bu gerçekten harika.
Sanki de mantıklı Dışarı 03:00 bir gece.
Ve ben, neden böyle oldu Ben bu kullanmak hiç?
>> Temelde, birleştirme tür Yani ne yapacak bu kadar olduğunu
Onu yıkmak ve onu kırmak için gidiyor Sadece tek unsurlar var kadar aşağı.
Tek elemanlar sıralamak kolay.
Biz görüyoruz.
Eğer bir eleman varsa, bu kadar Zaten sıralı kabul.
N elemanlı bir girişi Yani, n, en az 2 olması durumunda,
sadece aracı çünkü dönmek biz gördüğümüz gibi, 0 veya 1 ya var.
Bu Sıralı elemanlar olarak kabul edilir.
>> Aksi takdirde ikiye bölünürler.
Ikinci sıralamak, ilk yarıyı sıralamak Yarım ve daha sonra onları bir araya birleştirme.
Neden birleştirme sıralama denir.
Bu sıralamak edeceğiz Yani biz burada var.
Bu yüzden onlara sahip tutmak Dizi boyutu 1 kadar.
Bu yüzden 1 olduğunda, biz sadece geri dönmek Bu sıralanmış bir dizi olduğu için,
ve bu bir sıralı dizi olduğunu ve var sıralanmış bir dizi, hepimiz sıralanır ediyoruz.
Öyleyse biz ne biz ise onları bir arada birleştirme başlar.
>> Yani yol yapabilirsiniz birleşme olduğunu düşünmek
Sadece küçük kaldırmak alt dizilerin her biri sayısı
ve sadece ortaya diziye ekleyebilir.
Yani eğer biz zaman, buraya bak Bu setleri, biz 4, 6, ve 1 var.
Bu birleştirmek istediğinizde, bu ilk iki bakmak
ve biz 1 küçük, tamam, demek, önden gider.
4 ve 6, karşılaştırmak için bir şey yok o, sadece sonuna kadar onu etiketlemek için.
>> Bu ikisini birleştirdiğinizde, biz sadece Bu iki küçük birini almak
bu yüzden 1 var.
Ve şimdi biz almak Bu iki nedenle 2 küçük.
Bu iki, 3 küçük.
Bu iki, 4, 5, 6 küçük.
Yani sadece bu çekerek ediyoruz.
Ve onlar var çünkü Daha önce sıralandığını,
Eğer sadece bir tane var karşılaştırma var her zaman.
Burada çok fazla kod, sadece temsili.
Yani ortada başlayacak ve sıralama sağ ve sol
ve o zaman sadece o birleştirme.
>> Ve biz kod yok için burada birleştirme.
Ama, yine, sen giderseniz 50 çalışma, orada olacağım.
Aksi bana konuşmak gel sen eğer yine karıştı.
Yani burada serin şey iyi durumda, En kötü durumda, ve beklenen çalışma zamanı
n, her günlüğüne olan biz ettik daha iyidir
Bizim türlü geri kalanı için gördüm.
Biz gördük n kare ettik ve aslında ne
hangi büyük, n log olduğunu burada olsun.
>> Olduğunu ne kadar iyi bak.
Böyle güzel bir eğri.
Yani çok daha verimli.
Hiç can, kullanım sıralama birleştirme.
Bu size zaman kazandıracak.
Sonra tekrar, biz söylediğimiz gibi, eğer Eğer, bu alt bölgede aşağı konum
o yapmaz Bir fark çok.
Sen binlerce kalkmak ve girdilerin binlerce,
kesinlikle bir istiyorum daha verimli bir algoritma.
Her Ve yine, bizim güzel tablo Siz bugün öğrendim sıralar.
>> Bu yüzden yoğun bir gün oldu biliyorum.
Bu mutlaka gitmiyor senin pset size yardımcı olmak için.
Ama ben sadece bir feragatname yapmak istiyorum Bu bölüm sadece psets ilgili değil.
Tüm bu malzeme adil senin ara sınav için oyun.
Ve sen CS ile devam yapmak da eğer, Bu gerçekten önemli temelleri
Bu bilmeniz gerekir.
Bu yüzden bazı günler olacak Biraz daha pset yardım,
ama bazı hafta olacak daha gerçek içeriği
Bu süper gelmeyebilir Şu anda sizin için yararlı,
Eğer devam ederseniz ama ben söz veriyorum çok, çok yararlı olacaktır.
>> Peki o bölüm için var.
Tel Aşağı.
Ben bir dakika içinde yaptım.
Ama oraya gidin.
Ve ben çörek veya şeker sahip olacaktır.
Alerjik kimse mı Bu arada bir şey?
Yumurta ve süt.
Yani Donuts bir hayır vardır?
TAMAM MI.
Tamam.
Çikolata yok?
Yıldız patlaması.
Starbursts iyidir.
TAMAM MI.
Biz gidiyoruz Daha sonra önümüzdeki hafta patlamış.
Ben ne alırsınız.
Siz harika bir hafta var.
Senin spec okuyun.
>> Eğer herhangi bir sorunuz varsa bana bildirin.
Pset iki sınıflarda olmalı Perşembe size dışarı.
Herhangi bir sorunuz varsa Ben bir şey dereceli nasıl
ya neden yol şey kademeli , bana e-posta lütfen etmedi, konuş benimle gel.
Ben biraz deli Bu kulüpler hafta, ama söz veriyorum
Ben hala 24 saat içinde cevap verecektir.
Yani harika bir hafta, herkes var.
Senin pset İyi şanslar.