[RIPRODUZIONE DI BRANI MUSICALI] 

ANDI PENG: Benvenuti a settimana 3 della sezione. Grazie, ragazzi, per tutti provenienti per questo ora di inizio prima di oggi. Abbiamo una bella, piccolo intimo gruppo di oggi. Quindi speriamo ci arriveremo finitura, forse, presto, un po 'presto oggi. Così in fretta, solo alcuni annunci per l'ordine del giorno di oggi. Prima di iniziare, siamo intenzione di andare poco più alcune brevi problemi logistici, pset domande, debriefing, cose del genere. E poi ci immergeremo in pieno. Useremo un debugger GDB chiamato a iniziare a sfatare il nostro codice, che David ha spiegato in conferenza, l'altro giorno. Andremo oltre i quattro tipi di sorta. Andremo su di loro abbastanza rapidamente dato che sono piuttosto intenso. Ma sapere che tutte le diapositive e il codice sorgente è sempre on-line. Quindi sentitevi liberi, a vostro esame, a tornare indietro e dare un'occhiata a questo. 

Andremo attraverso Notazione asintotica, che è solo un modo elegante di dire "runtime" dove abbiamo la grande O, che David ha spiegato in conferenza. E abbiamo anche Omega, che è il runtime limite inferiore. E parleremo un po 'di più in profondità per quanto riguarda come quelli di lavoro. E, infine, supereremo ricerca binaria, perché un sacco di voi che hanno già guardò i tuoi pset sapere che probabilmente questa è una domanda che è nel vostro pset. Così sarete tutti contenti che copriamo questo oggi. 

E, infine, secondo la vostra sezione di feedback, in realtà ho lasciato circa 15 minuti a Alla fine di andare poco più logistica di pset3, tutte le domande, forse un po 'di guida, se si vuole, prima di iniziare la programmazione. Quindi cerchiamo di ottenere attraverso il materiale abbastanza rapidamente. E poi possiamo passare un po 'di tempo prendere più domande per il pset. OK. 

Rapidamente, in modo solo alcuni annunci prima di iniziare oggi. In primo luogo, non esitare a fare attraverso due delle vostre pset. Ho preso uno sguardo al your-- sì, LET'S ottenere un applauso per quello. In realtà, ero davvero, veramente colpito. Ho classificato il primo pset per voi ragazzi la scorsa settimana e voi ragazzi hanno fatto incredibile. 

Stile era sul punto oltre un paio di osservazioni. Assicurati di essere sempre commentando il codice. Ma i tuoi pset erano sul punto. E continuate così. Ed è un bene per il selezionatore a vedere che voi ragazzi stanno mettendo in tanto sforzo nel tuo stile ed il vostro disegno nel codice che vorremmo per voi a vedere. Così sto passando lungo la mia gratitudine per il resto dei TA. 

Tuttavia esistono alcune domande debriefing Voglio solo andare oltre che renderebbe la mia vita sia e un sacco di altra TA 'vive un po' più facile. In primo luogo, ho notato questo passato week-- quanti di voi sono stati in esecuzione su check50 il codice prima di inviare? OK. Quindi tutti dovrebbero fare check50, perchè-- un secret-- abbiamo effettivamente eseguire check50 come parte della nostra correttezza script per testare il codice. Così, se il codice non riesce check50, con ogni probabilità, sta probabilmente andando a fallire il nostro check pure. A volte voi ragazzi avere le risposte giuste. Come, in avida, alcuni dei si hanno i numeri giusti, basta stampare alcune cose in più. E quella roba in più in realtà non supera il controllo, perché il computer non davvero sapere cosa sta cercando. E così sarà solo scorrere, vedere che l'output non lo fa abbiniamo quello che ci aspettiamo la risposta di essere, e segnare è sbagliato. 

E so che è successo in alcuni dei vostri casi questa settimana. Così sono andato indietro e manualmente declassato il codice di tutti. In futuro, però, per favore, assicurati che si sta eseguendo controlla 50 sul vostro codice. Perché è una specie di dolore per la TA di dover tornare indietro e manualmente declassamento ogni singolo pset per ogni singolo, istanza poco perso. Quindi non ho preso fuori qualsiasi punti. Penso che mi sono tolto forse uno o due per la progettazione. In futuro, però, se siete in mancanza check50, saranno presi punti off per correttezza. 

Inoltre, sono pset dovuto venerdì a mezzogiorno. Penso che ci sia un sette minuti periodo di grazia tardi che vi diamo. Per il tempo di Harvard, avere il permesso di sette minuti di ritardo a tutto. Così qui a Yale, faremo aderire a quello. Ma più o meno, a 00:07, se il vostro pset non è in, che sta per essere contrassegnato come ritardo. E così mentre è segnato più tardi, il TA-- io sono ancora in corso di essere la classificazione vostri pset. Così ci si può comunque vedere apparire un grado. Tuttavia, so che a la fine del semestre, tutti i pset fine saranno solo azzerato automaticamente dal computer. 

Facciamo questo per due ragioni. Uno, a volte otteniamo scusato, come le scuse di Dean, più tardi che io non so ancora. Così ci piace per assicurarsi che stiamo classificazione tutto solo nel caso in cui, come, io sono manca la scusa di un decano. E in secondo luogo, di tenere mente, è ancora possibile escludere un pset che ha punti di ambito completi. E così ci piace grado tutti i pset solo fare in modo che l'ambito di lì e li sta cercando. Quindi, anche se è tardi, ci si può comunque ottenere credito per i punti di ambito, penso. 

Quindi morale della storia è, fare che i pset sono in tempo. E se non sono in su-tempo, sanno che non è grande. Sì, prima di passare, qualcuno ha Per qualsiasi domanda riguardante il feedback pset? Già. 

PUBBLICO: Hai detto che può cadere uno dei pset? 

ANDI PENG: Sì. Quindi c'è nove pset globale nel corso del semestre. E se avete portata points-- così ambito è solo, più o meno, stai tentando il problema, stai mettendo nel tempo, stai mostrando che hai dimostrato di aver letto le specifiche. Che è praticamente portata. E se si sta adempiendo punti di ambito, abbiamo può cadere il più basso uno su pieno scopo. Ecco, questo è in vostro vantaggio per completare e provare ogni pset. 

Anche se nessuno dei upload-- loro lavoro, li caricare. E poi ci si spera in grado di darvi alcuni di questi punti indietro. Cool. Altre domande? Grande. 

In secondo luogo, ufficio hours-- alcuni note rapide circa l'orario di ufficio. Quindi, prima, arrivato all'inizio della settimana. Nessuno è mai al orario di ufficio il lunedì. Christabel è venuto a orario di ufficio la notte scorsa. Sì, Christabel. E quello che abbiamo dovuto presso l'ufficio ore la scorsa notte, Christabel? 

PUBBLICO: Abbiamo avuto il gelato. 

ANDI PENG: Così che è di destra, abbiamo avuto gelato al orario di ufficio la scorsa notte. Mentre non posso promettere che avremo gelato a orario d'ufficio ogni settimana, quello che posso promettere è che ci sarà un significativo meglio studente al rapporto TA. Come legit, è come 00:57. Considerando che, per contrasto che con Giovedi, hai circa 150 davvero sottolineato i bambini e non gelato. E non è solo produttivo per chiunque. Quindi morale della storia è, venire presto per l'orario di ufficio e le cose buone accadrà. 

Inoltre, vengono preparati a fare domande. Sai? Indipendentemente da ciò che le agenzie di viaggi, io pensare, sono state dicendo, siamo stati sempre un paio di studenti che vengono in il Giovedi a, come, 10:50 Non avendo letto le specifiche essendo come me aiutare, aiutami. Sfortunatamente a quel punto, c'è non molto che possiamo fare per aiutarvi. Quindi, ti aspettiamo presto nella settimana. Venite presto a orari di ufficio. Siate preparati a fare domande. Assicurarsi che si, come uno studente, sono dove è necessario essere in modo che il TA in grado di guidarvi lungo, Che è ciò che l'orario d'ufficio dovrebbe essere assegnato per. 

In secondo luogo, quindi so professori vuole sorprenderci con i test. Avevo un professore di quelli come, yo, tra l'altro, ricordare che midterm avete Lunedi prossimo. Sì, io non conoscevo quella di medio termine. Quindi ho intenzione di essere che TA che si ricorda tutto quello quiz 0-- perché, si sa, siamo CS. Ora che abbiamo gli array fatto, si ottiene perché è quiz 0, non quiz 1, eh? OK. Oh, ho avuto qualche risatina su quello. OK. 

Così quiz 0 sarà del 14 ottobre se sei nella sezione Lunedi-Mercoledì e il 15 ottobre, se siete in la sezione Martedì-Giovedi. Ciò non vale per quelli di voi a Harvard who-- Penso che sarete tutti prendere i vostri quiz il 14. 

Quindi sì, la prossima settimana, se David, in conferenza, va, sì, così a tale proposito quiz la prossima settimana, a tutti voi non sarà scioccato perché siete venuti alla sezione e sapete che il vostro quiz 0 è in due settimane. E avremo recensione sessioni e tutto. Quindi nessuna preoccupazione circa essere spaventato per quello. Tutte le domande before-- tutte le domande a tutti i problemi logistici per quanto riguarda, di classificazione, le ore d'ufficio, sezioni? Già. 

AUDIENCE: Così il quiz è sta per essere durante la lezione? 

ANDI PENG: Sì. Così il quiz, credo, è 60 minuti assegnati in quella fascia oraria che ti basta prendere in aula. Quindi non c'è bisogno di venire a su, come, un caso 07:00. Va tutto bene. Già. Cool. 

Tutto ok. Quindi stiamo andando a introdurre un concetto a voi questa settimana che David ha già tipo di toccato in conferenza la scorsa settimana. Si chiama GDB. E quanti di voi, mentre in il corso di scrivere i pset, hanno notato un grande pulsante che dice "Debug" sulla parte superiore del vostro IDE? OK. Così ora ci realmente arrivare a dissotterrare il mistero di ciò che realmente pulsante fa. E vi garantisco, è un bella, bella cosa. 

