ALTAVEU 1: Hola a tots! Benvingut de nou a la secció. Així que m'alegro de veure a molts de vostès, tant aquí, i tot el món que està veient en línia. Així que, com de costum enrere benvinguda. Espero que tothom hagi tingut un preciós cap de setmana, ple de descans, la relaxació. Era bell el dia d'ahir. Així que, espero que hagin gaudit de l'aire lliure. Així que per primera vegada un parell d'anuncis. Classificació. Així, la majoria de vostès han d'haver rebut una un correu electrònic de mi sobre la seva joc de paràmetres Scratch, així com la classificació de joc de paràmetres gener. Així, només un parell de coses. Assegureu-vos d'utilitzar check50 a style50. Aquests estan destinats a ser recursos per a vostès, per assegurar-se que vostè està rebent tants punts com puguis sense innecessàriament perdre'ls. Per tant, coses com l'estil són molt importants. Anem a enlairar per a això. Alguns de vostès ja tenen notat que a partir del seu joc de paràmetres. I check50 és només un manera molt fàcil d'assegurar- que en realitat estem tornant el ha de ser retornat a l'usuari, i que tot està funcionant correctament. A la segona nota, assegureu-vos que el seu pujar coses a la carpeta correcta. Em fa la vida una poc més difícil si puges joc de paràmetres 2 joc de paràmetres 1 perquè en descarregar coses, no descarrega correctament. I sé que és una mica wonky en un sistema que acostumar-se a, però simplement ser súper cura, encara que només sigui per a mi, de manera que quan vostè està rebent missatges de correu electrònic igual que 02 a.m. i estic de qualificacions. Si no causar he de mirar tot per al seu joc de paràmetres. Refredar. Sé que és d'hora, però em totalment va ser pres amb la guàrdia baixa per un assaig que és degut aquest divendres, que meus professors eren com, oh sí. Recordi, vostè té un assaig a causa divendres. Per tant, no conec a ningú li agrada pensar en els exàmens parcials, però el seu primer concurs és el 15 d'octubre, que l'octubre està començant aquesta setmana. Per tant, pot ser que sigui més aviat del que esperava és tot. Així que vostè no està tirat amb la guàrdia baixa quan Esmento secció de la setmana que ve que oh, el seu concurs la setmana que ve, vaig pensar Et donaria una mica més dels caps per amunt ara. Així que, posa el teu problema, nombre tres. Com la gent ha llegit la spec per curiositat? Okay. Ens van donar un parell. Tipus de baix de l'última setmana, però això està bé. Sé que era bell a terme. Així Break Out. Definitivament després que es fan llegir avui la seva especificació com a mínim tractar com descarregar codi de distribució i el funcionament com la primera inicial El que et pregunten a. Com que estem utilitzant codi de distribució i una biblioteca que només hem estat using-- --És només la segona vegada que hem fet aquest joc de paràmetres, coses boges poden succeir amb el seu aparell, i vostè vol trobar que terme ara front més tard. Perquè si és la nit de dijous o és Dimecres a la nit i per alguna raó el seu aparell simplement no que desitgi executar amb la biblioteca o amb la distribució codi, que els mitjans ni tan sols es pot començar a fer la codificació. Perquè no es pot comprovar per veure si funciona. Tu no podràs per veure si es compila. Vostè vol tenir cura dels principis de la setmana, quan encara em pot enviar per correu electrònic o un dels altres TFS, i que puguem aconseguir els fixats. Perquè aquestes són qüestions que deixaran de vostè de fer cap progrés real. No és com una bestiola, que vostè pot tipus de saltar sobre. Si vostè està tenint problemes amb el seu aparell o codi de distribució, vostè realment vol aconseguir que prenen tenir cura de més d'hora que tard. Així que encara que no vas a realitat començar a programar, descarregar la distribució codi, llegiu la especificació, assegureu-vos tot el que està treballant allà. D'acord? Si només es pot fer això, jo prometre la seva vida serà més fàcil. I així, vostè està probablement va per fer-ho ara mateix no? Okay. Per tant, qualsevol pregunta allà? Qualsevol coses de logística? Tothom és bo? Okay. Exempció de responsabilitat per als de que a l'habitació i en línia. Jo vaig a estar tractant de canviar entre PowerPoint en l'aparell perquè anem estar fent una mica de codi avui per la demanda popular de l'anònim enquesta suggeriment que va enviar la setmana passada. Per tant, farem una mica de codi. Així que, si vostès també volen per encendre els seus aparells, i que hauria d'haver aconseguit un correu electrònic de mi, amb un arxiu d'exemple. Si us plau, si fóssiu lliure de fer-ho. Per tant, anem a parlar de BGF, que és un depurador. Això ajudarà a vostè tipus d'esbrinar on les coses van malament en el codi. És només una manera perquè facin un pas a través del seu codi com està succeint, i ser capaç d'imprimir les variables o veure el que està succeint realment sota el capó versos seu programa només córrer, és com les falles, i vostè és com, ni idea el que acaba de succeir aquí. No sé quina és la línia que va fallar a. Jo no sé d'on va sortir malament. Així, el BGF li va a ajudar amb això. A més, si vostè decideix continuar, sí, i prendre 61, el que realment, realment ser el seu millor amic, perquè jo puc dir perquè jo estic passant per aquesta classe. Anem a mirar binari recerca, que si vostès recordin el gran exemple de llibre de telèfon espectacle de classe. Estarem implementant això, i caminant a través que una mica més, i després anem a través de quatre diferents tipus, que són de la bombolla, La selecció, inserció, i Merge. Refredar. Així, el BGF com he esmentat, és un depurador. I aquests són una espècie de la gran coses, les grans funcions o ordres que s'utilitza dins de BGF, i vaig a caminar que a través d'una demostració que en un segon. Per tant, això no és només quedarà abstracte. Vaig a tractar de fer-ho el més concret com sigui possible per a vosaltres. Per tant, trencar. Serà ja sigui descans com, algun nombre, el qual representa una línia en el seu programa, o pot nomenar una funció. Així que, si vostè diu trencar principal, s'aturarà a principal, i li permeten caminar a través d'aquesta funció. De la mateixa manera, si vostè té alguns externs funcionar com Intercanviar o Cub, que vam veure la setmana passada. Si vostè diu que trenqui un d'aquests, cada vegada que el programa que realitza, que va a esperar per tu dir-li el que ha de fer. Abans que s'acaba d'executar el que en realitat podria intervenir dins de la funció i veure el que està passant. Així, A continuació, simplement salta sobre la següent línia, va més funcions. Pas. Tots aquests són poc abstracte. Així que, jo només vaig a córrer a través d'ells, però els veuràs en ús en un segon. Entra en una funció. Així com anava dient, com amb swap, ho faria li permeten realment com si estiguessis com entrar físicament a l'interior, vostè pot ficar-se amb aquestes variables, impressió el que són, veure el que està passant. Llista literalment només imprimir el codi circumdant. Així que, si vostè s'oblida de tipus on vostè està en el seu programa, o vostè s'està preguntant el que està passant al seu voltant, això només s'ha d'imprimir un segment de com cinc o sis línies al seu voltant. Per tant, vostè pot aconseguir orientat sobre on es trobi. Imprimir alguna variable. Per tant, si vostè té la clau com a en César, que veurem. Es pot dir Clau Imprimir en qualsevol punt. Se't dirà el que el valor és tan que, potser en algun lloc al llarg del camí, ha sobreescrit la seva clau. En realitat es pot dir que pel fet que en realitat es pot observar que el valor. En els locals, només impressions terme les seves variables locals. Així, en qualsevol moment que estàs dins d'un bucle, i el que desitja és veure com, oh. Què és el meu jo? Què és aquest valor de clau que inicialitzar aquí? Quin és el missatge en aquest moment? S'acaba d'imprimir tots d'ells, de manera que vostè no tenen que individualment dir, I. Imprimir Missatge. Clau d'impressió. I després mostrar. El que fa és com vostè pas a través del programa, que va només assegureu-vos que és mostrar alguna variable determinada en cada punt. Així que vostè també- --és una mena de drecera on vostè no ha de seguir així, oh. Clau Imprimeix o I. Només automàticament ho farà per vostè. Així que, amb això, anem per veure com va això. Vaig a tractar d'interruptor al meu aparell. A veure si puc fer això. Tots. Només anem a reflectir-la. No hi ha res boig en el meu ordinador portàtil de totes maneres. Okay. Això ha de ser aquest. És tan petita. Anem a veure si podem fer això. Okay. Alice està òbviament lluitant aquí només una mica, però anem a arribar a un record. Okay. Nosaltres només anem a augmentar aquest. Okay. Tot món pot veure quin tipus de? Potser una mica? Sé que és una mica petita. No es pot esbrinar per com fer-ho més gran. Si algú sap. Algú sap com fer que sigui més gran? Okay. Anem a rodar amb ell. No importa de totes maneres perquè és només aquest és el codi que vostès haurien tenir. El que és més important és el terminal d'aquí. I tenim aquí Per què és tan petit? Ajustos. Oh. Veritable Ike. Com és això? Fora d'allà. Això és millor per a tothom? Okay,. Refredar. Ja saps, quan estàs en un CS dificultats tècniques de classe són una mena de part d'ell-- Per tant, anem a aclarir això. Okay. Així que, aquí a la secció, que hem tingut aquí. César és un arxiu executable. Així que ho vaig fer. Així, una cosa és adonar-se amb GDB és que només funciona en arxius executables. Per tant, no es pot executar en un dotsy. Vostè ha de fer realitat Comproveu que el codi es compila, i que el que realment es pot executar. Per tant, assegureu-vos que si no ho fa compilar, que es compili, perquè pugui espècie d'executar a través d'ell. Així que, per començar a GDB, tot el que fan, Glòria tipus BGF, i després simplement la fitxer que voleu. Jo sempre escriure malament César. Però vostè vol assegurar-se que ja que és un arxiu executable, flash de punt de tu de manera que vol dir que vas per a executar CSI vas a executar aquest presenta, ja sigui amb el depurador. Okay. Així que, de fer-ho, s'obté aquest tipus de galimaties. És només totes les coses sobre depurador. Segur que no ha de preocupar d'això ara. I com pots veure, tenim aquest parens obertes, PIB, prop parens, i només una mica s'assembla a la nostra línia d'ordres, oi? Per tant, el que volem fer-- --així, La primera cosa és que volem triar un lloc per trencar-lo. Per tant, hi ha un error en aquest programa de César que presento, que anem a esbrinar. És el que fa és que es necessita l'entrada Barfoo en totes les tapes, i per alguna raó no canvia A. Simplement deixa sol, és tota la resta correcte, però la segona lletra A roman sense canvis. Per tant, anem a tractar de esbrinar per què és així. Per tant, el primer que solen voler fer cada vegada que s'iniciï el BGF és esbrinar on trencar-lo. Així que César és un programa bastant curt. Només tenim una funció, no? Quina era la nostra funció en Cèsar? Només hi ha una funció, dret principal? Principal és una funció per a tots els programes. Si no va tenir Principal, podria ser una mica preocupat en aquest moment, però espero que tots hagin tingut Principal allà. Per tant, el que podem fer és que pot simplement trencar principal, així com així. Així que, es diu, a D'acord. Fixem el nostre únic punt d'interrupció allà. Així doncs, ara el que cal recordar que és del Cèsar pren un argument de línia de comandament de la dreta i nosaltres no hem fet això en qualsevol lloc encara. Per tant, el que fas és quan en realitat es va a executar el programa, qualsevol programa que vostè està que s'executa en el BGF que necessita la línia d'ordres arguments, que van a l'entrada quan comenci a executar-lo. Així que, en aquest cas, ho fem Executar amb una clau de tres. I serà realment començar. Per tant, si vostè veu aquí, tenim Si RC no és igual a 2. Així que si vostès tots tenim aquest arxiu que vaig enviar fins veuràs que això és com la primera línia de la nostra funció principal, no? És la comprovació per veure si tenim el nombre correcte d'arguments. Així que, si vostè s'està preguntant RC si és correcta, vostè pot fer alguna cosa igual Imprimir RC. RC és de dos, que és el que esperàvem, oi? Per tant, podem anar a continuació, i continuar a través d '. Per tant, tenim alguna clau allà. I podem imprimir la nostra clau per assegurar-se que és correcte. Interessant. No és exactament el que esperàvem. Així, una cosa és adonar- amb el BGF també, és que no és fins que realment colpeja A continuació, que la línia que acaba de veure és en realitat executa. Així que, en aquest cas clau no ha estat assignat encara. Per tant, és un valor clau d'escombraries que es veu a la part inferior hi ha. Negatiu $ 120-- --És de mil milions i una cosa que coses estranyes oi? No és la clau que ens esperàvem. Però si arribem a continuació, i després tractar de tecla Print, és tres. Tothom veu això? Així que, si et donen alguna cosa que vostè és com, espera. Això és completament malament, i jo no ho sé com això havia de passar, perquè tot el que vull de fer és assignar un nombre, una variable, intentar colpejar A continuació, proveu d'imprimir de nou, i veure si funciona. Com que només es va a executar i en realitat assignar alguna cosa després colpejar a Següent. Tenir sentit per a tothom? Uh huh? ALTAVEU 2: aleatòries nombres ¿què vol dir això? ALTAVEU 1: És només a l'atzar. És només escombraries. És només una cosa que el seu ordinador li assignarà a l'atzar. Refredar. Així, ara podem passar a través, i així ara tenim aquesta plana GetString text. Per tant, permetin-me presentar el que passarà quan colpegem Següent aquí. La nostra BGF tipus de desapareix, no? Això es deu a GetString ara s'està executant, oi? Així que, quan vam veure text pla és igual a GetString, parens oberts i parens, i vam arribar a continuació, que té realment executada ara. Per tant, està esperant nosaltres a l'entrada d'alguna cosa. Per tant, anem a l'entrada del nostre menjar que és el que està fallant com et vaig dir i que només diu que és acabat d'executar, que la tanca significa suport és sortir d'aquest bucle. Així, podem colpejar Següent, i ara, com estic Segur que tots coneixem de César, és a dir, ¿quina és aquesta línia va a fer. És per Int I és igual a 0, N és igual Strlen, text pla, i després I és menor que n, que, a més, més. Què és aquest llaç farà? Obriu el seu missatge. Refredar. Per tant, anem a començar a fer això. Així que, si aquesta condició coincidir, per a la nostra primera? Si es tracta d'un B, que és text pla I. pot obtenir informació sobre els nostres locals. Per tant, I és zero, i si sis, que esperem, i la nostra clau és tres. Tot el que té sentit, oi? Aquests números són tots exactament el que haurien de ser. Així, taral·lejar? ALTAVEU 3: Tinc nombres aleatoris per a la meva. ALTAVEU 1: Bé, podem check-- --ens podeu parlar sobre això en un segon. Però vostè ha de ser aconseguir això. Per tant, si tenim un capital de B per a la nostra primera, aquesta condició ha de agafar-lo, oi? Així que, si arribem a continuació, veiem que aquest cas és executar. Perquè si vostè està seguint al llarg del seu codi, aquesta línia aquí, on el text sense format que se substitueix amb aquesta aritmètica, només s'executa si el Si condició és correcta oi? BGF només es mostrarà les coses que són realment d'execució. Així que si no es compleix aquesta condició si, és només va a passar a la següent línia. D'acord? Per tant, hem de. Aquest suport significa que és tancat fora d'aquest bucle ara. Per tant, va a començar de nou. Igual que. Així, que podem obtenir informació sobre els nostres vilatans aquí, i veiem que la nostra primera carta ha canviat, oi? Ara és una E, com ha de ser. Així, podem continuar. I tenim aquesta comprovació. I aquest control hauria de funcionar, no? És A. S'ha de canviar tres cartes cap endavant. Però si et fixes, ens aconseguir alguna cosa diferent. Així que en aquest cas fins aquí, em va cridar que, pel que aquesta línia executat, que va modificar la nostra B. Però, en aquest cas aquí, hem de acaba de saltar que, i se'n va anar a la [? L Siff. ?] Així que alguna cosa està passant allà. El que vostè està dient és que, sabem que s'ha d'agafar aquí, però no ho és. Algú pot veure el que el nostre problema està en aquesta línia? És una cosa molt minut. I també es pot mirar el codi. També es line-- oblidar quina línia és en allà-- però és en el [inaudible]. Sí? ALTAVEU 4: Està en la major de pàgina si ho llegeix en el llibre. ALTAVEU 1: Exactament. Per tant, el depurador no podia dir que això, però el depurador podria aconseguir-se a una línia que sap que no està funcionant. I de vegades, quan tot més endavant en el semestre, quan vostè està tractant amb un centenar, 1 cent poques línies de codi, i que no sé on està fallant, aquesta és una gran manera de fer-ho. Així, trobem el nostre error. Vostè pot fixar-lo en el seu arxiu, i llavors vostè podria córrer de nou, i tot funcionaria perfectament. I el més important és això pot semblar, a D'acord. Sí. Refredar. Tu sabies el que estàs buscant. Per tant, vostè sabia què fer. GDB pot ser súper útil perquè vostè pot imprimir totes aquestes coses que vostè no ho faria. És molt més útil que printf. Quants de vosaltres utilitza com declaracions printf esbrinar on era un error, no? Així que, amb això, no ho fa han de seguir anant, i els agrada comentar Printf, o comentant, i esbrinar el que vostè ha d'estar imprimint. En realitat, això només li permet pas a pas, imprimir coses com que estàs passant, així, vostè pot observar com canvien en temps real, com el seu programa s'està executant. I ho fa prendre una mica mica de temps per acostumar. Jo recomanaria només tipus de ser una mica frustrat amb ell per ara. Si passa una hora sobre la la propera setmana per aprendre a utilitzar el BGF, vostè s'estalviarà tant de temps més endavant. I literalment. li diem això a la gent tots els anys, i recordo quan vaig prendre la classe, jo estava com, vaig a estar bé. No Joc de paràmetres 6 s'ha encès i que era com, jo ​​vaig a aprendre com utilitzar GDB perquè jo no ho faig saber el que està passant aquí. Així que si es pren el temps per usar-lo en programes més petits que vostè serà treballant, com treballar per alguna cosa així Visionäre, com aquest. O si vols practicar més, estic segur Jo podria arribar als programes amb errors, per depurar si desitja. Però si vostè acaba de prendre una mica de temps per arribar acostumar-se a ell, simplement jugar una estona amb ell, el que realment li servirà bé. I és realment una de aquestes coses que vostè acaba de que hagi de provar, i embrutar-se les mans amb, abans que realment ho entén. Realment només vaig entendre una vegada Vaig haver de depurar les coses amb ella, i és molt més agradable per tenir una idea de com depurar més d'hora que tard. Okay. Refredar. Sé que és una cosa així com un curs intensiu en el BGF, i sens dubte treballar a aconseguir aquests es vegin més grans per a la propera vegada. Refredar. Així que, si ens remuntem a la nostra PowerPoint. Això va a treballar? Awh. Sí. Okay. Així que, si mai necessites qualsevol els que una vegada més, hi ha la llista. Cercar Així binari, que tothom recorda el gran espectacle de David esquinça els llibres de telèfon a la meitat. Jo realment no entenc la guies telefòniques més, perquè igual que per on aconseguir els llibres de telèfon en aquests dies? Realment no ho sé. Hi binària. Algú recorda com binari treballs de recerca? Qualsevol persona en absolut? Sí? ALTAVEU 5: Saps quan ens fixem en els quals la meitat seria a, sobre la base que, i desfer-se de l'altra meitat. ALTAVEU 1 Exactament. Així, recerca binària, és una espècie de A-- --ens agrada anomenar dividir i conquerir. Per tant, el que faràs és vostè es veurà en el medi, i veuràs si coincideix el que estàs buscant. I si no ho fa, a continuació, intenta esbrinar, és que quedarà la meitat o la meitat dreta. Per tant, això podria ser si vostè està buscant en una cosa que està en ordre alfabètic, veus, oh. ¿Ve Allison abans de M? Sí. Per tant, anem a mirar a la primera meitat. O podria ser que amb els números. Qualsevol cosa que pugui comparar, pot ser ordenada. Pots utilitzar la recerca binària sobre. Per tant, algú se'n recorda d'aquest gràfic o el que és això? És la complexitat asimptòtica. Per tant, aquest gràfic només descriu el temps que et porta a resoldre un problema com s'augmenta el nombre de les coses que utilitzeu. Per tant, hem N, que és el temps lineal. Si N més de dos, que és lleugerament millor, encara creix molt ràpid. I llavors hem Login, la qual és el que considerem recerca binària. Si ens adonem, com el seu problema aconsegueix molt i molt més gran, el temps que el porta a resoldre- en realitat no augmentar molt. És com comparables aquí al principi. Ets com, OK. Qualsevol cosa que aquí no fa realment importa que un que utilitzem, però vostè aconsegueix un milió, un bilió. Vostè està tractant de trobar some-- --you're tractant de trobar una agulla en un paller. Crec que vols aquest problema. Vostè vol que aquesta complexitat, no lineal, perquè per tot el que sé que tu vas a estar buscant a través de cada agulla individual, cosa de fenc, tractant de buscar l'agulla. I això no és gaire divertit al meu entendre. M'agrada ràpid. M'agrada eficient. I com esforçats estudiants van nois són, ja saps treballar més intel·ligentment, no més difícil que el tipus, la forma en què pot compensar aquests algoritmes. Per tant, anem a caminar només a través d'un exemple ràpid. Crec que vostès han de tenir una mà en la recerca binària, però en cas que algú és una mica borrós, volen reforçar-lo, anirem a través d'un exemple aquí. Per tant, estem buscant si la matriu conté set. Per tant, el primer que fem és buscar en el medi, no? I també serà la codificació Binary Cercar en tan sols un segon. Per tant, serà divertit. Així que ens fixem en la petites matrius mitjanes març. ¿Té 3 equivalen a 7? No ho fa. Són les sis. Així que, és menys de o superior a set? Menys que. Sí. Treball nois Niça. Sento que com que hauria tenir dolços perquè voler tirar-lo als patis. És el que vaig a fer la setmana que ve. Se li mantindrà nois agut. Així, ens tirem que primera meitat, no? va ser menor que. sabem que tot en aquest costat de l'esquerra serà menys del que en realitat estem buscant. Per tant, no hi ha necessitat de prestar atenció a ella. Simplement oblidar-se'n. Així doncs, ara ens fixem en el nostre costat dret, i ens fixem en el medi d'allà, i ara és de nou. Així, 9 és-- --Tots? Més del que som buscant, oi? Per tant, anem a llançar lluny de tot a la dreta. Igual que. Ara, tot el que ens queda és un. Així, comprovem, és aquest el que estem buscant? és. Hem trobat el que volíem. Així que hem acabat. Bilineal Cercar. I si et fixes, ens tenia set entrades allà. Només ens va portar com tres vegades, però si vostè està fent com un mil milions, vostès saben la quantitat de passos que ho faria prendre si tinguéssim 4000000000 de coses? Qualsevol conjectures? És 32. 32 passos per trobar alguna cosa en una de quatre mil milions element de la matriu causa de potències de dos. Així que dos és a 32, és de quatre mil milions. Com és això una bogeria encara estàs dins de com un nombre bastant reduït de passos per trobar alguna cosa en 4000000000 d'elements. Així que en aquest sentit, estem codificarà aquest així que vostès poden en realitat tipus de veure com funciona això. Molt bé, així que vostès poden codificar. Vaig a deixar que vostès parlar una mica. Conegui a la gent que t'envolta, que és el que algú volia d'última secció. Així que arribar a conèixer a les persones que t'envolten. Parli per una estona. I tot el que vull de tu nois en aquest moment és només tractar de crear un esquema de pseudocodi. D'acord? Whoa. Tot el que vull de vostès és que ets només va a omplir en aquest cas, mentre que. Així que m'he posat aquests superior i límits inferiors que representar el començament i al final de la nostra matriu. I vostè va a realitat recórrer i descobrir el que estem fent dins d'aquest bucle while. Així que si vostè pot calcular fora-- tinc una mica allà-- quins són els casos que tenim aquí? Així que si vols esbrinar la casos, anem als Pseudocodi i després anem a realment codificar. I serà, pensar, és d'esperar que va a ser una mica més fàcil del que s'esperava. Perquè no és que molt codi, en realitat, el que és realment genial. Mm-hm? ESTUDIANT: [inaudible]? INSTRUCTOR: Sí. Hi havia alguna cosa per trobar al medi. ESTUDIANT: Així que podem utilitzar això. Okay. INSTRUCTOR: Perfecte. Així que això és el primer que hem de fer. Així que trobar el mitjà. Gran. Així que tens una idea de com podríem en realitat trobar el centre amb codi? ESTUDIANT: Sí. n més de 2? PROFESSOR: Llavors n sobre 2. Així que una cosa a recordar és que els seus límits superior i inferior canvien. Seguim la constricció de la part de la matriu que estem buscant per. Així que n més de 2 només funcionarà per a la primera cosa que fem. Així que tenint superiors i inferiors en compte, ¿Com podem aconseguir que l'element mitjà? Perquè volem que el medi entre superior i inferior, a la dreta? Mm-hm? ESTUDIANT: [inaudible]. INSTRUCTOR: Així que tenim algun mitjà. I que serà superior, més baix en 2. Impressionant. Cal anar. Una línia cap avall. Vostès estan en el seu camí. Així que ara que tenim el nostre mitjà, què és el que volem fer? Just en general. No ha de codificar. Sí. ESTUDIANT: [inaudible]? INSTRUCTOR: Així que és més perquè ets trobar la mitjana entre els dos d'ells. Així que si vostè pensa en ells com a espècie d'augmentar des dels costats, pensar-hi quan s'aproxima el medi, que vol així. Així que si anés a cada costat de la mitjà, i tenim com 5 i 7. Quan s'agreguen junts obtenir 12, es divideix per 2, és de 6. A vegades és difícil explicar per què funciona, però si vostè treballa a través de un exemple de vegades, que ajudarà a determinar si hauria de ser més o menys. Sí. ESTUDIANT: [inaudible] exactament en el centre si tenien un cas en el qual hi ha una gran quantitat de nombres més petits i de la mateixa manera que un nombre gran? INSTRUCTOR: Així que tot el que necessita és el centre de la matriu. Així que si vostè tenia un munt de nombres petits i llavors un realment gran nombre al final, no importa. Tot el que importa és que que estan ordenats, només que desitgi veure en el centre de la matriu perquè ets encara tallant el seu problema a la meitat. Refredar. Així que ara que tenim la mitjà, què fem després? ESTUDIANT: Comparar. INSTRUCTOR: Comparar. Així que comparar a mig value_wanted. Refredar. Així que ja veus aquí dalt tenim aquest valor que volem aquí. Recordeu que aquest és un array. Així mitjà fa a l'índex. Així que volem fer valors de mitjana. No oblidis que si vols per comparar, dobles iguals. Vostè l'únic és igual que estiguis només va a reassignar, i després, per descomptat, és serà el paràmetre que voleu. Així que no facis això. Així que anem a veure si els valors en el medi és igual al valor que volem. No oblideu els vostres claus. Dropbox ha de desaparèixer. Així que, què fem en aquest cas? Si es tracta del que volem per tornar? Estem tractant de dir. ESTUDIANT: Imprimiu. INSTRUCTOR: Bé, no volen imprimir. Així que aquest és un bool aquí, així que volen tornar vertader o fals. Estem dient, és aquest número 1 [? RRA? ?] Així que si ho és, simplement tornem veritat. Si puc lletrejar cert. ESTUDIANT: Per què no li tornarà a zero? INSTRUCTOR: pel que podria tornar a zero si volies. Però en aquest cas perquè la nostra funció retorna un bool, hem de tornar, ja sigui vertadera o falsa. ESTUDIANT: Quan estàs dient expressió booleana, pots configurar igual a falsa? Igual que si vull dir, si aquesta condició no es compleix, de la mateixa manera que és superior és igual a falsa. ¿Va a entendre si només posar falsa a l'altra banda? INSTRUCTOR: Sí. Així que en realitat si estàs sempre fent alguna cosa com és superior o és menor, que retorna cert o fals i en realitat és un mal estil de per exemple igual a igual a veritable o iguals és igual a falsa. Vostè vol utilitzar aquest resultat com a si mateix com el seu xec. No era el que jo volia. Això és el que jo volia. Així que en el cas que vostè està demanant sobre alguna cosa així com guardar això en c. Així que si tenim int main (void) i alguna cosa com això. I vostè té si és superior d'alguna entrada i ja està preguntant si es pot fer alguna cosa com això? Dreta? ESTUDIANT: Jo estava tractant per fer-ho [inaudible]. Perquè si és-- INSTRUCTOR: Dret. ¿Així que vols que això és fals, no? ESTUDIANT: Sí. INSTRUCTOR: Així que en aquest cas vol que s'executa si no és veritat. Així que la cosa fresca que fas no és això. Així que recordi d'exclamació punt nega coses? Diu [inaudible] no vol dir. Així que si ens fixem en només aquesta part aquí, estaries diuen que avalua a fals com vostè desitja. No és fals és cert que significa això seria executar. Això té sentit? ESTUDIANT: Sí. INSTRUCTOR: Awesome. Okay. Així que poguéssim tornar cert en aquest cas. Així que ara tenim dos casos en aquest cas. Quins són els altres dos casos? Anem a fer-ho d'aquesta manera. Així que anem a començar amb una altra cosa si els valors de la mitjana és menor que el valor que volem. Així que el nostre valor en el medi és menys que el valor que estem buscant. Així que unit fer pensem que volem posar al dia? Alt o baix? Alta? Així quin costat de la matriu estarem mirant? ESTUDIANT: La més baixa. INSTRUCTOR: Ens anem a estar mirant a l'esquerra. Així la resta si poc valor és menor. Pel que el seu valor mitjà aquí és menys del que volem. Per això volem prendre la costat dret de la nostra matriu. Així que anem a actualitzar la nostra fita inferior. Així que anem a reassignar nostre inferior. I què creu vostè que hauria de ser més baixa? ESTUDIANT: El valor mitjà? INSTRUCTOR: Així que la value-- mitjà ESTUDIANT: Plus 1. INSTRUCTOR: --plus 1. Pot algú dir-me per què hem de més 1? ESTUDIANT: [? Cap valor?] és més igual a ella. INSTRUCTOR: Dret. Perquè ja sabem que nostre valor mitjà no és igual a i volem excloure de totes les recerques posteriors. Si se li oblida que més 1, aquest li agradaria bucle indefinidament. I només li atrapats en un bucle infinit i després podràs segfault i les coses van malament. Així que assegureu-vos sempre que vostè no està incloent el valor que acaba de mirat. Així que nosaltres ens encarreguem de que amb un més 1. Així que ara tenim la nostra última condició Sempre que per raons de seguretat vostè pot comprovar aquí, en cas contrari si el valor en el mitjà és major que el valor volem. Això vol dir que volem la meitat de la mà esquerra. Així que un anem a actualitzar? Superior. I quin és aquest serà igual? Medi menys 1, ja que, per descomptat, volem per assegurar-se que no estem mirant a aquest valor mitjà nou. I llavors el tenim. Això és tot. Això és tot de recerca binària és. No és tan dolent, oi? És com 10 línies de codi amb l'espai en blanc. Així que és molt potent, molt útil, es vol a utilitzar en un dels seus conjunts de processadors posteriors. Potser no aquest, però més tard. Així que aprendre. Vullga-ho. Es tractarà bé. Així que algú té algun preguntes sobre la recerca binària? Sí. ESTUDIANT: Importa si el n és parell o senar? INSTRUCTOR: No. Perquè ens tirem a la mitjana com 1 int, s'acaba de truncar la mateixa. Per tant, es mantindrà un nombre enter i ho farà eventualment ordenar a través de tot. Així que vostè no ha de preocupar-se per això. Tothom bé? Impressionant. Refredar. Així que, vostès em encàrrec. Presentació de diapositives. Així com que estàvem parlant, ho sé David va esmentar temps d'execució de complexitat. Així que en el millor dels casos, és només un, que anomenem constant de temps. Pot algú dir-me per què podria ser? Quin tipus d'escenari caldria implicar? Mm-hm. ESTUDIANT: [inaudible] primer-- INSTRUCTOR: Així que el mitjà és el primer element que vam arribar a, oi? Així que, o una matriu d'un o el que estem buscant només passa a ser just en el medi. Així que aquesta és la nostra millor dels casos. Et fiques en problemes reals, probablement no arribarà a [inaudible] que sovint. Què passa amb la nostra pitjor dels casos? El nostre pitjor dels casos és log n. I això té a veure amb el tot potències de dos cosa que vaig parlar. Així que en el pitjor dels casos que significaria que havíem de tallar la matriu cap avall fins que hi havia un element d'un. Així que vam haver de tallar cap avall a la meitat tantes vegades com ens sigui possible. És per això que és log n perquè que acaba de seguir dividint per dos. Així suposicions, coses que vosaltres necessita saber si alguna vegada utilitzarà una recerca binària. Els seus elements han de ser ordenats. Han de ser resolt perquè aquesta és l'única manera en què pot saber si vostè és capaç de de tirar la meitat d'ella. Si tinguessis aquesta borsa confusa dels nombres i que estàs dient, Bé, vaig a revisar el medi nombre i el nombre que estic buscant és menys que això, jo només vaig llençar arbitràriament la meitat. No sap si el seu nombres en aquest altre mitjà. La seva llista ha de ser resolt. A més, això pot ser seguir endavant una mica, però cal tenir accés aleatori. Has de ser capaç de simplement anar a aquest element mig. Si vostè ha de travessar a través d'una cosa o li pren mesures addicionals per arribar a aquest element mig, no és log n més perquè va a afegir més feina a ell. I això farà una mica més sentit en dues setmanes, però jo com que volia escriure el pròleg, vostès donar una idea del que és per venir. Però aquests són els dos supòsits importants que vostè necessita per obtenir una llista binari. Assegureu-vos que està ordenada. Aquesta és la gran un per vostès ara mateix. I en què podem entrar en la resta de les nostres classes. Així que 4 bombolla sorts--, inserció, selecció i combinació. Són tots una mena de fresc. Si vostès decideixen prendre CS 124, vostè aprendrà sobre tot tipus de gèneres. I si ets un fan de XKCD, hi ha és un còmic genial sobre com a tipus realment ineficaços, que em altament recomanable anar a mirar. Un d'ells és com una espècie de pànic, que és com, oh no, tornar disposició aleatòria. Sistema apagat. Deixa. Així humor geek és sempre bo. Així que algú recorda tipus d'com simplement una idea general de com funciona la bombolla espècie. Te'n recordes? ESTUDIANT: Sí. INSTRUCTOR: A per això. ESTUDIANT: Així que estàs passant i si és més gran, llavors vostè intercanvia els dos. INSTRUCTOR: Mm-hm. Exactament. Així que només iterar a través. Vostè comprova dos nombres. Si l'anterior és més gran que el que després, vostè acaba d'intercanviar de manera que en d'aquesta manera tots els números més alts la bombolla cap al final de la llista i tots els números més baixos de la bombolla baix. Ell et mostri nois la fresca efecte de so de classificació de vídeo? És una mena de fresc. Així com només va dir Robert, l'algoritme que acaba de pas a través de la llista, l'intercanvi dels valors adjacents si no estan en ordre. I a continuació, només seguir repetint fins que no es realitzin canvis. Així que no està malament, oi? Així que només tenim un exemple ràpid aquí. Així que això va a classificar en ordre ascendent. Així que quan anem a través de la primera temps, veiem a través de vuit -sis, òbviament, no són en fi, els canviem. Així que busqui en la següent. Vuit i no quatre en ordre. Intercanviar-les. I després de vuit i dos, ells swap. Cal anar. Així que després de la seva primera passada, pot saber que el seu nombre més gran serà tot el camí a la part superior, ja que és només estarà constantment més gran que tota la resta i que només va a la bombolla tot el camí fins al final allà. Això té sentit per a tothom? Refredar. Llavors ens fixem en el nostre segon passi. Sis i quatre, interruptor. Sis i dos, interruptor. I ara que tenim algunes coses en ordre. Així, per cada pas que ens fer a través de tota la nostra llista, sabem que igual que molts números al final li han estat ordenats. Així que fem una tercera passada, que és un intercanvi. I després en el quart passar, tenim zero ranures. I pel que sabem que el nostre matriu s'ha classificat. I aquest és el gran cosa amb la bombolla de classe. Sabem que quan ens tenir zero swaps, que significa que tot està en complet ordre. És una espècie de com vam comprovar. Així que també anem a codificar bombolla quin tipus tampoc és tan dolent. Cap d'aquests són tan dolents. Sé que pot semblar una mica de por. Sé que quan vaig prendre la classe, fins i tot quan jo va ser l'ensenyament de la classe de la primera vegada l'any passat, Jo estava com, com puc fer això? Té sentit en teoria, però ¿Com podem realment fer això? És per això que també vull caminar a través de codi amb vostès aquí. Així que tinc un pseudocodi per a vostès en aquesta ocasió. Així que tenir això en ment a mida estem a punt de fer la transició més. Així que tenim una mica de comptador que realitza un seguiment dels nostres swaps, perquè hem d'assegurar- que estem comprovant que. I iterem tota la matriu com acabem de fer amb aquest exemple. Si l'element és més gran que abans l'element després d'on estem, nosaltres els swap i incrementem la nostra comptador perquè tan aviat com ens intercanviem, volem que el nostre comptador sap. Qualsevol pregunta allà? Una cosa sembla divertit per aquí. ESTUDIANT: S'ajusta el comptador a zero cada vegada que vagi a través del bucle? No segueixes endavant de tornada a zero cada vegada? INSTRUCTOR: No necessàriament. Així que el que passa és que anem per aquí. Així que mentre que, recordi, això s'executarà una vegada sense falta. Així que va a establir el comptador igual a zero, a continuació, es va a recórrer. A mesura que itera a través de, s'actualitzarà taulell. Com s'actualitza taulell, quan es fa, quan s'arriba al final de la matriu, si la nostra llista no ha estat ordenat, comptador s'haurà actualitzat. Així llavors es comprova la condició i diu, està bé, és comptador més gran que zero. Si ho és, fer-ho de nou. Vostè vol restablir de manera que quan vostè anar a través de, el comptador és igual a zero. Si vostè va a través d'una ordenada matriu, res no canvia, això no funciona, i vostè tornar la llista ordenada. Això té sentit? ESTUDIANT: Es podria en una mica. INSTRUCTOR: OK. Si hi ha qualsevol altre pregunta que sorgeix. Sí. ESTUDIANT: Quina seria la funció serà per al canvi dels elements? INSTRUCTOR: Així que en realitat podem escriure que si anem a la dreta ara. Refredar. Així que en aquesta nota, Alison va per canviar de nou a l'aparell. Serà divertit. I tenim el nostre agradable bombolla espècie cosa aquí. Així que ja ho vaig fer en bicicleta a través de la matriu. Tenim els nostres swaps que són iguals a zero. Així que volem intercanviar adjacent elements si estan fora d'ordre. Així que el primer que hem de fer és iterar a través de la nostra gamma. Llavors, ¿com creu vostè que podríem iterar a través de la nostra gamma? Tenim per i i és igual a 0. Volem i a ser menys de n menys 1 menys k. I vaig a explicar que en un segon. Així que aquesta és una optimització aquí on, recordar com he dit després de cada passi a través de la qual array saber que tot el que és en-- Així que després d'una passada ens sé que això està solucionat. Després de dos passis sabem que tot això està ordenada. Després de tres passades ens Sé que és ordenats. Així que la forma en què estic iteració a través de la matriu aquí, s'està assegurant que anar sol a través del que sabem que és classificar. D'acord? Això és només una optimització. Es pot escriure que ingènuament només iteració a través de tot, seria just prendre més temps. Amb aquest bucle és de quatre només una bona optimització perquè sabem que després de cada ple iteració a través de la matriu aquí, com cada bucle complet aquí, sabem que un més d'aquests elements s'ordenaran al final. Així que no hem de preocupar-nos per aquells. Això té sentit per a tothom? Aquest petit truc genial? Així que en aquest cas, si estem iteració a través de, sabem que volem comprovar si matriu n i n + 1 estan en ordre. Okay. Així que aquí està el pseudocodi. Volem comprovar si matriu n i n + 1 estan en ordre. Llavors, ¿què podríem tenir-hi? Serà una mica de condicional. Serà un si. ESTUDIANT: Si matriu n és menys de matriu de n més 1. INSTRUCTOR: Mm-hm. Bé, menor que o més gran que. ESTUDIANT: Major que. Llavors volem per intercanviar-les. Exactament. Així que ara ens fiquem en el que és la mecanisme per a l'intercanvi d'ells? Així que ens vam anar a través d'aquest breu, un tipus de funció d'intercanvi de la setmana passada. Algú recorda com funcionava? Així que no podem simplement reassignar ells, oi? A causa de que un d'ells es perdi. Si hem dit que A és igual a B i B a continuació, és igual a A, tot sobte tots dos són només igual a B. Així que el que hem de fer és que tenir una variable temporal que és va a celebrar un dels nostres, mentre que estem en el procés d'intercanvi. Així que el que tenim és que tindrem una mica de int temperatura és igual A-- pot assignar al que vostè vol, només Assegureu-vos de mantenir un registre de it-- pel que en aquest cas, vaig a assignar-la a la matriu n + 1. Així que va a celebrar el que sigui valor està en aquest segon bloc que estem veient. I llavors el que podem fer és que podem anar endavant i varietat Reassignar n + 1, perquè sabem que que tenen valor emmagatzemat. Aquest és també un dels grans coses-- No sé si algun de vostès tingut problemes on si interruptor de dues línies de codi de sobte les coses van funcionar. L'ordre és molt important en CS. Així que assegureu-vos de diagramar les coses, si és possible pel que fa al que està succeint realment. Així que ara anem a reassignar matriu n + 1, perquè sabem que que tenen valor emmagatzemat. I podem assignar que a la matriu n o en aquest cas matriu i. Massa variables. Okay. Array Així que ara que hem reassignat i més 1 per a igualar el que està en sèrie i. I ara podem tornar enrere i assignar sèrie i per a què? Qualsevol persona? ESTUDIANT: 10. INSTRUCTOR: 10. Exactament. I una última cosa. Si hem canviat ara, ¿Què és el que hem de fer? Què és l'únic això va a dir-nos si alguna vegada acabar aquest programa? El que ens diu que hem tenir una llista ordenada? Si no realitzem cap swaps, oi? Si swaps és igual a zero al final d'aquest. Així que cada vegada que es realitza un intercanvi, ja que acaba de fer aquí, volem actualitzar els swaps. I jo sabia que hi havia un pregunta anterior sobre oi utilitzar zero o un en el seu lloc de vertader o fals. I això és el que fa això aquí. Així que això diu que si no els swaps. Així que si els swaps és zero, el que és-- Sempre aconseguir els meus veritats i les meves falses barrejats. Volem que avaluem true i no ho és. Així que si és zero, llavors és fals. Si negues amb un [? Bang?] Es converteix en veritable. Així que aquesta línia s'executa. Veritats i falsa i zeros i uns aconsegueixen boig. Només si vostè camina lentament a través d'ella tindrà sentit. Però això és el que aquest petit mica de codi aquí fa. Així que això comprova hem fet cap swaps. Així que si és una cosa més de zero, que serà fals i tota la cosa és va a executar de nou. Fresc? ESTUDIANT: Què fa el descans? INSTRUCTOR: Trencar només que trenca fora del circuit. Així que en aquest cas seria de la mateixa manera que acabar el programa i ho faria només tenir la seva llista ordenada. ESTUDIANT: Amazing. INSTRUCTOR: Ho sento? ESTUDIANT: Com que anteriorment utilitzat escrit 1 sobre escrit zero per presentar que si que funcionarà o no. INSTRUCTOR: Sí. Així que vostè pot tornar zero o 1. En aquest cas, perquè no estem en realitat fer qualsevol cosa amb la funció, només volem que es trenqui. En realitat no es preocupen per ell. Fre també és bo si s'utilitza per trencar de quatre bucles o condicions que vostè no desitja mantenir l'execució. Simplement et porta fora d'ells. És una mica d'una cosa matís. Em sento com si hagués una gran quantitat de mà que agita, com vostè aprendrà sobre això aviat. Però vostè aprendrà sobre això aviat. Prometo. Okay. Així que no tothom aconsegueix bombolla espècie? No està malament. Recórrer, coses swaps servir un variable TEMP, i tots estem estableix allà? Refredar. Impressionant. Okay. Tornar al principi PowerPoint. Qualsevol pregunta en general sobre aquests fins al moment? Refredar. Mm-hm. ESTUDIANT: [inaudible] int main normalment. No has de tenir que per això? INSTRUCTOR: Així que estàvem buscant just en l'algoritme d'ordenació real. Si haguessis de dins com un programa més ampli, vostè tindria un algun lloc principal int. Depenent d'on vostè utilitzar aquest algoritme, seria determinar quin és sent retornat per ell. No obstant això, per al nostre cas, estem estrictament mirant com funciona això en realitat recórrer una matriu. Així que no et preocupis per això. Així que estàvem parlant millor dels casos i pitjor dels casos per a la recerca binària. Així també és important fer que per a cada una de les nostres classes. Llavors, ¿què creu vostè que és el pitjor dels casos cas el temps d'execució de la bombolla espècie? Vostès recorden? ESTUDIANT: N almenys 1. INSTRUCTOR: N almenys 1. Així que això significa que hi ha n almenys 1 comparacions. Així que una cosa és adonar- que en la primera iteració, anem a través, comparem aquests dos-- així que això és 1. Aquests dos, tres, quatre. Així que després d'una iteració que ja té quatre comparacions. Quan estic parlant de temps d'execució i n. N representa el nombre de comparacions com una funció de quants elements tenim. D'acord? Així que anem a través, tenim quatre. La propera vegada que vostè sap no ho fem ha de fer-se càrrec d'això. Comparem aquests dos, aquests dos, aquests dos, i si no haguéssim de l'optimització amb els quatre bucle que vaig escriure, vostè estaria comparant aquí de totes maneres. Així que hauria de executar a través de la matriu i fer comparacions n n vegades, perquè cada vegada que córrer a través d'ell vam classificar una cosa. I cada vegada que ens trobem a través de la matriu, fem n comparacions. Així que el nostre temps d'execució d'això és en realitat n quadrat, que és molt pitjor en la nostra ingressi final perquè això vol dir que si teníem 4 milers de milions d'elements, és ens portarà 4000000000 quadrat en lloc de 32. Així que no és el millor temps d'execució, però per a algunes coses, ja saps, si estàs dins de d'un cert rang d'elements bombolla espècie pot estar bé per al seu ús. Okay. Així que ara el que és el millor temps d'execució de cas? ESTUDIANT: Zero? O 1? INSTRUCTOR: 1 Així que ho faria ser una comparació. Dreta. ESTUDIANT: N almenys 1? INSTRUCTOR: Així que, si. Així n almenys 1. Sempre que tingui un concepte com n menys 1, tendim a simplement deixar-ho i acabem de dir n perquè tens comparar cada un dels these-- cada parell. Així que seria n menys 1, que ens que acabàvem de dir és aproximadament n. Quan vostè està tractant amb el temps d'execució, tot està en aproximats. Mentre l'exponent és correcta, ets bastant bo. Així és com ens ocupem d'això. Així que el millor dels casos és n, el qual vol dir que la llista ja està ordenat, i tot el que fem és executar a través de i comprovi que està ordenada. Refredar. Bé. Així que com veus aquí, només hi ha algunes més gràfics. Així que n al quadrat. Diversió. Molt pitjor que n com veiem, i molt, molt pitjor que 2n registre. I llavors vostè també aconsegueix en registre registres. I vostè pren 124, et fiques en com a estrella de registre, que és com una bogeria. Així que si vostè està interessat, estrella de registre de cerca. És una mica de diversió. Així que tenim aquest gran quadre. Només un cap, aquest és un meravellosa carta tingui per al seu mitjà termini, ja que temps per demanar-li que aquests s'aprima. Així que només un caps, tenen això en el seu a mitjà termini en el seu full de trucs agradable Ja està. Així que acabem de veure bombolles espècie. Pitjor dels casos, n al quadrat, millor dels casos, n. I anem a mirar els altres. I com es pot veure, l'única un que realment li va bé és una espècie de combinació, que entrarem en per què. Així que anirem a la següent aquí-- selecció espècie. Algú recorda com selecció treballar espècie? No t'ho pensis. ESTUDIANT: Bàsicament passar per un ordre i crear una nova llista. I així com vostè està posant elements en, els va posar en el lloc correcte en la nova llista. INSTRUCTOR: Així que els sons més com l'ordenació per inserció. Però estàs molt a prop. Són molt similars. Fins i tot va arribar ells confonen de vegades. Abans d'aquesta secció jo estava com, esperi. Okay. Així que el que vostè desitja fer és una mena de selecció, la forma en què es pugui imaginar sobre això i la forma M'asseguro de no tractar d'aconseguir es confonguin, és que passa per i selecciona el menor nombre i posa que al principi de la seva llista. Es intercanvia amb aquest primer lloc. De fet, tenen un exemple per a mi. Impressionant. Així que una manera de pensar en la selecció it-- Ordena, seleccioneu el valor més petit. I anem a executar a través d'un exemple que crec que ajudarà perquè Crec visuals sempre ajuden. Així que vam començar amb alguna cosa que és completament sense classificar. Vermell serà sense classificar, verd, seran ordenats. Tot tindrà sentit en un segon. Així que anem a través i iterem des del principi fins al final. I diem, OK, 2 és el nostre nombre més petit. Així que tindrem 2 i anem per moure a la part davantera de la nostra gamma perquè és la nombre més petit que tenim. Així que això és el que això s'està fent aquí. És només canviarà tots dos. Així que ara tenim un classificat part i una part sense classificar. I el que és bo recordar sobre la selecció d'espècie és que només estem seleccionant de la part sense classificar. La part ordenada que acaba de deixar sols. Mm-hm? ESTUDIANT: Com sap el que és el més petit sense comparar- a qualsevol altre valor a la matriu. INSTRUCTOR: Ho fa comparar. Ens agrada el saltem. Això és només en general en general. Sí. Quan escrivim el codi que estic Segur que estarà més satisfet. Però vostè guarda el primer element com el més petit. Es tracta de comparar i vostè a dir, OK, és més petit? Sí. Keep it. Aquí és més petit? No? Aquest és el seu més petit, reassignar al seu valor. I seràs molt més feliç quan anem a través del codi. Així que anem a través, ens vam canviar, així que a continuació ens fixem en aquesta porció sense classificar. Així que anem a seleccionar tres. Anem a posar-ho en en Al final de la nostra part ordenada. I només seguirem fent que, fent això, i fent això. Així que aquest és el nostre tipus de pseudocodi aquí. Anem a codificar fins aquí en un segon. Però només una mica per caminar a través d'un alt nivell. Te n'aniràs de i és igual a 0 a n almenys 2. Aquesta és una altra d'optimització. No es preocupi massa sobre ell. Així com vostè deia. Com Jacob estava dient, com podem portar un registre del que el nostre mínim és? Com ho sabem? Hem de comparar tot en la nostra llista. Així mínim és igual a i. És simplement dient en aquest cas l'índex del nostre valor mínim. Així que es va a recórrer i va des de j és igual a i + 1. Així que ja sabem que aquest és el nostre primer element. No necessitem per a comparar-la amb la pròpia. Així que començar a comparar a la següent un que és per això que és i + 1 a n menys 1, que és el final de la matriu allà. I nosaltres vam dir si matriu a j és de menys de matriu min, llavors reassignar on els nostres índexs mínims és. I si min no és igual a i, com on estàvem de tornada per aquí. Així com quan ho vam fer per primera vegada aquest un. En aquest cas, seria començar a zero, seria arribar a ser dues. Així min no ho faria igual i en el final. Que ens permet saber que que necessitem per intercanviar-les. Em sento com un exemple concret ajudarà molt més que això. Així que vaig a codificar aquesta amb vosaltres en aquest moment i crec que serà millor. Ordena tendeixen a treballar d'aquesta manera en què sovint és millor només per veure'ls. Així que el que volem fer és el primer que volem la més petita element en la seva posició en l'array. Exactament el que Jacob estava dient. Necessita emmagatzemar que d'alguna manera. Així que anem a començar aquí iteració en la matriu. Anem a dir que és el nostre primer només per començar. Així que tindrem int més petit és igual a la matriu en i. Així que una cosa a notar, cada vegada aquest bucle s'executa, estem començant un pas més enllà al llarg. Quan vam començar ens fixem en aquest. La propera vegada que recórrer, estem començant a aquest i assignant-li el nostre valor més petit. Així que és molt similar a la bombolla de tipus on sabem que després d'una sola passada, aquest últim element està ordenada. Amb la selecció d'espècie, que és tot el contrari. A cada passi, sabem que la primera d'elles està ordenada. Després de la segona passada, el segon, seran ordenats. I com es va veure amb els exemples de diapositives, la nostra porció ordenats segueix creixent. Així que mitjançant l'establiment del nostre un més petit a matrius i, tot el que està fent es constricció del que estem veient amb la finalitat de per minimitzar el nombre de les comparacions que fem. Això té sentit per a tothom? Em necessita per funcionar a través d'aquest una altra vegada més lent o amb altres paraules? Estic feliç. Okay. Així que estem emmagatzemant el valor en aquest punt, però també volem emmagatzemar l'índex. Així que anem a emmagatzemar el la posició dels més petits un, que és només serà i. Així que ara Jacob està satisfet. Tenim coses emmagatzemades. I ara hem de mirar a través de la part no seleccionada de la matriu. Així que en aquest cas aquesta seria el nostre sense classificar. Això és i. Okay. Així que el que farem serà d'un bucle. Sempre que necessiti iterar a través d'una matriu, la seva ment podia anar a per un bucle. Així que per a alguns int k equals-- ¿què pensem k serà igual per a començar? Això és el que ens vam proposar com el nostre més petit valor i volem comparar. Què és el que volem comparar? Serà el pròxim un, oi? Pel que volem k per ser inicialitzat a i + 1 per començar. I volem k en aquest cas ja han emmagatzemat mida fins aquí, de manera que només podem usar mida. Mida ser la mida de la matriu. I només volem actualitzar k en un cada vegada. Refredar. Així que ara hem de trobar l'element més petit aquí. Així que si ens recórrer, ens vull dir, si en la matriu k és menor que el nostre value-- més petit aquí és on som en realitat fer el seguiment del que és el més petit aquí-- llavors volem reassignar quin és el nostre valor més petit és. Això vol dir que, oh, estem iteració a través d'aquí. Qualsevol que sigui el valor és aquí és no la cosa més petita. Nosaltres no volem. Volem tornar a assignar la mateixa. Així que si estem reassignant, què fer vostè pensa que podria estar en el codi aquí? Volem tornar a assignar més petit i la posició. Llavors, què és més petita ara? ESTUDIANT: Array k. INSTRUCTOR: Array k. ¿I quina és la posició ara? Què hi ha dels índexs de el nostre valor més petit? És només k. Així matriu k, k, que coincideixen. Així que volíem que reassignar. I a continuació, després que ens trobem la nostra més petita, així que al final d'aquest bucle for aquí hem trobat el que el nostre petit valor és, de manera que només s'intercanvie. En aquest cas, igual que dir que la nostra valor més petit és aquí. Aquest és el nostre valor més petit. Només volem canviar des d'aquí, que és la qual cosa la funció d'intercanvi a la part inferior vam fer, que només escrivim a dalt junts fa un parell de minuts. Per tant, hauria de semblar familiar. I llavors s'acaba de repetir fins que arriba a través de tot el camí fins al final, el que significa que vostè tenir zero elements que no classificades i tota la resta s'ha ordenat. Té sentit? Una mica més concreta? El codi ajuda? ESTUDIANT: Per una mida, mai realment definir o canviar-lo, ¿Com sap? INSTRUCTOR: Així que una cosa és compte aquí és la mida int. Així que estem dient en aquest tipus sort-- és una funció en aquest cas-- és selecció espècie, es va aprovar amb la funció. Així que si no es va aprovar en, vostè faria alguna cosa com amb la longitud de la matriu o vostè recórrer per trobar la longitud. Però com que es va aprovar en, només podem usar-lo. Vostè acaba d'assumir que l'usuari li va donar una grandària vàlid que en realitat representa una mida de la matriu. Fresc? Si vostès tenen algun problema amb aquests o desitja més pràctica de codificació tipus pel seu compte, vostè ha de anar a study.cs50. És una eina. Tenen un corrector que en realitat es pot escriure. Ho fan pseudocodi. Tenen més vídeos i diapositives incloent-hi els que utilitzo aquí. Així que si vostè encara està sentint un mica borrós, tracti d'això. Com sempre, venir a parlar amb mi, també. Pregunta? ESTUDIANT: ¿Està dient que el grandària es defineix anteriorment? INSTRUCTOR: Sí. La mida es defineix prèviament cap amunt aquí a la declaració de la funció. Així que vostè assumeix que ha estat aprovada en per l'usuari, i pel bé de la simplicitat, anem a suposar que el usuari ens va donar la talla correcta. Refredar. Així que aquesta és la selecció de classificació. Nois, saben que estem aprenent molt avui. És una densa dades per a la secció. Així que amb això, anem per anar a l'ordenació per inserció. Okay. Així que abans que nosaltres hem de fer la nostra anàlisi de temps d'execució aquí. Així, en el millor dels casos, concedit des que et vaig mostrar la taula que ja classe del que va delatar. Però millor temps d'execució cas, ¿què pensem? Tot ordenades. N al quadrat. Algú té una explicació per què et sembla? ESTUDIANT: Vostè està comparant through-- INSTRUCTOR: Dret. Vostè està comparant a través. A cada iteració, encara que estem decrementar aquest per un, vostè encara està buscant a través de tot per trobar el més petit. Així que fins i tot si el seu valor més petit és aquí al començament, vostè encara està comparant- contra tota la resta per assegurar-se que és la cosa més petita. Així que va a acabar corrent a través de aproximadament n vegades al quadrat. Bé. I quin és el pitjor dels casos? També n al quadrat perquè vas a estar fent això mateix procediment. Així, en aquest cas, la selecció tipus té alguna cosa que també anomenem el temps d'execució esperat. Així que en els altres, només sabem els límits superior i inferior. Depenent de què tan boig nostre llista és o com classificar el que sigui, que varien entre n o n al quadrat. No sabem. Però com que la selecció té el mateix tipus pitjor i millor dels casos, que ens diu que no importa quin tipus d'entrada que té, ja sigui completament ordenats o completament revertir ordenats, és va a prendre la mateixa quantitat de temps. Així que en aquest cas, si recordar de la nostra taula, que en realitat tenia un valor que aquestes dues classes no tenen, que és el temps d'execució esperat. Així que sabem que cada vegada que correm selecció espècie, està garantit que executar una n al quadrat del temps. No hi ha variabilitat allà. Només espera. I, de nou, si vols aprendre més, prendre CS 124 a la primavera. Bé. Hem vist aquesta. Refredar. Així que tipus d'inserció. I probablement vaig per cremar a través d'aquest. No vaig a tenir vostès codificar. Tindrem caminem a través d'ell. Així que l'ordenació per inserció és una espècie de tipus similar a la selecció en què tenim tant una sense classificar i ordenats part de la matriu. Però el que és diferent és que a mesura que avancem a través d'un a un, que acabem de prendre qualsevol nombre està al costat del nostre sense classificar, i classificar-lo correctament en la nostra matriu ordenada. Es va a fer més sentit amb un exemple. Així que tot comença com sense classificar, Igual que amb la selecció de classificació. I anem a resoldre això en ordre ascendent com ho hem estat. Així que en el nostre primer passi prenem el primer valor i diem, OK, vostè és ara en una llista pel seu compte. Com que vostè està en una llista per si mateix, que està ordenada. Felicitats per ser el primer element d'aquesta matriu. Vostè ja està la va ordenar tot pel seu compte. Així que ara tenim un classificat i un arsenal sense classificar. Així que ara tenim la primera. Què passa entre aquí i aquí és que nosaltres diem, Bé, anem a mirar el primer valor de la nostra gamma sense classificar i anem a l'entrada al seu lloc correcte en l'arranjament ordenat. Així que el que fem és que prenem 5 i diem, OK, 5 és més gran que 3, així que ens inserim dret a la dreta d'això. Som bons. Així que a continuació passem al nostre següent. I prenem febrer. Nosaltres diem, OK, 2 és menys de 3, pel que sabem que ha d'estar en el davant de la nostra llista ara. Així que el que fem és empenyem 3 i 5 cap avall i ens movem 2 a la primera ranura. Així que estem a només inserir-lo en el lloc correcte que hauria de ser. Llavors ens fixem en la nostra següent, i diem juny. Acceptar, 6 és més gran que tot en la nostra matriu ordenada, així que simplement etiquetar fins al final. I després ens fixem en 4. 4 és inferior a 6, és menys del 5 però és més gran que 3. Així que només ens enviem la dreta el medi entre 3 i 5. Així que per fer que una mica poc més concret, aquí és una espècie de la idea del que va passar. Així que per a cada element sense classificar, que determinar on a la part ordenada és. Així que tenint en compte la classificats i sense classificar, hem de recórrer a través de la figura i on encaixa en la matriu ordenada. I ho inserim desplaçant la elements a la dreta cap avall. I llavors ens mantenim iteració a través fins que tenir una llista totalment ordenada on no seleccionats és ara zero i ordenada ocupa el totalitat de la nostra llista. Així que, de nou, per fer les coses encara més concret, tenim pseudocodi. Així que, bàsicament, per a i és igual a 0 a n menys 1, això és només la durada de la nostra matriu. Hem algun element que és igual a la primera matriu o els primers índexs. Establim j igual a això. Així, mentre que j és més gran que zero i la matriu, j almenys 1 és més gran que la element, de manera que tot el que està fent és assegurar-se que el joc realment representa la part no seleccionada de la matriu. Així, mentre que encara hi ha coses per ordenar i j menys un ho és-- és l'element ella? J mai es va definir aquí. És una mica molest. Okay. De tota manera. Així j menys 1, vostè està comprovant l'element abans d'ella. Estàs dient, OK, és l'element abans allà on anem am-- realment treure això cap a fora. Així que diguem que aquest és com en el nostre segon passi. Així que serà igual a 1, el que és aquí. Així que serà igual a 1. Això seria 2, 4, 5, 6, 7. Bé. Així que el nostre element, en aquest cas serà igual a 4. I tenim alguns j que és serà igual a 1. Oh, j es decrement. Això és el que és. Així que j és igual a i, pel que és això dit és que a mesura que avancem, només estem assegurant que no som més la indexació d'aquesta manera quan estem tractant per a inserir coses a la nostra llista ordenada. Així que quan j és igual a 1 en aquest cas i matriu j menys un-- tan gamma j almenys 1 és 2 en aquest cas-- si això és més gran que l'element, llavors tot això està fent està canviant les coses. Així doncs, en aquest cas, matriu j menys un seria matriu zero, que és 2. 2 no és major que 4, pel que aquest no s'executa. Així que el canvi no es mou cap avall. El que això fa aquí és només moure la matriu ordenada cap avall. En aquest cas, en realitat, ens podria fer-- farem aquest març. Així que si anem a caminar a través de aquest exemple, ara estem aquí. Això es va solucionar. Això és sense classificar. Fresc? Així que i és igual a 2, per la el nostre element és igual a 3. I el nostre j és igual a 2. Així que mirem a través i ens a dir, OK, és matriu j menys un més gran que l'element que estem veient? I la resposta és sí, oi? 4 és més gran que 3 i j és 2, de manera que aquest codi s'executa. Així que ara el que fem un arranjament en 2, pel que aquí, els swap. Així que ens limitem a dir, OK, matriu a les 2 de ara serà de 3. I j serà igual j menys 1, que és 1. Això és horrible, però vostès nois es posen la idea. J és ara igual a 1. I gamma j és només serà igual al nostre element, que era 4. Vaig esborrar cosa que no hauria tenir o alguna cosa miswrote, però vostès nois es posen la idea. Es mou en el núm. I després, si això fos, ho faria bucle de nou i seria dir, OK, j és 1 ara. I gamma j almenys 1 és ara 2. És 2 menys que el nostre element? No? Això vol dir que hem inserit aquest element en el lloc correcte en la nostra matriu ordenada. Llavors podem prendre això i diguem, Acceptar, la nostra matriu ordenada és aquí. I seria prendre aquest número 6 i ser com, OK, és de 6 a menys d'aquest número? No? Refredar. Estem bé. Fes-ho de nou. Diem juliol. És 7 menys que la fi de la nostra matriu ordenada? No Així que estem bé. Així que aquest seria solucionat. Bàsicament tot el que això fa s'està dient pren el primer element de la matriu sense classificar, esbrinar a on va en la seva matriu ordenada. I això només es fa càrrec dels swaps de fer això. Bàsicament, s'està simplement intercanviant fins que estigui en el lloc correcte. La imatge visual és que ets movent tot per fer això. Així que és com la meitat de la bombolla espècie-esque. Fes un cop d'ull a estudi 50. Recomano provar per codificar això pel seu compte. Si vostè té algun problema o desitja veure codi d'exemple per a una ordenació per inserció, per favor hágamelo saber. Estic sempre al voltant. Així que el pitjor temps d'execució de cas i el millor temps d'execució cas. Al noi va veure des de la taula que ja que va mostrar, és tant n al quadrat i n. Així que tipus d'anar fora del que parlem sobre les classes amb els nostres anteriors, pitjor cas de temps d'execució és que si que està completament sense classificar, hem de comparar totes aquestes vegades n. Fem un munt de comparacions perquè si és en ordre invers, anem a dir, OK, aquest és el mateix, això és bo, i aquest haurà de ser comparat contra el primer a ser traslladat de nou. I a mesura que ens feia l'extrem de la cua, tenim per comparar, comparar i comparar contra tot. Per tant, acaba sent aproximadament n al quadrat. Si és correcta, llavors dius, OK, 2, ja està bo. 3, vostè està davant d'un 2. Aquestes bé. 4, que acaba de comparar a la cua. Aquestes bé. 6, compara la cua, que estàs bé. Així, per cada punt si ja està ordenats, vostè està fent una comparació. Així que és només n. I perquè tenim un millor temps d'execució de cas de n i un pitjor cas de temps d'execució de n quadrat, no tenim temps d'execució esperat. Només depèn de la el caos de la nostra llista allà. I de nou, un altre gràfic i l'altra taula. Així diferències entre classes. Jo només vaig a brisa a través, jo sentir que hem parlat extensament sobre la forma en què tota la classe de variar i unir. Així Ordenament per barreja és l'últim Jo et avorriré amb els nois. Tenim un quadre bonic colorit. Així fusionar espècie és un algoritme recursiu. Així que sap vostè el que nois una funció recursiva és? Algú vol dir? Vols provar? Així que una funció recursiva és només una funció que diu a si mateix. Així que si vostès estan familiaritzats amb la seqüència de Fibonacci, això és perquè considera recursiva vostè pren els dos anteriors i sumar- per obtenir el seu següent. Així recursiva, sempre penso de la recursivitat com com una espiral pel que vostè és com una espiral cap avall en ell. Però és només una funció que diu a si mateix. I, en realitat, molt ràpid em vostè pot mostrar el que sembla. Així recursiva aquí, si ens fixem, aquest és la manera recursiva per resumir a través d'una matriu. Així que tot el que fem és tenim la funció suma suma que pren una mida i una matriu. I si et fixes, la mida decrements en un cada vegada. I tot el que fa és si x és igual a zero-- així que si la mida de la matriu és igual a zero-- retorna zero. En cas contrari, resumeix aquest últim element de la matriu, i després pren una suma de la resta de la matriu. Així que és just i el descomponen en problemes més petits i més petits. Llarga història curta, la recursivitat, funció que diu a si mateix. Si això és tot el que tens fora d'això, això és el que és una funció recursiva. Si vostè pren 51, obtindrà molt, molt còmode amb la recursivitat. És realment genial. Tenia sentit de la mateixa manera que 03 a.m. una nit fora. I jo estava com, per què he mai usar-lo? Així que per a la fusió espècie, bàsicament, el que va a fer és que és trencarà cap avall i trencar cap avall fins que els seus elements només individuals. Els elements individuals són fàcils de classificar. Veiem que. Si vostè té un dels elements, és ja considerada ordenada. Així que en una entrada de n elements, si n és menor que 2, simplement tornar perquè això significa és 0 o 1 com hem vist. Els que es consideren elements ordenats. En cas contrari, trencar per la meitat. Ordeni la primera meitat, ordenar la segona la meitat, i després unir-los. Per què es diu fusió espècie. Així que tenim aquí resoldrem aquests. Així que seguim tenint-los fins que la mida de la matriu és 1. Per això, quan és 1, tot just tornem perquè aquest és un arranjament ordenat, i això és un arranjament ordenat, i això és una matriu ordenada, tots estem ordenats. Així que el que fem és que iniciar la fusió d'ells junts. Així que la forma en què pot pensar en la fusió és que acaba d'extreure la més petita nombre de cadascuna de les matrius de sub i només afegir a la matriu sorgit. Així que si vostè mira aquí, quan tenim aquests conjunts que tenen 4, 6, i 1. Quan volem fusionar aquests, ens fixem en aquests dos primers i diem, OK, 1 és més petita, que va a la part davantera. 4 i 6, que no hi ha res per comparar que, simplement Etiquétalo fins al final. Quan combinem aquests dos, que acabem de prendre el més petit d'aquests dos, pel que és 1. I ara tenim la més petit dels dos, així que 2. Més petit d'aquests dos, 3. Més petit d'aquests dos, 4, 5, 6. Així que vostè està tirant d'elles. I perquè no tenen estat ordenats prèviament, només n'hi ha un comparació cada vegada que hi ha. Així que més codi aquí, la representació justa. Així s'inicia en el centre i a ordenar a l'esquerra i la dreta i llavors simplement fusionar aquests. I no tenim codi per fusionar aquí. Però, de nou, si vostè va a estudiar 50, que va a ser-hi. En cas contrari, venir a parlar amb mi si vostè encara està confós. Així que el bo aquí és que millor dels casos, pitjor dels casos, i el temps d'execució esperat estan tots en log n, que és molt millor que la que hem vist per la resta de les nostres classes. Hem vist n al quadrat i el que en realitat arribar aquí es n log n, la qual cosa és genial. Mira el molt millor que és. Tal agradable corba. Així que molt més eficient. Si alguna vegada es pugui, utilitzar la combinació de classe. Això li estalviarà temps. D'altra banda, com hem dit, si estàs a baix en aquesta zona inferior, no ha de gran part de la diferència. Et lleves a milers i milers d'entrades, vostè definitivament vol un algoritme més eficient. I, de nou, la nostra bella taula de tots tipus que vostès van aprendre avui. Així que sé que ha estat un dia dens. Això no és necessàriament va per ajudar amb el seu conjunt de processadors. Però jo només vull fer un descàrrec de responsabilitat aquesta secció no es tracta només de conjunts de processadors. Tot aquest material és just joc per als seus exàmens parcials. I també si ho fa seguir endavant amb CS, aquests són fonaments molt importants que vostè necessita saber. Així que alguns dies seran un poc més pset ajuda, però algunes setmanes seran contingut molt més real que pot no semblar súper útil per a vostè en aquest moment, però et prometo si continua el serà molt, molt útil. Així que això és tot per secció. A baix a l'filferro. Ho vaig fer en un minut. Però cal anar. I tindré feu donació o dolços. És al·lèrgic a qualsevol persona res, per cert? Els ous i la llet. Així feu donació són un no? Okay. Bé. Hi ha xocolata? Starburst. Starbursts són bones. Okay. Tindrem Starburst setmana que llavors. Això és el que vaig a aconseguir. Vostès tenen una gran setmana. Llegeixi la seva especificació. Deixeu-me saber si vostè té alguna pregunta. PSET dos graus han de ser a vostè per dijous. Si vostè té alguna pregunta sobre com em vaig qualificar alguna cosa o per què jo vaig qualificar alguna cosa la forma en què va fer, si us plau envieu-me un correu electrònic, venir a parlar amb mi. Estic una mica aquesta bogeria setmana, però et prometo Encara vaig a respondre dins de 24 hores. Així que tenir una gran setmana, tothom. Bona sort en el seu conjunt de processadors.