SPEAKER 1: Ciao a tutti! Bentornato alla sezione. Così felice di vedere così tanti di voi sia qui, e tutti quelli che hanno la visione on-line. Quindi, come al solito bentornato. Spero che abbiate passato una bella fine settimana, pieno di riposo, relax. E 'stato bello ieri fuori. Quindi, spero che vi sia piaciuto l'aria aperta. 

Quindi, prima di un paio di annunci. Di classificazione. Così, la maggior parte di voi dovreste aver ottenuto un e-mail da me sulla tua Pset Scratch, nonché Valutazione per Pset 1. Quindi, solo un paio di cose. Assicurarsi di utilizzare check50 in style50. Queste sono destinate ad essere Risorse per voi ragazzi, per assicurarsi che stai ricevendo il maggior numero di punti possibile senza inutilmente perderle. Quindi, le cose come stile sono molto importanti. Stiamo andando a decollare per esso. Alcuni di voi potrebbero avere già notato che dal vostro Pset. E check50 è solo un modo molto semplice per fare in modo che realmente stiamo tornando quello deve essere restituito all'utente, e che tutto sta funzionando correttamente. 

Nella seconda nota, assicurarsi che il proprio caricamento cose nella cartella corretta. Rende la mia vita solo un po 'più difficile se si carica Pset 2 in 1 Pset perché quando si scarica le cose, non scarica correttamente. E io so che è un po 'traballante in un sistema per abituarsi, ma solo essere super attenzione, se non altro per me, in modo che quando stai ricevendo messaggi di posta elettronica a come 02:00 e io sono la classificazione. Se non provocare devo guardare tutto per il vostro Pset. Freddo. 

So che è presto, ma io completamente ma ho preso alla sprovvista da un saggio che è dovuto questo Venerdì, che i miei professori erano proprio come, oh yeah. Ricordate, si dispone di un saggio a causa il Venerdì. Quindi, so che a nessuno piace pensare midterms, ma il tuo primo quiz è il 15 ottobre, ottobre che inizia questa settimana. Quindi, potrebbe essere presto del previsto è tutto. In modo che non sei gettato alla sprovvista quando Cito parte della prossima settimana che oh, il quiz prossima settimana, ho pensato Ti darei un po 'di più di un testa a testa ora. 

Quindi, impostare il problema, numero tre. Come persone hanno letto il spec per curiosità? Ok. Abbiamo ottenuto una coppia. Tipo di giù rispetto allo scorso settimana, ma va bene così. So che era bello fuori. Così Break Out. Sicuramente dopo si ottiene fatto oggi letto il tuo spec almeno provare come il download codice distribuzione e funzionamento come la prima iniziale cosa che ti chiedono di. Poiché stiamo usando codice di distribuzione e una biblioteca che siamo solo stati using-- --È è solo la seconda volta che abbiamo fatto questo Pset, cose folli possono accadere con il vostro apparecchio, e si vuole scoprire che adesso rispetto a tardi. 

Perché se è Giovedi notte o è Mercoledì sera e per qualche motivo l'apparecchio solo non lo fa voler eseguire con la libreria o con la distribuzione codice, che significa non si può nemmeno iniziare a fare la codifica. Poiché non è possibile controllare per vedere se funziona. Il tuo non sara 'in grado per vedere se si compila. Si vuole prendersi cura di coloro che all'inizio del settimana, quando è ancora possibile scrivermi o uno degli altri TF, e siamo in grado di ottenere quelli fissati. Perché quelli sono problemi che stanno andando a fermarti di fare un reale progresso. Non è come un bug, che si può solo tipo di saltare. Se hai problemi con il tuo apparecchio o il codice di distribuzione, davvero si vuole ottenere che prese cura di più prima che poi. Quindi, anche se non riuscirai a realtà iniziare a scrivere codice, scaricare la distribuzione codice, leggere le specifiche, verificare che tutto è che vi lavorano. Ok? Se si può fare solo che, io promettere la vostra vita sarà più facile. E così probabilmente stai andando a farlo adesso giusto? Ok. Quindi, tutte le domande lì? Tutte le cose logistici? Il bene di tutti? Ok. 

Dichiarazione di non responsabilità per quelli di si in camera e on-line. Io vado a cercare di cambiare tra PowerPoint nell'apparecchio perché stiamo andando come fare un po 'di codifica oggi dalla grande richiesta di anonimo suggerimento sondaggio ho inviato la settimana scorsa. Quindi, faremo un po 'di codifica. Quindi, se voi volete anche di accendere i vostri apparecchi, e si dovrebbe aver ricevuto una e-mail da me, con un file di esempio. Non esitate a farlo. 

Quindi, stiamo andando a parlare di GDB, che è un debugger. E 'intenzione di aiutarvi tipo di capire dove le cose vanno male nel codice. E 'davvero solo un modo per fare un passo tramite il codice come sta accadendo, ed essere in grado di stampare le variabili o vedere cosa sta realmente accadendo sotto il cofano versi il tuo programma solo in esecuzione, è come faglie, e tu sei come, idea quello che è appena successo qui. Non so quale linea non è riuscito a. Non so dove è andata male. Quindi, GDB sta per aiutarvi in ​​questo. Inoltre, se si decide di continuare sì, e prendere 61, sarà davvero, davvero essere la vostra migliore amico, perché io posso dire perché sto attraversando quella classe. 

Stiamo andando a guardare binario di ricerca, che, se voi ragazzi ricordo il grande esempio rubrica telefonica spettacolo dalla classe. Saremo applicazione di tale, e a piedi attraverso che un po 'di più, e poi stiamo attraversando quattro diversi tipi, che sono Bolla, Selezione, inserimento, e Merge. Freddo. Quindi, GDB come ho detto, è un debugger. E questi sono un po 'grande cose, le grandi funzioni o comandi utilizzare all'interno di GDB, e io camminerò attraverso una demo di esso in un secondo. 

Quindi, questo non è solo intenzione di rimanere astratto. Cercherò di fare come concreta possibile per voi ragazzi. Così, rompere. Sarà o sarà rottura come, un numero, che rappresenta una riga nel programma, oppure si può chiamare una funzione. Quindi, se si dice rompere principale, si fermerà a principale, e ti permettono di camminare attraverso quella funzione. 

Allo stesso modo, se avete un po 'esterna funzionare come Swap o Cube, che abbiamo visto la scorsa settimana. Se dici trasgredirà uno solo di questi, ogni volta che il programma che colpisce, che sarà vi aspetta a dirgli cosa fare. Prima sarà solo eseguito in modo da potrebbe effettivamente un passo all'interno della funzione e vedere cosa sta succedendo. Quindi, la prossima, appena salta sopra il riga successiva, va oltre le funzioni. Step. Questi sono tutti po 'astratto. Quindi, sto solo andando a correre attraverso di loro, ma li vedrete in uso in un secondo. 

Entra in una funzione. Quindi, come dicevo, come con Swap, sarebbe permettono di realtà come se sei come fisicamente fare un passo dentro, si può pasticciare con queste variabili, stampa che cosa sono, vedere cosa sta succedendo. Elenco letteralmente basta stampare il codice circostante. Quindi, se si dimentica di genere dove siete nel vostro programma, o vi state chiedendo quello che sta succedendo intorno ad esso, questo sarà solo stampare un segmento di avere cinque o sei linee intorno ad esso. Quindi, è possibile ottenere orientato di dove siete. 

Stampa qualche variabile. Quindi, se avete la chiave come in Cesare, che vedremo. Si può dire Tasto print in qualsiasi momento. E ti dirò che cosa il valore è così che, forse da qualche parte lungo la strada, sovrascritti per la vostra chiave. Si può effettivamente dire che, a causa si può effettivamente osservare tale valore. 

In la gente del posto, solo stampe le vostre variabili locali. Così, ogni volta che sei all'interno di un ciclo, e si desidera solo per vedere come, oh. Qual è il mio io? Che cosa è questo valore della chiave che io inizializzare qui? Qual è il messaggio, a questo punto? E 'solo stampare tutto di questi, in modo che non devono singolarmente dire, Stampa I. Stampa Messaggio. Stampa Key. E quindi su Schermo. Ciò che fa è, come si passo attraverso il programma, sarà solo fare in modo che sia la visualizzazione di un po 'di certa variabile in ogni punto. In modo che si also-- --è è una specie di scorciatoia in cui non devi andare avanti come, oh. Tasto Stampa o Stampa I. E 'appena lo farà automaticamente per voi. 

Così, con questo, stiamo andando per vedere come questo va. Io vado a cercare di interruttore verso l'apparecchio in uso. Vedi se posso fare questo. Tutti. Stiamo solo andando a specchio esso. Non c'è niente di pazzesco sul mio portatile in ogni modo. Ok. Questo deve essere questa. E 'così piccolo. Vediamo se siamo in grado di farlo. 

Ok. Alice è ovviamente in difficoltà qui solo un po ', ma ci arriveremo in un Momento. Ok. Stiamo solo andando ad aumentare questo. Ok. Tutti possono vedere che tipo di? Forse un po '? Lo so che è un po 'piccola. Non riesco a capire come rendere questo più grande. Se qualcuno lo sa. Qualcuno sa come farlo più grande? Ok. Stiamo andando a rotolare con esso. Non importa comunque perché è solo questo è il codice che voi ragazzi dovrebbero avere. 

Che cosa è più importante è il terminale qui. E abbiamo qui Perché è così piccolo? Impostazioni. Oh. Vero Ike. Come va questo? Fuori di lì. Che è meglio per tutti? Ok ,. Freddo. 

Avete presente quando siete in un CS classe di difficoltà tecniche sono tipo di parte di the-- Quindi, cerchiamo di chiarire questo. Ok. Così, proprio qui in sezione, che abbiamo avuto qui. Cesare è un file eseguibile. Così ho fatto. Quindi, una cosa da realizzare con GDB è che funziona solo su file eseguibili. Quindi, non è possibile eseguire su un Dotsy. Si deve effettivamente fare Assicurarsi che il codice venga compilato, e che può effettivamente essere eseguito. 

