[MUZYKI] 

ANDI PENG: Witamy w tygodniu 3 sekcji. Dzięki, chłopaki, na wszystko przychodzi do tej wcześniejszej godzinie rozpoczęcia dzisiaj. Mamy ładny, mały kameralna grupa dziś. Więc mam nadzieję, że wrócimy do wykończenie, być może, na początku, trochę wcześnie dzisiaj. Tak szybko, tylko niektóre Komunikaty dla porządku obrad dziś. Zanim zaczniemy, jesteśmy będzie po prostu przejść nad niektóre krótkie kwestie logistyczne, zbior pytania, zdać sprawozdanie, takie rzeczy. A potem będziemy nurkować w prawo. Będziemy używać debuggera GDB do nazwie rozpocząć obalania nasz kod, który David wyjaśnione w wykładzie na drugi dzień. Pójdziemy na czterech typów rodzajów. Pójdziemy na nich dość szybko ponieważ są one bardzo intensywne. Ale wiem, że wszystkie slajdy i Kod źródłowy jest zawsze online. Dlatego zachęcamy, co Lektura, do wrócić i spojrzeć na to. 

Pojedziemy przez notacji asymptotycznej, które tylko fantazyjny sposób na powiedzenie "czas pracy" gdzie mamy duże O, które David wyjaśnione w wykładzie. I mamy też Omega, które jest dolna granica czas pracy. I porozmawiamy nieco więcej szczegółowe dotyczące jak te prace. I wreszcie, pójdziemy nad wyszukiwania binarnego, ponieważ wielu z was, którzy mają już Spojrzał na swoich psets Zapewne wiesz, że że jest to kwestia, która jest w twoim pset. Więc wszyscy są szczęśliwi że obejmuje to dzisiaj. 

I wreszcie, na swoje feedback sekcja, tak naprawdę pozostawił około 15 minut w koniec po prostu przejść nad logistyka pset3, wszelkie pytania, może trochę wskazówek, jeśli chcesz, przed rozpoczęciem programowania. Więc spróbujmy dotrzeć materiał dość szybko. A potem możemy spędzić trochę czasu biorąc więcej pytań dotyczących zbior. OK. 

Szybko, więc tylko kilka Komunikaty zanim zaczniemy dziś. Po pierwsze, zapraszamy do dokonywania go przez dwóch swoich psets. I przyjrzał się your-- tak, niech dostać brawa dla tego jednego. Właściwie, to było naprawdę, naprawdę pod wrażeniem. I klasyfikowane pierwszy pset dla was w zeszłym tygodniu i zrobiliście niesamowite. 

Styl był na miejscu oprócz kilku uwag. Upewnij się, że jesteś zawsze Komentując swój kod. Ale twoje psets byli na miejscu. I tak trzymać. I to jest dobre dla równiarka do zobaczyć, że chłopaki stawiają w tyle wysiłku w swoim stylu i projektowania w kodzie że chcielibyśmy, aby zobaczyć. Więc jestem przekazując mojej wdzięczności do końca TAS. 

Jednak istnieje Kilka pytań debrief Chcę po prostu przejść nad tym pozwoliłoby zarówno moje życie i wiele druga TAs "mieszka nieco łatwiejsze. Po pierwsze, zauważyłem to obok week-- ilu z was zostały uruchomione check50 na kod Przed wysłaniem? OK. Tak więc każdy powinien robić check50, because-- secret-- faktycznie uruchomić check50 ramach naszej poprawności skrypty do testowania kodu. Więc jeśli twój kod zawodzi check50, według wszelkiego prawdopodobieństwa, to prawdopodobnie będzie nie nasz data, jak również. Czasami chłopaki mają prawo odpowiedzi. Podobnie jak w chciwy, niektóre masz odpowiednie numery, po prostu wydrukować kilka dodatkowych rzeczy. I że dodatkowe rzeczy faktycznie nie sprawdzić, ponieważ komputer nie naprawdę wiedzą, co to jest szukasz. I tak będzie po prostu uruchomić poprzez, zobaczyć, że wyjścia nie ma pasuje, czego oczekujemy odpowiedzi być, i zaznaczyć, że jest źle. 

I wiem, że stało się w niektóre z przypadków, w tym tygodniu. Wróciłem więc i ręcznie przeklasyfikowanie wszystkich na kod. W przyszłości jednak Proszę, upewnij się, że używasz sprawdzić 50 na kodzie. Bo to jest rodzaj bólu TA aby wrócić i ręcznie zmiana klasyfikacji każdy pset dla każdego pojedyncze, mało brakowało instancji. Więc nie ma się żadnych punktów. Myślę, że zdjął może jedna lub dwie projektowania. W przyszłości jednak, jeśli jesteś braku check50, punkty zostaną podjęte od poprawności. 

Ponadto psets są ze względu piątki w godz. Myślę, że istnieje siedem minut późnego okresu karencji, że daje. Na czas Harvarda, są dopuszczone do za siedem minut późno na wszystko. Więc tutaj w Yale, będziemy przestrzegać, że dobrze. Ale dość dużo, na 12:07, jeśli pset nie jest, to będzie oznaczone jako późno. I tak, gdy jest zaznaczone tak późno, TA-- jestem nadal będzie klasyfikacji swoich psets. Więc można jeszcze zobaczyć gatunek pojawiają. Jednak wiem, że na koniec semestru, wszystkie późne psets będzie tylko automatycznie zerowany przez komputer. 

Robimy to z dwóch powodów. Jeden z nich, czasem dostajemy usprawiedliwiona, jak wymówek dziekana, później, że nie wiem o jeszcze. Więc chcemy upewnić się, mamy klasyfikacji wszystko tylko w przypadku, jak, jestem brakuje pretekst dziekana. A po drugie, należy Umysł, nadal można upuść jeden pset, że ma pełne punkty zakresie. I tak lubimy klasy wszystkich psets tylko aby upewnić się, że oscyloskopu tam i że je spróbować. Więc nawet jeśli jest późno, będziesz nadal zaliczenia punktów zakresu, tak myślę. 

Więc morał tej historii jest, aby że twoje psets są na czas. A jeśli nie są one na czas, wiem, że to nie jest wielki. Tak, zanim przejdę, czy ktoś ma Wszelkie pytania dotyczące informacji zwrotnej pset? Tak. 

PUBLICZNOŚCI: Czy powiedzieć, że może spaść jedną z psets? 

ANDI PENG: Tak. Więc nie ma dziewięć psets ogólna w ciągu semestru. A jeśli masz zakres points-- więc zakres jest tak, dość dużo, jesteś usiłujących dokonania Problem, jesteś oddanie się w czasie, ty pokazując, że masz wykazać czytałeś spec. To dość dużo zakres. A jeśli spełniają Punkty zakres, mamy może spaść do najniższych jeden na pełnym zakresie. Więc to w swoją korzyść wypełnić i spróbować każdy pset. 

Nawet upload-- jeśli żaden z ich pracy, przesłać je wszystkie. A potem mamy nadzieję być w stanie Ci niektóre z tych punktów z powrotem. Chłodny. Jeszcze jakieś pytania? Wielki. 

Po drugie, biuro hours-- kilka szybkie notatki o godzinach urzędowania. Więc po pierwsze, chodź na początku tygodnia. Nikt nie jest nigdy w godziny pracy w poniedziałki. Christabel przyszedł godziny pracy zeszłej nocy. Tak, Christabel. A co mamy w biurze godzin w nocy, Christabel? 

PUBLICZNOŚCI: Mieliśmy lody. 

ANDI PENG: Tak to prawda, mieliśmy lody w godzinach pracy w nocy. Chociaż nie mogę obiecać, że będziemy mieć lody w godzinach pracy co tydzień, co mogę ci obiecać jest to, że nie będzie to znacząco lepszy stosunek ucznia do TA. Podobnie jak prawda, to jak trzy do jednego. Mając na uwadze, że kontrastują z Czwartek, masz około 150 Podkreślił dzieci i naprawdę nie lody. I to nie tylko wydajne dla każdego. Więc morał tej historii jest, przyjść wcześnie do godzin pracy biura i dobrych rzeczy stanie się. 

Ponadto, przygotowana do zadawania pytań. Wiesz? Niezależnie od tego, TAS I myślę, mówili, byliśmy coraz parę studentów którzy wchodzą w czwartek o, jak, 10:50 nie po przeczytaniu specyfikacji jest jak mi pomóc, pomóż mi. Niestety w tym momencie nie ma nie wiele możemy zrobić, aby pomóc. Więc proszę przyjść na początku tygodnia. Przyjdź wcześniej do godzin pracy biura. Przygotowana do zadawania pytań. Upewnij się, że jako student, to miejsce, gdzie musisz być tak, że TAs może Cię razem, co jest, co godziny pracy powinien być przeznaczony na. 

Po drugie, tak, wiem, profesorów jak zaskoczyć nas z testów. Miałem profesor tych jak, yo, przy okazji, pamiętać, że śródokresową masz w następny poniedziałek. Tak, nie wiedziałem o tej perspektywie średnioterminowej. Więc mam zamiar być, że TA że przypomina ci cały ten quiz, 0-- bo wiesz, że jesteśmy CS. Teraz, że zrobiliśmy tablice, można uzyskać dlaczego to jest quiz, 0, nie quizu 1, co? OK. Och, mam kilka chichocze na jednym. OK. 

Więc Quiz 0 będzie 14 października, jeśli jesteś w dziale poniedziałku do środy i 15 października, jeśli jesteś w sekcja wtorek-czwartek. Powyższe nie ma zastosowania do tych, na Harvardzie who-- Myślę, że wszyscy będziemy odrywania quizy na 14. 

Więc tak, w przyszłym tygodniu, jeśli David, w wykładzie, idzie, Tak, tak, o tym quiz, w przyszłym tygodniu, wszyscy nie będzie w szoku, ponieważ przyszedł do sekcji i wiesz, że Quiz 0 jest w dwa tygodnie. I będziemy mieli recenzję sesje i wszystko. Więc nie ma obaw o się bać za to. Wszelkie pytania before-- wszelkie pytania na wszystkich dotyczących zagadnień logistycznych, klasyfikacji, godziny pracy, sekcje? Tak. 

PUBLICZNOŚCI: Więc quiz będzie podczas wykładu? 

ANDI PENG: Tak. Więc quizu, jak sądzę, jest 60 minut przydzielone w tym przedziale czasowym że będziesz po prostu wziąć w sali wykładowej. Więc nie masz przyjść na, jak, losowej 7:00 PM. Wszystko jest dobrze. Tak. Chłodny. 

W porządku. Więc będziemy przedstawić koncepcję dla Ciebie w tym tygodniu, że David ma już rodzaj z poruszone w wykładzie w ubiegłym tygodniu. To się nazywa GDB. A ilu z was, podczas gdy w przebieg pisanie psets, Zauważyłem duży przycisk z napisem "Debug" na górze IDE? OK. Więc teraz my rzeczywiście się wydobyć tajemnica co to przycisk rzeczywiście robi. I gwarantuję Ci, że jest to piękna, piękna rzecz. 