Quindi, fino ad ora, penso c'è stato due cose gli studenti sono stati in genere fare durante il debug pset. Uno, o aggiungere a printf () - così ogni poche righe, aggiungono in un printf () - oh, che cosa è questa variabile? Oh, che cosa è questa variabile now-- e tipo di vedere la progressione del codice durante l'esecuzione. O il secondo metodo bambini fanno è che hanno appena scrivono il tutto e poi andare così alla fine. Speriamo che funziona. Ti garantisco, GDB è meglio di entrambi i metodi. Già. Quindi questo sarà il tuo nuovo migliore amico. Perché è una bella cosa che visivamente visualizza sia ciò che il codice sta facendo in un punto specifico così come quello che tutti i tuoi variabili stanno portando, come quello che i loro valori sono, a quel punto specifico. E in questo modo, si può veramente impostare punti di interruzione nel codice. È possibile scorrere riga per riga. E GDB sarà solo avere per voi, visualizzato per voi, quello che tutte le variabili sono, cosa fanno, cosa sta succedendo nel codice. E in tal modo, è così molto più facile vedere cosa sta succedendo invece di printf-ing o scrivere i vostri dichiarazioni. 

Quindi faremo un esempio di questo più avanti. Quindi, questo sembra un po 'astratto. Non preoccuparti, faremo esempi. E così in sostanza, i tre più grandi, funzioni più utilizzate di cui ha bisogno in GDB sono il passo successivo e oltre, e Step in bottoni. Io vado a testa oltre lì, in realtà, in questo momento. 

Quindi voi ragazzi tutto può vedere che o forse dovrei ingrandire un po '? Nella parte posteriore, si può vedere che? Dovrei ingrandire? Solo un po? Ok bello. Ci siamo. OK. 

Così ho, qui, la mia implementazione per avidi. E mentre molti di voi ragazzi ha scritto avidi ciclo while form-- che è un modo perfettamente accettabile fare it-- un altro modo per farlo è quello di semplicemente suddividere nel modulo. Perché allora si può avere la valore e quindi hanno il tuo resto. E allora si può solo aggiungere tutto insieme. Fa la logica di quello che sto facendo qui dare un senso a tutti, prima di cominciare? Tipo? Cool. Grande. E 'un pezzo sexy di codice, direi. Come ho detto, David, a lezione, dopo un po ', sarete tutti iniziare a vedere il codice come qualcosa che è bello. E a volte quando si vede bella codice, è una sensazione meravigliosa. 

Quindi tuttavia, mentre questo codice è molto bello, non funziona correttamente. Così corriamo check50 su questo. Controllare 50 20-- oop. 2? È che PSet2? Già. Oh, pset1. OK. Così corriamo check50. 

E come voi potete vedere qui, è mancato un paio di casi. E per alcuni di voi, nel corso di fare i vostri insiemi di problemi, siete come, ah, perché non è vero funziona. Perché è lavorando da valori, ma non per gli altri? Beh, GDB sta per aiutarti a capire il motivo per cui gli ingressi non funzionavano. 

OK. Vediamo quindi, uno dei controlli Stavo venendo a mancare in check50 era il valore di ingresso di 0,41. Quindi la risposta corretta che si dovrebbe essere sempre è un 4. Invece quello che sto stampando è il 3-n, che non è corretto. Così facciamo solo eseguire questa operazione manualmente, semplicemente assicurarsi che check50 sta funzionando. Facciamo ./greedy. Oops, devo fare avido. Ci siamo. Ora ./greedy. 

Quanto è dovuto? Facciamo 0.41. E sì, vediamo qui che è l'output di 3 quando la risposta corretta, infatti, dovrebbe essere 4. Quindi cerchiamo di entrare GDB e vedere come noi può andare sulla risoluzione di questo problema. 

Quindi il primo passo in debug sempre il codice è quello di impostare un punto di interruzione, o un punto in cui si desidera che il computer o il debugger per iniziare a guardare. Quindi, se non si ha realmente sapere che cosa il vostro problema è, Di solito, la cosa tipica vogliamo fare è impostare il nostro punto di interruzione alla principale. Quindi, se voi potete vedere questo pulsante rosso proprio lì, sì, quello era soltanto un me breakpoint per la funzione principale. Clicco che. 

E poi posso andare al mio pulsante Debug. Mi ha colpito quel pulsante. Permettetemi di zoom indietro se posso. Ci siamo. Così abbiamo, qui, un pannello sulla destra. Mi dispiace, ragazzi nella parte posteriore, si non si può davvero vedere molto bene. Ma in sostanza, tutte questo pannello di destra sta facendo è tenere traccia sia della evidenziata linea, che è la linea di codice che il computer è in esecuzione, così come tutte le variabili qui sotto. 

Così hai centesimi, monete, n, tutti dichiarati a cose diverse a questo punto. Nessun problema, perché non hanno in realtà li inizializzato a tutte le variabili ancora. Quindi nel tuo computer, il calcolatore è appena visto, oh, 32767 è stata l'ultima funzione utilizzata di quello spazio di memoria nel mio computer. E così che è dove centesimi attualmente è. Ma no che una volta che si esegue il codice, dovrebbe diventare inizializzato. 

Quindi cerchiamo di passare attraverso, riga per la linea, che cosa sta succedendo qui. OK. Così qui sono i tre pulsanti che ho appena spiegato. Hai la riproduzione, o la funzione Run, pulsante, si ha il passaggio sopra il pulsante, e hai anche il passo in tasto. E essenzialmente, tutti e tre loro solo passare attraverso il codice e fare cose diverse. 

Così tipicamente, quando si è il debug, noi non vogliamo solo colpire Play, perché Play appena eseguito il codice per la fine di esso. E poi non sarà effettivamente sapere che cosa il vostro problema è se non si imposta più punti di interruzione. Se si imposta più punti di interruzione, lo farà solo automaticamente correre da un punto di interruzione, al successivo, a quello successivo. Ma in questo caso abbiamo solo che uno, perché noi voglia di lavorare il nostro modo dall'alto verso il basso. Così stiamo andando a ignorare quel pulsante in questo momento per fini del presente programma. 

Quindi il passo sopra funzione appena passi oltre ogni singola riga e ti dice cosa il computer sta facendo. Il passo in funzione va nella funzione reale che è sulla linea di codice. Così, per esempio, come printf (), che è una funzione, giusto? Se volessi fisicamente passo nella funzione printf (), Vorrei davvero andare nel pezzo di codice in cui printf () è stato scritto e vedere cosa sta succedendo li. 

Ma di solito, si assume che il codice che vi diamo funziona. Non ci assumiamo la printf () sta lavorando. Partiamo dal presupposto che GetInt () sta lavorando. Quindi non c'è bisogno di passo in tali funzioni. Ma se c'è funzioni scritta da voi che si desidera controllare cosa sta succedendo, si vorrebbe fare un passo in tale funzione. 

Così adesso stiamo solo andando per scavalcare questo pezzo di codice. Quindi cerchiamo di vedere. Oh, stampa, "Oh hai, come cambia molto è dovuto? " Non ci interessa. Sappiamo che sta funzionando, così facciamo un passo su di esso. 

Così n, che è il nostro galleggiante che Abbiamo initialized-- o declared-- nella parte superiore, ora siamo pari a quella di getFloat (). Quindi facciamo un passo su quella. E vediamo al fondo qui, il programma mi sta spingendo per introdurre un valore. Ingresso di modo da lasciare il valore che vogliamo testare qui, che è 0,41. Grande. 

Così ora n-- voi ragazzi vedere qui, al bottom-- è stored-- perché noi non hanno ancora arrotondati, è memorizzati in questo gigante come float che è 0,4099999996, che è abbastanza vicino al nostro scopi, in questo momento, a 0,41. E poi si vedrà più avanti, come noi proseguire scavalcando il programma, dopo qui, n è diventato arrotondato e centesimi è diventato 41. Grande. Così sappiamo che il lavoro del nostro arrotondamento. Sappiamo che abbiamo il corretto numero di centesimi, così sappiamo che questo è non è davvero il problema. 

Così continuiamo passo in questo programma. Siamo andate qui. E così dopo questa riga di codice, abbiamo dovrebbe sapere quanti trimestri abbiamo. Facciamo un passo sopra. E vedi che facciamo, infatti, abbiamo una quarto perché abbiamo sottratto 25 dal nostro valore iniziale di 41. E abbiamo 16 a sinistra per i nostri centesimi. 

Fa capire a tutti come il programma è un passo attraverso e perché centesimi è ormai diventato 16 e perché, ora, le monete è diventato uno? Sta seguendo tutti questa logica? Cool. Così come di questo punto, la funzionamento del programma, giusto? Sappiamo che sta facendo esattamente quello che noi vogliamo. E non abbiamo fatto in realtà avere per stampare, oh, che è centesimi a questo punto, ciò è monete a questo punto. 

Continuiamo passando attraverso il programma. Scavalcare. Cool. Andiamo su monetine. Grande. Vediamo che ci sono voluti off $ 0,10 per un centesimo. E ora abbiamo due monete. È corretto. 

Andiamo oltre centesimi e vediamo che abbiamo lasciato sopra centesimi. Hmm, questo è strano. Quassù al programma, ho dovuto di aver sottratto i miei soldini. Forse semplicemente non ero facendo questo diritto linea. E ahimè, si può vedere qui, perché sappiamo che stiamo intensificando attraverso le linee 32 e 33, è lì che il nostro programma impropriamente avevano variabili corrono. Così possiamo guardare e vedere, oh, Sto sottraendo centesimi qui, ma io non sono in realtà aggiungendo al mio valore della moneta. Sto aggiungendo di centesimi. E io non voglio aggiungere a centesimi, voglio aggiungere alle monete. Quindi, se cambiamo che a monete, abbiamo un programma di lavoro. Posso correre check50. Si può solo uscire dal GDB destra qui e quindi eseguire nuovamente check50. Potrei farlo. Devo fare avido. 0.41. E qui, è la stampa la risposta giusta. 