Quindi, assicurarsi che se non lo fa compilarlo, farlo compilare, in modo da poter genere di correre attraverso di essa. Quindi, per iniziare GDB, tutto ciò che fai, Gloria tipo GDB, e quindi solo il file che si desidera. Ho sempre errori ortografici Cesare. Ma si vuole fare in modo dal momento che è un eseguibile, dot flash ti in modo che significa che si sta andando per eseguire CSI si sta andando ad eseguire questo file sia con il debugger. Ok. Quindi, tu che, si ottiene questo tipo di parole senza senso. E 'solo tutte le cose su di debugger. In realtà non è necessario preoccuparsene adesso. E come vedete, abbiamo questo parentesi aperte, PIL, chiudere parentesi, e solo un po 'si presenta come la nostra linea di comando, giusto? 

Allora, che cosa vogliamo fare-- --quindi, La prima cosa è che vogliamo scegliere un posto per romperlo. Quindi, c'è un bug in questo programma di Cesare che presento, che che andremo a scoprire. E 'ciò che fa è che ci vuole l'ingresso Barfoo in tutte le protezioni, e per qualche motivo non cambia A. Lascia solo da solo, tutto il resto è corretto, ma la seconda lettera A rimane invariata. Quindi, stiamo andando a cercare di capire perché. Quindi, la prima cosa che in genere vuole fare ogni volta che si avvia il GDB è capire dove romperlo. 

Così Cesare è un programma piuttosto breve. Non ci resta che una funzione, giusto? Qual è stata la nostra funzione in Cesare? C'è solo una funzione, giusto principale? Principale è una funzione per tutti i vostri programmi. Se non aveste principale, potrei essere un po 'preoccupato in questo momento, ma spero abbiate passato principale in là. Allora, cosa possiamo fare è che possiamo basta rompere principale, proprio così. Così, si dice, OK. Abbiamo impostato il nostro unico punto di interruzione lì. 

Così, ora la cosa da ricordare è di Cesare prende un argomento della riga di comando di destra e non abbiamo nessuna parte ancora fatto. Quindi, ciò che si fa è quando si effettivamente andare a correre il programma, qualsiasi programma che si è esecuzione in GDB che ha bisogno della riga di comando argomenti, si sta andando a ingresso quando si inizia a eseguirlo. Quindi, in questo caso, facciamo Eseguire con una chiave di tre. E sarà effettivamente iniziare. 

Quindi, se vedete qui, abbiamo Se RC non è uguale a 2. Quindi, se voi ragazzi tutti hanno il file che ho mandato su vedrai che è come il prima linea la nostra funzione principale, giusto? E 'il controllo per vedere se abbiamo il numero corretto di argomenti. Quindi, se vi state chiedendo se RC è corretta, si può fare qualcosa come stampa RC. RC è due, che è quello che ci aspettavamo, giusto? 

Quindi, possiamo andare Avanti, e proseguire attraverso. Così, abbiamo qualche chiave lì. E siamo in grado di stampare la nostra chiave per assicurarsi che sia corretto. Interessante. Non è proprio quello che ci aspettavamo. Quindi, una cosa da realizzare con GDB inoltre, è che non è fino a che realmente ha colpito Avanti, che la linea che avete appena visto è effettivamente eseguito. Quindi, in questo caso Chiave non è stato ancora assegnato. Quindi, Key è un valore spazzatura che si vede sul fondo lì. Negativo $ 120-- --È di un miliardo e qualcosa di cose strane giusto? Non è la chiave che ci aspettavamo. Ma se ci ha colpito su Avanti, quindi siamo cercare di chiave di stampa, è tre. 

Ognuno vede che? Quindi, se si ottiene qualcosa che sei come, aspetta. Questo è completamente sbagliato, e io non lo so come questo possa accadere perché tutto quello che voglio fare è assegnare un numero, una variabile, provare a colpire Successivamente, provare a stampare di nuovo, e vedere se funziona. Perché è solo andando a eseguire e in realtà assegnare qualcosa dopo premere Avanti. Dare un senso a tutti? Uh huh? 

SPEAKER 2: Quando si casuale numeri che cosa significa? 

SPEAKER 1: E 'solo casuale. E 'solo spazzatura. E 'solo qualcosa che il vostro computer in modo casuale assegnare. Freddo. Quindi, ora siamo in grado di muoversi attraverso, e così ora abbiamo questo testo GetString normale. Quindi, lasciatemi introdurre quello accadrà quando ci ha colpito Avanti qui. Il nostro tipo di GDB scompare, giusto? Questo perché GetString è ora di esecuzione, giusto? Così, quando abbiamo visto il testo normale è uguale GetString, parentesi aperte e parentesi, e ci ha colpito Avanti, che ha in realtà eseguito ora. Quindi, è in attesa di noi all'ingresso qualcosa. 

Quindi, stiamo andando per inserire il nostro cibo che è quello che è mancato come ti ho detto e che dice solo che è terminato l'esecuzione, che il chiuso staffa significa che è All'uscita da questo carico. Quindi, siamo in grado di colpire Avanti, e ora, come io sono sicuro che siete tutti a conoscenza da parte di Cesare, questo è, che cosa è questa linea sta per fare. E 'per Int I è uguale a 0, N è uguale a Strlen, testo normale, e poi I è minore di n, io, più, più. Che cosa è questo ciclo intenzione di fare? Aprire il messaggio. Freddo. Quindi, cominciamo a farlo. 

Quindi, qualora questa condizione corrispondere, per il nostro primo? Se si tratta di un B, è solo testo I. Noi possono ottenere informazioni sui nostri locali. Così, I è pari a zero, e se sei, che ci aspettiamo, e la nostra chiave è di tre. Tutto ciò che ha senso, giusto? Questi numeri sono tutti esattamente quello che dovrebbe essere. Così, canticchiare? SPEAKER 3: Ho numeri casuali per il mio. SPEAKER 1: Beh, siamo in grado di check-- --dobbiamo si può parlare di che in un secondo. Ma si dovrebbe essere sempre presente. Quindi, se abbiamo un capitale B per il primo, questa condizione dovrebbe prenderlo, giusto? Quindi, se abbiamo colpito Avanti, vediamo che questo caso viene eseguito in realtà. Perché se stai seguendo avanti nel codice, questa linea qui, in cui il testo normale I è sostituito con questo aritmetica, esegue solo se il caso condizione è corretto giusto? 

GDB è solo andare a mostrare cose che sono effettivamente in esecuzione. Quindi, se questa condizione se non è stata rispettata, è solo andando per passare alla riga successiva. Ok? Quindi, abbiamo che. Questa staffa significa che è chiuso da questo carico di ora. Quindi, che sta per iniziare di nuovo. Proprio così. Quindi, che possiamo ottenere informazioni sulle nostre gente del posto qui, e vediamo che il nostro primo lettera è cambiata, giusto? Ora è una E, come dovrebbe essere. Quindi, possiamo continuare su. 

E noi abbiamo questo controllo. E questo controllo dovrebbe funzionare, giusto? È A. Si dovrebbe essere cambiato tre lettere in avanti. Ma se si nota, si ottenere qualcosa di diverso. Quindi, in questo caso fino qui, catturato esso, e quindi questa linea eseguita, che ha modificato il nostro B. Ma, in questo caso di specie, abbiamo che appena saltato, e andò al [? L SIFF. ?] Quindi, qualcosa sta succedendo lì. Cosa che si sta dicendo è che, sappiamo che si deve prendere qui, ma non lo è. Chiunque può vedere ciò che il nostro problema è in quella linea? E 'una cosa molto minuto. E si potrebbe anche guardare il vostro codice. E 'line-- anche dimenticare ciò che la linea è in there-- ma è in [incomprensibile]. Sì? 

SPEAKER 4: E 'il più grande di pagina se lo si legge nel libro. SPEAKER 1: Esattamente. Così, il debugger non poteva dire che, ma il debugger potrebbe arrivare fino a una linea che si sa non funziona. E a volte, quando in particolare più tardi nel semestre, quando hai a che fare con cento, centinaia di poche righe di codice, e si non so dove è in mancanza, questo è un ottimo modo per farlo. Così, abbiamo trovato il nostro bug. È possibile risolvere il problema nel file, e allora si potrebbe correre di nuovo, e tutto avrebbe funzionato alla perfezione. E la cosa più importante è questo può sembrare, OK. Sì. Freddo. Si sapeva che cosa stai cercando. Quindi, si sapeva che cosa fare. 

GDB può essere super disponibile, perché si può stampare tutte queste cose che si non lo farei. E 'molto più utile di printf. Quanti di voi usa come istruzioni printf per capire dove era un bug, giusto? Così, con questo, non è necessario deve andare avanti indietro, e come commentare in Printf, o commentando, e capire cosa si dovrebbe essere la stampa. Questo in realtà solo consente di scorrere, stampare le cose come stai passando, così, è possibile osservare come cambiano in tempo reale, come il programma è in esecuzione. 

E ci vuole un po ' po 'di tempo per abituarsi. Mi raccomando solo tipo di essere un po 'frustrato con esso per ora. Se si spendono un'ora sulla la prossima settimana per imparare a usare GDB, si salva te stesso tanto tempo successivamente. E letteralmente. diciamo questo per persone ogni anno, e mi ricordo quando ho preso il classe, ero come, mi andrà bene. No. Pset 6 è venuto su e mi è stato come, sto andando imparare come utilizzare GDB, perché non lo faccio sapere che cosa sta succedendo qui. 

Quindi, se si prende il tempo così usarlo su programmi più piccoli che si sta andando ad essere lavorando, come lavorare attraverso qualcosa di simile Visionare, come questo. O se volete la pratica in più, ne sono sicuro Potrei venire con programmi buggy, per eseguire il debug, se vuoi. 