Tak, aż do teraz, myślę, że nastąpiła dwie rzeczy Uczniowie byli zazwyczaj robi podczas debugowania psets. Jeden, to albo dodać printf () - więc co kilka linii, dodają w printf () - och, co to jest zmienna? Och, co to jest zmienna now-- i rodzaj zobaczyć postęp Twój kod, jak to działa. Albo druga metoda dzieci nie jest że wystarczy napisać całość a potem jak to w końcu. Mam nadzieję, że to działa. Gwarantuję Ci, GDB jest lepszy niż w obu tych metod. Tak. Więc to będzie twój nowy najlepszy przyjaciel. Bo to piękna rzecz że wizualnie wyświetla zarówno co robi Twój kod w określonym punkcie jak również to, co wszystkie swoje zmienne są nośne, jak to, co ich wartości, w tym konkretnym miejscu. I w ten sposób można naprawdę ustawić punkty przerwania w kodzie. Możesz przejrzeć linia po linii. I GDB będzie po prostu za Ci, wyświetlane dla Ciebie, co wszystkich zmiennych są, co robią, co się dzieje w kodzie. I w taki sposób, to jest o wiele łatwiej zobaczyć co się dzieje, zamiast printf-ing lub zapisywać swoje wypowiedzi. 

Więc zrobimy przykład tym później. Tak więc wydaje się nieco abstrakcyjne. Nie martw się, zrobimy przykłady. I tak w istocie, trzy największe, Najczęściej używane funkcje trzeba w GDB są Następnie Krok nad, i Krok do przycisków. Mam zamiar udać się nie, rzeczywiście, teraz. 

Więc można zobaczyć, że wszyscy faceci lub należy powiększyć trochę? Z tyłu, można zobaczyć, że? Powinny powiększać? Tylko trochę? Ok fajnie. No to jedziemy. OK. 

Więc mam tu, mój Implementacja chciwi. I choć wielu z was napisał chciwi w pętli while form--, że Jest to całkowicie dopuszczalne sposób to zrobić it-- inny sposób to zrobić, to po prostu podzielić w modulo. Bo wtedy można mieć wartość, a następnie mieć resztę. I wtedy można po prostu dodać to wszystko razem. Czy logikę, co robię tu sens dla wszystkich, zanim zaczniemy? Rodzaj? Chłodny. Wielki. Jest to całkiem sexy kawałek kodu, powiedziałbym. Tak jak mówiłem, Dawid, w wykład, po pewnym czasie, wy wszyscy zaczynają kod obejrzeniu jako coś, co jest piękne. A czasami, gdy widzisz piękne Kod, to takie wspaniałe uczucie. 

Tak więc, podczas gdy ten kod jest bardzo piękne, to nie działa prawidłowo. Warto więc uruchomić check50 na ten temat. Sprawdzić 50 20-- oop. 2? Czy to pset2? Tak. Och, pset1. OK. Więc uruchomić check50. 

A jak wy można zobaczyć tutaj, to w przypadku braku kilku przypadkach. A dla niektórych z was, w Oczywiście robi swoje zestawy problemowe, jesteś jak, ach, dlaczego nie jest to praca. Dlaczego to działa dla niektórych wartości, ale nie dla innych? Cóż, GDB pomoże Ci dowiedzieć dlaczego te wejścia nie działa. 

OK. Zobaczmy więc, jedną z upadających mnie sprawdza w check50 była wprowadzona wartość 0,41. Tak więc prawidłowa odpowiedź, że powinna być coraz to 4. Ale zamiast tego, co ja drukowanie jest 3-n, co jest nieprawidłowe. Więc po prostu uruchomić to ręcznie, po prostu upewnij się, że check50 działa. Zróbmy ./greedy. Ups, muszę zrobić chciwi. No to jedziemy. Teraz ./greedy. 

Ile jest winien? Zróbmy 0,41. A Tak, widzimy tutaj że to wyprowadzanie 3 gdy poprawna odpowiedź, W rzeczywistości, należy mieć 4. Warto więc wprowadzić GDB i zobaczyć, jak Można zabrać go naprawić ten problem. 

Tak więc pierwszy krok w Zawsze debugowania kodu jest, aby ustawić punkt przerwania, lub punkt w którym chcą komputera lub debugger, aby rozpocząć patrząc na. Więc jeśli naprawdę nie wiedzieć, jaki jest twój problem, Zwykle, typowa rzecz chcemy zrobić, to ustawić naszą przerwania w głównym. Więc jeśli faceci mogą to zobaczyć czerwony przycisk tam, Tak, to było mi przypisać a granicznych wartości funkcji głównej. Klikam to. 

A potem mogę iść do mojego przycisk Debug. Uderzyłem ten przycisk. Pozwól mi się widok, jeśli mogę. No to jedziemy. Tak więc mamy tu, w panelu po prawej stronie. Przykro mi, chłopaki z tyłu, można naprawdę nie można zobaczyć bardzo dobrze. Ale w zasadzie wszystko prawo to panel robi jest śledzenie zarówno podświetlony Linia, która jest linia kodu że komputer jest uruchomiony, jak również wszystkich zmiennych Tu na dole. 

Więc masz centów, monety, n, wszystkie zadeklarowane różnych rzeczy w tym momencie. Nie martw się, bo mamy w rzeczywistości nie inicjowane ich do jakichkolwiek zmiennych jeszcze. Więc w komputerze, twój Komputer po prostu widząc, och, 32767 była ostatnia funkcja używane tej przestrzeni pamięci w komputerze. I tak to gdzie centów jest obecnie. Ale nie, że po uruchomieniu kodu, powinno stać się zainicjowany. 

Warto więc przejść, linia po linia, co się tutaj dzieje. OK. Więc tutaj są trzy przyciski, które po prostu wyjaśnić. Masz Play, lub funkcji Run, Przycisk, masz Krok nad przyciskiem, i masz również krok w przycisku. A w zasadzie, wszystkie trzy im po prostu przejść przez kod i robić różne rzeczy. 

Więc zwykle, gdy jesteś debugowanie, Nie chcemy, aby po prostu wciskamy Play bo Grać będzie po prostu uruchomić Twój kod do końca. A wtedy nie będzie w rzeczywistości wiedzieć, co twój problem to chyba ustawić wiele punktów przerwania. Jeśli ustawisz kilka punktów przerwania, to będzie po prostu automatycznie uruchomić z jednego punktu przerwania, do drugiej, do drugiego. Ale w tym przypadku mamy wystarczy, że jeden, bo chcą wypracować sobie drogę z góry na dół do dołu. Więc będziemy ignorować ten przycisk teraz dla celów tego programu. 

Więc po kroku nad funkcją tylko Kroki ponad każdej linii i mówi, co komputer robi. Krok do funkcji idzie do rzeczywistej funkcji to jest na linii kodu. Tak na przykład, jak printf () że jest to funkcja, prawda? Gdybym chciał fizycznie krokiem do funkcji printf () Chciałbym rzeczywiście iść do kawałka Kod gdzie printf () został napisany i zobaczyć co się tam dzieje. 

Typowo jednak, zakładamy, że kod, który dajemy wam działa. Zakładamy, że printf () działa. Zakładamy, że GetInt () działa. Więc nie ma potrzeby krok do tych funkcji. Ale jeśli nie ma funkcji że piszesz siebie które chcesz sprawdzić się, co się dzieje, co chcesz krok w tej funkcji. 

Więc teraz jesteśmy po prostu się krok nad tym kawałkiem kodu. Więc zobaczymy. Och, druk, "Oh hai, jak wiele zmian jest winien? " Nie obchodzi. Wiemy, że to działa, więc krok nad nim. 

Więc n, które jest nasz pływak, że mamy initialized-- lub declared-- w górę w górę, jesteśmy teraz dorównujàcego do GetFloat (). Więc krok nad tym. I widzimy u Dno tutaj, program monituje o wejściu wartość. Warto więc wprowadzić wartość chcemy testować tutaj, co jest 0,41. Wielki. 

Więc teraz n-- zrobić chłopaki zobaczyć tu, u bottom-- to stored-- dlatego, że jeszcze nie zaokrąglone, to zapisane w tym jak gigant Pływak, że jest ,4099999996, który jest na tyle blisko, aby nasze cele, teraz, do 0,41. A potem zobaczymy później, jak my nadal wzmocnienie nad programem, Po tu n stała zaokrąglone i stał się 41 centów. Wielki. Wiemy, że nasz zaokrąglenia w pracy. Wiemy, że mamy prawidłowa liczba centów, tak, wiemy, że to jest naprawdę nie problem. 

Więc nadal stepping na w tym programie. Chodziliśmy tam. I tak po tej linii kodu, możemy powinien wiedzieć, ile czwarte mamy. Jesteśmy krok nad. I widzisz, że nie w rzeczywistości mają jeden kwartał, ponieważ mamy odjąć 25 z naszej wartości początkowej 41. I mamy 16 wyjechali do naszych centów. 

Czy wszyscy zrozumieć, jak program jest wzmocnienie przez i dlaczego centów stała się obecnie 16 i dlaczego teraz, monety stało się 1? Czy wszyscy po tej logiki? Chłodny. Tak więc, w tym momencie, działa program, prawda? Wiemy, że robi dokładnie to, co chcemy go. A my nie faktycznie trzeba wydrukować, och, co jest centów w tym momencie, monety, co jest w tym momencie. 

Kontynuujemy przechodzi programu. Krok nad. Chłodny. Jedziemy nad dziesięciocentówki. Wielki. Widzimy, że to jest zrobione od $ 0,10 na bilon. I teraz mamy dwie monety. To jest poprawne. 

Idziemy na grosze i widzimy, że mamy pozostały centów. Hmm, to dziwne. Tutaj na program, miałem mieć odjęte moje grosze. Być może po prostu nie było robi to prawo linii. I niestety, widać tutaj, bo wiemy, które intensyfikują poprzez linie 32 i 33, to gdzie nasz program nieprawidłowo miał zmienne uruchomić. Tak więc możemy patrzeć i widzieć, oh, Jestem odjęcie tutaj centów, ale nie jestem w rzeczywistości dodanie do mojej wartości monety. Dodaję do centów. A ja nie chcę, aby dodać do centów, chcę dodać do monet. Więc jeśli to zmienić do monet, mamy program pracy. Mogę uruchomić check50. Możesz po prostu wyjść z GDB prawo tutaj, a następnie ponownie uruchom check50. Może po prostu to zrobić. Mam do chciwi. 0.41. I tu, to drukowanie na właściwą odpowiedź. 