Così come voi potete vedere, GDB è uno strumento davvero potente per quando abbiamo così tanto codice in corso e così tante variabili che è difficile per noi, come un essere umano, per tenere traccia di. Il computer, in GDB debugger, ha la capacità per tenere traccia di tutto ciò. Lo so, in Visionaire, voi ragazzi probabilmente potrebbe aver colpito alcuni difetti di segmentazione perché si stesse eseguendo fuori dai limiti della propria matrice. Nell'esempio di Cesare, che è esattamente quello che ho implementato qui. 

Così ho dimenticato di verificare la presenza di cosa accadrebbe se io non ha avuto due argomenti della riga di comando. Solo che non ho messo in quella di controllo. E così, se corro Debug-- ho impostato il mio punto di interruzione per proprio lì. Corro Debug. 

OK. Già. Quindi, in realtà, avrebbe dovuto GDB a me hanno detto lì è stato un errore di segmentazione lì. Non so che cosa stava succedendo proprio lì, ma quando ho eseguito, stava funzionando. Quando si esegue righe di codice tramite e GDB potrebbe semplicemente smettere improvvisamente su di voi, salire e guardare ciò che l'errore è rosso. E ti dirò, hey, aveva un errore di segmentazione, il che significa che si è tentato di accedere spazio in una matrice che non esisteva. Già. 

Così nel prossimo problema set di questa settimana, ragazzi probabilmente hanno un sacco di variabili galleggianti intorno. Lei non sta andando ad essere sicuro di quello che vogliono dire a un certo punto. Così GDB sarà davvero aiutare a capire che cosa sono tutti pari ed essere in grado di vedere che visivamente. C'è qualcuno confuso su come niente di tutto questo stava funzionando? Cool. Tutto ok. Così, dopo che, siamo andando a tuffarsi a destra in quattro diversi tipi di genere per questa settimana. Quanti di voi, prima di tutto, prima di iniziare, hanno letto l'intera specifica per pset3? OK. Sono orgoglioso di voi ragazzi. Questo è come la metà della classe, che è molto più che l'ultima volta. 

Ecco, questo è grande, perché quando si parla di contenuti in lecture-- o dispiaciuto, in section-- Mi piace mettere in relazione un sacco di che torna a ciò che il pset è e come si desidera implementare che nel tuo pset. Quindi, se si arriva con leggere le specifiche, sarà molto più facile per voi capire che cosa sto parlando quando dico, Oh, hey, questo potrebbe essere davvero un buon posto per implementare questo tipo. Così quelli di voi che hanno letto il spec sapere che, come parte della vostra pset, si sta andando ad avere per scrivere un tipo di ordinamento. Quindi questo può essere molto utile per molti di voi oggi. 

Quindi inizieremo con, essenzialmente, il tipo più semplice della specie, la selezione tipo. L'algoritmo tipico per come ci piacerebbe andare su questo è-- Davide ha attraversato questi tutti in lezione, quindi mi muovo in fretta lungo qui-- è essenzialmente, è hanno una serie di valori. E poi si trova il piccolo valore indifferenziati e di scambiare tale valore con il primo valore non ordinato. E poi basta continuare a ripetere con il resto della vostra lista. 

Ed ecco una spiegazione visiva di come dovrebbe funzionare. Così, per esempio, se dovessimo iniziare con una serie di cinque elementi, indice 0 a 4, con 3, 5, 2, 6, e 4 valori collocato nel array-- così in questo momento, stiamo solo andando ad assumere che sono tutti indifferenziati perché non abbiamo provato altrimenti. 

Quindi, come una sorta di selezione sarebbe lavoro è che sarebbe prima percorrere la totalità dell'array indifferenziati. Sarebbe scegliere il valore più piccolo. In questo caso, 3, destra ora, è il più piccolo. Si arriva a 5. No, 5 non è maggiore than-- o mi dispiace, non è meno than-- 3. Quindi il valore minimo è ancora 3. E poi si arriva a 2. Il computer vede, oh, 2 è inferiore a 3. 2 deve ora il valore minimo. E così 2 swap con quel primo valore. 

Così, dopo un solo passaggio, noi davvero vediamo che il 2 e il 3 sono scambiati. E stiamo solo andando a continuare a fare questo nuovo con il resto della matrice. Quindi stiamo andando a correre solo attraverso gli ultimi quattro indici dell'array. Vedremo che 3 è il valore minimo successiva. Quindi stiamo andando a scambiare che con 4. E poi stiamo solo andando a tenere che attraversa fino a quando, alla fine, arrivare a un array ordinato in cui 2, 3, 4, 5, e 6 sono tutti ordinati. Fa capire a tutti la logica di come funziona un ordinamento per selezione? 

Devi solo qualche tipo di un valore minimo. Stai tenere traccia di quello che è. E ogni volta a trovarlo, si scambia esso con il primo valore della array-- o, non il primo value-- il valore successivo nella matrice. Cool. 

Così come voi ragazzi tipo di visto da un breve scorcio, stiamo andando a pseudocodice questo fuori. Quindi, se voi ragazzi nella parte posteriore vogliamo formare un gruppo, tutti a un tavolo può formare un piccolo compagno, io vado per darvi ragazzi come tre minuti di parlare solo attraverso la logica, in inglese, di come potremmo essere in grado di implementare pseudocodice a scrivere una selezione sorta. E c'è caramelle. Si prega di venire e ottenere caramelle. Se siete alla schiena e si desidera caramelle, posso buttare caramelle a voi. In realtà, fare fresco you--. Oh scusa. OK. 

Quindi, se vogliamo, come una classe, pseudocodice write per come si potrebbe affrontare questo problema, ritiene appena libera. Mi limiterò a andare in giro e, in ordine, chieda gruppi per la successiva riga di quello che dobbiamo fare. Quindi, se voi volete iniziare off, qual è la prima cosa a fare quando si sta cercando di implementare un modo per risolvere questo programma per ordinare selettivamente una lista? Diciamo solo assumere noi hanno una serie, va bene? 

PUBBLICO: Si desidera creare un po ' sorta di [incomprensibile] che sei che attraversa tutta l'array. 

ANDI PENG: Giusto. Così si sta andando a voler iterare attraverso ogni spazio, giusto? Cosi grande. Se voi volete darmi la prossimo line-- sì, nella parte posteriore. 

PUBBLICO: Dateci tutto per i più piccoli. 

ANDI PENG: Ci andiamo. Quindi vogliamo andare attraverso e controllare vedere ciò che il valore minimo è, giusto? Io vado per abbreviare quello a "min." Che cosa voi ragazzi volete fare dopo hai trovato il valore minimo? 

PUBBLICO: [incomprensibile] ANDI PENG: Quindi stai andando a voler passare con il primo di tale matrice, destra? Questo è l'inizio, ho intenzione di dire. Tutto ok. Quindi, ora che hai scambiato il primo uno, che cosa vuoi fare dopo? Così ora sappiamo che questa qui deve essere il valore più piccolo, giusto? Allora avete un riposo aggiuntivo della matrice che è indifferenziati. Allora, cosa si vuole fare qui, se ragazzi vogliono darmi la prossima linea? PUBBLICO: Allora volete iterare attraverso il resto della matrice. ANDI PENG: Sì. E così ciò che scorrendo tipo di implicano probabilmente avremo bisogno? Che tipo di-- 

PUBBLICO: Oh, una variabile aggiuntiva? ANDI PENG: Probabilmente un'altra per il ciclo, giusto? Quindi stiamo probabilmente andando a voler per scorrere through-- grande. E poi avete intenzione di tornare indietro e probabilmente controllare di nuovo il minimo, destra? E si sta andando a continuare a ripetere questo, perché i loop solo andando continuare a correre, giusto? 

Così come voi potete vedere, abbiamo solo avere un pseudocodice generale di come vogliamo questo programma per guardare. Questo iterate qui, quello che facciamo noi in genere bisogno di scrivere nel nostro codice se vogliamo iterare un array, che tipo di struttura? Credo che Christabel già detto prima. 

PUBBLICO: Un ciclo for. 

ANDI PENG: Un ciclo for? Di preciso. Quindi questo è probabilmente Sarà un ciclo for. Che cosa è un assegno qui andando a implicare? In genere, se si desidera controllare se qualcosa è qualcosa else-- 

PUBBLICO: se. 

ANDI PENG: Un caso, giusto? E poi lo swap qui, ce la faremo andare oltre tardi, perché David passato attraverso che in conferenza pure. E poi il secondo iterata implies-- 

PUBBLICO: Un altro ciclo for. 

ANDI PENG: --another per il ciclo, esattamente. Quindi, se stiamo cercando in questo correttamente, abbiamo può vedere che siamo probabilmente andando ad avere bisogno di un ciclo for nidificato con un'istruzione condizionale in là e quindi un pezzo reale del codice che è andando a scambiare i valori. Così ho appena generalmente scritto un codice pseudocodice qui. E poi stiamo effettivamente andando fisicamente, come classe, cercare di attuare questo oggi. Torniamo in questo IDE. 

Uh Oh. Perché è che not-- c'è. OK. Siamo spiacenti, vorrei provare a ingrandire un po 'di più. Ci siamo. Tutto quello che sto facendo qui è che ho creato un programma chiamato "selezione / sort.c." Ho creato una serie di nove valori, 4, 8, 2, 1, 6, 9, 7, 5, 3. Attualmente, come si può vedono, non sono ordinati. n sta per essere il numero che ti dice la quantità di valori avete nel vostro allineamento. In questo caso, abbiamo nove valori. E ho appena ricevuto un ciclo for qui che stampa l'array non ordinato. 

E alla fine, ho anche una per ciclo che stampa appena fuori di nuovo. Quindi teoricamente, se questo programma funzioni correttamente, alla fine, si dovrebbe vedere un stampate per il ciclo in cui 1, 2, 3, 4, 5, 6, 7, 8, 9 sono tutti in modo corretto. 

