>> GŁOŚNIK 1: Hej wszystkim!
Witamy z powrotem do sekcji.
Więc cieszę się, że tak wielu z was, zarówno tutaj, i każdy kto ogląda w Internecie.
Tak, jak zwykle Witamy z powrotem.
Mam nadzieję, że wszystko było piękne weekend, pełen odpoczynek, relaks.
To było piękne wczoraj.
Więc mam nadzieję, że cieszył się na zewnątrz.
>> Więc najpierw kilka ogłoszeń.
Klasyfikacja.
Tak, większość z was powinna zdobyć napisz mi o swoim Scratch Pset,
jak również klasyfikacji dla Pset 1.
Tak, tylko kilka rzeczy.
Należy używać check50 w style50.
Te mają być Zasoby dla was,
aby upewnić się, że dostajesz jak najwięcej punktów, jak to możliwe
bez niepotrzebnie ich utraty.
Tak, takie rzeczy jak styl są bardzo ważne.
Mamy zamiar startu do niego.
Niektórzy z was mogą już Zauważyłem, że od Pset.
I check50 tylko bardzo łatwy sposób, aby upewnić się,
że jesteśmy rzeczywiście powrocie co należy zwrócić się do użytkownika,
i, że wszystko działa prawidłowo.
>> Na drugim notatki, upewnij się, że przesyłania rzeczy do odpowiedniego folderu.
To sprawia, że ​​moje życie tylko Trochę trudniej
jeśli przesłać Pset 2 do Pset 1 bo kiedy pobrać rzeczy,
nie ściągnąć poprawnie.
I wiem, że to trochę słaby w systemie, aby przyzwyczaić się do,
ale po prostu super Uważaj, jeśli tylko dla mnie,
tak, że kiedy dostajesz e-maile na jak 2 A.M. i jestem klasyfikacji.
Jeśli nie powodować mam szukać dookoła dla Pset.
Fajne.
>> Wiem, że to wcześnie, ale całkowicie dostał podjąć tropu
w eseju, który jest piątek, z powodu tego, że moi profesorowie byli tak jak, oh yeah.
Pamiętaj, że masz Esej ze względu na piątek.
Tak, wiem, że nikt nie lubi myśleć o midterms,
ale twój pierwszy quiz jest na 15 października które października rozpoczyna w tym tygodniu.
Tak, to może być wcześniej niż oczekiwano wszystko.
Tak, że nie jesteś wyrzucony z tropu, kiedy Wspominam przyszłym tygodniu odcinek że oh,
quiz w przyszłym tygodniu, myślałem Chciałbym dać trochę więcej
od głowy do góry teraz.
>> Tak, ustaw problem, numer trzy.
Jak ludzie mają czytać wg planu z ciekawości?
OK.
Mamy kilka.
Niby się z ostatnim tydzień, ale to jest OK.
Wiem, że to było piękne na zewnątrz.
Więc Break Out.
Zdecydowanie po zrobienia dziś przeczytać specyfikację co najmniej
spróbować jak pobieranie Kod dystrybucji i prowadzenie
jak pierwszy inicjał rzeczą, że poprosi.
Ponieważ używamy Kod dystrybucji i biblioteki
że mamy jedynie using-- --It tylko drugi raz zrobiliśmy to Pset,
szalone rzeczy mogą się zdarzyć z urządzenia,
i chcesz, aby stwierdzić, że się teraz w stosunku później.
>> Bo jeśli jest to w czwartek wieczorem lub to Środę i z jakiegoś powodu
twoje urządzenie po prostu nie robi chce uruchomić z biblioteką
lub rozkładu Kod, że środki
nie można nawet zacząć robić kodowanie.
Ponieważ nie można sprawdzić aby sprawdzić, czy to działa.
Twoja nie będzie w stanie aby sprawdzić, czy kompiluje.
Chcesz zadbać o tych, na początku tydzień, kiedy można jeszcze napisz do mnie
lub jeden z pozostałych TFS i możemy dostać te stałe.
Ponieważ są to kwestie że zamierzamy się zatrzymać
z podjęciem prawdziwy postęp.
To nie tak, jeden błąd, że można po prostu rodzaj pominąć.
Jeśli masz problemy ze swoim urządzenie lub kod dystrybucji,
Naprawdę chcesz się, że podjęte dbać o raczej wcześniej niż później.
Więc nawet jeśli w rzeczywistości nie spodoba zacząć pisać, należy pobrać dystrybucję
Kod, przeczytaj specyfikację, upewnij się, wszystko działa tam.
OK?
Jeśli można tak zrobić, ja Obiecujemy wam życie będzie łatwiejsze.
I tak pewnie będzie zrobić to teraz dobrze?
OK.
Tak, jakieś pytania?
Wszelkie sprawy logistyczne?
Każdy jest dobry?
OK.
>> Zastrzeżone dla tych jesteś w pokoju i online.
Będę się starał, aby przełączyć między PowerPoint w urządzeniu
ponieważ będziemy się jakiejś kodowanie
dziś popularnej żądanie anonimowy Sugestia ankieta wysłałem w zeszłym tygodniu.
Tak, będziemy robić niektóre kodowania.
Tak więc, jeśli macie też chcą Do uruchomienia urządzenia,
i powinny masz e-mail ode mnie, z przykładowego pliku.
Prosimy, aby to zrobić.
>> Tak, będziemy mówić o GDB, który jest debugger.
To pomoże ci rodzaj dowiedzieć się, gdzie
wszystko idzie nie tak w kodzie.
To naprawdę tylko sposób na krok przez kod, jak to się dzieje,
i być w stanie wydrukować zmienne lub zobaczyć, co się rzeczywiście dzieje
Pod maską wersety program tak działa, to jak uskoki,
i jesteś jak, bez pomysłu co się stało tutaj.
Nie wiem, co to nie na linii.
Nie wiem, gdzie to się stało.
Tak, GDB pomoże Ci w tym.
Ponadto, jeśli zdecydujesz się na nadal tak, i wziąć 61,
to będzie naprawdę być twój najlepszym przyjacielem, bo mogę powiedzieć,
bo mam zamiar przez tej klasy.
>> Mamy zamiar spojrzeć na binarny wyszukiwarka, która jeśli faceci pamiętają
świetny przykład książki telefonicznej Spektakl z klasy.
Będziemy wykonawcze, że i przechodząc przez które trochę więcej,
a następnie jedziemy przez cztery różne rodzaje, które są Bańka,
Wybór, Wejścia i Merge.
Fajne.
Tak, GDB jak wspomniałem, jest debugger.
I to są niby duże rzeczy, wielkie funkcje i polecenia
że używasz w ciągu GDB i będę chodzić można przez nią demo w sekundę.
>> Tak więc, nie jest to Zostanę streszczenie.
Postaram się zrobić to jak beton jak to możliwe dla was.
Więc złamać.
To będzie być albo przerwa jak niektóre liczby, które
oznacza linię w programie, czy można wymienić funkcję.
Więc, jeśli powiesz, że łamać głównym, zatrzyma się w głównym,
i pozwala chodzić po tej funkcji.
>> Podobnie, jeśli masz jakiś zewnętrzny Zamiana lub działać jak Cube,
że spojrzał na ostatni tydzień.
Jeśli powiesz złamać jeden z tych, gdy program trafia, że
będzie ona czekać na ciebie powiedz to, co zrobić.
Zanim będzie to po prostu wykonać tak ci może rzeczywiście krok wewnątrz funkcji
i zobaczyć, co się dzieje.
Więc Następnie, po prostu pomija Następna linia, podchodzi funkcji.
Krok.
Są to trochę abstrakcyjne.
Tak, jestem po prostu będzie działać przez nich, ale można je zobaczyć w użyciu w sekundę.
>> Krok do funkcji.
Tak jak mówiłem, jak z wymiany, to będzie
pozwalają właściwie jakbyś jak fizycznie wyjście wewnątrz,
możesz zadzierać z tych zmiennych, druk się, czym one są, zobaczyć, co się dzieje.
Lista będzie dosłownie wydrukować z otaczającego kodu.
Tak więc, jeśli rodzaj zapomnieć gdzie jesteś w programie,
lub zastanawiasz co się dzieje wokół niego,
to będzie po prostu wydrukować segment od jak pięć lub sześć linie wokół niego.
Tak, można oswoić o tym, gdzie jesteś.
>> Drukuj trochę zmienną.
Tak więc, jeśli masz klucz jak w Cezara, że ​​przyjrzymy się.
Można powiedzieć, że klucz Drukuj w dowolnym momencie.
To będzie powiedzieć, co to jest wartość że może być gdzieś wzdłuż drogi,
zastąpiłeś klucz.
Rzeczywiście można powiedzieć, że z powodu rzeczywiście można zauważyć, że wartość.
>> W miejscowych, tylko odbitki z lokalnych zmiennych.
Tak, w każdej chwili jesteś w pętli, i po prostu chcesz zobaczyć, jak, och.
Jakie jest moje ja?
Jaka jest wartość tego klucza że zainicjować tutaj?
Co to jest wiadomość w tym momencie?
To po prostu wydrukować wszystkie z nich, tak, że ty
nie muszą indywidualnie powiedzieć, Drukuj I. Drukuj wiadomość.
Przycisk Print.
A następnie wyświetlić.
Co to robi, jest jak ty krok po kroku program,
będzie to po prostu upewnij się, że jest to wyświetlając jakąś pewną zmienną
w każdym punkcie.
Tak że also-- --it jest rodzaj skrótu gdzie
nie trzeba iść dalej jak, och.
Klucz do druku lub Drukuj I. To właśnie automatycznie zrobi to za Ciebie.
>> Tak, z tym, będziemy aby zobaczyć jak to działa.
Zamierzam spróbować i przełącznik do mojego urządzenia.
Zobacz, czy mogę to zrobić.
Wszystko.
Jesteśmy po prostu będzie to odzwierciedlać.
Nie ma nic do szaleństwa na moim laptopie i tak.
OK.
To musi być ten.
To takie małe.
Zobaczymy, czy uda nam się to zrobić.
>> OK.
Alicja jest oczywiście walczy tutaj tylko trochę,
ale dostaniemy go w momento.
OK.
Jesteśmy po prostu się do zwiększenia tego.
OK.
Czy każdy rodzaj zobaczyć?
Może trochę?
Wiem, że to trochę małe.
Nie dość rysunek się jak zrobić to większe.
Jeśli ktoś wie.
Czy ktoś wie jak zrobić to większe?
OK.
Mamy zamiar rzucić się z nim.
Nie ma znaczenia, tak czy inaczej, bo to jest po prostu jest to kod, który chłopaki powinni
mają.
>> Co ważne Zacisk jest tutaj.
I mamy tutaj Dlaczego jest tak mała?
Ustawienia.
Och.
Prawdziwa Ike.
Jak to jest?
Stamtąd.
Jest to, że lepiej dla wszystkich?
OK ,.
Fajne.
>> Wiesz, kiedy jesteś w CS klasy trudności techniczne
są swego rodzaju częścią the-- Tak, niech usunąć ten.
OK.
Tak, właśnie tutaj, w dziale, które mieliśmy tutaj.
Cezar jest plik wykonywalny.
Więc zrobiłem to.
Tak, aby zrealizować jedno z GDB jest że to działa tylko na pliki wykonywalne.
Tak więc, nie można go uruchomić na dotsy.
Trzeba rzeczywiście zrobić upewnić się, że kod kompiluje,
oraz, że w rzeczywistości może być uruchomiony.
>> Więc upewnij się, że jeśli nie kompilacji, zmusić go do kompilacji,
tak, że można rodzaj uruchomienia przez nią.
Tak, aby uruchomić GDB, wszystko co robisz, Typ Gloria GDB, a potem po prostu
plik, który chcesz.
Ja zawsze błędnie Cezara.
Ale chcesz się upewnić, ponieważ jest to plik wykonywalny,
kropka błysku, tak aby TI Oznacza idziesz
uruchomić CSI masz zamiar wykonać to pliki albo z debuggera.
OK.
Tak, to zrobisz, otrzymasz tego rodzaju bełkotem.
To tylko wszystkie rzeczy o debugger.
Tak naprawdę nie trzeba martwić się teraz o tym.
I jak widać, to mamy otwarte nawiasy, PKB, blisko nawiasy,
i po prostu rodzaj wygląda nasza linia poleceń, prawda?
>> Więc, co chcemy do-- -SO, Pierwszą rzeczą,
to chcemy wybrać miejsce, aby go złamać.
Tak, jest jeden błąd w tym programie Caesar
że mogę przedstawić, że mamy zamiar się dowiedzieć.
To co robi jest potrzeba wejścia Barfoo we wszystkich czapki, iz jakiegoś powodu
Nie zmienia A. To po prostu pozostawia on sam, Czy wszystko poprawne,
ale drugi list Pozostaje niezmieniona.
Tak, mamy zamiar spróbować dowiedzieć się, dlaczego tak jest.
Więc pierwszą rzeczą, którą zwykle chcemy robić przy każdym uruchomieniu na GDB
jest dowiedzieć się, gdzie go złamać.
>> Więc Cezar jest dość krótki program.
Mamy tylko jedną funkcję, prawda?
Jaka była nasza funkcja w Cezara?
Jest tylko jedna funkcja, główna prawda?
Główną funkcją jest dla wszystkich programów.
Jeśli nie masz Main, mógłbym być trochę martwi teraz,
ale mam nadzieję, że wszyscy mieli Main tam.
Tak więc, co możemy zrobić, to możemy po prostu złamać Main, tak po prostu.
Tak, to mówi, OK.
Wyznaczamy punkt przerwania jeden tam.
>> Tak, teraz jest, aby pamiętać Cezar trwa jeden argument wiersza poleceń prawo
i nie zrobiliśmy, że jeszcze nigdzie.
Więc, co można zrobić, to kiedy rzeczywiście iść do pracy
programu, każdy program, który jesteś działa w GDB, który potrzebuje wiersza poleceń
argumenty, masz zamiar wejścia gdy po raz pierwszy rozpocząć prowadzenie go.
Tak więc, w tym przypadku zrobić Uruchom z kluczem trzech.
I będzie zacząć.
>> Tak więc, jeśli widzisz, tutaj mamy Jeśli RC nie jest równy 2.
Więc jeśli faceci mają że plik, który wysłałem do
zobaczysz, że to jak Pierwsza linia naszym głównym zadaniem, prawda?
To się sprawdza, jeśli mamy poprawna liczba argumentów.
Więc jeśli zastanawiasz czy RC jest prawidłowe,
można zrobić coś tak jak Drukuj RC.
RC jest dwa, co jest to, czego oczekuje, prawda?
>> Tak, możemy iść dalej, i dalej przez.
Tak, mamy tam jakiś klucz.
I możemy wydrukować nasz klucz aby upewnić się, że jest prawidłowe.
Ciekawe.
Nie całkiem to, czego oczekiwaliśmy.
Tak więc, jedno do realizacji z GDB też jest
że to nie jest aż faktycznie hit Następnie, że wiersz, który właśnie zobaczył
jest faktycznie wykonywana.
Tak więc, w tym przypadku kluczem jeszcze nie został przydzielony.
Więc kluczem jest jakaś wartość śmieci które widzisz na tam na dole.
Negatywny $ 120-- --It na miliard i coś dziwne rzeczy prawda?
To nie jest klucz, że spodziewaliśmy.
Ale jeśli uderzymy Dalej, a następnie spróbować i klucz Drukuj, to trzy.
>> Każdy widzi?
Tak więc, jeśli coś że jesteś jak, poczekaj.
Jest to zupełnie tak, i nie wiem,
w jaki sposób to się stało, bo wszystko, co chcę zrobić, to przypisać numer, zmienna,
spróbować uderzając Dalej, spróbuj drukować to jeszcze raz, i zobaczyć, czy zadziała.
Bo to będzie tylko do wykonania i rzeczywiście przypisać coś po tobie
uderzył Dalej.
Sens dla wszystkich?
Uh huh?
>> GŁOŚNIK 2: Kiedy losowo numery co to oznacza?
>> GŁOŚNIK 1: To jest po prostu losowo.
To jest po prostu śmieci.
To jest po prostu coś, że twój Komputer losowo przypisać.
Fajne.
Tak, teraz możemy przejść przez i tak teraz mamy to zwykły getString tekstu.
Więc, pozwól mi tylko przedstawić to, co będzie się działo, kiedy uderzył Dalej tutaj.
Nasza GDB rodzaju znika, prawda?
To dlatego, że getString Obecnie wykonanie, prawda?
Tak więc, kiedy widzieliśmy zwykły tekst jest równa GetString, otwarte nawiasy i nawiasy,
i trafiliśmy Dalej, że ma faktycznie wykonywane teraz.
Tak, to czeka na nam coś wejściowego.
>> Tak, mamy zamiar wprowadzić nasze jedzenie to co to braku jak już mówiłem
i że po prostu mówi, że jest to zakończeniu wykonywania, że ​​zamknięte
Oznacza to wspornik wyjściu z tej pętli.
Tak więc, możemy trafić Dalej, a teraz, jak jestem się, że jesteś zaznajomieni z Cezara,
to, co to jest linia zrobić.
To dla int i jest równa 0, N równa Strlen, zwykły tekst, a następnie
I jest mniejsze od n, I, plus, oraz.
Co to jest pętla zrobić?
Otwórz wiadomość.
Fajne.
Więc zacznijmy robić.
>> Tak więc, należy ten warunek pasuje dla naszego pierwszego?
Jeśli jest to B, to jest zwykły tekst I. Mamy można uzyskać informacje na temat naszych mieszkańców.
Tak więc, jest zero, a jeżeli sześć, co oczekujemy, i nasz klucz jest trzy.
Wszystko to ma sens, prawda?
Liczby te są dokładnie to, co powinno być.
Tak, nucić?
GŁOŚNIK 3: mam liczb losowych dla kopalni.
GŁOŚNIK 1: Cóż, możemy check-- --we mogą rozmawiać o tym za chwilę.
Ale powinno być coraz to.
Tak więc, jeśli mamy kapitał B dla naszej pierwszej,
warunek ten powinien go złapać, prawda?
Tak więc, jeśli uderzymy Dalej widzimy Jeśli rzeczywiście, że to wykonuje.
Bo jeśli po razem w kodzie,
ta linia tutaj, gdzie ja zwykły tekst otrzymuje się z tego arytmetyki
wykonywana tylko wówczas, kiedy Warunkiem jest prawidłowe prawo?
>> GDB będzie tylko pokazać, rzeczy, które są faktycznie wykonującego.
Więc jeśli ten warunek nie został spełniony, to po prostu się przejść do następnej linii.
OK?
Tak, mamy to.
To oznacza, że ​​to wspornik zamknięte z tej pętli teraz.
Tak, to będzie zacząć od nowa.
Tak po prostu.
Tak, że możemy uzyskać informacje o naszych mieszkańców tutaj,
i widzimy, że nasz pierwszy List nie zmieniło, prawda?
To teraz E, tak jak powinno być.
Tak, możemy kontynuować.
>> I mamy to sprawdzić.
I ta kontrola powinna działać, prawda?
To A. powinien być zmieniony trzy litery do przodu.
Ale jeśli zauważysz, my dostać coś innego.
Tak więc w tym przypadku aż tutaj, to złapać to i tak ta linia wykonana,
które zmodyfikowano naszą B. Jednak w tym przypadku, tutaj
mamy, że to po prostu pominąć go, i udał się do [? L Siff. ?]
Więc coś się tam dzieje.
Co to się mówi, jest to, że wiemy, że powinna nadrobić tutaj,
ale to nie jest.
Czy ktoś może zobaczyć, co nasze Problem jest w tym wierszu?
To bardzo minut rzeczą.
I można też spojrzeć na kodzie.
Jest line-- również zapomnieć, co to jest linia w there-- ale w [niesłyszalne].
Tak?
>> GŁOŚNIK 4: Jest na większe niż strona jeśli czytasz go w książce.
GŁOŚNIK 1: Dokładnie.
Tak więc, nie można powiedzieć, debugger ty, ale debugger
może dostać się do linii że wiesz, nie działa.
A czasem, kiedy szczególnie później w semestrze, kiedy
masz do czynienia z setek, sto kilka linii kodu, a ty
nie wiem gdzie to jest w przypadku braku, jest to świetny sposób, aby to zrobić.
Tak, uważamy, że nasz błąd.
Można to naprawić w pliku, a następnie można go uruchomić ponownie,
i wszystko będzie działać idealnie.
A najważniejszą rzeczą jest może się to wydawać, OK.
Tak.
Fajne.
Wiedziałeś, co szukasz.
Więc wiedziałem, co robić.
>> GDB może być bardzo pomocne, ponieważ Ciebie Można wydrukować wszystkie te rzeczy, które
nie.
To o wiele bardziej przydatne niż printf.
Ilu z korzystania jak sprawozdania printf
dowiedzieć się, gdzie błąd był, prawda?
Tak, z tego, że nie robić trzeba wracać,
i jak komentując w Printf lub komentując na zewnątrz,
i dowiedzieć się, co powinno być drukowane.
To właściwie tylko pozwala na krok po kroku, wydrukować rzeczy
jak idziesz przez, tak, można obserwować, jak zmieniają się w czasie rzeczywistym,
w programie jest uruchomiony.
>> I zajmuje to trochę trochę przyzwyczaić.
Gorąco polecam po prostu rodzaj bycia z nim trochę sfrustrowany
do teraz.
Jeśli spędzasz godziny na w przyszłym tygodniu nauczenie GDB,
można się zapisać tyle czasu później.
I dosłownie. powiedzieć to ludzi rocznie,
i pamiętam, kiedy wziąłem klasa, ja na to będę w porządku.
Nie.
Pset 6 przyszedł na i byłem jak, mam zamiar uczyć się
jak używać GDB, bo nie wiedzieć, co się tu dzieje.
>> Więc jeśli masz trochę czasu, więc używać go na mniejszych programów
że masz zamiar być w pracy, jak praca
przez coś podobnego Visionare, tak.
Albo jeśli chcesz dodatkowej praktyki, jestem pewien, Mógłbym wymyślić programów buggy,
Ci debugowania, jeśli chcesz.
>> Ale jeśli tylko trochę czasu, aby dostać się do niego, po prostu bawić się z nim,
to będzie naprawdę dobrze służyć.
I to jest naprawdę jeden z te rzeczy, które po prostu
spróbować i ubrudzić sobie ręce się, zanim naprawdę go zrozumieć.
I tak naprawdę tylko raz zrozumiałem Musiałem rzeczy debugowania z nim
i to jest o wiele ładniejsza, aby mieć pomysł jak debugować raczej wcześniej niż później.
OK.
Fajne.
Wiem, że to trochę jak Crash Course w GDB,
i na pewno działa na coraz nich patrzeć większe następnym razem.
Fajne.
>> Tak więc, jeśli wrócimy do naszego programu PowerPoint.
Czy to będzie działać?
Awh.
Tak.
OK.
Tak więc, jeśli kiedykolwiek potrzeba żadnej z tych, ponownie, jest lista.
Więc Binary Search, które każdy Pamięta wielkie widowisko Dawida
zgrywania książek telefonicznych w połowie.
I naprawdę nie dostać książki telefoniczne więcej,
bo jak Skąd dostać książki telefoniczne w tych dniach?
I naprawdę nie wiem.
Binary Search.
Czy ktoś pamięta Jak działa wyszukiwanie? binarny
Każdy, kto w ogóle?
Tak?
GŁOŚNIK 5: Wiesz, kiedy patrzysz na których połowa
byłoby to w, podstawie, że i pozbyć się druga połowa.
>> GŁOŚNIK 1 Dokładnie.
Tak, Binary Search, to rodzaj A-- --we lubię nazywać go podzielić i podbić.
Więc, co musisz zrobić, to będziesz wyglądać w środku,
i zobaczysz czy pasuje czego szukasz.
A jeśli nie, to spróbuj dowiedzieć się, czy to będzie w lewo
połowa lub prawa połowa.
Tak, to może być, jeśli szukasz na coś, co jest alfabetycznie,
widzisz, och.
Czy Allison się przed M?
Tak.
Tak, mamy zamiar spojrzeć na pierwsze półrocze.
>> Albo może to być jak z liczbami.
Wszystko, co można porównania, może być sortowane.
Możesz użyć wyszukiwania binarnego na.
Tak, ktoś pamięta to Wykres lub co to jest?
To Asymptotic złożoności.
Tak, to właśnie wykres opisuje, jak długo
zabierze Cię do rozwiązania problemu, jak zwiększyć liczbę rzeczy
że używasz.
>> Tak więc, mamy N, która jest czas liniowy.
Jeśli n ponad dwie, nieco lepiej, wciąż rośnie bardzo szybko.
A potem mamy Zaloguj, która jest co uważamy za Binary Search.
Jeśli zauważymy, jako problemu dostaje dużo i znacznie większy,
Czas potrzebny Ci go rozwiązać tak naprawdę nie zwiększy to znacznie.
To jak porównać tutaj na początku.
Jesteś jak, OK.
Wszystko, co tu naprawdę nie ma względu na to, który z nich korzystamy,
ale można dostać się do miliona, miliarda.
Próbujesz znaleźć some-- --you're próbuje znaleźć igłę w stogu siana.
>> Myślę, że chcesz ten problem.
Chcesz tej złożoności, a nie liniowy, bo za wszystko
wiedzieć gonna być przeszukiwania każdy igły, co siana,
próbuje szukać swojej igły.
I to nie jest zbyt zabawne, moim zdaniem.
Lubię szybko.
Lubię wydajne.
I jako pracowici uczniowie You faceci są, wiesz pracować mądrzej,
nie trudniej typu rzecz, jak ci może uzupełnić te algorytmy.
>> Więc idziemy na spacer przez tylko szybki przykład.
Myślę, że chłopaki powinni mieć ręka na Binary Search,
ale w przypadku gdy ktoś jest mało rozmyte, chcę go wzmocnić,
będziemy po prostu pójść poprzez przykład.
Tak więc, jeśli szukasz Tablica zawiera siedem.
>> Więc, po pierwsze, co robimy jest wygląda w środku, prawda?
A także masz zamiar być kodowanie Binary Szukaj w ciągu sekundy.
Tak, to będzie zabawa.
Więc patrzymy w średnie małe tablice 3.
Czy 3 równe 7?
Nie.
To sześć.
Tak, to jest mniej niż lub większe niż siedem?
Mniej niż.
Tak.
Nice guys pracy.
Czuję, jak powinienem cukierki, bo mają
chcą ją wyrzucić do stoczni.
To, co mam zamiar zrobić w przyszłym tygodniu.
Będzie na bieżąco was ostre.
>> Tak, że wyrzucamy Pierwsza połowa, prawda?
był on mniej niż.
Wiemy, że wszystko, po tej stronie lewej
będzie mniejsza niż my rzeczywiście szukają.
Tak więc, nie ma potrzeby, aby zwracać uwagę na to.
Zapomnij o tym.
Tak, teraz patrzymy na naszej prawej stronie, i patrzymy na środku tam,
a teraz jest dziewięć.
Tak, 9 is-- --Everyone?
Większe niż to, co my szuka, prawda?
Tak, mamy zamiar rzucić się wszystko prawo.
Tak.
Teraz wszyscy jesteśmy z lewej jest jeden.
Więc sprawdzić, co jest w tym jeden szukamy? to jest.
Znaleźliśmy to, co chcieliśmy.
Tak skończymy.
Dwuliniowy Szukaj.
>> A jeśli zauważysz, my miał siedem wejść tam.
To tylko nas jak trzy razy, ale jeśli robisz jak miliard,
Wiecie ile kroków miałoby to podjąć, jeśli mieliśmy cztery miliardy rzeczy?
Wszelkie domysły?
To 32.
32 kroków, aby znaleźć coś, w czterech miliardów
element tablicy z powodu potęgi dwójki.
Więc dwa jest do 32, jest do czterech miliardów.
>> Więc dość szalony jak jesteś nadal w jak stosunkowo niewielkiej liczbie etapów
znaleźć coś w cztery miliardy elementów.
Więc na tej notatce, że jesteśmy Ten kod będzie
więc wy może rzeczywiście rodzaj zobaczyć jak to działa.
W porządku, więc chłopaki mogą kodować.
Zamierzam niech chłopaki rozmawiać na trochę.
Poznaj ludzi wokół ciebie, co jest co ktoś chciał z ostatniego odcinka.
>> Więc poznać ludzi wokół ciebie.
Dyskusja na trochę.
A wszystko czego chcę od ciebie faceci to teraz tylko
spróbować stworzyć zarys Pseudokod.
OK?
Whoa.
Wszystko, czego chcę od was to, że jesteś po prostu się wypełnić ten czas sprawy.
Więc postawiłem to górna i dolne granice, które
stanowią początek i koniec naszej tablicy.
I masz zamiar faktycznie pętli i dowiedzieć się,
co robimy w tej pętli while.
>> Więc jeśli można dowiedzieć out-- mam wskazówka there-- jakie są przypadki
że my tu mamy?
Tak więc, jeśli chcesz dowiedzieć się, przypadki, będziemy pseudokod tych
a potem będziemy rzeczywiście kodować je.
I to będzie, ja myślę, mam nadzieję, że będziesz
być trochę łatwiej niż można się spodziewać.
Bo to nie jest tak dużo kodu, w rzeczywistości, co jest naprawdę fajne.
>> Mm-hm?
>> STUDENT: [niesłyszalne]?
INSTRUKTOR: Tak.
Było coś znaleźć się w środku.
>> Uczeń: Tak więc możemy użyć.
OK.
>> INSTRUKTOR: Idealny.
Więc to jest pierwsza rzecz, którą trzeba zrobić.
Więc znaleźć pola.
Świetne.
Więc masz pomysł, jak moglibyśmy rzeczywiście znaleźć środek z kodem?
>> UCZEŃ: Tak.
n na 2?
INSTRUKTOR: Tak n nad 2.
Więc jedną rzeczą do zapamiętania jest to, że twoje górne i dolne granice zmienić.
Wciąż zwężenie części tablicy szukamy się.
Tak n ponad 2 działa tylko dla pierwszej rzeczy robimy.
Więc przy górnej i dolnej pod uwagę, w jaki sposób możemy uzyskać tego środkowego elementu?
Ponieważ chcemy środku pomiędzy górną i dolną, prawda?
Mm-hm?
>> STUDENT: [niesłyszalne].
>> INSTRUKTOR: Więc mamy trochę pola.
I to będzie górna oraz dolna ponad dwa.
Niesamowite.
Nie idziemy.
Jeden wiersz w dół.
Jesteście na najlepszej drodze.
Więc teraz, że mamy średnim, co chcemy zrobić?
Po prostu w ogóle.
Nie trzeba go zakodować.
Tak.
STUDENT: [niesłyszalne]?
INSTRUKTOR: Więc to dlatego, że jesteś oraz znalezienie średnio pomiędzy dwa
nimi.
Więc jeśli myślisz o nich jako rodzaj zwiększania się ze stron
myśleć o tym, jak podejście środkowy, chcesz tak.
Więc jeśli były po obu stronach środek i mamy jak 5 i 7.
Po dodaniu ich razem ci dostać 12, podzielić przez 2, to 6.
>> Czasami trudno wyjaśnić, dlaczego to działa,
ale jeśli pracujesz przez przykład czasem,
to pomoże Ci dowiedzieć się, czy powinno być plus lub minus.
Tak.
>> STUDENT: [niesłyszalne] dokładnie w środku
gdyby mieli przypadku, gdy jest dużo mniejszych liczbach
i jak jeden wielu?
>> INSTRUKTOR: Więc wszystko, czego potrzebujesz jest środek tablicy.
Więc jeśli miał kilka małych ilościach i wtedy naprawdę duża liczba
na końcu, to nie ma znaczenia.
Ważne jest to, że są one klasyfikowane, po prostu
zajrzeć do środka Tablica bo nadal jesteś
krojenie problemu w połowie.
Fajne.
Więc teraz, że mamy średnim, co robimy dalej?
>> STUDENT: Porównaj.
INSTRUKTOR: porównanie.
Więc porównanie środek do value_wanted.
Fajne.
Więc widać tutaj mamy ta wartość chcemy się tutaj.
Pamiętaj, to jest tablica.
Tak więc środkowa odnosi się do indeksu.
Dlatego chcemy, aby zrobić wartości środku.
Nie zapomnij, jeśli chcesz porównać, dwu równych.
Ty jesteś pojedynczy równa po prostu się go przypisać,
a następnie, oczywiście, jest to będzie wartość, którą chcesz.
Więc nie rób tego.
>> Więc mamy zamiar sprawdzić, czy wartości w środku
jest równa wartości chcemy.
Nie zapomnij szelki.
Dropbox powinien odejść.
Więc co mamy zrobić w tym przypadku?
Jeśli to, co chcemy wrócić?
Próbujemy powiedzieć.
>> STUDENT: wydrukować.
>> INSTRUKTOR: Cóż, nie chce wydrukować.
Więc to jest bool tutaj, więc Aby powrócić prawdziwe lub fałszywe.
Mówimy, jest to liczba [? RRA? ?] Więc jeśli tak jest,
po prostu wrócić to prawda.
Jeśli mogę przeliterować prawda.
>> STUDENT: Dlaczego nie wrócisz do zera?
INSTRUKTOR: tak można powrócić do zera, jeśli chciał.
Ale w tym przypadku, ponieważ nasza funkcja zwraca bool,
musimy wrócić albo prawdziwe, albo fałszywe.
STUDENT: Kiedy jesteś mówiąc logiczną wyrażenia,
Można ustawić go równa fałszywe?
Podobnie jak w przypadku chcę powiedzieć, jeśli ten warunek nie jest spełniony, jak jest górna równa false.
Będzie to zrozumieć, jeśli tylko umieścić fałszywy po drugiej stronie?
INSTRUKTOR: Tak.
Tak naprawdę, jeśli jesteś zawsze robi coś
jak jest górna lub jest niższa, która zwraca true lub false
i to jest rzeczywiście zły styl powiedzmy równa jest równa true lub równych
równa się fałszywe.
Chcesz używać tego wyniku tak samo jak czeku.
Nie to, co chciałem.
To jest to, co chciałem.
Tak więc w przypadku prosisz o czymś, jak zapisać to w c.
>> Więc jeśli mamy int main (void) i coś w tym rodzaju.
I masz, jeśli jest górna jakiegoś wejścia i jesteś
z pytaniem, czy można zrobić coś w tym rodzaju?
Prawda?
STUDENT: Starałem to zrobić [niesłyszalne].
Bo jeśli it's--
INSTRUKTOR: Zgadza się.
Więc chcesz to być fałszywe, prawda?
UCZEŃ: Tak.
INSTRUKTOR: Więc w tym przypadku chcesz go wykonać, jeśli to nie jest prawda.
Tak fajne robisz nie jest to.
Więc pamiętaj okrzyk punkt neguje rzeczy?
Mówi ona [niesłyszalne] nie oznacza.
Więc jeśli spojrzymy na tak ta część tu, że
ocenia się, że fałszywe, jak chcesz go.
Nie jest prawdą, która fałszywie oznacza to, by wykonać.
Czy to ma sens?
UCZEŃ: Tak.
INSTRUKTOR: Awesome.
OK.
Więc może po prostu wrócić prawda w tym przypadku.
Więc teraz mamy dwie inne przypadków w tym przypadku.
Jakie są nasze dwa inne przypadki?
Zróbmy to w ten sposób.
Więc zacznijmy od innego jeśli wartości w środku
jest mniejsza niż wartość chcemy.
Więc nasza wartość w środku jest mniej od wartości, które szukasz.
>> Więc który związany prawda że chcemy zaktualizować?
Górnej lub dolnej?
Górna?
Tak więc, po której stronie matrycy będziemy się patrzysz?
>> STUDENT: niższe.
>> INSTRUKTOR: My idziemy się patrząc na lewo.
Więc jeśli jeszcze trochę wartość jest mniejsza.
Więc swojej wartości średniej tutaj jest mniejsza niż to, co chcemy.
Dlatego chcemy, aby wziąć prawa strona naszej tablicy.
Więc mamy zamiar aktualizować nasze dolnej granicy.
Przydzielimy więc nasze niższe.
A co sądzisz niższa powinna być?
STUDENT: wartość środkowa?
INSTRUKTOR: Więc środkowy value--
STUDENT: Plus 1.
INSTRUKTOR: --plus 1.
Czy ktoś może mi powiedzieć, dlaczego mamy, że plus 1?
>> STUDENT: [? Nie wartość?] więcej równym.
>> INSTRUKTOR: Zgadza się.
Ponieważ wiemy już, że nasza wartość środkowa nie jest równa
to i chcemy wykluczyć od wszystkich kolejnych poszukiwań.
Jeśli zapomnisz, że plus 1, to spodoba pętlę bez końca.
I będziesz po prostu złapany w nieskończonej pętli i wtedy wysypać
i coś pójdzie źle.
Więc zawsze upewnić się, że nie jesteś w tym wartość, że po prostu
spojrzał na.
Więc zadbać o to z plusem 1.
>> Więc teraz mamy ostatni warunek które zawsze ze względów bezpieczeństwa
można sprawdzić tutaj, w przeciwnym wypadku, jeśli wartość w środkowy jest większy niż wartość
chcemy.
Oznacza to, że chcemy połowa lewa.
Więc który z nich będziemy aktualizować?
Górna.
A co to jest ten jeden będzie równy?
Bliski minus 1, ponieważ, Oczywiście, chcemy
aby upewnić się, że nie jesteśmy patrząc na tej wartości średniej ponownie.
A potem mamy to.
To wszystko.
To wszystko, przeszukiwanie binarne jest.
To nie jest tak źle, prawda?
To jak 10 linii Kod z białej przestrzeni.
Tak bardzo silny, bardzo przydatne, to będzie być używając go w jednym ze swoich późniejszych psets.
Może nie ten, ale później.
Więc się go nauczyć.
Uwielbiam go.
Będzie traktować cię dobrze.
Więc czy ktoś ma jakiekolwiek pytania o poszukiwanie binarne?
Tak.
>> STUDENT: Czy to ważne czy n jest parzyste, czy nieparzyste?
>> INSTRUKTOR: Nie
Dlatego, że rzucił ją na środku, jak int, to po prostu obciąć go.
Więc będzie zatrzymać liczbę całkowitą i będzie ostatecznie uporządkować wszystko.
Więc nie musisz się o to martwić.
Każdy dobry?
Niesamowite.
Fajne.
Tak, wy się tym.
Pokaz slajdów.
Tak jak mówiliśmy, wiem David wspomniał czasy pracy złożoności.
>> Tak więc w najlepszym przypadku, to tylko jeden, który nazywamy stałą czasu.
Czy ktoś może mi powiedzieć, dlaczego to może być?
Jaki rodzaj scenariusza, który pociąga za sobą?
Mm-hm.
>> STUDENT: [niesłyszalne] first--
INSTRUKTOR: Więc będąc w średnim Pierwszym elementem, który przyszedł do nas, prawda?
Więc albo tablica z jednego lub co szukamy tylko
dzieje się zimnica w środku.
Więc to jest nasz najlepszy przypadek.
Dostać się do rzeczywistych problemów, prawdopodobnie nie zamierza osiągnąć [niesłyszalne], że często.
Co z naszym najgorszym przypadku?
Nasz najgorszy jest log n.
I że ma do czynienia z całością Uprawnienia dwie rzeczy, że rozmawialiśmy.
>> Więc w najgorszym przypadku oznaczałoby to, że musieliśmy posiekać tablicę w dół
aż do uzyskania elementem drugim.
Więc musieliśmy posiekać go na pół tyle razy, jak to było możliwe.
To dlatego, że to dlatego, że dziennik n po prostu zachować dzieląc przez dwa.
Tak więc założenia, rzeczy, trzeba wiedzieć, jeśli kiedykolwiek
zamiar użyć wyszukiwania binarnego.
Twoje elementy muszą być sortowane.
Muszą być klasyfikowane ze względu to jedyny sposób, w jaki
Można wiedzieć, czy jesteś w stanie wyrzucić połowę.
>> Jeśli miał to pogmatwany torbę numerów, a mówisz,
OK, mam zamiar sprawdzić w środku liczba i liczba Szukam
jest mniejsza niż, że jestem po prostu arbitralnie wyrzucić połowę.
Nie wiem, czy twój Liczby w tej drugiej połowie.
Twoja lista ma być sortowana.
Jak również może to być posuwają się naprzód trochę,
ale musisz mieć swobodny dostęp.
Musisz być w stanie po prostu Do tego środkowego elementu.
Jeśli masz przemierzać przez coś
czy to ma się dodatkowe kroki aby dostać się do tego elementu środkowego,
nie jest to już, bo log n dodajesz więcej pracy w to.
I to będzie trochę więcej sensu w ciągu dwóch tygodni,
ale po prostu rodzaj chciał poprzedzić, Ci faceci się zorientować, co jest
przyjść.
Ale to są dwie ważne założenia
że trzeba do listy binarnym.
Upewnij się, że nie jest to klasyfikowane.
To wielki jeden dla wy teraz.
I że możemy iść do Reszta naszych rodzaju.
Tak więc cztery sorts-- Bańka, wstawiania, wybór i seryjnej.
Oni wszyscy niby chłodny.
Jeśli faceci decydują się CS 124, dowiesz się o różnego rodzaju rodzaju.
A jeśli jesteś fanem XKCD istnieje jest naprawdę fajny komiks o
jak bardzo nieskuteczne rodzaju, które Polecam Ci będzie patrzeć.
Jednym z nich jest jak panika rodzaju, który to jak, o nie, powrócić losową tablicę.
Zamknij system.
Zostaw.
Więc naukowy humor jest zawsze dobra.
>> Więc ma ktoś pamięta rodzaju jakby tylko ogólny pomysł
jak działa sortowanie bąbelkowe.
Pamiętasz?
>> UCZEŃ: Tak.
>> INSTRUKTOR: Idź do niego.
>> STUDENT: Więc idziesz przez i jeśli jest większa, to zamienić dwa.
>> INSTRUKTOR: Mm-hm.
Dokładnie.
Więc po prostu iterację.
Sprawdź czy dwa numery.
Jeśli jeden jest większy przed niż później,
po prostu zamienić je tak, aby w W ten sposób wszystkie wyższych liczbach
propagacji w kierunku końca listy i wszystkie niższe numery bańka dół.
>> Czy on pokazać wam fajne dźwięk efekt sortowania wideo?
To trochę chłodu.
Tak jak Robert po prostu powiedział, algorytmu że po prostu przejść przez liście,
zamiana sąsiednich wartości jeśli nie są w porządku.
A potem po prostu powtarzać dopóki nie sprawiają żadnych swapów.
Tak więc nie jest źle, prawda?
Więc po prostu tutaj szybki przykład.
Więc to będzie sortować je w kolejności rosnącej.
Kiedy więc przejść przez pierwszy razem, patrzymy przez osiem
sześć nie są oczywiście w porządku, możemy zamienić je.
>> Więc spójrz na następny.
Osiem i cztery nie w porządku.
Zamień je.
A potem osiem i dwa, zamienić je.
Nie idziemy.
Więc po pierwszym przejeździe, można wiesz, że największa liczba
będzie na drodze na górze, bo to jest po prostu
będzie stale większy niż wszystko inne
i to po prostu się do bańki w górę, aż do tam koniec.
Czy to ma sens dla każdego?
Fajne.
>> Tak więc patrzymy na naszego drugiego przebiegu.
Sześć i cztery, przełącznik.
Sześć, a dwa, przełącznik.
I teraz mamy kilka rzeczy w porządku.
Więc na każdym przejściu, że aby przez cały naszej liście,
wiemy, że podobnie jak wielu numerów Na koniec zostaną posortowane.
Więc robimy trzecią przepustkę, który jest jednym wymiany.
A następnie na nasz czwarty przekazać, mamy zerowe szczelin.
I tak wiemy, że nasze Tablica została posortowana.
>> I to jest wielki sprawa z bańki rodzaju.
Wiemy, że kiedy mieć zero swapy, że
oznacza, że ​​wszystko, Jest całkowicie kolejności.
To trochę jak sprawdzić.
Więc my też będziemy kodować bańki rodzaju, które także nie jest tak źle.
Żaden z nich nie jest tak źle.
Wiem, że mogą one wydawać się trochę przerażające.
Wiem, że kiedy wziąłem klasa, nawet gdy
uczył klasę dla po raz pierwszy w ubiegłym roku,
Byłem jak, jak mogę to zrobić?
To ma sens w teorii, ale w jaki sposób rzeczywiście to zrobić?
I dlatego ja też chcę chodzić poprzez kod z was tutaj facetów.
Więc mam Pseudokod dla chłopaki tym razem.
Więc po prostu pamiętać o tym, jak jesteśmy o przejście na drugą.
Więc mamy trochę licznik, który śledzi naszych swapy,
ponieważ musimy upewnić się, że mamy do sprawdzenia tego.
A my cały szereg iteracji tak właśnie zrobił z tego przykładu.
Jeśli element jest większa niż przed Element po których jesteśmy w,
możemy zamienić je i zwiększamy NASZEGO licznik, bo jak tylko zamienić,
chcemy, aby nasze przeciw wiedzieć.
Jakieś pytania?
Coś wydaje zabawne tutaj.
STUDENT: Czy ustawić licznik na zero za każdym razem przejść przez pętlę?
Nie można poddawać się z powrotem do zera za każdym razem?
INSTRUKTOR: Niekoniecznie.
Więc co się dzieje, to przechodzimy tutaj.
Więc podczas, pamiętaj, to wykona raz bez przerwy.
Więc to będzie ustawiony licznik na zero,
wtedy to będzie iterację.
Jak to, przechodzi przez, będzie aktualizować licznik.
Jak się aktualizuje licznik, kiedy to zrobić, kiedy to dotarł do końca tablicy,
jeśli nasza lista została posortowana, Licznik zostały zaktualizowane.
>> Więc to sprawdzanie stanu i mówi, OK, jest licznik większy od zera.
Jeśli tak, to jeszcze raz.
Chcesz przywrócić, tak aby po przejść, licznik jest równy zero.
Jeśli przejdziesz przez sortowane tablica, nic się nie zmieni,
to się nie powiedzie, a ty powrót posortowana lista.
Czy to ma sens?
STUDENT: Może w trochę.
INSTRUKTOR: OK.
Jeśli istnieje jakikolwiek inny Pytanie, które pojawia się.
Tak.
>> Student: Co by funkcja się do ciężkich elementów?
>> INSTRUKTOR: Tak naprawdę możemy napisać że jeśli mamy zamiar teraz.
Fajne.
Więc na tej notatce, Alison będzie aby przełączyć się z powrotem do urządzenia.
To będzie zabawa.
I mamy ładne sortowanie bąbelkowe, co tutaj.
Więc już nie na rowerze przez tablicę.
Mamy swapy, że są równe zero.
Dlatego chcemy, aby zamienić w sąsiedztwie elementy jeśli są w porządku.
Tak więc pierwszą rzeczą, musimy nie jest iterację naszej tablicy.
>> Więc jak myślisz, moglibyśmy iterację naszej tablicy?
Mamy dla i ja równa 0.
Chcemy i być mniej niż n minus jeden minus k.
I wyjaśnię, że w drugim.
Więc to jest tutaj, gdzie optymalizacja, pamiętam, jak powiedziałem, po każdym przejściu
przez my tablicy wiedzieć, że bez względu na to on--
>> Więc mamy po jednym przejściu wiem, że to jest posortowana.
Po dwóch przejściach wiemy że to wszystko jest posortowana.
Po trzech przejściach mamy wiem, że jest klasyfikowane.
Tak więc sposób mam iteracji tędy tablicy,
jest to upewniając się tylko iść przez to, co wiemy, jest nieposortowane.
OK?
To tylko optymalizacja.
Można go napisać naiwnie tylko iteracja wszystko
to po prostu dłużej.
Z tym czterech pętli to po prostu ładny optymalizacja
ponieważ wiemy, że po każdym pełnym iteracja przez tablicę tutaj,
jak każdej pełnej pętli tutaj, wiemy, że jedna z tych pierwiastków
są sortowane na końcu.
>> Tak więc nie musisz się martwić o te.
Czy to ma sens dla każdego?
To fajny mały trick?
A więc w tym przypadku, jeżeli mamy iteracji,
wiemy, że chcemy, aby sprawdzić, czy Tablica n i n plus 1 są w porządku.
OK.
Więc oto pseudokod.
Chcemy sprawdzić, czy tablica n i n plus 1 są w porządku.
Więc co możemy mieć tam?
To będzie część warunkowa.
To będzie, jeśli.
>> STUDENT: Jeśli tablica n mniej niż tablicy n plus 1.
INSTRUKTOR: Mm-hm.
Również mniejszą lub większą niż.
STUDENT: Większy niż.
Następnie chcemy, aby zamienić je.
Dokładnie.
Teraz przejdziemy do tego, co jest Mechanizm ich zamiana?
Więc poszliśmy przez to krótko, rodzaj funkcji wymiany w zeszłym tygodniu.
Czy ktoś pamięta, jak to działa?
Tak więc nie można po prostu przypisać je, prawda?
Ponieważ jeden z nich zgubisz.
Jeśli powiedział, jest równe B i B jest równa A, wszystko nagle oboje
są po prostu równe B.
>> Więc co mamy zrobić, to my mają tymczasową zmienną, która jest
będzie posiadać jeden z naszych chwilę jesteśmy w trakcie procesu zamiany.
Więc to, co mamy, to będziemy mieć jakieś int temperatura jest równa to-- można go przypisać
na rzecz tego, który chcesz, po prostu upewnij się śledzić it--
więc w tym przypadku, będę przypisać do tablicy n plus 1.
Tak, że będzie posiadać co wartość jest w tym drugim bloku
że patrzymy.
>> A potem możemy zrobić, to możemy iść do przodu i Przypisz ponownie tablica n plus 1,
ponieważ wiemy, że mają tę wartość przechowywaną.
Jest to również jeden z wielkim things-- Nie wiem czy ktoś z was
miał problemy gdzie jeśli przełączyć dwa linii kodu nagle wszystko się udało.
Zamówienie jest bardzo ważne w CS.
Więc upewnij się, że diagram rzeczy, jeśli to możliwe
co do tego, co się rzeczywiście dzieje.
Więc teraz jedziemy do przypisać tablicy n plus 1,
ponieważ wiemy, że mają tę wartość przechowywaną.
>> I możemy przypisać, że do tablicy n lub w tym przypadku tablicy i.
Zbyt wiele zmiennych.
OK.
Więc teraz mamy przypisane tablica I plus 1 równa co jest w tablicy i.
A teraz możemy wrócić i przypisać tablicę I do czego?
Każdy, kto?
>> STUDENT: 10.
>> INSTRUKTOR: 10.
Dokładnie.
I ostatnia rzecz.
Jeśli nie zamieniłem go teraz, co musimy zrobić?
Jaka jest jedna rzecz, że będzie nam powiedzieć,
jeśli kiedykolwiek zakończyć ten program?
Co mówi nam, że my mają posortowana lista?
Jeśli nie będziemy wykonywać żadnych swapów, prawda?
Jeśli swap jest równa zera na końcu tego produktu.
Jeśli więc wykonać swap, jak my tylko nie tutaj, chcemy zaktualizować swapy.
I wiem, że nie było Pytanie o możesz wcześniej
używać zero lub jeden, zamiast true lub false.
A to co to robi tutaj.
Więc to mówi, jeśli nie swapy.
Więc jeśli swap wynosi zero, co is-- zawsze dostać moje prawdy i moje falses pomieszane.
Chcemy nam ocenić true, a tak nie jest.
Więc jeśli jest to zera, to jest fałszywe.
Jeśli go negować [? walić?] staje się prawdą.
Tak więc ta linia wykonuje.
>> Prawdy i fałszu i zer i jedynek dostać szału.
Wystarczy, jeśli wolno chodzić przez to będzie to sensu.
Ale to właśnie ten mały fragment kodu tutaj robi.
Więc to sprawdza zrobiliśmy żadnych swapów.
Więc jeśli jest to coś poza zero, to będzie fałszywa
i wszystko jest będzie ponowne uruchomienie.
Cool?
>> Student: Co przerwa robi?
>> INSTRUKTOR: Break tylko łamie cię z pętli.
Tak więc w tym przypadku byłoby tak jak zakończyć program
a ty po prostu mieć posortowaną listę.
STUDENT: Niesamowite.
INSTRUKTOR: Przepraszam?
STUDENT: Ponieważ wcześniej mamy używane napisał jeden nad napisane zera
przedstawić, że jeśli który będzie działał czy nie.
>> INSTRUKTOR: Tak.
Więc można wrócić zero lub jeden.
W tym przypadku, ponieważ nie jesteśmy w rzeczywistości cokolwiek z tej funkcji,
po prostu chcę to przerwać.
Tak naprawdę nie dbam o to.
Hamulec jest również dobre, jeśli jest używany do rozbijania się
cztery pętle lub warunków, które nie chcesz, aby utrzymać wykonywania.
To po prostu ma cię z nich.
Jest trochę rzeczy nuance.
Czuję, że nie ma Wiele skinieniem ręki,
jak dowiesz się o tym wkrótce.
>> Ale dowiesz się o tym wkrótce.
Obiecuję.
OK.
Więc nie każdy się pęcherzyków rodzaju?
Nie jest tak źle.
Iterację, używając typu swap rzeczy Zmienna temperatura, a my wszystko ustawione tam?
Fajne.
Niesamowite.
OK.
Powrót do programu PowerPoint.
Wszelkie pytania w ogóle o nich do tej pory?
Fajne.
Mm-hm.
>> STUDENT: [niesłyszalne] int main zwykle.
Czy trzeba mieć, że do tego?
>> INSTRUKTOR: Więc po prostu patrząc tylko na rzeczywistej Sortowanie.
Gdybyś miał go w jak większego programu,
to masz int main gdzieś.
W zależności od miejsca korzystać z tego algorytmu,
byłoby określić, co jest są zwracane przez nią.
Ale dla naszej sprawy, że jesteśmy ściśle patrząc na to, jak robi to w rzeczywistości
iterację tablicy.
Więc nie martw się o to.
>> Więc rozmawialiśmy o najlepszą sprawę i najgorszym z możliwych scenariuszy dla wyszukiwania binarnego.
Więc to jest również ważne, aby zrobić że dla każdego rodzaju.
Więc to, co myślisz, że jest najgorszy przypadku czas pracy sortowanie bąbelkowe?
Wy pamiętacie?
>> STUDENT: N minus 1.
INSTRUKTOR: N minus 1.
Więc to oznacza, że ​​są n minus 1 porównań.
Więc jedna rzecz zdaje sobie sprawy, że w pierwszej iteracji
przechodzimy, porównamy te two-- więc to 1.
Te dwa, trzy, cztery.
Więc mamy po jednej iteracji już cztery porównań.
Kiedy mówię o czasie pracy i n.
N oznacza liczbę porównań jako funkcję jak wiele elementów
mamy.
OK?
>> Więc przechodzimy, mamy cztery.
Następnym razem, kiedy wiemy, że nie trzeba dbać o to.
Porównując te dwa, te dwa, te dwie,
a jeśli nie mamy, że optymalizacja z czterech pętli, które napisałem,
można byłoby porównanie tu i tak.
Więc trzeba by prowadzony przez tablicę
i dokonać porównań n n razy, ponieważ za każdym razem,
prowadzony przez to sortujemy jedno.
>> I za każdym razem uruchomić poprzez Tablica wykonujemy n porównań.
Tak więc nasz czas pracy jest to, faktycznie n do kwadratu, który
jest znacznie gorsza w naszym koniec, ponieważ zalogować
oznacza, gdybyśmy mieli cztery miliard elementów, to
zajmie nam cztery miliardy kwadratu zamiast 32.
Więc nie jest to najlepszy czas pracy, ale dla niektórych rzeczy,
wiesz, czy jesteś w zasięgu pewna gama elementów
sortowanie bąbelkowe może być dobrze używać.
>> OK.
Więc teraz to, co jest najlepszym przypadku czas pracy?
STUDENT: Zero?
Lub 1?
>> INSTRUKTOR: 1 będzie więc jeden porównanie.
Prawo.
>> STUDENT: N minus 1?
>> INSTRUKTOR: Tak, tak.
Tak n minus 1.
Gdy masz pojęcie jak n minus 1, mamy tendencję do po prostu upuść go
i po prostu powiedzieć, n, bo trzeba porównać każdy z these-- każdej pary.
Więc byłoby n minus 1, które chcemy tylko powiedzieć, jest w przybliżeniu n.
Kiedy masz do czynienia z wykonywania, wszystko jest w przybliżeniu.
Tak długo, jak jest wykładnik poprawne, jesteś bardzo dobry.
>> To, jak sobie z tym poradzić.
Więc, że najlepszym przypadku jest n, która oznacza, że ​​lista jest już posortowana,
i wszystko, co robimy jest prowadzony przez i sprawdzić, czy to jest klasyfikowane.
Fajne.
Dobrze.
Więc, jak widać tutaj, że Wystarczy jeszcze kilka wykresów.
Tak n do kwadratu.
Zabawa.
Znacznie gorzej niż n, jak widzimy, i dużo, dużo gorzej niż log 2n.
A potem można również uzyskać w dziennikach logów.
I wziąć 124, można dostać się do jak gwiazda dziennika, który jest jak szalony.
Więc jeśli jesteś zainteresowany, wyszukiwanie gwiazda dziennika.
Jest to rodzaj zabawy.
Mamy więc ten wielki wykres.
Zaledwie główek, to Wykres mieć wspaniały
do połowy kadencji, ponieważ długo, aby zadać te rozrzedza.
Więc tylko główek, masz to na swoim średniookresowy na ładnym ściągawki
tam.
Więc po prostu spojrzał na bubble rodzaju.
Najgorszy przypadek, n ​​do kwadratu, najlepszy przypadek, n.
I będziemy patrzeć na innych.
>> I jak widać, tylko jeden, który naprawdę dobrze
jest scalanie sortowanie, które dostaniemy do dlaczego.
Tak więc mamy zamiar udać się do następny here-- wybór rodzaju.
Czy ktoś pamięta, jak Wybór rodzaju pracował?
Idź do niego.
>> STUDENT: Zasadniczo przejść Porządek i utworzyć nową listę.
I tak jak ty elementy wprowadzenie w, umieścić je w odpowiednim miejscu
na nowej liście.
>> INSTRUKTOR: Tak, że dźwięki bardziej jak Sortowanie przez wstawianie.
Ale jesteś naprawdę blisko.
Są one bardzo podobne.
Nawet ja się im mieszać się czasami.
Przed tym dziale ja na to czekać.
OK.
Więc to, co chcesz to jest wybór rodzaju,
sposób można myśleć o nim i sposób
I upewnij się, że nie starają się je mieszać, to przechodzi przez
i wybiera Najmniejsza liczba i
stawia, że ​​na początku listy.
To zamienia go z tym pierwszym miejscu.
Oni faktycznie mają być przykładem dla mnie.
Niesamowite.
Więc po prostu sposób, aby myśleć o it-- wyboru sortowania, wybierz najmniejszą wartość.
I mamy zamiar prowadzony na przykładzie
Myślę, że pomoże, bo Myślę, że efekty wizualne zawsze pomaga.
Więc zaczynamy z czymś że jest całkowicie nieposortowane.
Czerwony będzie nieposortowane, zielone zostaną posortowane.
To wszystko ma sens w drugim.
>> Więc przechodzimy i iteracji od początku do końca.
I możemy powiedzieć, OK, 2 nasza najmniejsza liczba.
Więc mamy zamiar wziąć dwa i będziemy aby przesunąć go do przodu naszej tablicy
bo to Najmniej mamy.
Więc to, co ten robi się tutaj.
To po prostu się do wymiany tych dwóch.
Więc teraz mamy klasyfikowane części i nieposortowane część.
A co jest dobre do zapamiętania o wybór rodzaju
to mamy do wyboru tylko z niesegregowanych części.
>> Posortowane część po prostu zostawić w spokoju.
Mm-hm?
>> STUDENT: Jak to wiedzieć, co jest Najmniejszy bez porównania go
do wszystkich innych wartości w tablicy.
INSTRUKTOR: To nie porównać.
Lubimy pominąć go.
To tylko ogólny ogólny.
Tak.
Kiedy piszemy kod jestem pewien, że będziesz bardziej zadowolony.
Ale ten pierwszy przechowywanie Element jak najmniejsze.
Porównać i ty powiedzieć, OK, to jest mniejsza?
Tak.
Trzymaj go.
Oto jest mniejsza?
Nie?
>> To jest twój najmniejszy, przypisać je do wartości.
I będziesz o wiele szczęśliwszy gdy idziemy poprzez kod.
Więc przejść, możemy zamienić go, tak to patrzymy na ten niesegregowanych części.
Więc mamy zamiar wybrać trzy out.
Mamy zamiar umieścić go na co koniec naszej uporządkowanej części.
A my po prostu będziemy robić , że robi to, i robi to.
Więc to jest nasz rodzaj Pseudokod tutaj.
Będziemy tu kodować go w sekundę.
Ale coś się chodzić poprzez na wysokim poziomie.
Masz zamiar przejść z i wynosi od 0 do n minus 2.
To kolejna optymalizacja.
Nie przejmuj się zbytnio o tym.
Tak jak mówiłeś.
Jak Jakub mówił, w jaki sposób śledzić, co nasze minimum to?
Skąd wiemy?
Musimy porównać wszystko, co w naszej liście.
>> Tak więc minimalna równa i.
To tylko, że w tym przypadku Indeks naszych wartości minimalnej.
Więc to będzie iterację i to idzie z j równa i plus 1.
Tak więc wiemy już, że to nasz pierwszy element.
Nie musimy porównać go do siebie.
Więc zaczynamy porównując ją do następnego jeden, dlatego, że to ja plus 1 do n
minus 1, który jest koniec tam tablicy.
I powiedział, że jeśli w tablicy j wynosi mniej niż tablicy minut,
następnie przypisać gdzie nasze indeksy jest minimalne.
>> Min, a jeśli nie jest równa I, w których byliśmy z powrotem tutaj.
Tak jak wtedy, gdy pierwszy raz zrobił tego.
W tym przypadku, będzie ona uruchamiana zero, to w końcu jest dwóch.
Więc nie będzie równa min i w końcu.
To mówi nam, że musimy zamienić je.
Czuję, że konkretny przykład przyczyni się znacznie więcej niż to.
Więc ja ten kod się z wami teraz i myślę, że będzie lepiej.
>> Rodzaju zazwyczaj działa w ten sposób, że w często lepiej po prostu je zobaczyć.
Więc to, co chcemy zrobić, to najpierw chcą najmniejsza
element w pozycji w macierzy.
Dokładnie to, co Jacob mówi.
Musisz zapisać, że w jakiś sposób.
Więc mamy zamiar rozpocząć tutaj iteracji po tablicy.
Mamy zamiar powiedzieć, że to nasz Pierwszy z nich po prostu zacząć.
Więc będziemy mieć int Najmniejsza jest równa w tablicy i.
>> Więc jedna rzecz zauważyć, co Czas to pętla wykonuje,
zaczynamy o krok dalej.
Kiedy zaczynamy patrzymy na to.
Następnym razem iteracji, zaczynamy w tym jeden
i przypisanie to nasza najmniejsza wartość.
Więc to jest bardzo podobny do typu bubble gdzie wiemy, że po jednym przejściu,
Ten ostatni element jest posortowana.
Z wyboru rodzaju, to jest po prostu przeciwieństwem.
>> Na każdym przejściu, wiemy, że Pierwszy jest posortowana.
Po drugim przebiegu, Drugi zostaną posortowane.
A jak zobaczyłem z przykładami slajdów, tylko część naszej klasyfikowane rośnie.
Więc ustawiając nasz najmniejszy do tablic i wszystko to robi
co jest zwężenie patrzymy na tak
zminimalizowanie liczby porównań robimy.
Czy to ma sens dla każdego?
Czy mnie trzeba uruchomić przez to raz wolniej lub innymi słowami?
Jestem szczęśliwy.
OK.
>> Więc jesteśmy przechowywania wartość w tym momencie,
ale chcemy również do przechowywania indeksu.
Więc idziemy do przechowywania Stanowisko najmniejsza
jeden, który jest po prostu będzie i.
Więc teraz Jakub jest zadowolony.
Mamy wszystko zapisane.
A teraz musimy patrzeć przez nieposortowane część tablicy.
Tak więc w tym przypadku będzie naszym nieposortowane.
To jest: i.
OK.
>> Więc to, co mamy zamiar zrobić będzie dla pętli.
Gdy trzeba iterację tablicy,
Twój umysł może pójść do do pętli.
Więc przez jakiś int k equals-- co myślimy
k będzie wynosić na początek?
To jest to, co możemy ustawić jak nasza najmniejsza wartość i chcemy go porównać.
Co chcemy, aby porównać go do?
To będzie ten następny, prawda?
Dlatego chcemy, aby być inicjowane k do i plus 1, aby rozpocząć.
>> I chcemy k w tym przypadku już rozmiar przechowywane tutaj,
więc możemy po prostu użyć rozmiaru.
Wielkość jest rozmiar tablicy.
A my po prostu chcemy aktualną k jeden za każdym razem.
Fajne.
Więc teraz musimy znaleźć najmniejszy element tutaj.
Jeśli więc iterację, mamy chcesz powiedzieć, jeśli tablica na k
jest mniejsza niż naszego najmniejszego value-- to gdzie my właściwie
śledzenie co Najmniejszy here--
następnie chcemy przypisać co nasza najmniejsza wartość.
>> Oznacza to, że, och, my jesteśmy iteracja tutaj.
Cokolwiek tu jest wartość nie nasza najmniejsza rzecz.
Nie chcemy go.
Chcemy to zmienić.
Więc jeśli mamy przesunięcia go, co robić myślisz, że może być w tym kodzie tutaj?
Chcemy, aby przypisać Najmniejszy i pozycja.
Tak więc to, co jest teraz najmniejszy?
STUDENT: Array k.
INSTRUKTOR: Array k.
I to, co jest teraz pozycja?
Co indeksy nasza najmniejsza wartość?
To jest po prostu k.
Więc tablicy k, k, to zgadzają.
Więc chcemy przypisać, że.
A potem okazało się nasz najmniejszy, tak na końcu tego dla pętli
tutaj znaleźliśmy, co nasza najmniejsza wartość, więc po prostu zamienić.
W tym przypadku, jak mówią nasi Najmniejsza wartość jest tutaj.
To jest nasza najmniejsza wartość.
>> Chcemy tylko, aby go wymienić tutaj, co jest co to funkcję zamiany na dnie
zrobił, co właśnie napisałem razem kilka minut temu.
Tak powinno to wyglądać znajomo.
A potem będzie tylko iteracji aż do osiągnięcia przez całą drogę
do końca, co oznacza, że mieć zero elementów, które są nieposortowane
i wszystko inne jest klasyfikowane.
Ma sens?
Trochę bardziej konkretnie?
Pomocy kodu?
>> STUDENT: Dla wielkości, nigdy nie naprawdę zdefiniować lub zmienić,
jak to wiedzieć?
>> INSTRUKTOR: Więc jedna rzecz zauważyć tutaj jest int rozmiar.
Więc mówimy w tym sort-- rodzaju Funkcja ta jest w tym case-- to
Wybór rodzaju, to minęło się z tej funkcji.
Tak więc, jeżeli nie zostało przekazane się, że można zrobić coś
jak z długością tablicy lub chcesz iterację
znaleźć długości.
Ale ponieważ jest przekazywana w, możemy po prostu użyj go.
Po prostu zakładamy, że użytkownik dał wam poprawny rozmiar, który
faktycznie reprezentuje rozmiar macierzy.
Cool?
>> Jeśli macie jakieś problemy z nich lub chcesz więcej praktyki kodowania rodzaju
na własną rękę, należy Do study.cs50.
To narzędzie.
Mają sprawdzania, że rzeczywiście można napisać.
Robią Pseudokod.
Mają więcej filmów i slajdów w tym tych, które używam tutaj.
Więc jeśli nadal czujesz trochę rozmyte, spróbuj się.
Jak zawsze, chodź ze mną rozmawiać, też.
Pytanie?
>> Uczeń: Czy mówisz, rozmiar jest zdefiniowane wcześniej?
INSTRUKTOR: Tak.
Rozmiar jest zdefiniowane wcześniej w górę tutaj w deklaracji funkcji.
Więc założyć, że to było przekazywane w przez użytkownika oraz dla uproszczenia,
będziemy zakładać, że użytkownik dał nam odpowiedni rozmiar.
Fajne.
Więc to jest wybór rodzaju.
Chłopaki, wiem, że uczysz dużo dzisiaj.
To gęste dane dla sekcji.
Więc z tym, będziemy aby przejść do wstawiania rodzaju.
>> OK.
Więc wcześniej musimy zrobić nasza analiza tutaj czas pracy.
Tak więc w najlepszym przypadku, przyznawana od pokazałem
Stół już mam rodzaj dał ją.
Ale najlepszym przypadku czas pracy, co myślimy?
Wszystko sortowane.
N kwadratu.
Ktoś ma wyjaśnienie dlaczego uważasz, że?
>> STUDENT: Jesteś porównując through--
INSTRUKTOR: Zgadza się.
Masz porównanie przez.
W każdej iteracji, chociaż jesteśmy zmniejszanie tego jednego,
nadal jesteś przeszukiwania wszystko, aby znaleźć najmniejszy.
Więc nawet, jeśli najmniejszą wartość Jest tu na początku
nadal jesteś porównując ją przeciwko wszystkim innym
aby upewnić się, że najmniejsza rzecz.
Więc w końcu uruchomiony przez około n do kwadratu razy.
Dobrze.
A co w najgorszym przypadku?
Również n do kwadratu, ponieważ masz zamiar robić tę samą procedurę.
Więc w tym przypadku, wybór jakby coś
że również zadzwonić oczekiwany czas pracy.
Tak w innych, po prostu wiem, górne i dolne granice.
W zależności od tego jak szalony nasz Lista jest i jak nieposortowane jest,
różnią się one między n lub n kwadratu.
Nie wiemy.
>> Ale ponieważ wybór rodzaju ma to samo najgorszy i najlepszy przypadek, który mówi nam, że
bez względu na to, jaki typ wejścia mamy mają, czy to całkowicie
sortowane lub całkowicie odwrócić klasyfikowane, to
będzie mieć taką samą ilość czasu.
Więc w tym przypadku, jeśli pamiętam z naszej tabeli,
faktycznie miał wartość te dwa gatunki nie mają,
co jest z oczekiwaniami środowiska wykonawczego.
Wiemy, że gdy prowadzimy wyboru rodzaju,
to na pewno uruchomić n do kwadratu czasu.
Tam nie ma zmienność.
To jest po prostu oczekuje.
I znowu, jeśli chcesz dowiedzieć się więcej, wziąć CS 124 na wiosnę.
Dobrze.
Widzieliśmy ten jeden.
Fajne.
Więc Sortowanie przez wstawianie.
A ja prawdopodobnie będzie zaciosać przez to.
Nie masz chłopaki kodować go.
Będziemy po prostu przejść przez to.
Więc Sortowanie przez wstawianie jest rodzajem z podobna do wyboru rodzaju
się, że mamy zarówno nieposortowane i sortowane część tablicy.
>> Ale co innego jest to, że jak przejść przez jeden po drugim,
po prostu wziąć cokolwiek numer jest następny w naszym nieposortowane,
sortować je i poprawnie do naszego posortowanej tablicy.
To będzie bardziej sensowne przykładzie.
Tak więc wszystko zaczyna jako nieposortowane, Podobnie jak w przypadku wyboru rodzaju.
I mamy zamiar to rozwiązać w porządku rosnącym, jak byliśmy.
Tak więc na naszym pierwszym przejściu bierzemy pierwszą wartość
i powiedzieć, OK, jesteś Teraz na liście przez siebie.
>> Ponieważ jesteś na liście przez siebie, są klasyfikowane.
Gratulacje dla bycia Pierwszy element w tej tablicy.
Jesteś już sortowane wszystko na własną rękę.
Więc teraz mamy klasyfikowane i nieposortowane tablica.
Teraz bierzemy pierwszy.
Co się dzieje między tutaj i tutaj jest to, że możemy powiedzieć,
OK, mamy zamiar spojrzeć na Pierwsza wartość naszego niesegregowanych tablicy
i mamy zamiar wprowadzić go w jego właściwe miejsce w posortowanej tablicy.
>> Więc co robimy jest bierzemy 5 i powiedzieć, OK, 5 jest większa niż 3,
więc po prostu włóż go w prawo na prawo od tego.
Jesteśmy dobrzy.
Więc idziemy do naszego następnego.
I bierzemy dwa.
Możemy powiedzieć, OK, 2 jest mniej niż 3, więc wiemy, że to
musi być Przód naszej liście teraz.
Więc co możemy zrobić, to możemy wcisnąć 3 i 5 w dół i ruszamy 2 do tego pierwszego gniazda.
Więc po prostu wkładając ją do prawidłowe miejsce powinno być.
>> Następnie patrzymy na nasze następny, i mówimy 6.
OK 6 jest większa niż wszystko, co w naszej posortowanej tablicy,
więc po prostu oznaczyć go do końca.
A potem spojrzeć na cztery.
4 jest mniejsza niż 6, to jest mniej niż 5, ale jest większy niż 3.
Więc po prostu włożyć ją w prawo w środkowy między 3 i 5.
Tak więc, aby to trochę nieco bardziej konkretne,
tutaj jest trochę pomysł, co się stało.
Więc dla każdego elementu niesegregowanych, mamy określić, gdzie w części posortowanej
to jest.
>> Tak więc mając na uwadze sortowane i niesortowane,
musimy przechodzić przez i rysunek tam, gdzie to pasuje w posortowanej tablicy.
I wstawiamy go przez przesunięcie elementy, na prawo od niej w dół.
A potem po prostu zachować iteracja Dopóki
mają zupełnie posortowana lista gdzie jest teraz zerową niesortowana
i zajmuje sortowych Całość naszej liście.
Więc jeszcze raz, żeby było bardziej konkretne, mamy Pseudokod.
>> I tak jest w zasadzie dla równą 0 do n minus 1
to tylko długość naszej tablicy.
Mamy pewną element, który jest równy Pierwsza tablica lub pierwsze indeksy.
Stawiamy j równą.
Tak więc, j jest większa niż zero i tablica, j minus 1
jest większa niż elementem, więc wszystko, co robi
upewniając się, że jest Twój j naprawdę reprezentuje
nieposortowane część tablicy.
>> Więc póki nie jest jeszcze rzeczy sortowanie i jeden minus is-- co j
jest elementem jej?
J nie został zdefiniowany tutaj.
To trochę denerwujące.
OK.
Tak czy inaczej.
Więc j minus 1, jesteś sprawdzanie element przed nim.
Mówisz, OK, jest elementem zanim gdziekolwiek am-- I niech
rzeczywiście zwrócić na to uwagę.
Więc powiedzmy, że jest to jak w naszym drugim przejściu.
Tak i będzie równa 1, która jest tutaj.
>> I tak będzie równy 1.
To byłoby 2, 4, 5, 6, 7.
Dobrze.
Więc nasza elementem w tym przypadku będzie równa cztery.
I mamy trochę j, który jest będzie równe 1.
Och, j jest zmniejszanie.
To co to jest.
Więc j jest równa i, więc co to jest powiedzenie, że jak iść naprzód,
jesteśmy po prostu upewniając że nie jesteśmy na
indeksowanie w ten sposób, gdy próbujemy włożyć rzeczy do naszego posortowanej listy.
>> Tak więc, gdy j wynosi 1, i w tym przypadku Tablica j minus jedno- tak tablica j minus jeden
jest 2 w tym case-- jeśli to większy niż element
potem to wszystko robi przenosi rzeczy w dół.
Więc w tym przypadku, jedna tablica j minus będzie tablica zero, czyli 2.
2 nie jest większa niż 4, więc to nie wykonuje.
Tak więc zmiana nie rusza się.
Co to robi jest tu po prostu przesuwając posortowaną tablicę w dół.
W tym przypadku, w rzeczywistości, to może do-- zróbmy to 3.
Więc jeśli mamy przejść przez z ten przykład, że jesteśmy teraz tutaj.
To jest posortowana.
To nieposortowane.
Cool?
I tak jest równe 2, tak Nasz elementem jest równa 3.
I naszym j wynosi 2.
Tak więc i my patrzeć przez powiedzieć, OK, to jedna tablica j minus
większy niż element że patrzymy?
A odpowiedź brzmi: tak, prawda?
4 jest większa niż 3 i j wynosi 2, więc ten kod jest wykonywany.
>> Więc co teraz robimy tablicę na 2, tak, właśnie tutaj, możemy zamienić je.
Więc po prostu powiedzieć, OK, tablica Obecnie w dwóch będzie trzech.
I j będzie wynosić j minus 1, czyli 1.
To straszne, ale wy pomysł.
J jest teraz równa jeden.
I tablica j jest tylko będzie równej naszej elementu, która wynosiła 4.
I usunięte coś nie powinienem mają lub miswrote coś,
ale chłopaki pomysł.
>> To przenieść na n.
A potem, jeśli były, to by pętla ponownie i to powiedzieć, OK, j wynosi 1 teraz.
I tablica j minus 1 jest teraz 2.
Czy 2 mniej niż naszym elementu?
Nie?
To oznacza, że ​​mamy ten element włożony
w odpowiednim miejscu w naszym sortowanej tablicy.
Wtedy możemy wziąć to i powiedzieć, OK, nasz posortowana tablica jest tutaj.
I zajęłoby to numer 6 i być jak, dobrze, jest 6 mniej niż ten numer?
Nie?
Fajne.
Jesteśmy dobrze.
>> Zrób to jeszcze raz.
Mówimy 7.
7 jest mniejsza niż pod koniec naszego posortowanej tablicy?
Nie.
Więc jesteśmy w porządku.
Więc to będzie klasyfikowane.
W zasadzie to wszystko działa jest to mówiąc zabiorą
Pierwszy element Twój nieposortowane tablica,
dowiedzieć się, gdzie to idzie w posortowanej tablicy.
I to właśnie dba swapów, aby to zrobić.
Jesteś w zasadzie tylko zamiana dopóki nie jest w odpowiednim miejscu.
Wizualny obraz jest, że jesteś porusza wszystko przez to robić.
>> Tak to jest jak pół bańki sort-owskiej.
Zapoznaj się badania 50.
Gorąco polecam spróbować kodować to na własną rękę.
Jeśli masz jakiekolwiek problemy lub chcesz zobacz przykładowy kod dla typu wstawiania
proszę dać mi znać.
Jestem zawsze w pobliżu.
Więc w najgorszym przypadku czas pracy i najlepszym przypadku środowiska wykonawczego.
Jak facet widział od stołu już pokazałem, to zarówno n do kwadratu i n.
>> Więc niby schodzili z tego, co mówił o naszych poprzednich rodzaju, najgorsze
Sprawa jest, że jeśli czas pracy to całkowicie nieposortowane,
mamy do porównania wszystkich tych n razy.
Mamy mnóstwo porównań robić bo jeśli jest to w odwrotnej kolejności,
mamy zamiar powiedzieć, OK, to jest taki sam, to jest dobre
i ten będzie musiał być porównywane przed pierwszym mają być przeniesione z powrotem.
A ponieważ mamy ku koniec ogona, mamy
porównanie, porównaj, porównać przeciwko wszystkiemu.
>> Tak więc kończy się na tym, że około n do kwadratu.
Jeśli jest poprawne wtedy powiedzieć, OK, 2, jesteś dobry.
3, jesteś w porównaniu do dwóch.
Jesteś dobry.
4, po prostu porównać do ogona.
Jesteś dobry.
6, w porównaniu do ogona, jesteś w porządku.
Więc dla każdego miejsca, czy to już sortowane, robisz jedno porównanie.
Więc to jest po prostu brak.
A ponieważ mamy najlepszym przypadku czas pracy n i najgorszym starcie n
kwadratu, nie mamy spodziewany czas pracy.
>> To po prostu zależy od Chaos naszej liście tam.
I znowu, inny wykres i inny stolik.
Więc różnic pomiędzy rodzajami.
Jestem po prostu będzie wiatr przez, ja poczuć się jak rozmawialiśmy szeroko
o tym, jak wszelkiego rodzaju od zmieniać i łączyć.
Więc Sortowanie przez scalanie jest ostatni Będę nosił was z.
Mamy dość barwny obraz.
Więc połączyć algorytm sortowania jest rekurencyjny.
Więc nie wiem, co wy rekurencyjna funkcja?
>> Każdy, kto chce powiedzieć?
Chcesz spróbować?
Tak jest po prostu funkcja rekurencyjna funkcja, która nazywa siebie.
Więc jeśli jesteście zaznajomieni z ciągu Fibonacciego,
który jest uznany rekurencyjne, ponieważ wziąć dwie poprzednie
i dodać je razem aby uzyskać następny.
Tak rekurencyjne, zawsze myślę rekursji co jak spirali
tak, jesteś jak rosną w dół do niego.
Ale to tylko funkcja że nazywa się.
>> I, rzeczywiście, bardzo szybko I może pokazać, co to wygląda.
Więc tutaj rekurencyjne, jeśli spojrzymy, to jest rekurencyjny sposób podsumować na tablicę.
Więc wszystko, co możemy zrobić, to mamy sumę funkcji
Suma, która ma rozmiar i tablicę.
A jeśli zauważysz, rozmiar ubytki o jeden za każdym razem.
A wszystko to nie jest wtedy, gdy x jest równa zero-- więc jeśli rozmiar tablicy
jest równa zero-- powraca do zera.
>> W przeciwnym razie jest to streszcza ostatni element tablicy,
a następnie wykonuje sumę Reszta tablicy.
Więc to jest po prostu łamanie go do coraz mniejszych problemów.
Krótko mówiąc, rekurencja, funkcja, która nazywa siebie.
Jeśli to wszystko masz z tego, to, co jest funkcja rekurencyjna.
Jeśli wziąć 51, otrzymasz bardzo, bardzo wygodne z rekursji.
To jest naprawdę fajne.
To miało sens w jak 3 AM jedną noc.
A ja na to, dlaczego nigdy tego używać?
>> Więc dla scalania rodzaju, w zasadzie co to będzie zrobić, to jest to
będzie rozbicie go i złamać aż to tylko pojedyncze elementy.
Poszczególne elementy są łatwe do sortowania.
Widzimy, że.
Jeśli masz jeden element, to już za sortowane.
Tak więc na wejściu elementów n, gdy n jest mniejsze niż 2,
po prostu wrócić, bo tej pomocy to 0 lub 1, jak widzieliśmy.
Ci, są uważane za elementy posortowane.
>> Inaczej przerwać ją na połowę.
Sortuj pierwszą połowę, drugą sortowania na pół, a następnie połączyć je razem.
Dlaczego to się nazywa Sortowanie przez scalanie.
Mamy więc tutaj będziemy sortować je.
Więc trzymamy ich posiadania dopóki rozmiar tablicy to 1.
Więc kiedy jest jeden, po prostu wrócić bo to jest posortowana tablica,
i to jest posortowanej tablicy, i to posortowanej tablicy, wszyscy jesteśmy klasyfikowane.
Tak więc, co możemy zrobić, to my rozpocząć łączenie ich ze sobą.
>> Tak więc sposób można Łączenie jest myśleć o
po prostu usunąć mniejsze Ilość każdej z tablic podrzędnych
i po prostu dodać go do wyłonił tablicy.
Więc jeśli spojrzeć tutaj, kiedy mamy te zestawy mamy 4, 6 i 1.
Kiedy chcemy połączyć te, patrzymy na tych dwóch pierwszych
i powiedzieć, OK, 1 jest mniejszy, to idzie do przodu.
4 i 6, nie ma nic do porównania go tylko oznaczyć je do końca.
>> Gdy połączymy te dwa, po prostu wziąć mniejszy jeden z tych dwóch,
więc jest to jeden.
A teraz bierzemy mniejszy z tych dwóch, SO2.
Mniejszy z tymi dwoma, 3.
Mniejszy z tych dwóch, 4, 5, 6.
Więc po prostu ściągając je.
A ponieważ mam posortowane wcześniej,
wystarczy jeden Porównanie każdym razem.
Więc więcej kodu, po prostu reprezentacja.
Więc gdy w środku i sortowania po lewej i prawej
a potem po prostu połączyć te.
>> I nie mamy kodu do scalenia tutaj.
Ale znowu, jeśli pójdziesz na studia 50, to będzie tam.
Inaczej przyjść do mnie porozmawiać jeśli nadal mylić.
Tak fajne jest to, że najlepszym przypadku, w najgorszym przypadku, a oczekiwano czas pracy
są w dzienniku n, która Jest o wiele lepiej niż mamy
widoczna dla reszty naszego rodzaju.
Widzieliśmy n do kwadratu i to, co w rzeczywistości
się tu n log n, który jest świetny.
>> Spójrz, jak wiele lepiej, że jest.
Takie ładne krzywej.
O wiele bardziej efektywne.
Jeśli kiedykolwiek możliwe, stosowanie scalania sortowania.
Pozwala zaoszczędzić czas.
Potem znowu, jak już powiedzieliśmy, jeśli jesteś w tej dolnej części,
to nie robi, że dużej różnicy.
Dostać się do tysięcy i tysiące wejść,
na pewno chcesz bardziej efektywny algorytm.
I znowu, nasz piękny stół wszystkim rodzaju, że chłopaki nauczyli dziś.
>> Tak wiem, to było gęste dzień.
Nie jest to koniecznie dzieje aby pomóc w Pset.
Ale ja po prostu chcę, aby zastrzeżenie że sekcja nie tylko psets.
Wszystko to materiał jest sprawiedliwe Gra dla midterms.
A także, jeśli nie dalej z CS, to są naprawdę ważne fundamenty
które musisz znać.
Więc kilka dni będzie trochę więcej pset pomocy,
ale kilka tygodni będzie znacznie bardziej rzeczywista zawartość
że nie może wydawać się super, przydatne dla Ciebie w tej chwili,
ale obiecuję, jeśli nadal na będzie bardzo, bardzo przydatna.
>> Więc to dla sekcji.
W dół do drutu.
Zrobiłem to w ciągu jednej minuty.
Ale nie jesteś.
I będę miał pączki i cukierki.
Czy ktoś jest uczulony na coś, na drodze?
Jajka i mleko.
Więc pączki są nie?
OK.
Dobrze.
Czekolada nie?
Gwiazda.
Starbursts są dobre.
OK.
Mamy zamiar mieć Gwiazda w przyszłym tygodniu to.
To, co dostanę.
Chłopaki mają wielki tydzień.
Przeczytać specyfikację.
>> Daj mi znać, jeśli masz jakiekolwiek pytania.
Pset powinny być dwa stopnie do ciebie do czwartku.
Jeśli masz jakieś pytania o tym, jak coś mi klasyfikowane
lub dlaczego klasyfikowane coś jak ja nie, napisz do mnie, chodź ze mną rozmawiać.
Jestem trochę szalony to tydzień, ale obiecuję
Będę jeszcze odpowiedzieć w ciągu 24 godzin.
Więc mają wielki tydzień, każdego.
Powodzenia w Pset.