Tak jak chłopaki widzą, GDB Jest to naprawdę potężne narzędzie do kiedy mamy tak dużo kodu dzieje i tak wiele zmiennych, że trudno dla nas, jak człowiekiem, aby śledzić. Komputer, w GDB debugger, ma możliwość aby śledzić wszystko. Wiem, w Visionaire, prawdopodobnie chłopaki mogło trafić kilka usterek segmentacji dlatego, że zostały uruchomione poza granice swojej tablicy. W przykładzie z Cezara, to dokładnie to, co ja tu realizowane. 

Więc zapomniałem sprawdzić co by się stało, gdybym nie mieć dwa argumenty wiersza poleceń. Ja po prostu nie umieścić w tej kontroli. I tak, jeśli uruchomię Debug-- ustawić mój punkt przerwania tam prawo. Biegnę Debug. 

OK. Tak. Tak naprawdę, GDB miał się, że powiedział mi, że Usterka nie była segmentacja. Nie wiem, co się dzieje właśnie tam, ale kiedy prowadził ją, to działa. Po uruchomieniu linii kodu przez i GDB może po prostu nagle rzucić się na ciebie, udać się i spójrz, co czerwone jest błąd. To będzie wam powiedzieć, hej, ty miał winy segmentacji, co oznacza, że ​​starał się dostęp miejsca w tablicy, który nie istnieje. Tak. 

Więc w następnym problemu określone w tym tygodniu, chłopaki będzie prawdopodobnie dużo Zmienne pływających wokół. Nie zamierzamy być pewien, co wszystkie one oznaczają w pewnym momencie. Więc GDB będzie naprawdę pomóc w zastanawianie z czego wszystkie są zrównując i jest w stanie zobaczyć, że wizualnie. Czy ktoś wiedzą jak żadnej z tych rzeczy działa? Chłodny. W porządku. Więc po tym, jesteśmy zamiar nurkować w prawo na cztery różne rodzaje rodzaju na ten tydzień. Jak wielu z was, najpierw wszystkim, zanim zaczniemy, Przeczytałem całą specyfikację dla pset3? OK. Jestem dumny z was. To tak, jakby połowa klasy, która jest znacznie więcej niż ostatnim razem. 

Tak, to świetnie, bo gdy mówimy o treści w lecture-- lub przykro, w section-- lubię odnoszą się wiele, że z powrotem do tego, co pset jest i jak chcesz wdrożenie, że w pset. Więc jeśli przyjdziesz o przeczytać specyfikację, to będziesz być o wiele łatwiejsze do zrozumienia to, co mówię, kiedy mówię, oh hej, to może być naprawdę Dobrym miejscem do realizacji tego rodzaju. Więc tych, którzy czytać spec wie, że w ramach swojej pset, będziesz musiał Napisać do rodzaju sortowania. Więc może to być bardzo pomocne dla wielu z was dzisiaj. 

Będziemy więc zacząć od, zasadniczo, najprostszy typ od rodzaju, rodzaj wyboru. Typowy algorytm jak pójdziemy na ten temat jest-- Dawid przeszedł przez to wszystko wykład, więc będę szybko poruszać się here-- jest w istocie, to mają tablicę wartości. A potem odnaleźć Najmniejsza wartość nieposortowane i zamienić tę wartość z pierwsza wartość nieposortowane. A potem po prostu powtarzać z resztą swojej listy. 

A oto wizualne wyjaśnienia o tym, jak to będzie działać. Tak na przykład, jeśli było rozpocząć z tablicą z pięciu elementów, indeks 0 do 4, z 3, 5, 2, 6 i 4 Wartości umieszczony w array-- więc teraz, jesteśmy po prostu zamiar założyć że wszyscy są nieposortowane dlatego, że nie testowałem inaczej. 

Więc jak to swego wyboru będzie Praca jest, że będzie to pierwszy prowadzony przez całości z nieposortowanej tablicy. To wybrać się najmniejszą wartość. W tym przypadku, 3, tuż Teraz jest najmniejsza. To staje się 5. Nie, 5 nie jest większa than-- lub przykro, to nie mniej than-- 3. Tak więc wartość minimalna jest nadal 3. A następnie dostać się do 2. Widzi, oh komputer, 2 jest mniejsza niż 3. 2 musi być teraz wartość minimalna. I tak 2 swapy z tej pierwszej wartości. 

Więc po jednym przejściu, możemy rzeczywiście zobaczyć że 2 i 3 są zamienione. A my po prostu będzie dalej robić to ponownie z resztą tablicy. Więc będziemy po prostu uruchomić poprzez ostatnie cztery indeksy tablicy. Zobaczymy, że 3 następna wartość minimalna. Tak więc mamy zamiar zamienić, że z 4. A potem po prostu zamiar utrzymać przebiegającej przez aż w końcu, ty dostać się do posortowanej tablicy, w której Wszystko 2, 3, 4, 5 i 6 są klasyfikowane. Czy wszyscy rozumieją logikę jak działa to swego wyboru? 

Wystarczy mieć jakiś o minimalnej wartości. Jesteś śledzenie, co to jest. A kiedy go znaleźć, można go wymienić od pierwszej wartości w array-- lub nie pierwszym value-- następna wartość w tablicy. Chłodny. 

Tak was rodzaj widziałem z krótkim spojrzenie, będziemy pseudocode to. Więc jeśli macie w plecy chcą tworzą grupę, wszyscy w tabeli mogą tworzyć trochę partnera, zamierzam dać wam jak trzy minuty po prostu porozmawiać przez logika, w języku angielskim, w jaki sposób możemy być w stanie realizować pseudokod napisać coś w rodzaju wyboru. I nie cukierki. Proszę przyjść i dostać cukierki. Jeśli jesteś w plecy i chcesz cukierki, słodycze mogę rzucić na ciebie. Właściwie, to you-- cool. Przepraszam. OK. 

Więc jeśli chcemy, jak klasa, zapisu pseudokod w jaki sposób można się zbliżyć ten problem, po prostu czuć się swobodnie. Ja po prostu przejść się i, w porządku, poproś grupy do następnego wiersza co powinniśmy robić. Więc jeśli chcecie zacząć się, co jest pierwszą rzeczą, robić, gdy starasz się wdrożenie sposób, aby rozwiązać ten program do selektywnego posortować listę? Załóżmy po prostu my mają tablicę, dobrze? 

PUBLICZNOŚCI: Chcesz stworzyć niektóre rodzaj [niesłyszalne], że jesteś przebiegającej przez całe tablicy. 

ANDI PENG: Racja. Więc masz zamiar chcą iteracji na każdym miejscu, prawda? Tak, świetnie. Jeśli chcecie mi dać następna line-- tak, w plecy. 

PUBLICZNOŚCI: Sprawdź je wszystkie najmniejszego. 

ANDI PENG: Nie pójdziemy. Dlatego chcemy, aby przejść i sprawdzić, zobaczyć, co wartość minimalna jest, prawda? Mam zamiar skrócić, że do "min." Co chcecie zrobić po znalazłeś minimalną wartość? 

PUBLICZNOŚCI: [niesłyszalne] ANDI PENG: Więc będziesz chciał przełączyć go pierwszy z tej tablicy, dobrze? To początek, mam zamiar powiedzieć. W porządku. Więc teraz, kiedy zamieniłem pierwszy jedno, co chcesz zrobić, po tym? Więc teraz wiemy, że ten tutaj musi być najmniejsza wartość, prawda? Wtedy masz dodatkowy odpoczynek tablicy, która jest bez sortowania. Więc to, co chcesz robić tutaj, jeśli Ciebie faceci chcą dać mi kolejną linię? PUBLICZNOŚCI: Więc chcesz iteracji w pozostałej części tablicy. ANDI PENG: Tak. A więc to, co jest iteracja rodzaj oznaczać będziemy prawdopodobnie potrzebować? Jaki rodzaj-- 

PUBLICZNOŚCI: Och, dodatkowa zmienna? ANDI PENG: Prawdopodobnie inny dla pętli, prawda? Więc pewnie będzie chciał iteracyjne through-- świetnie. I wtedy masz zamiar wrócić i Prawdopodobnie ponownie sprawdzić minimalną, dobrze? I masz zamiar powtarzać to, ponieważ pętle po prostu się biec, prawda? 

Tak jak chłopaki widzą, mamy Wystarczy ogólny Pseudokod od tego, jak chcemy ten program szukać. Ten iterate tutaj, co mamy zazwyczaj trzeba pisać w naszym kodzie jeśli chcemy iteracji przez tablica, jaki typ struktury? Myślę, że Christabel już powiedziałem tego wcześniej. 

PUBLICZNOŚCI: A dla pętli. 

ANDI PENG: A dla pętli? Dokładnie. Więc to jest chyba będzie na pętli. Co to jest kontrola tutaj będzie oznaczać? Zazwyczaj, jeśli chcesz sprawdzić jeśli coś jest coś else-- 

PUBLICZNOŚCI: Jeśli. 

ANDI PENG: AN jeśli, prawda? A następnie konwersja tutaj, będziemy przejść na później, bo David przeszedł, że w wykładzie, jak również. A potem drugi iterate implies-- 

PUBLICZNOŚCI: Kolejna pętla for. 

ANDI PENG: --another pętli, dokładnie. Więc jeśli szukamy co to poprawnie, możemy Można zobaczyć, że jesteśmy prawdopodobnie będzie potrzebował zagnieżdżonych pętli for z instrukcji warunkowej w nie a następnie rzeczywisty fragment kodu, który jest zamiar zamienić wartości. Tak już po prostu ogólnie napisane kod tutaj pseudokod. I wtedy jesteśmy naprawdę dzieje fizycznie, jako klasa starają się realizować to dzisiaj. Wróćmy do tego IDE. 

O o. Dlaczego jest to, że not-- tam jest. OK. Niestety, pozwól mi spróbować przybliżyć nieco więcej. No to jedziemy. Wszystko robię tu stworzyłem program o nazwie "Wybór / sort.c." Stworzyłem tablicę dziewięciu Wartości, 4, 8, 2, 1, 6, 9, 7, 5, 3. Obecnie, jak można zobaczyć, że są nieuporządkowane. n będzie liczbą, że informuje o ilości wartości masz w tablicy. W tym przypadku mamy dziewięć wartości. A ja właśnie dostałem pętli for tutaj że wypisuje nieposortowanej tablicy. 

I na koniec, Ja również dostałem w Pętla, że ​​po prostu drukuje go ponownie. Więc teoretycznie, jeśli tego programu działa poprawnie, na koniec, powinieneś zobaczyć wydrukowane na pętli w której 1, 2, 3, 4, 5, 6, 7, 8, 9 są prawidłowo kolejności. 

Więc mamy naszą Pseudokod tutaj. Czy ktoś chce to-- jestem zamiar iść prosić o volunteers-- Powiedz mi dokładnie, co, jeśli typ Chcemy, aby, po pierwsze, po prostu iteracji przez początku tablicy? Co to jest linia kodu jestem Prawdopodobnie będzie trzeba tutaj? 

PUBLICZNOŚCI: [niesłyszalne] 

ANDI PENG: Tak, czuję wolne to-- Przepraszam Cię nie mają stanąć up-- dotyk swobodnie podnosić głos trochę. 