Così abbiamo il nostro pseudocodice qui. Qualcuno vuole a-- Sono solo intenzione di andare a chiedere per volunteers-- dirmi esattamente che cosa digitare se vogliamo, prima, basta scorrere attraverso l'inizio di questo array? Qual è la linea di codice che sono Probabilmente avrà bisogno di qui? 

PUBBLICO: [incomprensibile] 

ANDI PENG: Sì, si sentono gratis a-- dispiace, non c'è bisogno di stare up-- tatto libero di alzare la voce un po '. 

Destinatari: per int i è uguale a 0-- 

ANDI PENG: Sì, bene. 

PUBBLICO: i è minore lunghezza dell'array. 

ANDI PENG: Quindi tenete a mente qui, perché noi non hanno una funzione che ci dice la lunghezza di un array, abbiamo già una valore che memorizza tale. Destra? Un'altra cosa da tenere in mind-- in un array di nove valori, quali sono gli indici? Diciamo solo che questa matrice è 0-3. Si vede che l'ultima indice è in realtà 3. Non è 4, anche se non c'è quattro valori nella matrice. 

Così qui, dobbiamo essere molto attenti di ciò nostra condizione per la lunghezza sarà. 

PUBBLICO: Non sarebbe n meno 1? ANDI PENG: Sta andando n meno 1, esattamente. Ha senso, perché è n meno 1, tutti? È perché gli array sono zero indicizzati. Essi partono da 0 e correre fino a n meno 1. Sì, è un po 'complicato. OK. E poi-- PUBBLICO: Isnt'1 che già curato, però, semplicemente non dicendo "inferiore o uguale a "e basta dire" meno? " 

ANDI PENG: Questo è un davvero bella domanda. Allora sì. Ma anche, il modo in cui siamo l'attuazione del diritto di controllo, è necessario confrontare due valori. Così si vuole realmente lasciare la "a" vuoto. Perché se si confronta questo, non hai intenzione avere nulla dopo da confrontare con, giusto? Già. Così i ++. Aggiungiamo i nostri parentesi. Ops. Grande. Così abbiamo l'inizio del nostro ciclo esterno. Così ora probabilmente vogliamo creare una variabile per mantenere traccia del valore minimo, giusto? Qualcuno ha voglia di darmi il riga di codice che potrebbe farlo? Che cosa abbiamo bisogno se vogliamo a voler conservare qualcosa? 

Destra. Forse un nome migliore per questo avrebbe essere-- "temp" totalmente works-- forse più giustamente intitolato sarebbe, se vogliamo che il più piccolo value-- 

PUBBLICO: min. ANDI PENG: min, ci andiamo. min sarebbe buono. Ed ecco, che cosa fare noi vuole inizializzare a? Questo è un po 'complicato. Perché in questo momento al inizio di questa matrice, non hai guardato nulla, giusto? Così che cosa, automaticamente, se siamo solo su i è uguale a 0, cosa vogliamo inizializzare il nostro primo valore minimo? PUBBLICO: i. ANDI PENG: i, esattamente. Christabel, perché vogliamo inizializzare per i? 

PUBBLICO: Perché, beh, stiamo iniziando con 0. Quindi perché non abbiamo nulla da confrontare a, minimo finirà per essere 0. 

ANDI PENG: Esattamente. Quindi lei è esattamente giusto. Perché non abbiamo in realtà visto ancora nulla, non sappiamo qual è il nostro valore minimo è. Vogliamo inizializzare solo che i, che, attualmente, è proprio qui. E mentre continuiamo a spostare verso il basso questa matrice, vedremo che, con ogni passaggio aggiuntivo, i incrementi. E così a quel punto, i è probabilmente andando a voler essere il minimo, perché sta andando essere quello è l'inizio della matrice indifferenziati. Cool. 

Così ora vogliamo aggiungere un ciclo for qui che è andando a scorrere l' indifferenziati, o il resto di questo array. Qualcuno ha voglia di darmi una riga di codice che potrebbe farlo? Hint-- ciò che abbiamo bisogno qui? Che cosa sta per andare in questo ciclo for? Già. PUBBLICO: Quindi ci piacerebbe un intero diverso, perché stiamo correndo per il resto della matrice anziché i, quindi forse j. 

ANDI PENG: Si, j suona bene a me. Uguale? 

PUBBLICO: Quindi sarebbe i più 1, perché si sta iniziando al valore successivo. E poi al end-- modo nuovo, j è meno di n meno 1, quindi j ++. ANDI PENG: Grande. 

E poi qui, stiamo andando a voler controllare per vedere se la nostra condizione è soddisfatta, destra? Perché si vuole modificare il valore minimo se in realtà è più piccolo di quello che si sta confrontando a, giusto? Allora, cosa stiamo andando a voler qui? Controllare per vedere. Che tipo di istruzione siamo probabilmente stiamo andando ti vuole utilizzare se noi consiglia di controllare qualcosa? 

PUBBLICO: Un if. 

ANDI PENG: An if. Così se: e quello che sta per essere la condizione che si vuole all'interno della nostra istruzione if? 

Pubblico: Se il valore di j è inferiore al valore di i-- 

ANDI PENG: Esattamente. Così se: quindi questa matrice si chiama "allineamento". Grande. Quindi, se array-- cosa è stato? Dire ancora una volta che. 

PUBBLICO: Se array j è minore di matrice-i, allora avremmo cambiato la min. Così il minimo sarebbe j. 

ANDI PENG: Ha senso? OK. E ora qui, in realtà desidera implementare lo scambio, giusto? Quindi ricorda, in conferenza, che David, quando stava cercando di scambiare the-- quello che era succo d'arancia e it-- milk-- 

PUBBLICO: Che era indecente. 

ANDI PENG: Sì, che era piuttosto disgustoso. Ma è stato un buon concetto di tempo dimostrando. Quindi, pensare dei vostri valori qui. Hai una matrice di min, una serie di i, o quello che stavamo cercando di scambiare qui. E probabilmente non si possono versare in l'altro allo stesso tempo, giusto? Allora, cosa stiamo andando per necessità di creare qui al fine di scambiare correttamente i valori? 

PUBBLICO: Una variabile temporanea. 

ANDI PENG: Una variabile temporanea. Allora, facciamo int Temp. Vedere, questo sarebbe una migliore tempo a-- whoa, che cosa è stato? OK. Quindi questo sarebbe stato una migliore il tempo di assegnare un nome al "temp." variabile Allora, facciamo int Temp. Che cosa stiamo andando a set temperatura pari a qui? PUBBLICO: Min? ANDI PENG: E 'un po' complicato. In realtà non importa, alla fine. Non importa quello che fine si sceglie di scambiare in a patto che si sta facendo in modo che sei tenere traccia di ciò che si sta scambiando. 

PUBBLICO: Potrebbe essere di matrice-i. 

ANDI PENG: Sì, facciamo matrice-i. E allora qual è la riga successiva di codice vogliamo avere qui? PUBBLICO: array-i è uguale a matrice-j. ANDI PENG: E infine? PUBBLICO: array-j è uguale matrice-i. Pubblico: O array j uguali array temp-- o, temperatura. 

ANDI PENG: OK. Così corriamo questo e vedere se si tratta di andare a lavorare. Dove è che accadendo? Oh, questo è un problema. Vediamo, sulla linea 40, siamo cercando di utilizzare array j? Ma da dove viene j esistere solo in? 

AUDIENCE: Nel ciclo for. ANDI PENG: Giusto. Allora, cosa stiamo andando ad avere bisogno di fare? 

PUBBLICO: Definire fuori the-- PUBBLICO: Sì, credo che avete per usare un'altra istruzione if, giusto? Così come, se il minimum-- tutto bene, fammi pensare. 

ANDI Peng: Ragazzi, provare a dare un'occhiata di Let vediamo, ciò che è qualcosa che possiamo fare qui? 

PUBBLICO: OK. Quindi, se il minimo non è uguale j-- quindi se il minimo è I-- ancora allora non avremmo da scambiare. 

ANDI PENG: Fa che la parità io? Cosa vuoi dire qui? 

PUBBLICO O sì, se il minima non è uguale i, sì. ANDI PENG: OK. Bene che risolve, specie di, i nostri problemi. Ma questo ancora non risolve il problema di cosa succede se j-- dal j non esiste al di fuori di esso, cosa cosa ci vuoi fare? Dichiarare fuori? Proviamo l'esecuzione di questo. Uh Oh. Il nostro ordinamento non funziona. 

Come potete vedere, la nostra iniziale matrice aveva quei valori. E poi dovrebbe avere stato in 1, 2, 3, 4, 5, 6, 7, 8, 9. La sua non funziona. Ahh. Cosa facciamo? PUBBLICO: Debug. ANDI PENG: Va bene, siamo in grado di provare che. Siamo in grado di eseguire il debug. Zoom indietro un po '. Fissiamo il nostro punto di interruzione. Andiamo like-- OK. 

Quindi perché già sappiamo che queste linee, da 15 a 22, sono working-- perché tutto quello che sto facendo è solo scorrendo e printing-- Posso andare avanti e saltare quella. Partiamo alla riga 25. Oop, mi permetta di ottenere liberarsi di questo. 

AUDIENCE: Quindi il punto di interruzione dove ha inizio il debug? ANDI PENG: o si ferma. PUBBLICO: o si arresta. ANDI PENG: Sì. È possibile impostare più punti di interruzione e si può semplicemente passare da uno all'altro. Ma in questo caso non lo sappiamo dove l'errore sta accadendo. Quindi vogliamo solo iniziare dall'alto verso il basso. Yep. OK. 

Così questa linea qui, siamo in grado di intervenire. Potete vedere qui sotto, abbiamo un array. Questi sono i valori che sono nella matrice. Vedete che, come indice di 0, corrisponde al value-- oh, Io vado a cercare per ingrandire. Ci dispiace, è davvero difficile a see-- a indice di matrice 0, abbiamo un valore di 4 e allora così via e così via. Abbiamo le nostre variabili locali. In questo momento i è uguale a 0, che noi vogliamo che sia. 