Ma se si prende un po 'di tempo per ottenere l'abitudine, basta giocare con essa, sarà davvero servirà bene. Ed è davvero una delle quelle cose che hai appena devono provare, e sporcarsi le mani con, prima che realmente capire. Ho davvero capito solo una volta Ho dovuto eseguire il debug di cose con esso, ed è molto più bello di avere un'idea di come eseguire il debug il più presto possibile. Ok. Freddo. So che è un po 'come un corso intensivo di GDB, e ci tornerò sicuramente lavorare per ottenere questi per sembrare più grandi la prossima volta. Freddo. 

Quindi, se torniamo al nostro PowerPoint. E 'questo di andare a lavorare? Awh. Sì. Ok. Quindi, se mai hai bisogno di qualsiasi quelli di nuovo, c'è la lista. Cerca Quindi binario, che tutti ricorda il grande spettacolo di David ripping rubriche a metà. Io davvero non capisco il rubriche più, perché come dove si fa ottenere rubriche in questi giorni? Io davvero non lo so. La ricerca binaria. Qualcuno ricorda Come funziona binario di ricerca? Chiunque a tutti? Sì? SPEAKER 5: Non si sa quando si guarda a cui la metà sarebbe in, base di questo, ed eliminare l'altra metà. 

SPEAKER 1 Esattamente. Così, la ricerca binaria, è una specie di a-- --dobbiamo piace chiamarlo divide et impera. Allora, che cosa farai è ti aspetto nel mezzo, e vedrete se corrisponde quello che stai cercando. E se non lo fa, quindi si tenta di capire, sta andando ad essere lasciato metà o la metà destra. Quindi, questo potrebbe essere se siete alla ricerca a qualcosa che è alfabetizzato, vedi, oh. Ha Allison viene prima M? Sì. Quindi, stiamo andando a guardare il primo tempo. 

Oppure potrebbe essere come con i numeri. Tutto ciò che si può confrontare, si può essere ordinato. È possibile utilizzare la ricerca binaria su. Così, qualcuno ricorda questo grafico o di cosa si tratta? E 'Complessità asintotica. Quindi, questo grafico solo descrive quanto tempo si porta a risolvere un problema come si aumenta il numero di cose che si sta utilizzando. 

Così, abbiamo N, che è il tempo lineare. Se N più di due, che è leggermente meglio, cresce ancora super veloce. E poi abbiamo il login, che è quello che noi consideriamo Ricerca binaria. Se notiamo, come il problema diventa molto più e molto più grande, il tempo necessario per risolverlo in realtà non aumenta più di tanto. E 'come paragonabile qui all'inizio. Sei come, OK. Tutto ciò che qui non lo fa davvero importa che uno si usa, ma si arriva ad un milione, un miliardo. Stai cercando di trovare some-- --you're cercando di trovare un ago in un pagliaio. 

Penso che si desidera questo problema. Volete questa complessità, non lineare perché per tutto quello che il vostro andando essere alla ricerca attraverso ogni singolo ago, cosa di fieno, cercando di cercare l'ago. E non è troppo divertente a mio parere. Mi piace veloce. Mi piace efficiente. E gli studenti come laboriosa voi ragazzi sono, si sa lavorare meglio, non di più tipo cosa, come si può compensare questi algoritmi. 

Quindi, stiamo andando a camminare attraverso solo un esempio veloce. Penso che voi ragazzi dovreste avere una mano sulla ricerca binaria, ma nel caso qualcuno è un po ' fuzzy, vogliono rafforzarlo, stiamo per andare solo attraverso un esempio qui. Quindi, stiamo cercando se l'array contiene sette. 

Quindi, prima cosa da fare è guardare in mezzo, giusto? E inoltre si sta andando ad essere la codifica Binary Cerca in appena un secondo. Quindi, che sta per essere divertente. Quindi guardiamo in medio piccole matrici 3. Ritiene 3 pari 7? Non lo fa. Sono le sei. Quindi, è meno di o maggiore di sette? Meno di. Sì. Ragazzi bel lavoro. Mi sento come se dovessi avere caramelle perché voglia di buttare fuori nei cortili. E 'quello che ho intenzione di fare la prossima settimana. Manterrà voi ragazzi taglienti. 

Così, gettiamo via che primo tempo, giusto? era inferiore. noi sappiamo che tutto ciò che su quella sinistra sta per essere inferiore a quello in realtà stiamo cercando. Quindi, non c'è bisogno di prestare attenzione ad esso. Basta non pensarci più. Così, ora guardiamo alla nostra destra, e guardiamo a metà laggiù, e ora è nove. Quindi, 9 è-- --Everyone? Maggiore di ciò che siamo cercando, giusto? Quindi, stiamo andando a buttare via tutto a destra. Come quella. Ora, tutto quello che ci rimane è uno. Quindi controlliamo, è questo ciò che stiamo cercando? esso è. Abbiamo trovato quello che volevamo. Così abbiamo finito. Bilineare ricerca. 

E se ci fate caso, abbiamo aveva sette ingressi lì. Ci sono voluti solo come tre volte, ma se si sta facendo come un miliardo, ragazzi sapere quanti passi sarebbe prendere se avessimo quattro miliardi di cose? Qualche ipotesi? Si tratta di 32. 32 passi per trovare qualcosa in quattro miliardi elemento di un array a causa di potenze di due. Quindi due è a 32, è quello di quattro miliardi. 

Così come abbastanza pazzo sei ancora all'interno come un numero relativamente basso di passi di trovare qualcosa in quattro miliardi di elementi. Quindi, su questa nota, siamo andando a codificare questo così voi ragazzi può effettivamente tipo di vedere come funziona. Va bene, quindi voi potete codificare. Ho intenzione di lasciare che voi ragazzi parlare per un po '. Vieni a conoscere persone intorno a voi, che è quello che qualcuno voleva da ultima sezione. 

Quindi, per conoscere le persone intorno a voi. Parlare per un po '. E tutto quello che voglio da te ragazzi in questo momento è solo cercare di creare una struttura di pseudocodice. Ok? Whoa. Tutto quello che voglio da voi ragazzi è che sei solo andando a riempire in questo caso, mentre. Quindi io ho posto questi superiore e limiti inferiori che rappresentare l'inizio e fine della nostra matrice. E si sta andando a realtà loop through e capire quello che stiamo facendo in questo ciclo while. 

Quindi, se si riesce a capire fuori-- ho un suggerimento there-- quali sono i casi che abbiamo qui? Quindi, se si vuole capire il casi, ci saranno quelli pseudocodice e poi ci troveremo a loro codice. E sarà, io pensare, si spera che sarà essere un po 'più facile del previsto. Perché non è che molto codice, in realtà, che è davvero cool. 

Mm-hm? 

STUDENTE: [incomprensibile]? ISTRUTTORE: Sì. C'era qualcosa trovare nel mezzo. 

STUDENTE: Quindi possiamo usare quella. Ok. 

ISTRUTTORE: Perfect. Ecco, questo è la prima cosa che dobbiamo fare. Quindi, trovare il centro. Ottimo. Così avete un'idea di come potremmo effettivamente trovare il mezzo con il codice? 

STUDENTE: Sì. n più di 2? ISTRUTTORE: Quindi oltre 2 n. Quindi, una cosa da ricordare è che i tuoi limiti superiori e inferiori cambiano. Continuiamo costrizione parte della matrice che stiamo cercando di. Quindi n oltre 2 funziona solo per la prima cosa che facciamo. Quindi, prendendo superiore e inferiore in considerazione, come potremmo ottenere che elemento centrale? Perché vogliamo che il centro tra superiore e inferiore, giusto? Mm-hm? 

STUDENTE: [incomprensibile]. 

ISTRUTTORE: Così abbiamo un po 'di mezzo. E sarà superiore più basso su 2. Impressionante. Ci andiamo. Una linea verso il basso. Voi ragazzi siete sulla buona strada. Quindi, ora che abbiamo la nostra mezzo, cosa vogliamo fare? Proprio in generale. Non è necessario codificare esso. Sì. STUDENTE: [incomprensibile]? ISTRUTTORE: Quindi è più perché sei calcolando la media tra i due di loro. Quindi, se si pensa a loro come genere crescente dai lati, pensare a come ci si avvicina Al centro, si vuole così. Quindi, se si fosse su entrambi i lati del mezzo, e abbiamo come 5 e 7. Quando si aggiunge insieme si ottenere 12, si divide per 2, è di 6. 

A volte è difficile spiegare perché funziona, ma se si lavora attraverso un esempio talvolta, vi aiuterà a capire se dovrebbe essere più o meno. Sì. 

STUDENTE: [incomprensibile] esattamente al centro se avessero un caso in cui ci sono un sacco di numeri più piccoli e come un gran numero? 

ISTRUTTORE: Quindi tutto ciò che serve è al centro della matrice. Quindi, se si ha un gruppo di piccoli numeri e poi un numero molto grande alla fine, non importa. Tutto ciò che conta è che stanno ordinati, appena desiderare di guardare al centro del l'array perché sei ancora affettare il problema a metà. Freddo. Quindi, ora che abbiamo la mezzo, cosa facciamo dopo? 

STUDENTE: Confronta. ISTRUTTORE: La confrontare. Quindi confrontare mezzo a value_wanted. Freddo. Quindi, vedete qui abbiamo questo valore vogliamo qui. Ricordate che questo è un array. Quindi mezzo si riferisce all'indice. Così vogliamo fare i valori di centro. Non dimenticare, se si desidera di confrontare, doppio uguale. Fate equivale esattamente singolo sei solo andando a riassegnare esso, e poi, naturalmente, è sarà il valore che si desidera. Quindi non farlo. 

Quindi stiamo andando a vedere se i valori a mezzo è uguale al valore che vogliamo. Non dimenticare la tua parentesi. Dropbox dovrebbe andare via. Allora che cosa facciamo in questo caso? Se è quello che vogliamo tornare? Stiamo cercando di dire. 

STUDENTE: stampare. 