PUBLICZNOŚCI: Dla int i równa 0-- 

ANDI PENG: Tak, dobrze. 

PUBLICZNOŚCI: i jest mniejsza niż długość tablicy. 

ANDI PENG: Tak trzymać się nic tu, bo nie mają funkcję, która mówi nam długość tablicy, Mamy już wartość, która przechowuje, że. Dobrze? Inną rzeczą, aby utrzymać w mind-- w tablicy z dziewięciu wartości, jakie są wskaźniki? Powiedzmy, że ta tablica była od 0 do 3. Zobaczysz, że ostatni Strona jest w rzeczywistości 3. Nie jest to 4, chociaż istnieje cztery wartości w tablicy. 

Więc tutaj, musimy być bardzo ostrożni, tego, co nasz warunek długości będzie. 

PUBLICZNOŚCI: Czy nie byłoby n minus 1? ANDI PENG: To będzie n minus 1, dokładnie. Czy to ma sens, dlaczego to n minus 1, każdy? To dlatego, że tablice są indeksowane od zera. Zaczynają się od 0 i uruchomić do n minus 1. Tak, to jest trochę skomplikowane. OK. I wtedy-- PUBLICZNOŚCI: Isnt'1, że już załatwione choć, Nie mówiąc po prostu "mniejsze lub równa się "i po prostu mówiąc" mniej niż? " 

ANDI PENG: To bardzo dobre pytanie. Więc tak. Ale także sposób, w jaki jesteśmy realizacji prawa kontroli, trzeba porównać dwie wartości. Więc rzeczywiście chcesz zostawić "na" pusty. Bo jeśli porównać ten jeden, nie będziesz mają nic po nim porównać, prawda? Tak. Więc i ++. Dodajmy nasze uchwyty w. Ups. Wielki. Mamy więc początek naszego zewnętrznej pętli. Więc teraz pewnie chce utworzyć zmienną o utrzymanie utwór najmniejszej wartości, prawda? Czy ktoś chce dać mi linia kodu, który miałby to robić? Czego potrzebujemy, jeśli chcemy chciał zapisać coś? 

Dobrze. Może lepiej, że nazwa by być: "temp" całkowicie works-- może bardziej trafnie nazwany będzie, jeśli chcemy najmniejszą value-- 

PUBLICZNOŚCI: Min. ANDI PENG: min, nie idziemy. min byłoby dobre. I tak oto, co my Aby zainicjować go? Jest to trochę skomplikowane. Bo teraz u początek tej tablicy, nie patrzył na nic, prawda? Więc co, automatycznie, jeśli jesteśmy po prostu na i jest równa 0, co chcemy zainicjować nasza pierwsza wartość minimalna do? PUBLICZNOŚCI: i. ANDI PENG: i dokładnie. Christabel, dlaczego chcemy sformatować ją do i? 

PUBLICZNOŚCI: Ponieważ, dobrze, Zaczynamy od 0. Tak, bo nie mamy nic do porównania jej minimalna będzie w końcu jest 0. 

ANDI PENG: Dokładnie. Więc ona jest dokładnie prawo. Ponieważ nie mamy w rzeczywistości spojrzał na cokolwiek jeszcze, nie wiemy, co nasz Minimalna wartość to. Chcemy po prostu zainicjować go ja, który obecnie jest tutaj. A jak będziemy ruch w dół tej tablicy, zobaczymy, że z każdym dodatkowe przejście, i zwiększa. I tak w tym punkcie, I prawdopodobnie będzie chce być minimalna, bo to będzie cokolwiek jest początkiem nieposortowanej tablicy. Chłodny. 

Więc teraz, że chcemy dodać pętli for tutaj to będzie iterację nieposortowane, czy reszta tej tablicy. Czy ktoś chce dać mi linia kodu, który miałby to robić? Hint-- co musimy tutaj, w dół? Co się dzieje w tym iść do pętli? Tak. PUBLICZNOŚCI: Więc my chcemy mieć inną liczbę całkowitą ponieważ jesteśmy uruchomiony przez resztę tablicy zamiast I, więc może j. 

ANDI PENG: Tak, j brzmi dobrze dla mnie. Równa? 

PUBLICZNOŚCI: Więc byłoby ja plus 1, ponieważ zaczynasz na następnej wartości. A następnie do end-- Ponownie więc, j jest mniejszej niż n minus 1, a następnie j ++. ANDI PENG: Świetnie. 

A potem tu, będziemy chcieli aby sprawdzić, czy nasz warunek jest spełniony, dobrze? Ponieważ chcesz Zmiana wartości minimalnej czy jest to w rzeczywistości mniejsze niż to, co jesteś porównując ją, prawda? Więc co będziemy chcieli tutaj? Sprawdź. Jaki typ rachunku są prawdopodobnie będzie ti chcesz używać, jeśli chcę coś sprawdzić? 

PUBLICZNOŚCI: if. 

ANDI PENG: if. Więc if-- i co będzie warunkiem, że chcemy wewnątrz naszego if? 

PUBLICZNOŚCI: Jeżeli wartość j jest mniejsza od wartości ja-- 

ANDI PENG: Dokładnie. Więc if-- więc ta tablica jest nazywany "tablica". Wielki. Więc jeśli array-- co to było? Powtórz to. 

PUBLICZNOŚCI: Jeśli tablica-j jest mniejsza niż tablica-i, to możemy zmienić min. Więc min będzie j. 

ANDI PENG: Czy to ma sens? OK. A teraz tutaj, w rzeczywistości chcą wprowadzić swap, prawda? Więc przypominam, w wykładzie, że Dawid, kiedy próbował zamienić the--, co było it-- sok pomarańczowy i milk-- 

PUBLICZNOŚCI: To było obrzydliwe. 

ANDI PENG: Tak, to był rodzaj brutto. Ale to był całkiem dobry Pojęcie czasu wykazania. Więc myślę o swoich wartościach tutaj. Masz tablicę od min, tablica i, czy co staraliśmy się zamienić tutaj. I prawdopodobnie nie może przelać je do siebie w tym samym czasie, co? Więc co my teraz w celu trzeba utworzyć tutaj w celu wymiany wartości poprawnie? 

PUBLICZNOŚCI: Zmienna tymczasowa. 

ANDI PENG: Zmienna tymczasowa. Więc zróbmy int temp. Zobacz, to byłoby lepiej Czas to-- zaraz, co to było? OK. Więc to byłoby lepiej Czas nazwać zmienną "temp". Więc zróbmy int temp. Co my teraz ustawiona temp równą tutaj? PUBLICZNOŚCI: Min? ANDI PENG: To trochę skomplikowane. To naprawdę nie ma znaczenia, w końcu. Nie ma znaczenia, co Kolejność zdecydujesz się zamienić w tak długo, jak jesteś upewniając się, że jesteś śledzenie, co masz zamiana. 

PUBLICZNOŚCI: To może być tablica-i. 

ANDI PENG: Tak, zróbmy tablicy-I. A potem, co jest następna linia kodu chcemy tu mamy? PUBLICZNOŚCI: tablica-i równa tablicy-J. ANDI PENG: I na koniec? PUBLICZNOŚCI: array tablica-j-i równa. Publiczność: Albo tablica-j równi tablica-temp-- lub temp. 

ANDI PENG: OK. Warto więc uruchomić to i zobaczyć jeśli to się uda. Gdzie jest, że dzieje? Och, to jest problem. Zobacz, na linii 40, jesteśmy próby użycia tablicy-j? Ale gdzie j istnieją tylko w? 

PUBLICZNOŚCI: W pętli for. ANDI PENG: Racja. Tak więc to, co mamy zamiar zrobić? 

PUBLICZNOŚCI: Zdefiniuj go poza the-- PUBLICZNOŚCI: Tak, myślę, że masz użyć innego if, prawda? Więc jak, jeśli minimum-- Wszystko w porządku, niech pomyślę. 

ANDI Peng: Chłopaki, spróbuj Pozwól, aby wziąć spojrzenie na zobacz, co się coś, co może zrobić tutaj? 

PUBLICZNOŚCI: OK. Tak więc, jeśli minimalna nie równa j-- więc jeśli minimalna jest nadal ja-- wtedy nie będzie musiał wymieniać. 

ANDI PENG: Czy to równe i? Co chcesz tu powiedzieć? 

PUBLICZNOŚCI: Albo tak, jeśli minimalna nie równy i, tak. ANDI PENG: OK. Dobrze, że rozwiązuje, rodzaj, nasze problemy. Ale to wciąż nie rozwiązuje Problem, co się stanie, jeśli j-- od j nie istnieje poza tym, to, co czy chcemy z nim zrobić? Zadeklarować go na zewnątrz? Spróbujmy działa to. O o. Nasz jakby nie działa. 

Jak widać, nasz pierwotny Tablica miał te wartości. A potem powinien mieć była w 1, 2, 3, 4, 5, 6, 7, 8, 9. To nie działa. Ahh. Co robimy? PUBLICZNOŚCI: Debug. ANDI PENG: Wszystko w porządku, możemy spróbować. Możemy debugowania. Oddalanie się trochę. Ustawmy naszą pułapkę. Chodźmy like-- OK. 

Tak, bo już wiemy, że te linie, 15 do 22, są working-- ponieważ wszystkie robię to po prostu iteracja i printing-- Mogę iść do przodu i pominięcia. Zacznijmy od linii 25. Oop, pozwól mi pozbyć się tego. 

PUBLICZNOŚCI: Więc Breakpoint gdzie zaczyna się debugowania? ANDI PENG: Albo przystanki. PUBLICZNOŚCI: Albo przystanki. ANDI PENG: Tak. Można ustawić kilka punktów przerwania i może po prostu przejść z jednego do drugiego. Ale w tym przypadku nie wiemy jeżeli błąd się dzieje. Więc po prostu chcą zacząć od góry do dołu. Tak. OK. 

Tak więc ta linia tutaj, możemy wkroczyć. Widać tu, mamy tablicę. To są wartości które są w tablicy. Czy widzisz, że, jak wskaźnik 0, to odpowiada value-- oh, Mam zamiar spróbować, aby powiększyć. Niestety, jest to naprawdę trudne do see-- na indeks tablicy 0, możemy mieć wartość 4, a Następnie tak dalej i tak dalej. Mamy zmiennych lokalnych. Teraz i jest równe 0, co chcemy go mieć. 

I tak trzymajmy Krokowe. Nasz minimalna jest równa 0, które my także chcemy go mieć. A potem wejść na nasz drugi do pętli, jeśli tablica-j jest mniejsza niż tablicy-i, którym nie jest. Więc nie widzisz, jak które pomijane, że? 