E così teniamo passando attraverso. Il nostro minimo è uguale a 0, che anche noi vogliamo che sia. E allora entriamo nostra seconda per cappio, se di matrice-j è minore di matrice-i, che non era. Così hai visto come che saltati su questo? 

PUBBLICO: Quindi, qualora il caso minimo, tutto che-- non dovrebbe che essere dentro il primo ciclo for? ANDI PENG: No, perché si vuole ancora provare. Vuoi fare un confronto ogni tempo, anche dopo aver eseguito attraverso di essa. Non si vuole solo per farlo al primo passante. Si vuole farlo con ogni passaggio di nuovo supplementare. Così si vuole verificare la presenza di la sua condizione all'interno. Quindi stiamo solo andando a continuare a correre attraverso qui. Ti do un suggerimento ragazzi. Essa ha a che fare con il fatto che quando si sta controllando la vostra condizione, non stai controllando per l'indice corretto. Così adesso si sta controllando per indice di campo di j è minore di matrice indice i. Ma che cosa stai facendo su a l'inizio del ciclo for? Non stai impostando j pari a I? 

Sì, così possiamo realmente uscire dal debugger qui. Quindi, diamo uno sguardo al nostro pseudocodice. For-- stiamo andando a partono i è uguale a 0. Stiamo per andare fino a n meno 1. Controlliamo, abbiamo dovuto questo diritto? Sì, quello era giusto. 

Allora dentro qui, siamo andando a creare un valore minimo e impostare che pari a i. L'abbiamo fatto? Sì, lo ha fatto. Ora nel nostro interiore ciclo for, siamo andando a fare i j è uguale a n 1 meno. L'abbiamo fatto? In effetti, abbiamo fatto. 

Allora però, che cosa stiamo confrontando qui? 

PUBBLICO: j più 1. ANDI PENG: Esattamente. E poi si sta andando a voler impostare il vostro minimo pari a j + 1 pure. Così ho passato che molto velocemente. Voi ragazzi capiate perché è j + 1? OK. 

Quindi nel tuo array, in il vostro primo passaggio, il vostro ciclo for, per int i è uguale a 0, diciamo solo assumere questo non è stato ancora cambiata. Abbiamo una vasta gamma di, completamente, solo quattro elementi non ordinati, giusto? Quindi vogliamo inizializzare i uguale a 0. E mi sta per solo correre attraverso questo ciclo. E così nel primo passaggio, stiamo andando per inizializzare una variabile chiamata "min" che è uguale anche io, perché non abbiamo un valore minimo. Ecco, questo è attualmente pari a 0 pure. E poi stiamo per passare attraverso. E vogliamo scorrere di nuovo. Ora che abbiamo trovato ciò che il nostro minimo è, vogliamo iterare di nuovo per vedere se è il confronto, giusto? Così j, qui, sta andando alla parità di i, che è 0. E poi se matrice j più i, che è quello che è eccessivo seguente, come meno di quello che la tua corrente minima valore, che si desidera scambiare. 

Così facciamo solo dire che abbiamo ottenuto, come, 2, 5, 1, 8. In questo momento, i è uguale a 0 e j è uguale a 0. E questo è il nostro valore minimo. Se array j più i-- quindi se quello che è dopo quello che stiamo guardando è maggiore di quella precedente, sta andando a diventare il minimo. 

Quindi, qui vediamo che 5 non è inferiore a quello. Così sta andando non essere 5. Vediamo che 1 è inferiore a 2, giusto? Così ora sappiamo che il nostro minimo è sarà il valore di indice a 0, 1, 2. Sì? E poi quando si arriva qui, è possibile scambiare i valori corretti. 

Così, quando stavate solo avere la j prima, non stavate guardando quello dopo ciò. Stavi guardando lo stesso valore, che è perché semplicemente non stava facendo nulla. Questo fa senso a tutti, perché abbiamo bisogno che più 1 lì? OK. Ora facciamo solo attraversano per renderlo che il resto del codice è corretto. Perché è quella accadendo? Ah, è il minimo qui. Stavamo confrontando il valore errato. Oh no. 

Oh sì, qui siamo stati scambiando i valori errati pure. Perché stavamo guardando i e j. Questi sono quelli che stavano controllando. Noi in realtà vogliamo scambiare la minimo, la corrente minima, con qualunque quella esterna è. E come voi potete vedere giù qui, abbiamo un array ordinato. E 'appena avuto a che fare con il fatto che quando ci siamo registrati il valori stavamo confrontando, noi non stavamo guardando i giusti valori. Stavamo cercando allo stesso qui, in realtà non lo scambio di esso. Bisogna guardare quello vicino ad esso e quindi è possibile scambiare. Ed è quello che era una sorta di intercettazioni nostro codice prima. E quello che ho fatto qui è tutto il debugger avrebbe potuto fare per voi Ho appena fatto sul bordo, perché è più facile per vedere piuttosto che cercare per ingrandire il debugger. Questo fa senso a tutti? Cool. 

Tutto ok. Siamo in grado di passare a parlare Notazione asintotica, che è solo un modo elegante per dire la tempi di esecuzione di tutti questi tipi. Quindi so Davide, in conferenza, toccato runtime. E andò per tutta la formula di come calcolare i tempi di esecuzione. Nessuna preoccupazione circa che. Se siete veramente curiosi su come funziona, sentitevi liberi di parlare con me dopo la sezione. Siamo in grado di camminare attraverso le formule insieme. Ma tutti voi ragazzi avete veramente sapere è che n quadrato oltre 2 è la stessa cosa di n quadrato. Poiché il numero maggiore, l'esponente, cresce più. E così per i nostri scopi, tutto ci preoccupiamo è che il numero gigante che sta crescendo. 

Allora, qual è il caso migliore tempo di esecuzione dell'ordinamento per selezione? Se avete intenzione di avere per scorrere una lista e poi scorrere il resto di tale elenco, quante volte sono hai intenzione di probabilmente, nel peggiore case-- nel caso migliore, sorry-- percorrere? Forse la domanda migliore è di chiedere, qual è il caso peggiore tempo di esecuzione dell'ordinamento per selezione. PUBBLICO: n al quadrato. ANDI PENG: E 'n al quadrato, destra. Quindi, un modo semplice per pensare a questo è come, ogni volta che si hanno due cicli for nidificati, che sta per essere n quadrato. Perché non solo si sono che attraversa una volta, si deve andare indietro intorno e correre attraverso di essa nuovamente all'interno per ogni valore. Quindi, in questo caso, si sta eseguendo n n volte quadrato, che è-- mi dispiace, n volte n, che è uguale al quadrato n. 

Ed è sorta anche un po ' unica nel senso che non importa se questi I valori sono già in ordine. E 'ancora in corso a correre attraverso comunque. Diciamo solo che questo è stato di 1, 2, 3, 4. Indipendentemente dal fatto che o non era in ordine, ancora sarebbe correva attraverso e ancora controllato il valore minimo. Avrebbe fatto il stesso numero di controlli ogni volta, anche se in realtà non toccare nulla. 

Quindi, in questo caso, i migliori e peggiori tempi di esecuzione sono in realtà equivalenti. Così il runtime previsto di ordinamento per selezione, che noi chiamiamo con il simbolo di theta, theta, in questo caso, sarebbe anche n quadrato. Tutti e tre di questi sarebbero n quadrato. È tutto chiaro il motivo il runtime è n quadrato? 

Tutto ok. Così sto solo andando a correre velocemente per il resto delle specie. L'algoritmo per bolla sort-- ricordo, questo è stato il primo Davide passò in conferenza. In sostanza, fate un passo attraverso l'intera lista e tu hai appena swap-- confrontare due alla volta. E se uno è più grande, quanto basta scambiarli. Quindi, se questi sono maggiori, si potrebbe scambiare. Ho ufficiale proprio qui. 

Così facciamo solo dire hai avuto 8, 6, 4, 2. Faresti confronta il 8 ed un 6. Avresti bisogno di scambiarle. Si potrebbe confrontare l'8 e 4. Avresti bisogno di scambiarle. Se si deve scambiare l'8 e il 2, cambiare loro. Quindi, in un senso, si può vedere, svolto su un lungo periodo di tempo, come i valori tipo di bolla per le estremità, che è per questo che lo chiamano bubble sort. 

Ci sarebbe solo correre attraverso di nuovo su il nostro secondo passaggio, e il nostro terzo passaggio, e il nostro quarto passaggio. In sostanza, bubble sort corre solo fino a quando non apportare più swap. In questo senso, questo è solo pseudocodice generale per esso. Nessun problema, questi saranno on-line tutti. Non abbiamo di andare effettivamente su questo. 

Abbiamo appena inizializzato un contatore variabile che parte da 0. E noi scorrere l'intero array. E se un valore è-- se questo valore è maggiore di tale valore, si sta andando a scambiarle. E poi sei solo intenzione di andare avanti. E si sta andando a contare. E hai intenzione di continuare a fare questo mentre il contatore è maggiore a 0, il che significa che ogni volta che si deve scambiare, si sa che si vuole andare indietro e prova di nuovo. Si desidera mantenere il controllo finché non si sa che non c'è bisogno di scambiare più. 

Ma quali sono i migliori e peggiori caso Runtime da bubble sort? E hint-- questo è in realtà diverso dalla selezione specie nel senso che queste due risposte non sono gli stessi. Pensate a cosa sarebbe successo in un caso se è stato già risolto. E pensare a ciò che cosa accadrebbe se fosse nel caso in cui non è stato risolto. E si può sorta di eseguire attraverso il motivo che sta succedendo. Ti darò ragazzi, come, 30 secondi per pensarci. 

OK. Qualcuno ha una supposizione a ciò che il caso peggiore runtime di bubble sort è? Già. 

PUBBLICO: Sarebbe, come, n volte n meno 1 o qualcosa del genere? Come, ogni volta che viene eseguito, è proprio, come, uno scambio meno che qualunque cosa fosse. 