ISTRUTTORE: Beh, abbiamo non si vuole stampare. Quindi questo è un bool qui, in modo da vuole restituire true o false. Noi stiamo dicendo, è questo numero un [? RRA? ?] Quindi, se lo è, abbiamo appena torniamo vero. Se posso incantesimo vero. 

STUDENTE: Perché non si restituire zero? ISTRUTTORE: così si potrebbe ritorno pari a zero se si voleva. Ma in questo caso, perché la nostra funzione restituisce un bool, abbiamo bisogno di tornare true o false. STUDENTE: Quando sei dicendo espressione booleana, puoi impostarlo uguale a falso? Come se voglio dire, se questa condizione non è soddisfatta, come è in alto è uguale a false. Sarà capire se solo mettere falso dall'altra parte? ISTRUTTORE: Sì. Quindi, in realtà, se siete mai fare qualcosa come è superiore o è inferiore, che restituisce true o false e in realtà è cattivo stile di diciamo uguale uguale vero o uguale è uguale a false. Si desidera utilizzare tale risultato come se stesso come il vostro controllo. Non è quello che volevo. Questo è quello che volevo. Quindi, nel caso di che stai chiedendo su qualcosa di simile a salvare questo in c. 

Quindi, se abbiamo int main (void) e qualcosa di simile a questo. E si ha se è superiore di alcuni input e sei chiedendo se si può fare qualcosa di simile? Giusto? STUDENTE: Stavo cercando per farlo [incomprensibile]. Perché se it's-- ISTRUTTORE: Giusto. Così si desidera che questo sia falso, giusto? STUDENTE: Sì. ISTRUTTORE: Quindi, in questo caso vogliono da eseguire se non è vero. Quindi la cosa interessante lì fare è questo. Quindi ricorda esclamativo punto nega le cose? Dice [incomprensibile] non significa. Quindi, se guardiamo solo questa parte qui, che ci si dicono che restituisce falso come si desidera. Non è falso è vero che significa che questo sarebbe eseguire. Questo fa senso? STUDENTE: Sì. ISTRUTTORE: Awesome. Ok. Così abbiamo potuto solo tornare vero in questo caso. Così ora abbiamo due altri casi in questo caso. Quali sono i nostri altri due casi? Diciamo solo farlo in questo modo. Quindi cominciamo con il resto se valori a mezzo è inferiore al valore che vogliamo. Quindi il nostro valore nel mezzo è meno rispetto al valore che stiamo cercando. 

Quindi, quale limite si fa pensiamo vogliamo aggiornare? Superiore o inferiore? Superiore? Quindi quale lato della matrice abbiamo intenzione di essere alla ricerca di? 

STUDENTE: Più bassa. 

ISTRUTTORE: Noi stiamo andando essere guardando sinistra. Quindi, altrimenti se poco valore è inferiore. Così il vostro valore medio qui è inferiore a quello che vogliamo. Quindi, vogliamo prendere il lato destro della nostra matrice. Quindi stiamo andando a aggiornare il nostro limite inferiore. Quindi dovremo riassegnare il nostro più bassa. E voi cosa ne pensate inferiore dovrebbe essere? STUDENTE: Il valore centrale? ISTRUTTORE: Così il value-- mezzo STUDENTE: Plus 1. ISTRUTTORE: --plus 1. Qualcuno può dirmi perché abbiamo che più 1? 

STUDENTE: [? Nessun valore?] è più uguale ad esso. 

ISTRUTTORE: Giusto. Perché sappiamo già che il valore medio non è uguale a e vogliamo escluderlo da tutte le ricerche successive. Se si dimentica che più 1, questo sarà come ciclo a tempo indeterminato. E devi semplicemente essere catturati in un ciclo infinito e poi ti segfault e le cose vanno male. Quindi, accertarsi sempre che non sei compreso il valore che avete appena guardato. Così ci prendiamo cura di che con un più 1. 

Così ora abbiamo la nostra ultima condizione che ho sempre per motivi di sicurezza è possibile controllare qui, altrimenti se il valore a il mezzo è maggiore del valore che vogliamo. Ciò significa che vogliamo metà sinistra. Quindi quale stiamo andando ad aggiornare? Superiore. E qual è questo uno che va a pari? Medio meno 1 perché, naturalmente, vogliamo per essere sicuri che non siamo guardando quel valore centrale di nuovo. E allora noi ce l'abbiamo. Questo è tutto. Questo è tutto ciò di ricerca binaria è. Non è poi così male, vero? E 'come 10 linee di codice con uno spazio bianco. Quindi molto potente, molto utile, sarà essere di utilizzarlo in una delle tue p-set successivi. Forse non questo, ma più tardi. Quindi imparare. Lo adoro. Si tratterà bene. Così qualcuno ha qualche domande sul binario di ricerca? Sì. 

STUDENTE: Ha importanza se il n è pari o dispari? 

ISTRUTTORE: No. Perché abbiamo gettato al centro come un int, sarà solo troncherà esso. Quindi rimarrà un intero e sarà eventualmente ordinare attraverso tutto ciò. Quindi non dovete preoccuparvi di questo. Tutto bene? Impressionante. Freddo. Così, voi ragazzi ha ottenuto questo. Slideshow. Così come stavamo parlando, lo so David menzionato runtime complessità. 

Quindi, nel migliore dei casi, è solo uno, che noi chiamiamo costante di tempo. Qualcuno può dirmi il motivo che potrebbe essere? Che tipo di scenario che comporterebbe? Mm-hm. 

STUDENTE: [incomprensibile] first-- ISTRUTTORE: Quindi la centrale è la primo elemento che veniamo a, giusto? Quindi, o una serie di uno o tutto ciò che stiamo cercando solo sembra essere nel bel mezzo. Ecco, questo è il nostro migliore dei casi. Si ottiene in problemi reali, probabilmente non andando a raggiungere il [incomprensibile] che spesso. E il nostro caso peggiore? Il nostro caso peggiore è log n. E questo ha a che fare con tutta la potenze di due cosa che ho parlato. 

Quindi, nel caso peggiore significherebbe che abbiamo dovuto tagliare la matrice verso il basso finché era un elemento di uno. Così abbiamo dovuto tagliare verso il basso a metà il numero di volte che potevamo. Ecco perché è log n, perché basta tenere dividendo per due. Così ipotesi, cose che voi bisogno di sapere se siete mai intenzione di usare una ricerca binaria. I suoi elementi devono essere ordinati. Devono essere ordinati perché questo è l'unico modo in cui si può sapere se si è in grado buttare via la metà di esso. 

Se hai avuto questa borsa confuso di numeri e che stai dicendo, OK, vado a controllare il mezzo numero e il numero che sto cercando è inferiore a quello, sto solo andando gettare arbitrariamente fuori una metà. Tu non sapere se il vostro numeri in detto altro mezzo. Il tuo elenco deve essere ordinato. Inoltre, questo può essere andando avanti un po ', ma è necessario disporre di accesso casuale. È necessario essere in grado di solo andare a quel elemento centrale. Se si deve attraversare attraverso qualcosa o ci vogliono misure supplementari per arrivare a questo elemento centrale, non è più perché log n si aggiunge più lavoro in esso. E questo renderà un po ' più senso in due settimane, ma ho appena sorta di voluto premettere, voi ragazzi dare un'idea di ciò che è a venire. Ma questi sono i due presupposti importanti che è necessario per un elenco binario. Assicuratevi che sia risolto. Questo è il grande per ragazzi adesso. E su questo siamo in grado di andare in il resto della nostra specie. Così quattro bolla sorts--, l'inserimento, la selezione, e si fondono. Sono tutti i tipi di fresco. Se voi ragazzi decidono di prendere CS 124, imparerete a conoscere tutti i tipi di sorta. E se sei un fan di XKCD, ci è un fumetto davvero cool su come i tipi veramente inefficaci, che ho consigliamo di andare a guardare. Uno di loro è come il panico specie, che è come, oh no, tornare matrice casuale. Sistema di arresto. Lascia. Così l'umorismo geek è sempre buona. 

Così qualcuno si ricorda genere di come solo un'idea generale di come funziona bubble sort. Ti ricordi? 

STUDENTE: Sì. 

ISTRUTTORE: Go for it. 

STUDENTE: Quindi stai passando e se è più grande, poi si scambiano i due. 

ISTRUTTORE: Mm-hm. Esattamente. Quindi basta eseguire iterazioni. Controllate due numeri. Se il precedente è più grande di quella successiva, appena li scambiano in modo che in in questo modo tutti i numeri superiori bolla verso la fine della lista e tutti i numeri inferiori bolla verso il basso. 

Ti ha mostrano ragazzi il fresco effetto sonoro di ordinamento video? È un po 'freddo. Quindi, come ha appena detto Robert, l'algoritmo che hai appena passo attraverso la lista, scambiando i valori adiacenti se non sono in ordine. E poi basta continuare a ripetere fino a quando non si effettuano operazioni di swap. Quindi non male, vero? Quindi non ci resta che un esempio veloce qui. Quindi questo sta per ordinare li in ordine crescente. Così, quando andiamo attraverso il primo tempo, guardiamo attraverso otto e sei non sono ovviamente in ordine, li scambiamo. 

Così guardare il prossimo. Otto e quattro non in ordine. Scambiarli. E poi otto e due, li scambiano. Ci andiamo. Così, dopo il primo passaggio, si sapere che il maggior numero sta per essere fino in fondo in alto perché è solo sta per essere costantemente più grande di tutto il resto ed è solo andando a bolla up fino alla fine lì. Non che abbia un senso per tutti? Freddo. 

Allora guardiamo al nostro secondo passaggio. Sei e quattro, l'interruttore. Sei e due, l'interruttore. E ora abbiamo un paio di cose in ordine. Quindi per ogni passo che abbiamo fare attraverso tutta la nostra lista, sappiamo che, come che molti numeri alla fine saranno state filtrate. Quindi facciamo un terzo passaggio, che è uno scambio. E poi il nostro quarto passare, abbiamo a zero slot. E così sappiamo che il nostro array è stato ordinato. 