PUBLICZNOŚCI: Nie wolno również, jeśli Minimalna, wszystkie that-- nie powinien, że się wewnątrz pierwszej pętli? ANDI PENG: Nie, ponieważ nadal chcesz przetestować. Chcesz zrobić porównanie każdego czas, nawet po uruchomieniu przez niego. Nie można po prostu chcę to zrobić na pierwszym przełożenia. Chcesz to zrobić z każdy dodatkowy karnet ponownie. Więc chcesz sprawdzić Twój stan wewnątrz. Więc jesteśmy po prostu będzie biec przez tutaj. Dam ci faceci podpowiedź. Ma to związek z faktem, że kiedy jesteś sprawdzanie twój warunkowe, nie masz kontroli dla właściwego indeksu. Więc teraz jesteś sprawdzanie indeks tablicy z j jest mniejsza od tablicy indeks i. Ale co ty robisz się na początek pętli for? Czy nie ustawienie j równy I? 

Tak, tak, możemy rzeczywiście wyjść tutaj debuggera. Warto więc przyjrzeć się naszej Pseudokod. For-- będziemy zaczynają się i jest równa 0. Mamy zamiar iść do n minus 1. Sprawdźmy, czy mamy takie prawo? Tak, to była prawda. 

Tak więc w środku tu jesteśmy zamiar utworzenia wartości minimalnej i ustawić, że równe i. Czy mamy to zrobić? Tak, zrobiłem to. Teraz w naszej wewnętrznej pętli for, jesteśmy zamiar zrobić j równa i do n 1 minus. Czy mamy to zrobić? Rzeczywiście, zrobiliśmy to. 

Tak więc, co mamy porównanie tutaj? 

PUBLICZNOŚCI: j plus 1. ANDI PENG: Dokładnie. A potem będziesz chciał ustawić minimalna równa j plus 1 oraz. Poszedłem więc przez to bardzo szybko. Czy wy zrozumieć dlaczego to jest j plus 1? OK. 

Tak więc w swojej tablicy, w Twoja pierwsza przechodzi przez, Twój pętli, na int i równa 0, po prostu Zakładamy, nie zostało jeszcze zmieniać. Mamy tablicę, całkowicie, zaledwie cztery elementy nieposortowane, prawda? Dlatego chcemy, aby zainicjować i równej 0. A ja ma tylko prowadzony za pośrednictwem tej pętli. I tak w pierwszym przejeździe, jedziemy zainicjować zmienną o nazwie "min" które również jest równy i, dlatego, nie mamy minimalną wartość. Więc to jest obecnie równa 0, jak również. A potem mamy zamiar przejść. I chcemy ponownie iteracji. Teraz, gdy już znaleźli nasz minimalna jest, chcemy iteracji ponownie, aby sprawdzić, czy jest to porównanie, prawda? Więc j, tu się dzieje do jednakowego i, który jest 0. A potem, jeśli tablica j plus i, co to ten, który jest następny w ciągu, jako mniej niż co aktualnie minimum wartość, chcesz zamienić. 

Więc powiedzmy mamy ale, jak, 2, 5, 1, 8. Właśnie teraz, i jest równe 0 i j wynosi 0. I to jest nasza wartość minimalna. Jeśli tablicy-j oraz ja-- więc jeśli jeden to po jednym Patrzymy jest większa niż przed nią to się stać minimalna. 

Więc widzimy, że 5 nie mniej. Więc to się nie być 5. Widzimy, że 1 jest mniejsza niż 2, prawda? Więc teraz wiemy, że nasze minimum to będzie wartość indeksu w 0, 1, 2. Tak? I wtedy, gdy pojawi się tutaj, można zamienić poprawne wartości. 

Więc kiedy wy właśnie o j przed, nie patrząc na jednego po tym. Masz pomysł na ta sama wartość, która Dlatego po prostu nie robi nic. Czy to ma sens dla wszystkich, Dlatego potrzebne, że plus 1 tam? OK. Teraz wystarczy uruchomić po to, aby Upewnij się, że reszta kod jest poprawny. Dlaczego to się dzieje? Ach, to jest to min tutaj. Byliśmy porównanie błędną wartość. O nie. 

O tak, tu byliśmy zamiana błędne wartości, jak również. Ponieważ byliśmy patrząc na i oraz j. To są ci, byliśmy kontroli. My rzeczywiście chcą zamienić minimalny prąd minimum, z tym, co na zewnątrz jest jeden. I jak faceci widzą w dół tutaj mamy posortowaną tablicę. To po prostu miał do czynienia z fakt, że przy byliśmy sprawdzania Wartości trakcie porównywania Nie szukaliśmy w odpowiednich wartości. Szukaliśmy w tym samym jednym tutaj, w rzeczywistości nie wymieniając go. Musisz spojrzeć na jeden obok do niego, a następnie można zamienić. Więc to, co było swego rodzaju podsłuch nasz kod wcześniej. I co ja tu jest wszystko debugger mógłby zrobić dla Ciebie Po prostu zrobił to na wyżywienie, ponieważ łatwiej aby zobaczyć, a nie stara aby powiększyć debuggera. Czy to ma sens dla każdego? Chłodny. 

W porządku. Możemy przejść do rozmowy o notacji asymptotycznej, które tylko fantazyjny sposób mówiąc runtimes wszystkich tych rodzajów. Tak wiem, Dawida, w wykładzie, poruszył czasy pracy. I poszedł przez cały wzoru od tego, jak obliczyć czas pracy. Nie martw się o to. Jeśli jesteś naprawdę ciekawa na, jak to działa, nie krępuj się mówić do mnie po sekcji. Możemy przejść przez wzory razem. Ale wszyscy macie naprawdę wie, że n do kwadratu ponad 2 to samo jak n do kwadratu. Ponieważ największą liczbę, wykładnik, rośnie najbardziej. I tak, dla naszych celów, wszystkim dbamy o jest fakt, że gigantyczna liczba, która rośnie. 

Więc co jest najlepszym przypadku runtime wyboru rodzaju? Jeśli masz zamiar mieć do iteracji listy a następnie iterację reszta tej listy, ile razy są zamierzasz chyba, w najgorszym case-- w najlepszym przypadku, sorry-- uruchomić poprzez? Być może lepszym pytaniem jest zapytać, co jest najgorszym przypadku runtime wyboru rodzaju. PUBLICZNOŚCI: n do kwadratu. ANDI PENG: Jest n do kwadratu, w prawo. Więc to prosty sposób, aby myśleć o tym jest jak, za każdym razem masz dwie zagnieżdżone pętle, to będzie n do kwadratu. Bo nie tylko ty jesteś przebiegającej przez po raz kolejny, trzeba wrócić wokół i przepuszczano przez nią ponownie wewnątrz każdej wartości. Więc w tym przypadku, używasz n Czasy n do kwadratu, co jest-- przykro, n razy n, która równa się n do kwadratu. 

I sortowania jest również nieco unikalne w tym sensie to, że nie ma znaczenia, czy to Wartości są już w kolejności. To wciąż będzie przebiegać przez jakikolwiek. Powiedzmy, że jest to 1, 2, 3, 4. Niezależnie od tego, czy jest czy nie jest w Kolejność, to nadal byłby przebiegł i nadal sprawdzana wartość minimalną. Byłoby to uczyniły sama liczba kontroli za każdym razem, nawet jeśli nie faktycznie niczego dotykać. 

Więc w takim przypadku, najlepsze i najgorsze czasy pracy są rzeczywiście równoważne. Tak oczekiwany czas pracy od wyboru rodzaju, które wyznaczają symbolem theta, theta, w tym przypadku, będzie również n kwadratu. Wszystkie trzy z nich będą n do kwadratu. Czy wszyscy są jasne, dlaczego runtime jest n do kwadratu? 

W porządku. Więc jestem po prostu szybko uruchomić przez resztę rodzaju. Algorytm bańka sort-- pamiętać, to był pierwszy David podszedł w wykładzie. Zasadniczo, krok przez całą listę i swap-- Cię tylko porównać dwa na raz. A jeśli jest większa, niż ty po prostu zamienić je. Więc jeśli są większe, należy zamienić. Mam oficjalne tutaj. 

Więc powiedzmy, że trzeba było 8, 6, 4, 2. Można by porównaj 8 i 6. Trzeba by zamienić je. Będziesz porównaj 8 i 4. Trzeba by zamienić je. Jeśli masz do wymiany 8 i pozycji 2, zmienić je dobrze. Więc w takim sensie, można zobaczyć, odtwarzane w ciągu długiego okresu czasu, jaki rodzaj wartości od bańki do końce, dlatego nazywamy je sortowanie bąbelkowe. 

Chcemy po prostu uruchomić poprzez ponownie nasz drugi przebieg, a nasz Trzeci przebieg, a nasz czwartego przebiegu. Zasadniczo, sortowanie bąbelkowe prostu działa dopóki nie tworzyć kolejnych swapów. Więc w tym sensie, jest to po prostu ogólna pseudokod dla niego. Nie martw się, to wszystko będzie w Internecie. Nie mamy rzeczywiście przejść nad tym. 

Po prostu zainicjować licznik zmienna, która rozpoczyna się od 0. A my iterację całej tablicy. A jeśli jedna wartość jest-- jeśli wartość jest większa od tej wartości, masz zamiar zamienić je. A potem po prostu będzie dalej. I masz zamiar się liczyć. A ty po prostu się to robić ten czas licznika jest większa niż 0, co oznacza, że za każdym razem masz do wymiany, wiesz, że chcesz iść z powrotem i spróbuj ponownie. Chcesz zachować kontrolę, aż wiesz, że nie masz do wymiany już. 

Więc jakie są najlepsze i najgorsze środowisko wykonawcze dla przypadku bańki rodzaju? I hint-- to jest rzeczywiście inna od wyboru rodzaju w tym sensie, te dwie odpowiedzi nie są takie same. Pomyśl o tym, co by się stało, w przypadek, gdy było już klasyfikowane. I myśleć o tym, co by było, gdyby to było W przypadku, w którym nie został przydzielony. I można rodzaju uruchomić poprzez dlatego, że się dzieje. Dam wam, jak, 30 sekundy, aby myśleć o tym. 

OK. Czy ktoś ma przypuszczenie na co Najgorszy czas pracy sortowanie bąbelkowe jest? Tak. 

PUBLICZNOŚCI: byłoby to, jak, n razy n minus 1 lub coś w tym stylu? Podobnie jak za każdym razem działa, to jest po prostu, jak, jeden wymiany mniej że cokolwiek to było. 

ANDI PENG: Tak, tak, jesteś całkowicie prawo. I to jest sprawa, w której swoje Odpowiedź była w rzeczywistości bardziej skomplikowane niż ten, musimy dać. Więc to będzie run-- jestem zamierza usunąć to wszystko tutaj. Czy wszyscy są dobre? Czy mogę wymazać tego? OK. Będziesz prowadzony przez n Czasy po raz pierwszy, prawda? A oni będą przebiegać przez n minus 1 drugi raz, prawda? A potem idziesz do utrzymania dzieje, n moje 2, et cetera. David zrobił to w wykładzie, gdzie, jeśli zsumować wszystkie te wartości, masz coś, co jest like-- yeah-- ponad 2, które w istocie po prostu zmniejsza do n do kwadratu. Masz zamiar dostać dziwne część tam. I tak, po prostu wiem, że n do kwadratu zawsze ma pierwszeństwo przed frakcji. I tak w tym przypadku, w najgorszym czas pracy byłby n do kwadratu. Jeśli to było w porządku malejącym Kolejność, myślę, ci trzeba dokonać wymiany za każdym razem. 