ANDI PENG: Sì, così sei completamente a destra. E questo è un caso in cui la vostra risposta era in realtà più complessa di quello che dobbiamo dare. Così sta andando a run-- Sono andando a cancellare tutto questo qui. Sono tutti buoni? Posso cancellare questo? OK. Stai andando a correre attraverso n volte la prima volta, giusto? E che stanno andando a correre attraverso n meno 1 per la seconda volta, giusto? E poi si sta andando a mantenere andare, il mio n 2, eccetera. David ha fatto questo in una conferenza, dove, se si aggiungono tutti quei valori, si ottiene qualcosa che è like-- yeah-- su 2, che sostanzialmente si riduce solo fino a n quadrato. Stai andando a ottenere un frazione strano in là. E così è sufficiente sapere che il n quadrato sempre ha la precedenza sulla frazione. E così in questo caso, la peggiore runtime sarebbe n al quadrato. Se era in decrescente ordine, pensare, voi devono fare uno swap ogni singola volta. 

Quale sarebbe, potenzialmente, il miglior tempo di esecuzione caso? Diciamo solo che, se la lista era già in ordine, quale sarebbe il runtime essere? 

PUBBLICO: n. ANDI PENG: E 'n, esattamente. E perché è n? PUBBLICO: Perché hai appena devono controllare ogni volta. ANDI PENG: Esattamente. Così nel miglior runtime possibile, se questa lista era già sorted-- diciamo 1, 2, 3, 4-- voi sarebbe solo passare attraverso, si potrebbe verificare, si dovrebbe vedere, oh, tutti pan. Non ho avuto da scambiare. Ho finito. Quindi, in questo caso, è solo n o il numero di passi che solo dovuto controllare nel primo elenco. 

E dopo, ora ha colpito insertion sort, dove l'algoritmo è essenzialmente divide in una porzione ordinato e non ordinato. E poi uno per uno, i valori sono sottoposti a cernita inserito nella loro appropriata posizioni nella all'inizio della lista. 

Così, per esempio, abbiamo un elenco di 3, 5, 2, 6, 4 di nuovo. Sappiamo che è attualmente indifferenziati perché abbiamo solo iniziato a guardarla. Diamo un'occhiata e sappiamo che il primo valore viene ordinato, giusto? Se stai cercando solo in una serie di formato uno, sai che è ordinato. 

Allora sappiamo che la altre quattro sono indifferenziati. Andiamo attraverso e vediamo che il valore. Torniamo indietro. Vedere quel valore di 5? Diamo un'occhiata a questo. Confrontiamo a 3. Sappiamo che è più grande di 3, quindi sappiamo che questo è risolto. Così ora sappiamo che i primi due vengono ordinati e gli ultimi tre non lo sono. 

Diamo un'occhiata alle 2. Per prima cosa controlliamo con 5. È meno di 5? Non è. Quindi dobbiamo continuare a guardare verso il basso. Poi si controlla 2 fuori 3. E 'meno? No. Quindi conoscere un 2 deve essere inserito nella parte anteriore e 3 e 5 entrambi devono essere spinto fuori. Farlo di nuovo con 6 e 4. E abbiamo appena mantenere il controllo in sostanza, dove abbiamo appena controlliamo, controllare, controllare. E fino a quando è nel giusto posizione, abbiamo tipo solo inserirla nella giusta posizione, che è dove il nome di provenienza. 

Ecco, questo è solo l'algoritmo, pseudocodice di per sé, un po ', su come avremmo implementare un insertion sort. Pseudocodice è qui. E 'tutto on-line. Nessun problema se voi ragazzi siete cercando di copiare questo giù. Così ancora una volta, la stessa cosa interrogo sarebbe la migliore e peggiori tempi di esecuzione per insertion sort? E 'molto simile all'ultima domanda. Ti darò ragazzi, come, 30 secondi per pensare a questo. 

OK Qualcuno ha voglia di dammi il runtime peggiore? Già. 

PUBBLICO: n al quadrato. 

ANDI PENG: E 'n al quadrato. E perché è n quadrato? 

PUBBLICO: Perché in ordine inverso, si ha passare attraverso n volte n, che è-- ANDI PENG: Sì, esattamente. Così stessa cosa come nel bubble sort. Se questa lista è in ordine decrescente, sei andando a controllare la prima volta. E poi con ogni valore aggiunto, sei andando ad avere per verificare il rispetto ogni singolo valore, giusto? E così tutto, si sta andando a fare una volte n passa un altro n passano, che è n quadrato. Che cosa circa il caso migliore? Già. 

Pubblico: n meno 1, perché la prima è già quadrato. 

ANDI PENG: Quindi, chiudere. La risposta è in realtà n. Perché mentre il primo è ordinato, non può che actually-- siamo appena stati fortunati, in questo esempio, che 2 è capitato di essere il numero più piccolo. Ma non sarà sempre così. Se 2 è già ordinati all'inizio ma si guarda e c'è un 1 qui, il 1 sta per urtarla. E sta andando a finire per essere urtato comunque. 

Così nel migliore dei casi, in realtà è solo andare a essere n. Se si dispone di 1, 2, 3, 4, 5, 6, 7, 8, sei andando a correre attraverso che tutta la lista una volta per controllare per vedere se va tutto bene. E 'chiaro a tutti a correre tempi di selezione come pure? So che sto passando questi veramente veloce. Ma basta sapere che se si conosce la concetti generali, si dovrebbe essere buona. OK. Quindi mi limiterò a darvi ragazzi forse, come, un minuto per parlare con i vostri vicini su quelle che sono solo alcuni delle differenze principali tra questi tipi di sorta. Andremo oltre che presto. PUBBLICO: Oh, OK. ANDI PENG: Sì. OK. Fresco, cerchiamo di riconvocare come classe. OK. Quindi questa è stata una specie di domanda a risposta aperta, nel senso che c'è un sacco di risposte. E andremo su alcuni di loro brevemente. Volevo solo farti ragazzi pensando a quello differenziato tutti e tre i tipi di sorta. E ho sentito, anche, un grande interrogo ciò che merge sort fare? Grande questione, perché è quello che stiamo coprendo prossimo. 

Così merge sort è il un tipo che funziona in modo molto diverso dagli altri tipi. Come voi potete see-- fece Davide che demo dove ha avuto tutto il fresco rumori di vedere come unire specie corse, come infinitamente più veloce rispetto agli altri due tipi? OK. Ecco, questo è perché merge sorta implementa che divide e conquistare il concetto che abbiamo parlato molto in conferenza. In questo senso che ci piace lavorare più intelligente, non di più, quando si divide e conquistare i problemi, e romperli giù, e poi metterli insieme, buone cose accadono sempre. 

Quindi il modo che si fondono lavori sorta essenzialmente è che divide un matrice indifferenziati a metà. E poi è ottenuto due metà di array. E ordina solo quei due metà. Si continua a dividere a metà, in mezzo, a metà fino a quando tutto è ordinato e quindi in modo ricorsivo mette tutto insieme. 

Ecco, questo è davvero astratto. Quindi questo è solo un po 'di pseudocodice. Questo fa senso in il modo in cui è in esecuzione? Quindi diciamo solo che si dispone di un array di n elementi, giusto? Se n è inferiore a 2, si può tornare. Perché sai che se c'è solo una cosa, deve essere ordinata. Altrimenti, si ordina la metà sinistra, e poi si ordina la metà di destra, e poi si uniscono. 

Così, mentre che sembra davvero semplice, in realtà, a pensarci è piuttosto difficile. Perché tu sei come, Beh, questo è tipo di esecuzione su se stessa. Destra? E 'in esecuzione su se stessa. Quindi, in questo senso, David toccato su ricorsione in classe. E questo è un concetto parleremo di più. E 'questo che, queste due linee qui, in realtà è solo il programma dicendogli di correre stesso con ingresso differente. Quindi, piuttosto che correre con sé l'insieme di n elementi, è possibile abbattere in la metà sinistra e la metà destra e quindi eseguirlo di nuovo. 

E poi vedremo visivamente, perché io sono uno studente visivo. Funziona meglio per me. Così vedremo un esempio visivo qui. 

Diciamo che abbiamo un array, sei elementi, 3, 5, 2, 6, 4, 1, non filtrate. Va bene, c'è molto in questa pagina. Quindi, se voi potete guardare il primo passo qui, 3, 5, 2, 6, 4, 1, è possibile dividere a metà. Hai 3, 5, 2, 6, 4, 1. Voi sapete che queste si aren't-- Non so se sono ordinati o no, in modo da mantenere la rottura giù, in mezzo, a metà, a metà, fino alla fine, si dispone di un solo elemento. E un elemento è sempre ordinato, giusto? 

Così sappiamo che il 3, 5, 2, 4, 6, 1, da soli, sono ordinati. E ora siamo in grado di rimetterli insieme. Così sappiamo il 3, 5. Abbiamo messo insieme quelli. Sappiamo che è ordinato. I 2 è ancora lì. Siamo in grado di mettere il 4 e il 6 insieme. Sappiamo che questo è risolto, così abbiamo messo che, insieme. E il 1 c'è. 

E poi basta guardare queste due metà proprio qui. Avete il 3, 5, 2, 2, 3, 5. Si può solo confrontare la inizio di tutto. Perché si sa che questo è ordinato e si sa che questo è risolto. Allora non c'è nemmeno bisogno di confrontare il 5, basta confrontare il 3. E il 2 è inferiore a 3, così sai 2 deve andare alla fine. 

Stessa cosa là. Il 1 deve andare qui. E poi quando si va a mettere questi due valori, si sa che questo è ordinato e si sa che quello è ordinato. Allora l'1 e il 2, la 1 è inferiore a 2. Che ti dice che il 1 dovrebbe andare alla fine di questo senza nemmeno guardare 3 o 5. E poi il 4, si può solo controllare, va bene qui. Non c'è bisogno di guardare il 5. Stessa cosa con il 6. Voi sapete che il 6-- solo non ha bisogno di essere guardato. 