E questo è il grande cosa con bubble sort. Sappiamo che quando abbiamo avere zero swap, che significa che tutto è in modo completo. È un po 'come controlliamo. Così stiamo anche andando a codificare bolla che tipo, inoltre, non è poi così male. Nessuno di questi sono così male. So che può sembrare un po 'paura. So che quando ho preso la classe, anche quando insegnava la classe per la prima volta lo scorso anno, Ero come, come posso fare questo? Ha senso in teoria, ma come possiamo effettivamente fare questo? È per questo che voglio anche andare a piedi tramite il codice con voi qui. Così ho un pseudocodice per voi ragazzi questa volta. Quindi basta tenere questo in mente come stiamo per passare oltre. Così abbiamo un po 'di contatore che tiene traccia dei nostri swap, perché abbiamo bisogno di fare in modo che stiamo controllando che. E iteriamo l'intero array come abbiamo appena fatto con questo esempio. Se l'elemento prima è maggiore l'elemento dopo dove siamo, noi li scambiamo e incrementiamo il nostro contatore perché non appena ci scambiamo, vogliamo lasciare il nostro contatore sapere che. Tutte le domande lì? Qualcosa sembra divertente qui. STUDENTE: Avete impostato il contatore a zero ogni volta che si passa attraverso il ciclo? Non andare avanti torna a zero ogni volta? ISTRUTTORE: Non necessariamente. Quindi, quello che succede è che andiamo di qui. Quindi fare mentre, ricordate, questo sarà eseguita una volta a colpo sicuro. Così sta andando a impostare la controvalore pari a zero, allora sta andando a scorrere. Mentre esegue un'iterazione, verrà aggiornato contatore. Come si aggiorna il contatore, quando è fatto, quando viene raggiunta la fine dell'array, se il nostro elenco non è stato ordinato, contatore sono stati aggiornati. 

Ecco che allora si verifica la condizione e dice, OK, è contatore maggiore di zero. Se lo è, farlo di nuovo. Si desidera ripristinare in modo che quando si passare attraverso, contatore è uguale a zero. Se si passa attraverso un ordinato array, non cambia nulla, questo non riesce e viene restituisce la lista ordinata. Fa questo ha un senso? STUDENTE: Potrebbe in un po '. ISTRUTTORE: OK. Se c'è un altro domanda che viene in su. Sì. 

STUDENTE: Cosa sarebbe la funzione essere per scambiare gli elementi? 

ISTRUTTORE: Così possiamo effettivamente scrivere che se stiamo andando in questo momento. Freddo. Quindi, su questa nota, Alison sta andando per tornare alla macchina. Sta andando essere divertente. E noi abbiamo la nostra bella bubble sort cosa qui. Così ho già fatto in bicicletta attraverso l'array. Abbiamo i nostri swap che sono uguali a zero. Quindi vogliamo scambiare adiacente elementi se sono fuori uso. Quindi la prima cosa abbiamo bisogno di non è scorrere la nostra gamma. 

Quindi, come si fa a pensare che potrebbe scorrere la nostra gamma? Abbiamo per e i è uguale a 0. Vogliamo i per essere meno di n meno 1 meno k. E ti spiego che in un secondo. Quindi si tratta di una ottimizzazione qui dove, ricordare come ho detto dopo ogni passaggio attraverso la matrice di noi sapere che tutto ciò che è on-- 

Così, dopo un passaggio che so che questo è ordinato. Dopo due passaggi che conosciamo che tutto questo è ordinato. Dopo tre passaggi siamo sanno che è ordinato. Quindi il modo in cui sto iterazione attraverso la matrice qui è vero è fare in modo di andare solo attraverso quello che sappiamo è indifferenziati. Ok? Questo è solo una ottimizzazione. Si potrebbe scrivere ingenuamente solo l'iterazione attraverso tutto ciò, sarebbe solo necessario più tempo. Con questo ciclo di quattro è solo una bella ottimizzazione perché sappiamo che dopo ogni pieno un'iterazione attraverso l'array qui, come ogni ciclo completo qui, sappiamo che uno più di questi elementi sarà filtrate alla fine. 

Quindi non dobbiamo preoccuparci di quelli. Non che abbia un senso per tutti? Questo piccolo trucco fresco? Quindi, in questo caso, se stiamo scorrendo, sappiamo che vogliamo verificare se matrice n ed n + 1 sono in ordine. Ok. Quindi, ecco la pseudocodice. Vogliamo verificare se array di n ed n + 1 sono in ordine. Che cosa potremmo fare lì? Sta andando essere qualche condizionale. Sarà un caso. 

STUDENTE: Se array di n è meno di array di n + 1. ISTRUTTORE: Mm-hm. Ebbene, inferiore o superiore. STUDENTE: Maggiore di. Poi vogliamo scambiarle. Esattamente. Così ora arriviamo in quello che è il meccanismo per lo scambio di loro? Così siamo andati attraverso questo breve, un tipo di funzione swap scorsa settimana. Qualcuno ricorda come funzionava? Quindi noi non possiamo semplicemente riassegnare, giusto? Perché uno di loro andranno persi. Se abbiamo detto A è uguale a B e poi B è uguale ad A, tutto ad un tratto entrambi sono solo pari a B. 

Quindi quello che dobbiamo fare è che avere una variabile temporanea che è intenzione di tenere uno dei nostri, mentre siamo nel processo di scambio. Quindi ciò che abbiamo è che avremo un po 'di int temperatura è uguale a-- è possibile assegnarlo a seconda di quale quello che si desidera, basta assicuratevi di tenere traccia di it-- quindi in questo caso, ho intenzione di assegnarlo a matrice n + 1. In modo che sta andando a tenere tutto ciò che valore è in questo secondo blocco che stiamo guardando. 

E allora che possiamo fare è che possiamo andare avanti e serie Riassegna n + 1, perché sappiamo che avere quel valore memorizzato. Questo è anche uno dei grandi things-- Non so se qualcuno di voi avuto problemi in cui se si passa a due righe di codice improvvisamente le cose funzionavano. L'ordine è molto importante in CS. Quindi assicuratevi di diagramma le cose, se possibile, su ciò che sta realmente accadendo. Così ora stiamo andando a riassegnare array di n + 1, perché sappiamo che avere quel valore memorizzato. 

E possiamo assegnare tale a matrice n o in questo caso matrice i. Troppe variabili. Ok. Matrice Così ora abbiamo riassegnato i più 1 per eguagliare ciò che è in serie i. Ed ora possiamo tornare indietro e assegnare serie i per che cosa? Chiunque? 

STUDENTE: 10. 

ISTRUTTORE: 10. Esattamente. E un'ultima cosa. Se abbiamo scambiato ora, che cosa dobbiamo fare? Qual è l'unica cosa che sta per dirci se mai terminiamo questo programma? Che cosa ci dice che noi avere una lista ordinata? Se non si esegue alcuna swap, giusto? Se swap è pari a azzerare alla fine di questo. Così ogni volta che si esegue uno swap, come noi appena fatto qui, vogliamo aggiornare swap. E so che c'è stato un domanda precedente riguardo anche voi utilizzare zero o uno invece di vero o falso. Ed è quello che fa qui. Quindi questo dice che se non swap. Quindi, se swap è pari a zero, che è-- ho sempre mettere le verità ei miei falses mescolati. Vogliamo di valutare di vero e non lo è. Quindi, se è pari a zero, allora è falso. Se si nega con un [? Bang?] diventa vero. Allora questa linea esegue. 

Verità e falsi e zero e uno impazzire. Solo se si cammina lentamente attraverso di essa sarà un senso. Ma questo è ciò che questo piccolo pezzo di codice qui fa. Quindi questa verifica abbiamo fatto nessuna swap. Quindi, se si tratta di qualche cosa oltre pari a zero, che sta per essere falso e il tutto è andando a eseguire di nuovo. Cool? 

STUDENTE: Cosa pausa fare? 

ISTRUTTORE: Rompere solo si rompe fuori dal giro. Quindi in questo caso sarebbe proprio come terminare il programma e si farebbe solo avere la vostra lista ordinata. STUDENTE: Amazing. ISTRUTTORE: Mi dispiace? STUDENTE: Perché in precedenza abbiamo usato 1 scritto sopra scritto a zero presentare che se che funzionerà o meno. 

ISTRUTTORE: Sì. Così si può tornare a zero o 1. In questo caso, perché non siamo in realtà di fare qualsiasi cosa con la funzione, vogliamo solo la rottura. Noi in realtà non importa a questo proposito. Freno è anche un bene se è utilizzato per scoppiare di quattro loop o condizioni che non si desidera mantenere in esecuzione. Ci vogliono appena fuori di essi. E 'un po' di una cosa sfumatura. Mi sento come se ci fosse un sacco di mano d'ondeggiamento, come imparerete a conoscere questo presto. 

Ma imparerete a conoscere questo presto. Prometto. Ok. Quindi non tutti ottenere bubble sort? Non troppo male. Scorrere, le cose di swap usando un variabile TEMP, e stiamo tutti insieme lì? Freddo. Impressionante. Ok. Torna all'inizio PowerPoint. Tutte le domande in generale su queste fino ad ora? Freddo. Mm-hm. 

STUDENTE: [incomprensibile] int main solito. Non si deve avere che per questo? 

ISTRUTTORE: Così ci eravamo solo in cerca proprio sull'algoritmo ordinamento. Se tu avessi entro come un programma più ampio, si avrebbe un qualche luogo principale int. A seconda di dove si utilizzare questo algoritmo, sarebbe determinare ciò che è essere restituito da esso. Ma per il nostro caso, noi siamo strettamente guardando come fa questo in realtà scorrere un array. Quindi non ti preoccupare. 

Così stavamo parlando migliore dei casi e scenari peggiori per la ricerca binaria. Quindi è anche importante fare che per ciascuno dei nostri sorta. Allora, cosa pensi sia il peggiore caso di esecuzione di bubble sort? Voi ragazzi ricordate? 