Co byłoby, potencjalnie, najlepszym przypadku czas pracy? Powiedzmy tylko, jeśli lista już było w porządku, co by runtime być? 

PUBLICZNOŚCI: brak. ANDI PENG: Jest n, dokładnie. I dlaczego jest to n? PUBLICZNOŚCI: Bo Ciebie tylko trzeba sprawdzić na sobie raz. ANDI PENG: Dokładnie. Więc w najlepszym możliwym czasie wykonywania, jeśli ta lista już było sorted-- powiedzmy, 1, 2, 3, 4-- ci po prostu przejść, należy sprawdzić, to zobaczysz, och, wszystkie one ułoży. Nie miałem do wymiany. Mam dość. Więc w tym przypadku, to tylko n lub liczba kroków po prostu musiał sprawdzić w pierwszej listy. 

I po, teraz hit Sortowanie przez wstawianie, gdzie algorytm jest zasadniczo podzielić że na część sortowane i niesortowane. A następnie jeden po drugim wartości nieposortowane są włożony w ich właściwe pozycje na początku listy. 

Tak na przykład, mamy Lista 3, 5, 2, 6, 4 ponownie. Wiemy, że jest to obecnie nieposortowane, ponieważ mamy tylko zaczął patrząc na niego. Przyjrzymy i wiemy, że pierwsza wartość jest posortowana, prawda? Jeśli szukasz tylko na tablicy Rozmiar, wiesz, że to jest klasyfikowane. 

Tak więc wiemy, że Pozostałe cztery są nieposortowane. Idziemy przez i widzimy, że wartość. Wracajmy. Zobacz, że wartość 5? Możemy spojrzeć na niego. Porównując go do 3. Wiemy, że jest większa niż 3, więc wiemy, że to jest klasyfikowane. Więc teraz wiemy, że dwa pierwsze są klasyfikowane, a trzy ostatnie nie są. 

Możemy spojrzeć na 2. Najpierw sprawdź to z 5. Jest to mniej niż 5? To nie jest. Więc musimy zachować patrząc w dół. Następnie należy sprawdzić 2 od 3. Czy jest to mniej niż? Nie. Więc wiesz, 2 musi być włożona do przodu, 3 i 5 oba muszą być wypchnięty. Czy to znowu z 6 i 4. A my po prostu zaglądać w istocie, gdzie po prostu sprawdzić, sprawdzić, sprawdzić. I dopóki to w prawo pozycja, my niby tylko włóż ją do właściwej pozycji, czyli tam, gdzie nazwa pochodzi. 

Więc to tylko algorytm, pseudokod per se, rodzaj, w jaki sposób będziemy realizować sortowania wstawiania. Pseudokod jest tutaj. To wszystko jest w Internecie. Nie martw się, jeśli jesteście próbuje skopiować ten dół. Więc jeszcze raz, sam question-- co byłoby najlepsze i najgorsze czasy pracy do wstawiania rodzaju? To jest bardzo podobna do tej ostatniej kwestii. Dam wam, jak, 30 sekundy, aby myśleć o tym, jak dobrze. 

OK Czy ktoś chce daj mi najgorszy czas pracy? Tak. 

PUBLICZNOŚCI: n do kwadratu. 

ANDI PENG: Jest n do kwadratu. I dlaczego jest to n do kwadratu? 

PUBLICZNOŚCI: Ponieważ w odwrotnej kolejności, trzeba przejść przez n razy n, które jest-- ANDI PENG: Tak, dokładnie. Tak samo jak w bubble rodzaju. Jeśli ta lista jest w kolejności malejącej, jesteś będzie musiał sprawdzić pierwszy raz. A potem z każdym Dodatkowym atutem, jesteś będzie musiał sprawdzić je przed każda wartość, prawda? A tak w ogóle, masz zamiar zrobić an razy n karnetów kolejny n przejść, które n jest kwadratowy. Co najlepszym przypadku? Tak. 

PUBLICZNOŚCI: n minus 1, ponieważ Pierwszy z nich jest już do kwadratu. 

ANDI PENG: Tak, blisko. Odpowiedź jest n. Ponieważ, podczas gdy pierwszy z nich jest sortowane, że nie może to actually-- po prostu pecha, w że przykładem, że 2 stało się najmniejsza liczba. Ale nie zawsze tak było. Jeśli 2 jest już posortowana na początku ale wyglądasz i tam 1 tutaj, W 1 ma zamiar go uderzyć. I to się skończy się być wpadł jakikolwiek. 

Tak więc, w najlepszym przypadku, to faktycznie tylko będzie n. Jeśli masz 1, 2, 3, 4, 5, 6, 7, 8, jesteś będzie przebiegać przez że cała lista raz aby sprawdzić, czy wszystko jest w porządku. Czy wszyscy są jasne, na prowadzeniu Czasy selekcji, jak również? Wiem, że przeżywa to naprawdę szybko. Ale po prostu wiem, że jeśli wiesz, że ogólne koncepcje, powinno być dobrze. OK. Więc ja po prostu dać wam może, jak, minutę, aby porozmawiać z sąsiadami co to tylko niektóre z głównych różnic pomiędzy tymi typami rodzaju. Pójdziemy nad tym wkrótce. PUBLICZNOŚCI: Och, OK. ANDI PENG: Tak. OK. Cool, niech się ponownie zebrać w klasie. OK. Więc to był swego rodzaju pytanie otwarte, w tym sensie, że jest wiele odpowiedzi na nie. I pójdziemy na niektóre z nich krótko. Chciałem się was myśląc o tym, co zróżnicowane wszystkie trzy typy rodzaju. I usłyszałem, także wielki question-- co to sortowanie przez scalanie zrobić? Dobre pytanie, bo to co mamy obejmujące obok. 

Więc sortowanie przez scalanie jest jeden rodzaj, który działa bardzo odmienny od innych rodzajów. Jak wy może see-- Dawid zrobić tego demo gdzie miał wszystkie fajne odgłosy widząc, jak połączyć jakby biegł, jak nieskończenie szybciej niż dwa inne rodzaje? OK. Więc to dlatego scalanie Sortuj realizuje tę przepaść i podbić pojęcia, że ​​mamy rozmawialiśmy o wielu w wykładzie. W tym sensie, że chcemy pracować mądrzej, a nie ciężej, po podzieleniu i podbić problemy i je łamać w dół, a następnie umieścić je razem, dobre rzeczy zawsze się zdarzają. 

Więc drogi, które łączą Sortuj zasadniczo działa jest to, że dzieli nieposortowane tablica na pół. I to ma dwie połówki tablic. I to właśnie sortuje te dwie połówki. To po prostu utrzymuje dzieląc na pół, w pół, na pół, dopóki wszystko nie jest posortowana a następnie rekurencyjnie stawia to wszystko razem. 

Więc to jest bardzo abstrakcyjne. Więc to jest tylko trochę Pseudokod. Czy to ma sens w sposób to działa? Więc powiedzmy użytkownik posiada Tablica n elementów, prawda? Jeśli n jest mniejsze niż 2, można wrócić. Bo wiesz, że jeśli nie ma tylko jedna rzecz, to musi być sortowane. Indziej, sortowania lewą połowę, a następnie posortować prawą połowę, a następnie scalić. 

Tak więc, że wygląda naprawdę łatwe, w rzeczywistości, o tym myśleć to rodzaj trudne. Ponieważ jesteś podobny, Dobrze, że to rodzaj działa na siebie. Dobrze? To działa na siebie. Więc w tym sensie, David dotknął na rekursji w klasie. I to jest koncepcja porozmawiamy o więcej. To, że w tym, te dwie linie tutaj, w rzeczywistości jest tylko program informując go uruchomić się z innym wejściem. Tak więc, zamiast uruchomić się z całość n elementów, można złamać go w dół do Lewa połowa i prawa połowa a następnie uruchom go ponownie. 

A potem będziemy patrzeć na to wizualnie, bo jestem wzrokowcem. To działa lepiej dla mnie. Więc zobaczymy wizualny przykład tutaj. 

Powiedzmy, że mamy tablicę, sześć Elementy, 3, 5, 2, 6, 4, 1, bez sortowania. W porządku, jest wiele na tej stronie. Więc jeśli faceci mogą spojrzeć na Pierwszy etap tutaj, 3, 5, 2, 6, 4, 1, można podzielić ją na pół. Masz 3, 5, 2, 6, 4, 1. Wiesz, że to aren't-- was nie wiem, czy są one klasyfikowane czy nie, tak trzymać rozbijając ich w połowie, na pół, w połowie, aż ostatecznie masz tylko jeden element. A jednym z elementów jest zawsze posortowana, prawda? 

Wiemy, że 3, 5, 2, 4, 6, 1, przez siebie, są klasyfikowane. A teraz możemy umieścić je z powrotem. Więc wiemy, 3, 5. Stawiamy te razem. Wiemy, że jest sortowane. W 2 nadal tam jest. Możemy umieścić na 4 i 6 razem. Wiemy, że to jest klasyfikowane, więc umieścić, że razem. A 1 ma. 

A potem po prostu spojrzeć na te dwie połówki tutaj. Masz 3, 5, 2, 2, 3, 5. Możesz po prostu porównują początek wszystkiego. Bo wiesz, że to jest posortowana i wiesz, że to jest klasyfikowane. Tak więc nawet nie trzeba porównanie 5, wystarczy porównać 3. I 2 jest mniejsza niż 3, tak, wiesz 2 musi iść w końcu. 

Samo tam. W 1 musi udać się tutaj. A potem, gdy idziesz do wprowadzenia razem te dwie wartości, wiesz, że to jest sortowane i wiesz, że to jest klasyfikowane. Więc to 1 a 2, 1 jest mniejsza niż 2. Który mówi, że 1 powinien udać się na koniec tego nawet nie patrząc na 3 lub 5. A następnie na 4, można po prostu sprawdzić, to idzie się w tutaj. Nie musisz patrzeć na 5. Samo z 6. Wiesz, że 6-- to tylko nie musi być postrzegana. 

I tak, w ten sposób, że jesteś tylko oszczędność siebie wiele kroków, gdy porównujemy. Nie musisz porównać każdego Element w stosunku do innych elementów. Wystarczy porównać z tymi że trzeba porównać je przed. Więc to rodzaj abstrakcyjnego pojęcia. Nie martw się, jeśli nie jest dość uderzając cię jeszcze rację. Ale zwykle jest to jak sortowanie przez scalanie działa. Pytania, szybkie pytania, zanim przejdę? Tak. 