E così in questo modo, sei solo risparmiando un sacco di passi quando si sta confrontando. Non c'è bisogno di confrontare ogni elemento contro altri elementi. Basta confrontare contro quelli che è necessario confrontare contro. Ecco, questo è tipo di un concetto astratto. Non preoccuparti se non è piuttosto si colpendo a destra ancora. Ma in generale, questo è come un merge sort funziona. Domande, domande veloci, prima di passare? Già. 

PUBBLICO: Quindi lei ha detto che si prende 1, e quindi il 4 e il 6 e metterli in. Quindi non sono those-- non sono si guardarli come elementi separati, non come l'intero? ANDI PENG: Sì. Allora, cosa sta succedendo è che è fondamentalmente stanno creando una nuova matrice di zecca. Così si sa che, qui, ho due array di dimensioni 3, giusto? Così si sa che il mio array ordinato deve avere sei elementi. Quindi basta creare un nuova quantità di memoria. Quindi sei un po 'come sperperare della memoria, ma questo non ha importanza perché è così piccolo. Quindi si guarda al 1 e si guarda al 2. E si sa che la 1 è inferiore a 2. Così si sa che uno dovrebbe andare a l'inizio di tutte quelle. 

Non c'è nemmeno bisogno di guardare il 3 e il 5. Allora sai 1 va là. Poi è fondamentalmente recidere la 1. E ', come, morto per noi. Poi dobbiamo solo 2, 3, 5, e quindi 4 e 6. E poi si sa che, si confrontare il 4 e 2, oh, il 2 dovrebbe andare in là. Così si plop il 2 verso il basso, si chop off. Allora avete appena il 3 e il 5 in 4 e 6. E basta tenere tagliare fuori fino a quando li metti nella matrice. 

PUBBLICO: Quindi sei sempre solo confrontando il [incomprensibile]? 

ANDI PENG: Esattamente. Quindi, in questo senso, si è solo il confronto, in sostanza, un numero contro l'altro numero. E perché non si sa che è ordinato, è non c'è bisogno di guardare attraverso tutti i numeri. Basta guardare il primo. E allora si può solo plop giù, perché non si sa essi appartengono dove devono appartenere. Già. Bella domanda. 

E poi se qualcuno di voi sono un po 'ambizioso, sentitevi liberi di guardare a questo codice. Questo è in realtà la realizzazione fisica di come avremmo scrivere merge sort. E si può vedere, è molto breve. Ma le idee dietro esso sono piuttosto complessi. Quindi, se avete voglia di disegnare questo fuori nel vostro lavoro stasera, non esitate a. 

OK. Davide è andato anche su questo in conferenza. Quali sono i migliori caso tempi di esecuzione, peggiori tempi di esecuzione, e i tempi di esecuzione previsti di merge sort? Un paio di secondi per pensare. Questo è abbastanza duro, ma tipo di intuitivo se ci pensate. Tutto ok. 

AUDIENCE: E 'il caso peggiore n log n? ANDI PENG: Esattamente. E perché è n log n. 

PUBBLICO: Non è perché diventa esponenzialmente più veloce, quindi è come una funzione di tale invece di essere semplicemente n quadrato o qualcosa del genere? ANDI PENG: Esattamente. Quindi la ragione per cui la runtime su questo è log n n è quello che si sono perchè-- facendo in tutti questi passaggi? Stai solo tagliare a metà, giusto? E così, quando stiamo facendo la log, tutto quello che sta facendo è dividere un problema a metà, a metà, a metà, in più metà. E in questo senso, si può tipo di eliminare il modello lineare che abbiamo usato. Perché quando si taglia cose in mezzo, si tratta di un registro. Questo è solo il matematico modo di rappresentarlo. 

E poi finalmente, alla fine, si è solo fare un ultimo passaggio attraverso a mettere tutti in ordine, giusto? E così, se devi solo controllare una cosa, che è n. E così sei tipo di moltiplicando i due insieme. Quindi è come se hai quella finale verificare la presenza di n per quaggiù con un log di n quassù. E se si moltiplicano loro, questo è n log n. 

E così il caso migliore e peggiore caso e atteso sono tutti n log n. E 'anche come un altro tipo. E 'come ordinamento per selezione nel senso che non importa che cosa il vostro elenco è, è solo andare per fare la stessa cosa ogni volta. OK. Così come voi potete vedere, anche se il genere che siamo passati through-- n squadrato, non è molto efficiente. E anche questo registro n n è non il più efficiente. Se voi siete curiosi, c'è meccanismi di ordinamento che sono così efficienti che siano quasi sostanzialmente piatto nel runtime. 

Hai qualche log n di. Hai qualche log log n di. Noi non tocchiamo su di loro in questa classe in questo momento. Ma se voi siete curiosi, sentitevi liberi di Google, che cosa è i meccanismi di ordinamento più efficienti. Non lo so, ci sono alcuni tra quelli veramente divertenti, like-- c'è qualche davvero quelli divertenti che le persone fanno. E ti chiedi come mai pensato. Così Google, se avete un po 'di ricambio tempo, su, quali sono alcuni modi divertenti che people-- nonché efficienti persone ways-- sono stati in grado di attuare i tipi. OK. Ed ecco un po grafico a portata di mano. So tutto di te, prima che quiz 0, sarà nella vostra camera probabilmente cercando di memorizzare quello. Ecco, questo è bello in là per voi ragazzi. Basta non dimenticare la logica che made-- perché quei numeri si verificavano. Se stai sempre perso, basta fare Assicuratevi di sapere quali sono i tipi sono. E si può correre attraverso loro nella vostra mente di capire perché quelli le risposte sono quelle risposte. 

Tutto ok. Quindi stiamo andando a spostare on, infine, per la ricerca. Perché, come quelli di voi che hanno letto il pset, la ricerca è anche parte di Il problema di questa settimana pone. Ti verrà chiesto di implementare due tipi di ricerca. Uno è una ricerca lineare e uno è una ricerca binaria. 

Così la ricerca lineare è abbastanza facile. Hai voglia di cercare elemento di una lista per vedere se si ottiene. Devi solo scorrere. E se è uguale a qualcosa, si può solo tornare, giusto? Ma quello che noi siamo più interessato a parlare è ricerca binaria, a destra, che è la dividere e conquistare il meccanismo che David stava dimostrando a lezione. 

Ricordate l'esempio rubrica telefonica che continua a portare in su, quello che tipo di fatica un po 'in questo anno passato, dove si divide il problema a metà, a metà, a metà, ancora e ancora, fino a trovare quello che stai cercando? E tu hai il tempo di esecuzione anche di questo. E si può vedere, è molto più efficienti rispetto a qualsiasi altro tipo di ricerca. 

Quindi il modo che saremmo andati su l'attuazione di una ricerca binaria è, se avessimo un array, indice 0 a 6, sette elementi, possiamo guardare al centro, a destra- sopra scusate, se la nostra domanda first-- se vogliamo porre la domanda di, fa l'array contiene l'elemento 7, ovviamente, essendo esseri umani, e avendo come una serie di piccole, è facile per noi dire di sì. Ma il modo per implementare un binario ricerca sarebbe di guardare al centro. 

Sappiamo che l'indice 3 è mezzo, perché che ci sono sette elementi. Cosa 7 diviso 2? Si può recidere quel qualcosa in più 1. Hai 3 nel mezzo. Così è array di 3 pari a 7? Non è, giusto? Ma possiamo fare un paio di controlli. È serie di 3 o inferiore a 7 è matrice di 3 superiore a 7? 

E sappiamo che è meno di 7. Quindi sappiamo che, oh, si deve non essere nella metà sinistra. Sappiamo che deve essere nella metà destra, giusto? Così possiamo solo recidere la metà della matrice. Non hanno nemmeno bisogno di guardare più. Perché sappiamo che metà del nostro problem-- sappiamo che la risposta è in la metà destra del nostro problema. Quindi ci limitiamo a guardare adesso. 

Ora diamo un'occhiata al metà di ciò che resta. Tale indice 5. Facciamo di nuovo lo stesso controllo e vediamo che è più piccolo. Quindi guardiamo a sinistra di quello. E poi vediamo che il check. È il valore della matrice di Indice 4 pari al 7? Esso è. Così possiamo tornare vero, perché abbiamo trovato il valore della nostra lista. Fa il modo in cui ho passato che ha senso per tutti? OK. Ti darò ragazzi forse, come, tre, quattro minuti per capire come pseudocodice questo. 

Quindi immagino ti ho chiesto di scrivere un funzione chiamata di ricerca () che ha restituito un valore, un valore booleano, questo era vero o false-- come, vero se avete trovato il valore, falso se non l'avete fatto. E allora tu eri passato nel valore erano alla ricerca di valori, che in è il array-- oh, ho sicuramente messo che nel posto sbagliato. OK. In ogni modo, che dovrebbe avere stato a destra dei valori. E poi int n è il numero di elementi di tale matrice. Come si va a provare a pseudocodice che problema? Ti darò ragazzi come tre minuti per farlo. No, penso che ci sia only-- sì, ce n'è uno proprio qui. PUBBLICO: Posso? ANDI PENG: Sì, lo avete ottenuto. È che il lavoro? Ok bello. 

OK. Tutti i ragazzi di destra, noi siamo andando a frenare in. OK. Quindi assumiamo noi abbiamo questa bella poco array con n valori in esso. Non ho fatto disegnare le linee. Ma come potremmo fare per cercando di scrivere questo? Qualcuno ha voglia di dammi la prima linea? Se volete darmi la prima linea di questo pseudocodice. 

PUBBLICO: [incomprensibile] PUBBLICO: Che ci si vuole iterare through-- PUBBLICO: Solo un altro per il ciclo? PUBBLICO: --per. 

ANDI PENG: Quindi questo è un po 'complicato. Pensate about-- vuoi continuare a correre questo ciclo più e più volte fino a quando? 

AUDIENCE: Fino a quando il [incomprensibile] valore è uguale a quel valore. ANDI PENG: Esattamente. Così si può in realtà solo write-- possiamo anche semplificare più. Possiamo solo fare un ciclo while, giusto? Così si può solo avere loop-- sappiamo che è un po '. Ma per ora, sto andando per dire "loop" - con che cosa? Loop until-- ciò che è la nostra condizione finale? Credo di aver sentito. Ho sentito qualcuno dire che. 