STUDENTE: N meno 1. ISTRUTTORE: N meno 1. In modo che significa che ci sono n meno 1 confronti. Quindi, una cosa da capire è che alla prima iterazione, attraversiamo, mettiamo a confronto questi two-- così che è 1. Questi due, tre, quattro. Così, dopo una iterazione che già quattro i confronti. Quando sto parlando di runtime e n. N rappresenta il numero di confronti in funzione di quanti elementi abbiamo. Ok? 

Quindi attraversiamo, abbiamo quattro. La prossima volta che sai che non lo facciamo devono prendersi cura di questo. Confrontiamo questi due, questi due, questi due, e se non abbiamo avuto che l'ottimizzazione con i quattro loop che ho scritto, si sarebbe confrontando qui comunque. Quindi, si dovrebbe correre attraverso la matrice e fare paragoni n n volte, perché ogni volta che correre attraverso di essa noi ordiniamo una cosa. 

E ogni volta si corre attraverso l'array, facciamo paragoni n. Così il nostro tempo di esecuzione di questo è realtà n al quadrato, che è molto peggio nel nostro log fine perché significa che se avessimo quattro miliardi di elementi, è andando a prendere noi quattro miliardi quadrato invece di 32. Quindi non il migliore tempo di esecuzione, ma per alcune cose, sai, se sei all'interno di una certa gamma di elementi bubble sort può andare bene per l'uso. 

Ok. Così ora che cosa è il miglior runtime caso? STUDENTE: Zero? O 1? 

ISTRUTTORE: 1 Così sarebbe uno confronto. Destra. 

STUDENTE: N meno 1? 

ISTRUTTORE: Quindi, sì. Quindi n meno 1. Ogni volta che avete un concetto come n meno 1, tendiamo a cadere appena fuori e abbiamo solo dire n perché avete per confrontare ciascuna di these-- ogni coppia. Quindi sarebbe n meno 1, il quale avevamo appena diciamo è di circa n. Quando hai a che fare con il tempo di esecuzione, tutto è in armonizza. Fintanto che l'esponente è corretto, sei abbastanza bravo. 

È così che abbiamo a che fare con esso. In modo che il caso migliore è n, che significa che l'elenco è già ordinato, e tutto quello che facciamo è gestito attraverso e verificare che sia risolto. Freddo. Bene. Quindi, come vedete qui, noi basta avere più grafici. Quindi n al quadrato. Fun. Molto peggio di n come si vede, e molto, molto peggio di registro 2n. E poi si arriva anche in log logs. E si prende 124, si entra in come stella di registro, che è come un matto. Quindi, se siete interessati, stella di log di ricerca. E 'una specie di divertimento. Così abbiamo questa grande tabella. Solo un testa a testa, questo un meraviglioso grafico di avere per il medio termine perché noi a lungo per chiedere a voi queste si assottiglia. Quindi, solo un testa a testa, hanno questo sul tuo a medio termine sul foglietto bello Là. Così abbiamo appena guardato bubble sort. Nel peggiore dei casi, n squadrato, migliore dei casi, n. E stiamo andando a guardare gli altri. 

E come si può vedere, l'unico uno che fa davvero bene è merge sort, di cui parleremo in perché. Quindi stiamo per andare al prossimo qui-- selection sort. Qualcuno ricorda come selezione lavorato genere? Andare per esso. 

STUDENTE: Fondamentalmente passare attraverso un ordine e creare un nuovo elenco. E come si sta mettendo elementi in, metterli al posto giusto nel nuovo elenco. 

ISTRUTTORE: In modo che i suoni più come insertion sort. Ma sei davvero vicino. Sono molto simili. Anche io confonderle volte. Prima di questa sezione ho pensato, aspetta. Ok. Quindi, ciò che si vuole fare è ordinamento per selezione, il modo in cui si può pensare su di esso e il modo Mi assicuro che non cercare di ottenere li confondono, è passa attraverso e seleziona il minor numero e mette che all'inizio della vostra lista. Si scambia con quel primo posto. In realtà sono un esempio per me. Impressionante. Quindi, solo un modo di pensare di selezione it-- Ordina, selezionare il valore più piccolo. E stiamo andando a correre attraverso un esempio che penso aiuterà perché Penso immagini aiutano sempre. Quindi si parte con qualcosa che è completamente indifferenziati. Red sarà indifferenziati, verde verrà ordinata. Sarà tutto un senso in un secondo. 

Quindi attraversiamo e iteriamo dall'inizio alla fine. E noi diciamo, OK, 2 è il nostro numero più piccolo. Quindi stiamo andando a prendere 2 e stiamo andando per spostarlo verso la parte anteriore della nostra matrice perché è il numero più piccolo che abbiamo. Ecco, questo è ciò che questo sta facendo qui. E 'solo andando a scambiare quei due. Così ora abbiamo un ordinato parte e una parte non ordinato. E ciò che è bene ricordare su ordinamento per selezione è che stiamo selezionando solo dalla parte non differenziati. 

La parte che avete appena ordinato lasciano in pace. Mm-hm? 

STUDENTE: Come fa a sapere che cosa è il più piccolo senza confrontarlo ad ogni altro valore nella matrice. ISTRUTTORE: Lo fa confrontarlo. Ci piace saltato. Questo è solo generale complessiva. Sì. Quando si scrive il codice sono sicuro che sarete più soddisfatti. Ma si memorizza questa prima elemento come il più piccolo. Si confrontano e si dire, OK, è più piccolo? Sì. Keep it. Qui è più piccolo? No? 

Questo è il tuo più piccolo, riassegnare al tuo valore. E sarai molto più felice quando andiamo attraverso il codice. Quindi attraversiamo, ci scambiamo, così poi guardiamo a questa parte non differenziati. Quindi stiamo andando a selezionare tre su. Stiamo andando a metterlo su a la fine della nostra porzione ordinato. E stiamo solo andando a continuare a fare che, facendo questo, e farlo. Quindi questo è il nostro tipo di pseudocodice qui. Ci codice che esso qui in un secondo. Ma solo qualcosa a camminare attraverso su un livello alto. Hai intenzione di andare da i uguale a 0 per n meno 2. Questo è un altro di ottimizzazione. Non preoccupatevi troppo su di esso. Quindi, come dicevi tu. Come Jacob stava dicendo, come facciamo tenere traccia di ciò che il nostro minimo è? Come facciamo a saperlo? Dobbiamo confrontare tutto nella nostra lista. 

Così minima equivale i. E 'solo che in questo caso l'indice del nostro valore minimo. Allora sta andando a scorrere e va da j è pari a i + 1. Quindi sappiamo già che questo è il nostro primo elemento. Non abbiamo bisogno di confrontarlo con se stesso. Così cominciamo a confronto con il prossimo quello che è il motivo per cui è i più 1 per n meno 1, che è il fine dell'array lì. E abbiamo detto in caso di array a j è minore di matrice min, poi riassegnare dove i nostri indici minimi è. 

E se min è diverso da i, come in cui siamo tornati qui. Così come quando abbiamo fatto questo. In questo caso, sarebbe cominciare zero, finirebbe per essere due. Così min non sarebbe uguale i alla fine. Che ci fa sapere che abbiamo bisogno di scambiarle. Mi sento come un esempio concreto aiuterà molto più di questo. Quindi io questo codice con voi ragazzi in questo momento e penso che sarà meglio. 

Tipo tende a lavorare in questo modo in quanto spesso è meglio solo per vedere loro. Quindi, quello che vogliamo fare è per prima cosa vogliamo che il più piccolo elemento nella propria posizione nella matrice. Esattamente quello che Jacob stava dicendo. Hai bisogno di memorizzare che in qualche modo. Quindi stiamo andando a iniziare da qui iterare su l'array. Stiamo andando a dire che è il nostro prima solo per cominciare. Quindi, stiamo andando ad avere int più piccolo è uguale a matrice a i. 

Quindi una cosa da notare, ogni volta che questo ciclo viene eseguito, stiamo iniziando un passo più avanti. Quando cominciamo guardiamo questo. La prossima volta che iterare, stiamo iniziando a questo e assegnandogli il nostro valore più piccolo. Quindi è molto simile a bubble sort dove sappiamo che dopo un passaggio, quest'ultimo elemento è ordinato. Con ordinamento per selezione, è esattamente l'opposto. 

Ad ogni passo, sappiamo che il primo è ordinato. Dopo il secondo passaggio, la secondo verrà ordinata. E come avete visto con gli esempi di scorrimento, la nostra porzione ordinati continua a crescere. Quindi, impostando il nostro unico piccolo agli array i, tutto quello che sta facendo è costrizione cosa stiamo guardando in modo da ridurre al minimo il numero di confronti che facciamo. Questo fa senso per tutti? Avete bisogno di me per correre attraverso quella ancora più lento o con parole diverse? Sono felice di. Ok. 

Quindi stiamo memorizzare il Valore a questo punto, ma vogliamo anche memorizzare l'indice. Quindi stiamo andando a memorizzare il posizione del più piccolo uno, che è solo sarà i. Così ora Jacob è soddisfatto. Abbiamo cose memorizzati. E ora abbiamo bisogno di guardare attraverso la parte non ordinata dell'array. Quindi in questo caso questa sarebbe la nostra indifferenziati. Questo è i. Ok. 

Così che cosa stiamo andando a fare sta per essere per un ciclo. Ogni volta che avete bisogno di scorrere un array, la tua mente potrebbe andare in per un ciclo. Così, per un po 'int k equals-- cosa pensiamo k sta per essere uguale per iniziare? Questo è ciò che abbiamo impostato come il nostro più piccolo valore e vogliamo confrontarlo. Quello che vogliamo confrontarlo con? E sarà questo prossimo, giusto? Quindi vogliamo k da inizializzare per i più 1 per iniziare. 