PUBLICZNOŚCI: Tak powiedział Pan, że bierzesz W 1, a następnie 4 i 6 i umieścić je w. Więc nie są those-- nie są Patrzysz na nich jako oddzielne elementy, a nie jako całości? ANDI PENG: Tak. Więc co się dzieje jest to, że w zasadzie Tworzymy nową tablicę. Więc wiesz, że tutaj mam dwie tablice wielkości 3, prawda? Więc wiesz, że moja posortowanej tablicy musi mieć sześć elementów. Więc po prostu stworzyć Nowa ilość pamięci. Więc jesteś trochę jak jest marnotrawstwem pamięci, ale to nie ma znaczenia dlatego, że jest tak mały. Więc spójrz na 1 i spojrzeć na 2. I wiesz, że 1 jest mniejszy niż 2. Więc wiesz, że jeden powinien iść w początek wszystkie z nich. 

Nie trzeba nawet patrzeć w pozycji 3 i 5. Więc wiesz, jeden idzie. Potem w zasadzie odciąć 1. To, jak, żyje nam. Następnie musimy tylko 2, 3, 5 i 4 i 6. I wtedy wiesz, że Cię porównaj 4 i 2, Och, 2 powinien tam wejść. Więc rzuć na 2 w dół, odcinamy. Więc po prostu mają 3 i 5 w 4 i 6. I po prostu zachować siekanie go aż umieścić je w tablicy. 

PUBLICZNOŚCI: Więc jesteś po prostu zawsze porównanie [niesłyszalne]? 

ANDI PENG: Dokładnie. Więc w tym sensie, że jesteś tylko porównanie, zasadniczo, numer jeden przed drugim numerem. A bo wiesz, że to jest klasyfikowane, ciebie nie trzeba patrzeć przez wszystkich numerów. Trzeba tylko spojrzeć na pierwszego. A potem po prostu rzuć im się, bo wiesz, należą gdzie trzeba należeć. Tak. Dobre pytanie. 

A jeśli ktoś z was są nieco ambitny, Zapraszam do zapoznania się z tym kodem. To jest rzeczywiście Realizacja fizyczna od tego, jak będziemy pisać sortowanie przez scalanie. I widać, że to bardzo krótka. Ale Idee że są dość skomplikowane. Więc jeśli czujesz się jak rysunek na to uwagę w swojej pracy domowej dziś wieczorem, nie krępuj się. 

OK. Dawid udał się nad tym w wykładzie. Jakie są najlepsze case czasy pracy, czasy pracy najgorszego przypadku, i oczekiwane czasy pracy sortowanie przez scalanie? Kilka sekund myśleć. Jest to dość trudne, ale rodzaj intuicyjne, jeśli myślisz o tym. W porządku. 

PUBLICZNOŚCI: Czy najgorszy przypadek n log n? ANDI PENG: Dokładnie. I dlaczego jest n log n. 

PUBLICZNOŚCI: Czy to nie dlatego, że staje się wykładniczo szybciej, tak to jest jak funkcja, która zamiast po prostu będąc n kwadratu, czy coś? ANDI PENG: Dokładnie. Zatem powodem Czas pracy na to n log n jest because-- co ty robi w każdym z tych etapów? Jesteś po prostu siekanie go na pół, tak? I tak, gdy jesteśmy robi log, wszystko, co robi dzieli problem w połowie na pół, w połowie, w większej części. I w tym sensie, można rodzaju lub wyeliminowanie model liniowy które używaliśmy. Bo kiedy chop rzeczy w połowie, to jest dziennik. To tylko matematyczne sposobem reprezentowania go. 

I w końcu, w końcu, jesteś tylko co raz ostatni przechodzą przez umieścić je wszystkie w porządku, prawda? I tak, jeśli po prostu trzeba sprawdzić jedną rzecz, to n. A więc jesteś rodzaju mnożąc dwa razem. Tak to jest jak masz, że ostateczna sprawdzić n tu z dziennika n tu na górze. A jeśli pomnożyć im, że to n log n. 

A więc najlepszym przypadku i najgorsze Sprawa i oczekiwane są n log n. Jest to także jak w innym rodzaju. To jak wybór rodzaju w tym sensie, że nie ma znaczenia, co się Lista jest, to po prostu się aby zrobić to samo za każdym razem. OK. Tak jak chłopaki widzą, choć sortuje, że zaszliśmy through-- n kwadratu, to nie jest bardzo wydajny. I nawet to n log n nie najbardziej skuteczny. Jeśli jesteście ciekawi, tam mechanizmy sortowania które są tak skuteczne, że są one prawie zasadniczo płaska w czasie pracy. 

Masz jakiś log n-tych. Masz jakiś log log n-tych. Nie dotykamy nimi w tej klasie teraz. Ale jeśli jesteście ciekawi, zapraszam do google, co jest najbardziej efektywne mechanizmy sortowania. Nie wiem, nie są kilka naprawdę zabawnych te, like-- tam kilka naprawdę śmieszne te, które ludzie robią. I zastanawiasz się, w jaki sposób Myślałeś kiedyś o tym. Więc google, jeśli masz trochę wolnego Czas, na jakie są jakieś zabawne sposoby że people-- jak również wydajne ways-- ludzi była w stanie realizować rodzaju. OK. A tutaj jest po prostu mało poręczne wykres. Wiem, że wszyscy z was, przed tym quizie 0, będzie w pokoju, prawdopodobnie próbując zapamiętać, że. Tak, że miło się tam dla was. Tylko nie zapomnij, logikę, że made-- dlaczego te liczby miały miejsce. Jeśli zawsze stracone, tylko zrobić pewien, że wiesz, co rodzaju są. I można uruchomić poprzez im w głowie dowiedzieć się, dlaczego ci, Odpowiedzi są te odpowiedzi. 

W porządku. Tak więc mamy zamiar przenieść na końcu, w celu wyszukiwania. Bo jak ci z was, którzy czytali pset, Wyszukiwanie jest również częścią Problem w tym tygodniu zestawy. Zostaniesz poproszony do wdrożenia dwa rodzaje wyszukiwań. Jednym z nich jest przeszukiwanie liniowe i jeden jest przeszukiwanie binarne. 

Więc przeszukiwanie liniowe jest dość łatwe. Po prostu chcesz, aby szukać elementu z listy, aby zobaczyć, czy się uda. Musisz tylko iterację. A jeśli jest równa coś, możesz po prostu odesłać go, prawda? Ale ten, że jesteśmy najbardziej zainteresowany rozmową na temat jest przeszukiwanie binarne, prawo, które jest Dziel i rządź mechanizm Dawid wykazując w wykładzie. 

Pamiętaj przykład książki telefonicznej że wciąż wychowuje, ten, że rodzaj zmagał nieco na ten ostatni rok, gdzie można podzielić problem na pół, na pół, na pół, znowu i znowu, aż znajdziesz to, czego szukasz? I masz runtime, że dobrze. I widać, że to znacznie bardziej wydajne niż jakikolwiek inny rodzaj wyszukiwania. 

Więc sposób, że pójdziemy na temat wdrożenie przeszukiwanie binarne to, gdybyśmy mieli tablicę, Strona 0 do 6, siedem elementów, możemy spojrzeć w środku, prawy-- Przepraszam, jeśli nasze pytanie first-- jeśli chcemy zadać pytanie, czy tablica zawiera element 7, Oczywiście, jest ludzi, posiadające taka mała tablica, jest to dla nas łatwe powiedzieć tak. Ale sposób, aby wdrożyć binarny wyszukiwarka będzie wyglądać w środku. 

Wiemy, że indeks 3 jest w środku, bo wiem, jest siedem elementów. Co 7 podzielona przez 2? Możesz odciąć, że dodatkową 1. Masz 3 w środku. Więc jest tablica z 3 równe 7? To nie jest, prawda? Ale możemy zrobić kilka kontroli. Czy tablica 3 mniej niż 7 lub jest tablica z 3 większa niż 7? 

I wiemy, że jest to mniej niż 7. Więc wiemy, że och, to musi nie być w lewej połówce. Wiemy, że musi być w prawej połowie, prawda? Więc może po prostu odciąć połowę tablicy. Nie trzeba nawet spojrzeć na to już. Ponieważ wiemy, że połowa naszej problem-- wiemy, że odpowiedź jest w prawo połowa naszego problemu. Więc po prostu patrzeć na to teraz. 

Teraz przyjrzymy się Środek to, co pozostało. Że wskaźnik 5. Znów zrobić to samo sprawdzanie i widzimy, że jest mniejszy. Więc patrzymy na lewo od tego. A potem widzimy, że czek. Czy wartość tablicy w Strona 4 równe 7? To jest. Tak więc możemy wrócić prawda, bo okazało się, że wartość naszej liście. Czy drogę przeszedłem to ma sens dla każdego? OK. Dam wam może, jak, trzy, cztery minuty, aby dowiedzieć się, jak pseudocode o tym. 

Więc wyobraź sobie, poprosiłem, aby napisać Funkcja o nazwie wyszukiwania (), który powrócił wartość, wartość logiczna, to było prawdziwe, czy false-- jak, prawda, jeśli okazało się, że wartość false jeśli nie. A potem były przeszedł w wartości można szukaliśmy na wartości, które jest array-- och, zdecydowanie umieścić że w niewłaściwym miejscu. OK. W każdym razie, że powinien mieć było na prawo od wartości. A następnie int n jest liczbą elementów w tej tablicy. Jak byś go o próby do pseudocode ten problem? Dam wam jak trzy minuty, aby to zrobić. Nie, myślę, że jest only-- Tak, jest jedna aż tutaj. PUBLICZNOŚCI: Czy mogę? ANDI PENG: Tak, mam ciebie. Czy to działa? Ok fajnie. 

OK. W porządku chłopaki, jesteśmy zamiar powstrzymania go. OK. Więc zakładamy, że mamy ten piękny mała tablica z n wartości w nim. Nie rysować linie. Ale jak pójdziemy na temat próbuje pisać to? Czy ktoś chce dał mi pierwszą linię? Jeśli chcesz dać mi Pierwsza linia tego Pseudokod. 

PUBLICZNOŚCI: [niesłyszalne] PUBLICZNOŚCI: czego chcesz iteracyjne through-- PUBLICZNOŚCI: Jeszcze jeden dla pętli? PUBLICZNOŚCI: --for. 

ANDI PENG: Więc ta jest nieco kłopotliwe. Pomyśl about-- chcesz biec tej pętli kółko do momentu, kiedy? 

PUBLICZNOŚCI: Do [niesłyszalne] wartość jest równa tej wartości. ANDI PENG: Dokładnie. Więc może faktycznie po prostu write-- możemy nawet uprościć go więcej. Możemy po prostu zrobić pętli while, prawda? Więc może po prostu trzeba loop-- Wiemy, że jest to jednocześnie. Ale na razie, zamierzam powiedzieć "pętlę" - przez co? Pętla until-- to, co jest nasz kończąc warunek? Myślę, że to usłyszałem. Słyszałem, jak ktoś powiedzieć. 