Pubblico: Valori equivale a metà. ANDI PENG: Dillo ancora. PUBBLICO O, fino a quando la valore che si sta cercando per è uguale al valore medio. 

ANDI PENG: Che cosa se non è lì dentro? Che cosa succede se il valore che si sta cercando perché non è in realtà in questo array? PUBBLICO: Si ritorna 1. 

ANDI PENG: Ma cosa vogliamo ciclo finché se abbiamo una condizione? Già. 

PUBBLICO: Fino a quando non c'è un solo valore? ANDI PENG: è possibile ciclo until-- in modo da sapere che sei avrà un valore massimo, giusto? E si sa che si sta andando avere un valore minimo, giusto? Perché anche, questo è qualcosa Ho dimenticato di dire prima, che qualcosa che è critico su ricerca binaria è che l'array è già ordinato. Perché non c'è modo di fare questo se sono valori solo casuali. Non sai se uno è maggiore dell'altro, giusto? 

Così sapete che il vostro max e i tuoi minuti sono qui, giusto? Se avete intenzione di essere regolare il tuo massimo nei tuoi minuti e le mid-- facciamo solo assumere la tua valore medio è qui-- giusto si sta andando a fondo ciclo fino a quando il minimo è più o meno come il tuo massimo, a destra, o se il vostro max non è lo stesso del vostro min. Destra? Perché quando ciò accade, si sa che hai finalmente colpito lo stesso valore. Così si vuole fino a quando il ciclo min è inferiore o uguale a-- oops, non meno di o uguale a, l'altro modo around-- max è. 

Fatto che ha senso? Ho preso un paio di tentativi per ottenere tale diritto. Ma fino a quando il ciclo valore massimo è essenzialmente quasi meno o uguale al minimo, giusto? Questo è quando si sa che hai convergenti. PUBBLICO: Quando sarebbe il vostro massimo valore sia inferiore al minimo? ANDI PENG: Se si mantiene adattandolo, che è quello che stiamo andando di fare in questo. Questo fa senso? Minima e massima sono solo interi che siamo probabilmente andando a voler creare a mantenere traccia di dove stiamo cercando. Perché esiste la matrice indipendentemente da quello che stiamo facendo. Come, non siamo in realtà fisicamente tagliando l'array, giusto? Stiamo solo regolando dove stiamo cercando. Questo fa senso? 

PUBBLICO: Sì. 

ANDI PENG: OK. Quindi, se questa è la condizione per il nostro ciclo, cosa vogliamo all'interno di questo ciclo? Che cosa abbiamo intenzione di mancare di fare? Quindi in questo momento, abbiamo max e min, a destra, probabilmente creato qui da qualche parte. Stiamo andando a voler probabilmente per trovare una via di mezzo, giusto? Come facciamo a essere in grado di trovare il mezzo? Qual è il mathematical-- PUBBLICO: Max Plus min diviso per 2. ANDI PENG: Esattamente. Questo fa senso? E voi ragazzi vedo perché noi non solo use-- perché abbiamo fatto questo invece di fare solo n diviso 2? È perché n è un valore che sta andando a rimanere lo stesso. Destra? Ma, come registriamo il nostro minimo e valori massimi, che stanno andando a cambiare. E di conseguenza, il nostro mezzo sta per cambiare. Ecco perché vogliamo per fare questo qui. OK. 

E poi, ora che abbiamo trovato our-- sì. 

PUBBLICO: Solo un rapido interrogo quando si dice min e max, stiamo assumendo che è già ordinato? 

ANDI PENG: Sì, che in realtà è un precondizione per una ricerca binaria, che dovete sapere è ordinato. È per questo tipo, si scrive nella tua problema posto davanti la ricerca binaria. OK. Quindi, ora che sappiamo dove il nostro punto centrale è, che cosa vuoi fare qui? 

PUBBLICO: Vogliamo confrontare che all'altra. ANDI PENG: Esattamente. Quindi si sta andando a confrontare metà di valore, giusto? E che cosa fa che raccontano noi quando confrontiamo? Che cosa vogliamo fare dopo? 

AUDIENCE: Se il valore è più grande che la metà, vogliamo tagliare fuori. ANDI PENG: Esattamente. Quindi, se il valore è maggiore che la metà, siamo intenzione di voler cambiare questi Maxes minimo e, giusto? Che cosa vogliamo cambiare? Quindi, se conosciamo il valore è da qualche parte nel sito, cosa dobbiamo cambiare? Noi vogliamo cambiare il nostro minima per essere a metà, giusto? E poi il resto, se è in questo mezzo, che cosa vogliamo cambiare? 

PUBBLICO: Il tuo massimo. ANDI PENG: Sì. E poi si sta solo andando per mantenere looping, giusto? Perché ora, dopo una iterazione attraverso, hai un max qui. E poi si può ricalcolare un mid. E poi si può confrontare. E si sta andando a andare avanti fino a quando i minuti e le Maxes hanno sostanzialmente convergenti. E questo è quando si sa che hai colpito alla fine di esso. E neanche lo avete trovato non si dispone a quel punto. 

Questo senso per tutti? OK. Questo è abbastanza importante, perché avrete scrivere questo nel codice stasera. Ma voi ragazzi avete un buon senso di ciò che si dovrebbe fare, che è buono. OK. Quindi abbiamo circa sette minuti dalla fine sezione. Quindi stiamo andando a parlare di questo pset che faremo. Così il pset è diviso in due metà. Il primo tempo coinvolge attuazione di un ritrovamento in cui si scrive una ricerca lineare, un ricerca binaria, e un algoritmo di ordinamento. 

Quindi questa è la prima tempo in un pset dove saremo dando ragazzi ciò che è chiamato codice di distribuzione, che è il codice che abbiamo pre-scritta, ma appena lasciato alcuni pezzi off per finire di scrivere. Quindi ragazzi, quando si guarda a questo codice, si potrebbe ottenere davvero spaventato. Se sei proprio come, ahh, ho non so cosa che sta facendo, Non lo so, come, che sembra così complicato, ahh, rilassatevi. Va bene. Leggere le specifiche. Le specifiche vi spiegherà esattamente ciò che tutti questi programmi stanno facendo. 

Ad esempio, è un programma generate.c che verrà con il vostro pset. In realtà non è necessario toccare, ma si dovrebbe capire che cosa sta facendo. E generate.c, tutto ciò che sta facendo è o generazione di numeri casuali oppure si può dare un seme, come un numero predisposto che ci vuole, e genera più numeri. Quindi non c'è un modo specifico per implementare generate.c in cui si può solo fare un po 'di numeri per testare le vostre altri metodi su. 

Quindi, se si voleva, per esempio, testare la vostra scoperta, si vorrebbe eseguire generate.c, generare un po 'di numeri, e quindi eseguire la funzione aiutanti. La vostra funzione aiutanti è dove sei in realtà la scrittura di codice fisicamente. E pensate di aiutanti come un file di libreria stai scrivendo che ritrovamento sta chiamando. E così all'interno helpers.c, ti fare ricerca e l'ordinamento. 

E poi si sta andando a essenzialmente basta metterli tutti insieme. Le specifiche vi dirà come mettere che nella riga di comando. E voi sarete in grado di verificare se Non la tua specie e di ricerca stanno lavorando. Cool. Qualcuno ha già iniziato e problemi incontrati o domande hanno ora con questo? OK. 

PUBBLICO: Aspetta. Ho una domanda. 

ANDI PENG: Sì. 

PUBBLICO: Così ho iniziato a fare la ricerca lineare in helpers.c e non era davvero lavorando. Ma poi, ho scoperto che abbiamo appena necessario eliminare e fare ricerca binaria. Quindi cosa importa se non funziona? 

ANDI PENG: Breve risposta è no. Ma dal momento che siamo not-- PUBBLICO: Ma nessuno di in realtà il controllo. ANDI PENG: Non siamo mai andando a vedere che. Ma probabilmente si vuole fare sicuro che la ricerca sta lavorando. Perché se il vostro lineari ricerca non funziona, allora è probabile che il vostro binario ricerca non è andare a lavorare pure. Perché hai simile logica in entrambi. E no, non ha molta importanza. Così gli unici si piega in genere sono e ricerca binaria. Già. 

E inoltre, molti bambini erano cercare di compilare helpers.c. Non sta effettivamente permesso per fare questo, perché helpers.c non ha una funzione principale. E così si dovrebbe solo essere in realtà la compilazione generare e trovare, perché trovare le chiamate helpers.c e le funzioni all'interno di esso. In modo che rende il debugging un dolore nel culo. Ma questo è ciò che dobbiamo fare. PUBBLICO: Devi solo fare tutto, giusto? ANDI PENG: Si può solo fare tutti così, sì. OK. In modo che sia in termini di ciò il pset sta chiedendo a tutti voi di fare. Se avete qualsiasi domanda, a chiedere a me dopo la sezione. Sarò qui per, come, a 20 minuti. 

E sì, i pset di non è affatto male. Voi ragazzi dovreste essere OK. Questi, basta seguire le linee guida. Genere di avere un senso di, logicamente, cosa dovrebbe accadere e non avrete problemi. Non essere troppo spaventato. Ci sono un sacco di codice già lì scritta. Non essere troppo spaventati se non lo fai capire che cosa tutto questo significhi. Se si tratta di un sacco, è totalmente bene. E vieni a orari di ufficio. Ti aiuteremo a dare un'occhiata. 

AUDIENCE: Con l'extra funzioni, cosa guardiamo quelli sopra? 

ANDI PENG: Sì, quelli sono nel codice. Nel gioco del 15, la metà di è già scritto per voi. Quindi queste funzioni sono già nel codice. Yep. Tutto ok. Beh, buona fortuna. E 'un giorno disgustoso. Quindi spero che voi ragazzi non si sentono troppo male di stare dentro e codifica.