E vogliamo k in questo caso si già ha formato accumulato qui, in modo che possiamo semplicemente usare dimensioni. Dimensione è la dimensione della matrice. E vogliamo solo aggiornare k di uno ogni volta. Freddo. Così ora abbiamo bisogno di trovare il più piccolo elemento qui. Quindi, se iterare, abbiamo voglio dire, se a matrice k è inferiore al nostro piccolo value-- è qui che siamo in realtà tenere traccia di ciò che è il più piccolo qui-- poi si vuole riassegnare qual è il nostro valore più piccolo è. 

Ciò significa che, oh, siamo scorrendo qui. Qualunque sia il valore è qui è non la nostra più piccola cosa. Noi non lo vogliamo. Vogliamo riassegnare esso. Quindi, se siamo riassegnandolo, che cosa fare si pensa possa essere in questo codice qui? Vogliamo riassegnare più piccolo e la posizione. Così che cosa è più piccolo ora? STUDENTE: Array k. ISTRUTTORE: Array k. E qual è la posizione in questo momento? Cosa c'è di indici di il nostro valore più piccolo? E 'solo k. Così matrice k, k, si corrispondono. Così abbiamo deciso di riassegnare tale. E poi dopo abbiamo trovato il nostro piccolo, così alla fine di questo ciclo for qui abbiamo trovato ciò che il nostro più piccolo valore è, quindi abbiamo appena scambiare esso. In questo caso, come dire che la nostra valore più piccolo è qui. Questo è il nostro valore più piccolo. 

Vogliamo solo scambiarlo qui, che è cosa che funzione swap sul fondo fatto, che abbiamo appena scritto su insieme un paio di minuti fa. Così dovrebbe essere familiare. E allora sarà solo scorrere attraverso fino a raggiungere fino alla fine, il che significa che si avere zero elementi che sono indifferenziati e tutto il resto è stato risolto. Dare un senso? Un po 'più concretamente? La guida in codice? 

STUDENTE: Per una dimensione, non hai mai davvero definirlo o modificarlo, come fa a sapere? 

ISTRUTTORE: Quindi una cosa da notare qui è la dimensione int. Quindi stiamo dicendo in questo tipo sort-- è una funzione in questo case-- è ordinamento per selezione, è passato con la funzione. Quindi, se non è stato passato in, si dovrebbe fare qualcosa come con la lunghezza della matrice o si dovrebbe scorrere per trovare la lunghezza. Ma perché è passato in, possiamo semplicemente usare. Basta dare per scontato che l'utente ti ha dato una dimensione valida che in realtà rappresenta una dimensione dell'array. Cool? 

Se voi ragazzi avete problemi con questi o vuole più pratica di codifica tipo da soli, si dovrebbe andare a study.cs50. Si tratta di uno strumento. Hanno un controllo che si può effettivamente scrivere. Fanno pseudocodice. Hanno altri video e diapositive compresi quelli che uso qui. Quindi, se siete ancora sentire un po 'confuso, provare che fuori. Come sempre, venire a parlare con me, anche. Domanda? 

Studente: Stai dicendo che il dimensione viene definita in precedenza? ISTRUTTORE: Sì. Il formato è definito in precedenza su qui nella dichiarazione di funzione. Quindi si assume che è stato approvato nel dall'utente, e per semplicità, stiamo andando a supporre che la utente ci ha dato la dimensione corretta. Freddo. Ecco, questo è l'ordinamento per selezione. Ragazzi, so che stiamo imparando molto oggi. E 'un dato denso per la sezione. Quindi, con questo, stiamo andando per andare a insertion sort. 

Ok. Quindi, prima che dobbiamo fare la nostra analisi runtime qui. Quindi, nel migliore dei casi, concesso da quando ti ho mostrato il tavolo ho già tipo di dato via. Ma meglio runtime caso, cosa pensiamo? Tutto risolto. N al quadrato. Qualcuno ha una spiegazione per il motivo per cui si pensa? 

STUDENTE: si sta confrontando through-- ISTRUTTORE: Giusto. Si sta confrontando con. Ad ogni iterazione, pur siamo decrementare questo per uno, siete ancora alla ricerca attraverso tutto per trovare il più piccolo. Quindi, anche se il valore più piccolo è qui all'inizio, si sta ancora confrontandolo contro tutto il resto per assicurarsi che sia la più piccola cosa. Così si finirà che attraversa circa n volte quadrato. Bene. E qual è il caso peggiore? Anche n al quadrato perché si sta andando di fare la stessa procedura. Quindi, in questo caso, la selezione ha qualcosa tipo che anche noi chiamiamo tempo di esecuzione previsto. Quindi, in altri, sappiamo solo i limiti superiore e inferiore. A seconda di come il nostro pazzo lista è o come misti sia, variano tra n oppure n squadrato. Non lo sappiamo. 

Ma perché ordinamento per selezione ha lo stesso peggiore e migliore dei casi, che ci dice che non importa quale tipo di input che hanno, che si tratti di tutto ordinati o completamente invertire ordinato, è andando a prendere la stessa quantità di tempo. Quindi, in questo caso, se si ricordare dal nostro tavolo, in realtà aveva un valore che questi due tipi non hanno, che è tempo di esecuzione previsto. Così sappiamo che ogni volta che corriamo ordinamento per selezione, è garantito per eseguire un tempo n al quadrato. Non c'è variabilità lì. E 'solo previsto. E, ancora una volta, se si vuole imparare più, prendere CS 124 in primavera. Bene. Abbiamo visto questo. Freddo. Sorta così l'inserimento. E sto probabilmente andando a tracciare attraverso questo. Non voglio che voi ragazzi codificarlo. Cose da fare solo a piedi attraverso di essa. Così insertion sort è una specie di simile a selection sort in che abbiamo sia un non ordinato e filtrate parte della matrice. 

Ma cosa c'è di diverso è che come andiamo attraverso uno per uno, dobbiamo solo prendere qualunque sia il numero è il prossimo nella nostra indifferenziati, e correttamente risolvere la nel nostro array ordinato. Sarà più senso con un esempio. Quindi, tutto ciò che inizia come indifferenziati, Proprio come con selection sort. E abbiamo intenzione di risolvere la questione in ordine crescente come siamo stati. Così il nostro primo passaggio prendiamo il primo valore e si dice, OK, tu sei ora in un elenco da solo. 

Perché ci si trova in un elenco da soli, si sono allineati. Complimenti per essere il primo elemento di questa matrice. Sei già ordinato tutto da solo. Così ora abbiamo un ordinato e un array non ordinato. Così ora si prende la prima. Cosa succede tra qui e qui è che noi diciamo, OK, stiamo andando a guardare il primo valore della nostra serie non ordinata e abbiamo intenzione di inserire nel suo posto giusto nel array ordinato. 

Quindi, quello che facciamo è prendiamo 5 e si dice, OK, 5 è maggiore di 3, così abbiamo appena inseriamo giusto a destra di quello. Siamo a posto. Allora andiamo al nostro prossimo. E prendiamo 2. Diciamo, OK, 2 è meno di 3, quindi sappiamo che deve essere al di fronte alla nostra lista ora. Quindi, quello che facciamo è spingiamo 3 e 5 verso il basso e ci muoviamo 2 in quel primo slot. Quindi stiamo solo inserendolo in il posto giusto dovrebbe essere. 

Poi guardiamo al nostro prossimo, e diciamo 6. OK, 6 è maggiore di tutto quanto in nostro array ordinato, quindi abbiamo il tag fino alla fine. E poi guardiamo 4. 4 è inferiore a 6, è meno al 5 ma è superiore a 3. Così abbiamo appena inseriamo a destra in mezzo tra 3 e 5. Quindi, per fare che un po ' po 'più concreto, qui è una specie di idea di quello che è successo. Quindi, per ogni elemento indifferenziato, abbiamo determinare dove nella porzione ordinata esso è. 

Quindi, tenendo conto della ordinato e non ordinato, dobbiamo attraversare attraverso e figura dove si inserisce nel vettore ordinato. E lo inseriamo spostando il elementi a destra giù. E poi dobbiamo solo continuare scorrendo fino a quando non avere una lista del tutto ordinato dove indifferenziati è ora pari a zero e ordinato riprende il totalità della nostra lista. Quindi, ancora una volta, per rendere le cose ancora più concreto, abbiamo pseudocodice. 

Quindi, in pratica per i è uguale a 0 a n meno 1, questo è solo la lunghezza del nostro array. Abbiamo qualche elemento che è uguale a il primo array oi primi indici. Abbiamo impostato j uguale a quello. Così, mentre j è maggiore zero e la matrice, j meno 1 è maggiore del elemento, così tutto quello che sta facendo è fare in modo che la tua j rappresenta davvero la porzione indifferenziati dell'array. 

Così, mentre ci sono ancora cose per ordinare e uno j meno è-- cosa è l'elemento lei? J non è mai stato definito qui. È un po 'fastidioso. Ok. In ogni modo. Così j meno 1, si sta controllando l'elemento prima. Stai dicendo che, OK, è l'elemento prima che ovunque io am-- cerchiamo di in realtà disegnare questo fuori. Quindi diciamo che questo è come il nostro secondo passaggio. Così ho sta per essere uguale a 1, che è qui. 

Così ho sta per essere uguale a 1. Questo sarebbe 2, 4, 5, 6, 7. Bene. Così il nostro elemento in questo caso sta per essere uguale a 4. E abbiamo un po 'di j che è sta per essere uguale a 1. Oh, j è decremento. Questo è quello che è. Così j è pari a i, quindi di cosa si tratta detto è che man mano che andiamo avanti, stiamo solo facendo in modo che non siamo su indicizzazione questo modo quando stiamo cercando per inserire le cose nella nostra lista ordinata. 