WIDOWNI: Wartości równe pola. ANDI PENG: Powiedz to jeszcze raz. PUBLICZNOŚCI: Albo, aż Wartość szukacie , jest równa średniej wartości. 

ANDI PENG: Co zrobić, jeśli nie jest w środku? Co zrobić, jeśli wartość szukacie , nie jest ona w tej tablicy? PUBLICZNOŚCI: powrót 1. 

ANDI PENG: Ale to, co chcemy Pętla do czasu, gdy mamy stan? Tak. 

PUBLICZNOŚCI: Dopóki istnieje tylko jedna wartość? ANDI PENG: Można pętli until-- więc wiesz, że jesteś będzie mieć wartość maksymalną, prawda? A wiesz, że masz zamiar mieć wartość min, prawda? Bo też, że coś Zapomniałem powiedzieć wcześniej, że coś, co jest krytycznie wyszukiwania binarnego jest to, że tablica jest już posortowana. Ponieważ nie ma sposobu prowadzenia tego, czy są wartości tylko losowe. Nie wiesz, jeśli jest większe niż inne, prawda? 

Więc wiesz, że max i Twoje minut tu, prawda? Jeśli masz zamiar być dostosowanie Twój max w swoim minut i mid-- niech po prostu zakładamy, że wartość średniej jest tuż here-- będziesz w zasadzie pętli, aż minimalna jest o tym samym jako max, w prawo lub jeśli max nie jest taka sama, jak min. Dobrze? Bo gdy tak się dzieje, wiesz, że już w końcu uderzył w samą wartość. Więc chcesz pętli aż do min jest mniejsza niż lub równa to-- mmm nie mniejsza niż lub równa odwrotnie around-- max jest. 

Czy to ma sens? Zrobiłem kilka prób, aby uzyskać to prawo. Ale pętli aż do maksymalnej wartości jest w zasadzie prawie mniej lub równą do minimum, tak? To jest, gdy wiesz, że już zbieżne. PUBLICZNOŚCI: Kiedy będzie maksymalna wartość może być mniejsza niż minimum? ANDI PENG: Jeśli będziecie zachowywać dostosowując go, co jest to, co mamy zamiar robić w tym. Czy to ma sens? Minimalna i maksymalna są tylko liczby całkowite, które są prawdopodobnie będzie chciał stworzyć, aby utrzymać utwór z których szukamy. Ponieważ tablicy istnieje niezależnie od tego, co robimy. Podobnie jak, nie jesteśmy w rzeczywistości fizycznie odcięcie tablicy, prawda? Jesteśmy po prostu dostosowanie gdzie szukamy. Czy to ma sens? 

PUBLICZNOŚCI: Tak. 

ANDI PENG: OK. Więc jeśli jest to warunek naszej pętli, co chcemy wewnątrz tej pętli? Co będziemy się chce zrobić? Więc teraz, że mamy max i min, w prawo, prawdopodobnie stworzył tu gdzieś. Mamy zamiar prawdopodobnie chcesz znaleźć środku, prawda? Jak będziemy się w stanie znaleźć w środku? Co się mathematical-- PUBLICZNOŚCI: Max oraz min podzielić przez 2. ANDI PENG: Dokładnie. Czy to ma sens? A czy wy, dlaczego my nie tylko use-- dlaczego to zrobił zamiast robić po prostu n dzieli się przez 2? To dlatego, że n jest wartością że zamierza pozostać taka sama. Dobrze? Ale jak możemy dostosować naszą minimalną i wartości maksymalne, że będziemy zmieniać. I w rezultacie, nasz środkowy zmieni zbyt. Więc dlatego chcemy aby to zrobić tutaj. OK. 

A potem, teraz, Odkryliśmy our-- tak. 

PUBLICZNOŚCI: Wystarczy szybkie question-- kiedy mówisz, min i max, zakładając, że jesteśmy to już klasyfikowane? 

ANDI PENG: Tak, to rzeczywiście Warunkiem wstępnym poszukiwania binarnego, że trzeba wiedzieć, że jest klasyfikowane. Dlatego właśnie rodzaju, piszesz w swojej Problem ustawione przed wyszukiwania binarnego. OK. Więc teraz, że wiemy, gdzie nasz punkt środkowy jest, co chcesz tu zrobić? 

PUBLICZNOŚCI: Chcemy, aby porównać że w drugiej. ANDI PENG: Dokładnie. Więc masz zamiar porównać średniej wartości, prawda? I co to mówi nam, gdy porównamy? Co chcemy zrobić potem? 

PUBLICZNOŚCI: Jeśli wartość jest większa niż w połowie, chcemy go odciąć. ANDI PENG: Dokładnie. Tak więc, jeśli wartość jest większa niż w połowie, jesteśmy będzie chciał zmienić te Minimalne i maxes, prawda? Co chcemy zmienić? Tak więc, jeśli wiemy, że wartość jest gdzieś tu, co prawda, że ​​do zmiany? Chcemy zmienić nasze Minimalna się w połowie, prawda? A potem jeszcze, czy jest w tym połowę, co chcemy zmienić? 

PUBLICZNOŚCI: Twoja maksymalna. ANDI PENG: Tak. I to jesteś po prostu się zachować zapętlenie, prawda? Bo teraz, po jednej iteracji dzięki, masz max tutaj. A potem można przeliczyć w połowie. I wtedy można porównać. I masz zamiar jechać dalej aż minut i maxes są zasadniczo zbieżne. I to jest, gdy wiesz, że musisz trafić na koniec. I albo już go znajdziesz albo nie mają w tym momencie. 

Czy to ma sens dla każdego? OK. To jest bardzo ważne, bo będziesz miał napisać to w dzisiejszy wieczór kodu. Ale faceci mają całkiem dobry poczucie tego, co należy robić, co jest dobre. OK. Tak więc mamy około siedmiu minut lewej sekcji. Tak więc mamy zamiar rozmawiać o Ten zbior, że będziemy robić. Tak więc pset jest podzielony na dwie części. Pierwsza połowa dotyczy wdrożenie find w którym piszesz przeszukiwanie liniowe, A przeszukiwanie binarne i algorytm sortowania. 

Więc to jest pierwszy Czas w pset gdzie będziemy dając wam to, co się nazywa Kod dystrybucji, która jest kod że mamy wstępnie napisane, ale tylko w lewo niektóre kawałki off , aby zakończyć pisanie. Więc chłopaki, jeśli spojrzeć na to Kod, można dostać naprawdę bać. Jeśli jesteś po prostu lubię, ahh, I nie wiem co to robi, Nie wiem, jak, który wydaje tak skomplikowane, ahh, zrelaksować się. Jest ok. Przeczytaj specyfikację. Spec wyjaśni dokładnie, Co wszystkie te programy robią. 

Na przykład, generate.c to program że przyjdzie z pset. W rzeczywistości nie ma go dotknąć, ale należy zrozumieć, co robi. I generate.c, wszystko co robi jest albo generowanie liczb losowych czy można dać ziarno, jak umówiony numer, który trwa, i generuje więcej numerów. Więc nie ma specyficzny sposób wdrożenie generate.c, w którym można po prostu zrobić kilka numerów , aby sprawdzić swoje inne sposoby na. 

Więc jeśli chcesz, na Przykładem, sprawdzić swoje znalezisko, co chcesz uruchomić generate.c, generować kilka numerów, a następnie uruchomić funkcję pomocników. Twoja funkcja pomocnicy, gdzie jesteś faktycznie fizycznie pisania kodu. I pomyśleć pomocników w postaci pliku biblioteki piszesz, że znalezisko dzwoni. I tak w ciągu helpers.c, będziesz zrobić wyszukiwania i sortowania. 

A potem będziesz zasadniczo wystarczy umieścić je wszystkie razem. Spec powie, jak umieścić, że w linii poleceń. I będziesz w stanie sprawdzić, czy nie twoja sortowania i wyszukiwania pracy. Chłodny. Czy ktoś już się rozpoczął, a napotkane problemy lub pytania mają teraz z tym? OK. 

PUBLICZNOŚCI: Czekaj. Mam pytanie. 

ANDI PENG: Tak. 

PUBLICZNOŚCI: Więc zacząłem robić wyszukiwanie liniowe w helpers.c i nie było naprawdę działa. Ale później okazało się, że po prostu trzeba go usunąć i wykonać przeszukiwanie binarne. Więc to ma znaczenie, jeśli to nie działa? 

ANDI PENG: Krótka odpowiedź brzmi: nie. Ale ponieważ jesteśmy not-- PUBLICZNOŚCI: Ale nikt nie rzeczywiście sprawdzanie. ANDI PENG: Nigdy nie jesteśmy zobaczymy, że. Ale prawdopodobnie chcesz, aby upewnić się, że wyszukiwarka działa. Bo jeśli liniowa wyszukiwarka nie działa, to są szanse, binarny wyszukiwarka nie będzie działać, jak również. Bo masz podobny Logika w obu z nich. I nie, to nie ma znaczenia. Więc jedyne będziesz kolei w to sortowanie i wyszukiwanie binarne. Tak. 

A także, wiele dzieci były próbuje skompilować helpers.c. Nie jesteś w rzeczywistości dozwolone aby to zrobić, ponieważ helpers.c nie posiada głównej funkcji. I tak powinieneś tylko być właściwie kompilacją generowanie i znaleźć, bo znaleźć połączenia helpers.c i funkcji w nim. Więc sprawia, że ​​debugowanie ból w tyłek. Ale to, co mamy do zrobienia. PUBLICZNOŚCI: Ty po prostu zrobić wszystko, prawda? ANDI PENG: Można po prostu uczynić wszystko, jak również, tak. OK. Więc to w kategoriach co pset prosi wszystkich do zrobienia. Jeśli masz jakiekolwiek pytania, nie wahaj do zadawania mi po sekcji. Będę tu przez jakieś 20 minut. 

I tak, gdy pset użytkownika naprawdę nie jest tak źle. Wy powinno być OK. Te, wykonaj następujące wytyczne. Niby mają poczucie, logicznie, co powinno się dziać, a wszystko będzie w porządku. Nie należy się bać. Jest dużo kodu już tam jest napisane. Nie należy się bać, jeśli nie zrozumieć, co to wszystko znaczy. Jeśli jest to dużo, to jest całkowicie w porządku. I przychodzą do godzin pracy biura. Pomożemy Ci spojrzeć. 

PUBLICZNOŚCI: z dodatkowym funkcje, możemy spojrzeć ci się? 

ANDI PENG: Tak, to są w kodzie. W grze 15 połowa to już napisany dla Ciebie. Więc te funkcje są już w kodzie. Tak. W porządku. Cóż, powodzenia. To jest obrzydliwe dni. Więc mam nadzieję, że chłopaki nie czują się zbyt źle o pobyt wewnątrz i kodowania.