Così, quando j è uguale a 1 nel caso di specie e matrice j meno tra-- così serie j meno 1 è 2 in questo case-- se questo è superiore dell'elemento, allora tutto questo sta facendo si sta spostando le cose. Quindi in questo caso, matrice j meno uno sarebbe matrice zero, che è 2. 2 non è superiore a 4, quindi questo non viene eseguito. Quindi lo spostamento non si muove verso il basso. Quello che fa qui è solo spostando il vettore ordinato verso il basso. In questo caso, infatti, ci potrebbe fare-- facciamo questo 3. Quindi, se vogliamo camminare con questo esempio, siamo ora qui. Questo è ordinato. Questo è indifferenziati. Cool? Così i è uguale a 2, in modo nostro elemento è uguale a 3. E la nostra j è uguale a 2. Quindi guardiamo attraverso e noi dire, OK, è un array j meno superiore dell'elemento che stiamo guardando? E la risposta è sì, giusto? 4 è maggiore di 3 e j è 2, quindi questo codice viene eseguito. 

Così ora che cosa facciamo un array a 2, così proprio qui, li scambiano. Quindi ci limitiamo a dire, OK, matrice a 2 è ora sta per essere 3. E j sta per eguagliare j meno 1, che è 1. Questo è orribile, ma voi ragazzi l'idea. J è ora uguale a 1. E la matrice j è solo andare a essere pari al nostro elemento, che era 4. Ho cancellato qualcosa che non dovrebbe avere o miswrote qualcosa, ma voi ragazzi ottiene l'idea. 

Si muovono al n. E poi se questo fosse, sarebbe cappio di nuovo e sarebbe dire, OK, j è 1 ora. E la matrice j meno 1 ora 2. 2 è inferiore al nostro elemento? No? Questo significa che abbiamo inserito questo elemento nel punto corretto nel nostro array ordinato. Poi possiamo prendere questo e dire, OK, il nostro array ordinato è qui. E ci sarebbe voluto il numero 6 ed essere come, OK, è 6 meno di questo numero? No? Freddo. Stiamo bene. 

Fallo di nuovo. Diciamo 7. È 7 inferiore alla fine del nostro array ordinato? No. Quindi stiamo bene. Quindi questo sarebbe stato risolto. In pratica tutto questo fa si sta dicendo prendere il primo elemento di l'array non ordinato, capire dove va nel tuo array ordinato. E questo vuole solo cura di swap per farlo. Stai fondamentalmente solo scambiando fino a quando è nel posto giusto. L'immagine visiva è che sei spostando tutto dal farlo. 

Quindi è come la metà bubble sort-esque. Scopri studio 50. Consiglio vivamente di provare per codificare da soli. Se avete problemi o se si vuole vedi codice di esempio per un insertion sort, Per favore mi faccia sapere. Io sono sempre in giro. Così peggiore runtime caso e meglio runtime caso. Come ragazzo visto dalla tabella ho già si mostrò, che è sia n al quadrato e n. 

Così gentile di andare fuori di ciò che abbiamo parlato in giro con i nostri tipi precedenti, peggiore runtime caso è che se è completamente non ordinato, dobbiamo confrontare tutti questi n volte. Facciamo un sacco di confronti perché se è in ordine inverso, stiamo andando a dire, OK, questo è la stessa, questo è buono, e questo dovrà essere confrontato contro il primo ad essere spostato indietro. E come abbiamo più verso la coda, abbiamo per confrontare, confrontare, e confrontare contro tutto. 

Così si finisce per essere circa n al quadrato. Se è corretto, allora si dice, OK, 2, sei bravo. 3, il gioco è rispetto a 2. Sei bravo. 4, si confronta solo alla coda. Sei bravo. 6, confrontare fino alla coda, che stai bene. Così, per ogni punto se è già ordinati, si sta facendo un confronto. Quindi è solo n. E perché abbiamo un migliore runtime caso di n e un tempo di esecuzione nel caso peggiore di n quadrato, non abbiamo tempo di esecuzione previsto. 

Dipende solo sul il caos della nostra lista lì. E ancora, un'altra grafico e un altro tavolo. Quindi, le differenze tra i tipi. Sto solo andando a brezza attraverso, ho sentire come abbiamo parlato ampiamente sul modo in cui tutti i tipi di variare e collegare tra loro. Così merge sort è l'ultimo Io annoiarvi con ragazzi. Noi abbiamo un quadro abbastanza colorato. Così merge sort è un algoritmo ricorsivo. Quindi, voi ragazzi sapete cosa una funzione ricorsiva è? 

Chiunque vuole dire? Vuoi provare? Quindi una funzione ricorsiva è solo una funzione che si chiama. Quindi, se voi siete a conoscenza con la sequenza di Fibonacci, che è considerato ricorsiva perché si prende i due precedenti e aggiungerli insieme per ottenere il vostro prossimo. Così ricorsiva, penso sempre di ricorsione come come una spirale quindi siete come la spirale verso il basso in esso. Ma è solo una funzione che si chiama. 

E, in realtà, molto velocemente mi in grado di mostrare cosa che sembra. Così ricorsiva qui, se guardiamo, questo è il modo ricorsivo per riassumere su un array. Quindi tutto ciò che facciamo è abbiamo funzione di somma somma che prende una dimensione e una matrice. E se ci fate caso, le dimensioni diminuisce di uno ogni volta. E tutto ciò che fa è se x è uguale a zero-- quindi se la dimensione della matrice è uguale zero-- restituisce zero. 

In caso contrario, le somme per questo ultimo elemento della matrice, e poi prende una somma di il resto della matrice. Quindi è solo la rottura verso il basso in problemi sempre più piccoli. Per farla breve, la ricorsione, funzione che chiama se stessa. Se questo è tutto ciò che hai da questo, questo è ciò che una funzione ricorsiva è. Se si prende 51, si otterrà molto, molto confortevole con la ricorsione. E 'davvero cool. Aveva senso a come 03:00 una notte fuori. E mi sono detto, perché non ho mai usare questo? 

Così per merge sort, in fondo che cosa sta andando a fare è che è andando a rompere verso il basso e romperlo verso il basso fino a quando è solo elementi singoli. I singoli elementi sono facili da ordinare. Vediamo che. Se si dispone di un elemento, è già considerato ordinato. Quindi su un input di n elementi, se n è minore di 2, solo tornare perché questo significa è 0 o 1, come abbiamo visto. Coloro che sono considerati elementi ordinati. 

In caso contrario, rompere a metà. Ordina prima metà, ordinare la seconda metà, e poi unirli insieme. Perché si chiama merge sort. Così abbiamo qui ci risolveremo questi. Così continuiamo averli fino a quando la dimensione della matrice è 1. Così, quando si tratta di 1, abbiamo appena ritorniamo perché questo è un array ordinato, e questo è un array ordinato, e questo è un array ordinato, siamo tutti allineati. Allora quello che facciamo è che avviare la fusione insieme. 

Quindi, il modo in cui è possibile pensare fusione è basta rimuovere il più piccolo numero di ciascuna delle sub array e basta aggiungerlo alla matrice emersa. Quindi, se si guarda qui, quando abbiamo questi gruppi abbiamo 4, 6, e 1. Quando vogliamo unire questi, guardiamo a questi primi due e si dice, OK, 1 è più piccolo, va al fronte. 4 e 6, non c'è niente da confrontare a, solo Taggalo fino alla fine. 

Quando si combinano questi due, abbiamo appena prendere il più piccolo di questi due, quindi è 1. E ora prendiamo il più piccolo di questi due, quindi 2. Più piccolo di questi due, 3. Più piccolo di questi due, 4, 5, 6. Quindi, si sta solo tirando fuori questi. E perché hanno stati ordinati in precedenza, vi è solo un Confronto ogni tempo. Quindi, più codice qui, solo rappresentazione. Così si inizia a metà e si ordina di sinistra e destra e poi basta unire quelli. 

E noi non abbiamo il codice per unire proprio qui. Ma, ancora una volta, se si va su studiare 50, sarà lì. In caso contrario, venire a parlare con me se siete ancora confusi. Quindi cosa interessante qui è che migliore dei casi, caso peggiore, e tempo di esecuzione previsto sono tutti in log n, che è molto meglio di quanto abbiamo visto per il resto della nostra specie. Abbiamo visto n Squared e ciò che in realtà arrivare qui è n log n, che è grande. 

Guarda quanto migliore che è. Tale una bella curva. Tanto più efficiente. Se è mai possibile, l'uso merge sort. Essa vi consente di risparmiare tempo. Poi di nuovo, come abbiamo detto, se sei giù in questa regione più bassa, non fa che molta differenza. È possibile ottenere fino a migliaia e migliaia di ingressi, se lo desiderate un algoritmo più efficiente. E, ancora una volta, il nostro bel tavolo di tutti tipi che voi ragazzi hanno imparato oggi. 

Quindi io so che è stata una giornata densa. Questo non è necessariamente andare per aiutarvi con il vostro pset. Ma io voglio solo fare una dichiarazione di non responsabilità che la sezione non è solo p-set. Tutto questo materiale è giusto gioco per i vostri elezioni di medio termine. E anche se lo fai continuare con CS, questi sono fondamenti veramente importanti che si avrebbe bisogno di sapere. Così alcuni giorni saranno un po 'più di aiuto pset, ma qualche settimana sarà molto più contenuto effettivo che non può sembrare eccellente utile a voi in questo momento, ma vi prometto se si continua su sarà molto, molto utile. 

In modo che è tutto per sezione. Giù per il filo. L'ho fatto in un minuto. Ma ci si va. E avrò ciambelle o caramelle. C'è qualcuno allergico a qualsiasi cosa, a proposito? Uova e latte. Così ciambelle sono un no? Ok. Bene. No al cioccolato? Starburst. Starbursts sono buone. Ok. Stiamo per avere Starburst la prossima settimana poi. Questo è quello che vado a prendere. Voi ragazzi avete una grande settimana. Leggi il tuo spec. 

Fatemi sapere se avete domande. PSET due gradi dovrebbero essere a voi da Giovedi. Se avete domande di come mi Graded qualcosa o perché ho classificato qualcosa che il mio modo di ha, prego email me, venire a parlare con me. Sono un po 'questo pazzo settimana, ma prometto Io ancora risponderemo entro 24 ore. In modo da avere una grande settimana, tutti. Buona fortuna per il tuo pset.