[Música tocando] 

ANDI Pengo: Benvido á semana 3 da sección. Grazas, rapaces, para todo o que vén a esta data de inicio máis cedo hoxe. Temos unha nice, pouco grupo íntimo hoxe. Polo tanto, esperamos que nós imos chegar a acabado quizais antes, un pouco máis cedo hoxe. Entón, rapidamente, só algúns anuncios para a axenda de hoxe. Antes de comezar, estamos indo a ir un pouco máis algunhas breves cuestións loxísticas, pset preguntas, interrogue, cousas así. E entón nós imos mergullo na dereita. Imos usar un depurador chamado GDB comezar a desbancar o noso código, que David explicou en rolda o outro día. Nós falaremos sobre os catro tipos de tipos. Nós imos pasar por riba deles moi rapidamente xa que son moi intensivos. Pero sei que todo diapositivas e código fonte están sempre en liña. Entón, Sinto-se a liberdade, na súa lectura, a volver e un ollo niso. 

Nós imos pasar por notación asintótica, que é só un xeito elegante de dicir "tempos de execución", onde temos a gran O que David explicou en rolda. E tamén temos Omega, que é o tempo de execución límite inferior. E imos falar un pouco máis en profundidade acerca de como os traballos. E, finalmente, imos pasar por riba de busca binaria, porque moitos de vostedes que xa teñen mirou para os seus Serie de exercicios probablemente sabe que que é un tema que está no seu pset. Entón vai ser feliz todos que nós Cubrimos iso hoxe. 

E, por último, á súa o producto sección, realmente deixou uns 15 minutos a fin de ir un pouco máis loxística de pset3, dúbidas, quizais un pouco de orientación, se quere, antes de iniciar a programación. Entón, imos tentar pasar o material moi rapidamente. E entón podemos pasar algún tempo tendo máis preguntas ao pset. Aceptar. 

Rapidamente, así que só algúns anuncios antes de comezar hoxe. En primeiro lugar, benvido a facer Lo través de dous dos seus Serie de exercicios. Eu dei un ollo ao your-- Si, imos obter unha salva de palmas para que un. En realidade, eu estaba realmente, realmente impresionado. I clasificado o primeiro pset para vós a semana pasada e que vostedes fixeron incrible. 

Estilo estaba no punto ademais de algúns comentarios. Asegúrese de que está sempre comentando seu código. Pero os seus Serie de exercicios foron no punto. E mantelo. E é bo para o alumno a ver que vostedes están poñendo en tanto esforzo no seu estilo eo seu proxecto no seu código que queremos para ti ver. Entón, eu estou pasando ao longo da miña gratitude para o resto dos TAS. 

Con todo, hai un algunhas preguntas Debrief Eu só quero pasar por riba dese faría tanto a miña vida e unha morea de outros TAS "vive un pouco máis fácil. En primeiro lugar, eu teño notado iso pasado week-- cantos de vós xa están a funcionar en check50 seu código antes de enviar? Aceptar. Entón, todos deben estar facendo check50, porque-- un secret-- realmente executar check50 como parte da nosa corrección scripts para probar o seu código. Polo tanto, se o seu código está fallando check50, con toda probabilidade, probablemente vai falla noso check tamén. Ás veces, vostedes ter as respostas correctas. Como, en ganancioso, algúns dos tes os números correctos, só imprimir algún material extra. E ese material extra realmente falla a verificación, porque o ordenador non fai realmente sabe o que está a procurar. E así ela só vai percorrer, ver que a súa saída non corresponden ao que esperamos que a resposta para ser, e marcalo é incorrecto. 

E sei que pasou en algúns dos seus casos esta semana. Entón, eu fun para atrás e manualmente Reclassificados código de todos. No futuro, porén, por favor, por favor, asegúrese que está executando comprobar 50 no seu código. Porque é un tipo de dor ao TA ter que volver e manualmente regrade cada pset único para cada instancia única, pouco perdida. Así que non aproveitar os puntos. Creo que eu tirei quizais un ou dous para o proxecto. No futuro, aínda que, se está fallando check50, Os puntos serán tomadas off para corrección. 

Ademais, son Serie de exercicios debido venres ao mediodía. Eu creo que hai unha de sete minutos período de carencia tarde que lle damos. Por tempo de Harvard, eles están autorizados a ser de sete minutos de atraso para todo. Entón, aquí en Yale, imos unirse a iso tamén. Pero practicamente, ás 12:07, se o seu non está na pset, que vai ser marcado como final. E así, mentres está marcado tan tarde, o TA-- son aínda vai ser Grading seus Serie de exercicios. Entón, aínda ver un grao aparecer. Con todo, sabemos que a o final do semestre, todas Serie de exercicios final será só zerada automaticamente polo ordenador. 

Facemos isto por dúas razóns. Un deles, ás veces ficamos desculpado, como desculpas de Dean, máis tarde que eu non sei sobre iso aínda. Por iso, quere ter a certeza de que estamos clasificación todo só no caso, como, eu son falta a escusa dun reitor. E en segundo lugar, Lembre mente, tamén se pode soltar un pset que ten puntos ámbito completo. E así nos gusta de grao todos os seus Serie de exercicios só para asegurarse de que o seu ámbito de alí e estás eles. Así, mesmo se é tarde, aínda obter crédito para puntos de ámbito, eu creo. 

Entón moral da historia é, torná- se dos seus Serie de exercicios están en dentro do prazo. E no caso de que non están en en tempo, sei que non é grande. Si, antes de seguir adiante, alguén ten calquera dúbida sobre o producto pset? Si. 

Audiencia: Vostede dixo que pode soltar unha das Serie de exercicios? 

ANDI Pengo: Si. Polo tanto, hai nove Serie de exercicios xeral ao longo do semestre. E se ten alcance points-- tan ámbito é xusto, moi ben, que estás a problema, está poñendo o tempo, está amosando que ten demostrada leu o spec. Iso é moi fermoso ámbito. E se está cumprindo Os puntos de alcance, nós pode soltar o menor un fóra de alcance global. Entón esta é a súa vantaxe para cubrir e tentar todo pset. 

Mesmo se ningún dos upload-- Los traballar, subir de todos eles. E entón esperamos ser capaces de darlle algúns destes puntos de volta. Legal. Algunha pregunta? Gran. 

En segundo lugar, oficina horas-- algúns notas rápidas sobre o horario de oficina. Entón, primeiro, entrar no inicio da semana. Ninguén está sempre en o horario de oficina os luns. Christabel veu a o horario de oficina na noite pasada. Si, Christabel. E o que temos na oficina horas na noite pasada, Christabel? 

Audiencia: Tivemos sorbete. 

ANDI Pengo: Entón, iso é certo, tivemos sorbete no horario de oficina na noite pasada. Mentres eu non podo prometer-lle que teremos sorbete no horario de oficina cada semana, o que podo prometer-lle é que haberá un aumento significativamente mellor relación de alumnos por TA. Como lexítimo, é como 3-1. Considerando que, contrastan coa que Xoves, ten preto de 150 realmente estrés nenos e non sorbete. E non é só produtivo para ninguén. Entón moral da historia é, chegou cedo para as horas de expediente e cousas boas vai pasar. 

Ademais, veña preparado para facer preguntas. Ti sabes? Independentemente do que tas, I pensan, teñen que chegou a dicir, recibimos un par de estudantes que entran en xoves, como, 10:50 non ler a especificación sendo como me axude, me axude. Por desgraza, neste punto, non hai Non moito que podemos facer para axudar. Entón, por favor, veña a principios da semana. Chegue antes para o horario de oficina. Veña preparado para facer preguntas. Asegúrese de que, como un estudante, onde son ten que ser para que o TAS poden oriente-lo xunto, que é o que o horario de oficina debe ser asignado para. 

En segundo lugar, entón eu sei profesores quere sorprender cos probas. Eu tiña un profesor quen como, yo, por certo, lembre que intercalar tes vindeiro luns. Si, eu non sei nada sobre iso intercalar. Entón, eu estou indo ser que TA que recorda todo o que proba 0-- porque, xa sabe, somos CS. Agora que temos matrices feito, comeza por iso que é proba 0, non quiz-1, eh? Aceptar. Oh, eu teño algunhas risadas sobre iso. Aceptar. 

Entón cuestionario 0 será 14 de outubro se está na sección de luns a mércores e 15 de outubro, se está en a sección de martes a xoves. Isto non se aplica para aqueles de vostedes en Harvard who-- Eu creo que vai ser todo tendo súas probas o día 14. 

Entón, si, a próxima semana, se David, en charla, vai, si, entón con iso proba a próxima semana, todos vostedes non quedará impresionado porque veu á sección e vostede sabe que o seu 0 proba é en dúas semanas. E teremos avaliación sesións e todo máis. Así, non se preocupa estar con medo por iso. Todas as preguntas antes-- dúbidas en todas as cuestións loxísticas relativas, clasificación, o horario de oficina, seccións? Si. 

Audiencia: Entón a proba é será durante a charla? 

ANDI Pengo: Si. Entón o quiz, eu creo, é 60 minutos asignados en que período de tempo que só vai tomar na clase. Entón non ten que vir en en, tipo, un aleatoria 19:00. É todo de bo. Si. Legal. 

Todo ben. Entón, nós estamos indo a introducir un concepto para ti esta semana que David xa tipo de abordou en charla a semana pasada. É chamado de GDB. E como moitos de vostedes, mentres en o curso de escribir as súas Serie de exercicios, notar un gran botón que di "Debug" na parte superior do seu IDE? Aceptar. Entón agora imos realmente comezar a desenterrar o misterio do que aquel botón, en realidade, fai. E eu asegura que, é unha bonito, cousa linda. 

Entón, ata agora, creo houbo dúas cousas os alumnos foron tipicamente facendo cando depuración Serie de exercicios. Un deles, eles quere engadir printf () - polo que cada poucas liñas, eles engadir nun printf () - Oh, o que é esa variable? Oh, o que é esa variable agora-- e tipo de ver a progresión do seu código como é executado. Ou o segundo método é facer os nenos que simplemente escribir a cousa toda e despois ir como este ao final. Esperemos que funciona. Eu asegura que, o mellor GDB de ambos os métodos. Si. Polo tanto, este será o seu novo mellor amigo. Porque é unha cousa bonita monitores que tanto visualmente o que o seu código está facendo nun punto específico así como o que todo o seu variables están levando, como cales son os seus valores, nese punto específico. E, deste xeito, pode realmente definir puntos de interrupción no seu código. Pode realizar a través de liña por liña. GDB e só terá para ti, exhibido para ti, que todas as variables están, o que están facendo, o que está a suceder no código. E, de tal xeito, que é moito máis fácil de ver o que está a suceder no canto de printf-ing ou escribir para abaixo súas declaracións. 

Entón, imos facer un exemplo diso máis tarde. Entón, iso parece un pouco abstracto. Non te preocupes, nós imos facer exemplos. E así, esencialmente, as tres grandes, funcións máis usadas que precisa en GDB son os próximos, Pasa, e Póñase en botóns. Vou de cabeza hai, en realidade, no momento. 

Entón vostedes todos poden ver que ou eu debería ampliar un pouco? Na parte de atrás, pode ver iso? Debo facer zoom? Só un pouquiño? OK, legal. Alí imos nós. Aceptar. 

Entón, eu teño, aquí, a miña implantación para ganancioso. E mentres unha morea de vostedes escribiu ganancioso en loop while que form-- é un xeito perfectamente aceptable para facer ele-- outra forma de facelo é simplemente dividir o módulo. Porque entón pode que o seu valor e, a continuación, ter o seu restante. E entón podes só engadir lo todos xuntos. Será que a lóxica do que eu estou facendo aquí ter sentido para todos, antes de comezar? Tipo de? Legal. Gran. É unha peza moi sexy de código, eu diría. Como dixen, David, en charla, despois dun tempo, todo o que vai comezar a ver código como algo que é bonito. E ás veces cando ve fermosa código, é unha sensación marabillosa. 

Entón, con todo, mentres este código é moi bonito, non funciona correctamente. Entón, imos correr check50 sobre este asunto. Consulte 50 20-- OOP. 2? É que pset2? Si. Oh, pset1. Aceptar. Entón corremos check50. 

E, como podedes ver aquí, está fallando un par de casos. E para algúns de vós, no curso de facer os seus conxuntos de problemas, vostede é como, ah, por que non funciona. Por que é traballar para algúns valores, pero non para outros? Ben, GDB vai axudar a figura por que esas entradas non estaban funcionando. 

Aceptar. Entón imos ver, un dos cheques que estaba fallando en check50 o valor de entrada foi de 0,41. Polo tanto, a resposta correcta que ten que estar recibindo é un 4. Pero en vez diso o que estou imprimindo é o 3-N, que é correcta. Entón imos realizar isto manualmente, só asegúrese de que check50 funciona. Imos facer ./greedy. Uups, eu teño que facer ganancioso. Alí imos nós. Agora ./greedy. 

Canto é debido? Imos facer 0,41. E si, vemos aquí que é a saída 3 cando a resposta correcta, de feito, debe ser de 4. Entón, imos entrar GDB e ver como nós pode ir sobre como corrixir este problema. 

Así, o primeiro paso na sempre depuración do código é establecer un punto de interrupción, ou un punto no que quere que o ordenador ou o depurador para comezar a ollar para. Entón, se realmente non sabe cal é o seu problema, Normalmente, a cousa típica queremos facer é establecer o noso punto de interrupción na principal. Entón, se vostedes poden ver iso botón vermello alí mesmo, Si, iso foi me establecendo un breakpoint para a función principal. Eu prema iso. 

E entón eu podo ir ata o meu botón Debug. Eu bater ese botón. Déixeme zoom out se poida. Alí imos nós. Polo tanto, temos, aquí, un panel da dereita. Sinto moito, persoal na parte de atrás, vostede non pode realmente ver moi ben. Pero, esencialmente, todo este panel dereita está facendo é manter o control de ambos destaque A liña, que é a liña de código que o ordenador está en execución, así como todas as súas variables aquí abaixo. 

Entón tes centavos, moedas, n, todos declararon a cousas distintas neste punto. Non te preocupes, porque non temos, en realidade, iniciar a eles a calquera variables aínda. Así, no seu ordenador, o seu ordenador só está a ver, Oh, 32767 foi a última función utilizada de que o espazo de memoria no meu ordenador. E así que é onde actualmente é centavos. Pero non que unha vez que realizar o código, debe chegar a ser iniciado. 

Entón, imos pasar por, liña por liña, o que está a suceder aquí. Aceptar. Entón, aquí están os tres botóns que eu só explicada. Ten o Play, ou a función Run, botón, ten a Paso sobre o botón, e tamén ten o botón Step Into. E esencialmente, os tres eles só pasar polo seu código e facer cousas distintas. 

Entón, normalmente, cando está depurando, nós non queremos é só usar Play, porque o xogo só funcionará seu código para o fin de todo. E entón non vai realmente sei que o seu problema é a menos que definir varios puntos de interrupción. Se establecer varios puntos de interrupción, Ela só vai automaticamente executado desde un punto de interrupción, ao seguinte, para o próximo. Pero neste caso temos só que un, porque quere traballar o noso camiño arriba abaixo abaixo. Entón, imos ignorar ese botón agora para os fins deste programa. 

Así, o Paso sobre a función só etapas, ao longo de cada liña única e dille o que o ordenador está facendo. O Paso en función vai para a función real que está na súa liña de código. Así, por exemplo, como printf (), que é unha función, non? Se eu quixese fisicamente paso para a función printf (), Gustaríame realmente ir ao anaco de código onde printf () foi escrito e vexa o que está a suceder alí. 

Pero, normalmente, asumimos que o código que nós dámoslle traballa. Asumimos o printf () funciona. Asumimos que GetInt () funciona. Polo tanto, non hai necesidade de paso a estas funcións. Pero se hai funcións que escribe en que quere comprobar o que está pasando, ía querer paso en que a función. 

Entón, agora nós só estamos indo de pasar por riba este anaco de código. Entón imos ver. Oh, impresión, "Oh hai, como moita cambio é debido? " Non nos importa. Sabemos que está a traballar, por iso, pasar por riba dela. 

Entón n, que é o noso flotador que temos initialized-- ou declared-- na parte superior, estamos agora igualando que a GetFloat (). Entón, imos pasar por riba diso. E vemos no inferior aquí, o programa está me levando para introducir un valor. Entón entrada de deixar o valor que queremos para probar aquí, que é 0,41. Gran. 

Entón agora n-- facer vostedes ver aquí, no bottom-- é stored-- porque non arredondados, é almacenados neste xigante como flotador que é 0,4099999996, que é preto o suficiente para o noso propósitos, agora, para 0,41. E entón nós imos ver máis adiante, como nós seguir pisando sobre o programa, despois aquí, n converteuse redondeado e centavos converteuse en 41. Gran. Entón, nós sabemos que o traballo do noso redondeo. Sabemos que temos que número correcto de centavos, polo que sabemos que iso é non é realmente o problema. 

Entón, nós seguimos pisando en neste programa. Imos aquí. E así, despois desta liña de código, Debes saber cantos cuartos que temos. Nós pasar por riba. E ve o que facemos, de feito, ten un trimestre porque temos subtraído 25 do noso valor inicial de 41. E nós temos 16 esquerda nosos centavos. 

Será que todo o mundo entender como estexa percorrendo e por centavos, pasou a ser 16 e por que, agora, as moedas tornouse un? Todos están seguindo esta lóxica? Legal. Así, a partir deste punto, o de traballo do programa, non? Sabemos que está facendo exactamente o que quere que sexa. E nós non o fixo, en realidade, ten que imprimir, oh, o que é centavos, neste punto, o que é moedas neste momento. 

Seguimos a atravesar o programa. Pasar por riba. Legal. Nós pasar por riba de moedas de dez centavos. Gran. Vemos que é tomado fóra de $ 0,10 para un centavo. E agora temos dúas moedas. Isto é correcto. 

Nós pasar por riba de moedas de un centavo e vemos que temos dabondo centavos. Hmm, iso é raro. Ata aquí no programa, eu debería ter subtraído meus tostões. Poida que eu só non foi facendo este dereito liña. E, por desgraza, pode ver aquí, porque sabemos que estamos pisando a través das liñas 32 e 33, que é onde o noso programa impropiamente tivo variables executado. Así, podemos ollar para ver, oh, Estou subtraindo centavos aquí, pero eu non son realmente engadindo a miña valor da moeda. Eu estou engadindo ao centavos. E eu non quero engadir centavos, quero engadir a moedas. Entón, se nós cambiar isto para moedas, temos un programa de traballo. Eu podo correr check50. Pode simplemente saír do GDB dereita aquí e despois executar check50 novo. Eu podería só facer. Teño que facer ganancioso. 0.41. E aquí, é impresión a resposta correcta. 

Entón, como podedes ver, GDB é unha ferramenta moi poderosa para cando temos tanto código pasando e tantas variables que é difícil para nós, como un ser humano, para acompañar. O ordenador, o GDB depurador, ten a capacidade manter o control de todo. Sei, en Visionaire, vostedes probablemente pode atinxir algúns fallos de segmentación porque estaba executando fóra dos límites da súa matriz. No exemplo de César, que é exactamente o que eu teño aplicado aquí. 

Entón, eu esquezo de comprobar a o que acontecería se eu non ter dous argumentos de liña de comandos. Eu só non poñer nesa selección. E así se eu executar Debug-- eu definir o meu punto de interrupción para a dereita alí. Eu corro Debug. 

Aceptar. Si. Entón, en realidade, era suposto GDB ter me dixo que non Foi hai un fallo de segmento. Non sei o que estaba acontecendo alí mesmo, pero cando eu execute, que estaba a traballar. Cando fai liñas de código mediante e GDB pode de súpeto deixar en ti, ir cara arriba e mira o que o erro é vermello. Só pode dicir-lle, hey, tivo un fallo de segmentación, o que significa que intentou acceder espazo nunha matriz que non existía. Si. 

Así, o próximo problema definir esta semana, vostedes probablemente vai ter unha chea de variables flotando. Non vai estar seguro de que todos eles significan nun determinado punto. Entón GDB vai realmente axudar en descubrir o que están todos igualando e ser capaz de ver que visualmente. Alguén está confuso sobre como calquera que estaba a traballar? Legal. Todo ben. Entón, despois diso, estamos vai mergullo na dereita en son catro diferentes tipo de tipo para esta semana. Como moitos de vostedes, en primeiro lugar de todo, antes de comezar, lin toda a especificación para pset3? Aceptar. Estou orgulloso de vós. Isto é como a metade da clase, que é significativamente máis que a última vez. 

Entón, iso é óptimo, porque cando falamos sobre o contido en lecture-- ou desculpe, en section-- me gusta para relacionar unha morea de que ao seu que o pset é e como quere aplicar tanto no seu pset. Entón, se vén tendo ler a especificación, que vai ser moito máis doado para ti entender o que eu estou falando de como digo, oh hey, iso pode ser un realmente bo lugar para aplicar este tipo. Así, aqueles de vostedes que leron o especs saber que, como parte da súa pset, vai ter que escribir un tipo de especie. Entón, iso pode ser moi útil para unha morea de ti hoxe. 

Entón, imos comezar con, Esencialmente, o tipo máis simple do tipo, o tipo de selección. O algoritmo típico para como iríamos facer isto é-- David pasou por todas de charla, entón eu vou moverse rapidamente ao longo aqui-- é esencialmente, ten ten unha matriz de valores. E entón atopar o menor valor sen clasificar e cambiar ese valor con o primeiro valor indiferenciados. E entón simplemente seguir repetir co resto da súa lista. 

E aquí está unha explicación visual de como funciona isto. Así, por exemplo, se tivésemos de comezar cunha serie de cinco elementos, índice 0 a 4, con 3, 5, 2, 6 e 4 valores colocado no array-- entón agora, nós só estamos indo a asumir que todos son indiferenciados porque non proba o contrario. 

Entón, como unha especie de selección faría traballo é que ía primeiro executado a través da totalidade da matriz indiferenciados. El escollía o menor valor. Neste caso, 3, dereita agora, é o menor. El está a 5. Non, 5 non é maior than-- ou desculpe, non é menos than-- 3. Así, o valor mínimo é aínda 3. E entón comeza a 2. O ordenador ve, oh, 2 é inferior a 3. 2 agora debe ser o valor mínimo. E así 2 swaps que o primeiro valor. 

Entón, despois de un pase, nós realmente ver que os 2 e os 3 son trocados. E nós só estamos indo a seguir fazê- este novo co resto da matriz. Entón, nós estamos indo só para percorrer os últimos catro índices da matriz. Imos ver o que é 3 o valor mínimo seguinte. Entón imos cambiar isto con 4. E entón nós só estamos indo a mantê- que atravesa ata que, finalmente, chegar a unha matriz clasificada en que 2, 3, 4, 5, e 6 son todos clasificados. Será que todo o mundo entender a lóxica de como unha especie de selección funciona? 

Só ten algún tipo dun valor mínimo. Está mantendo o control de o que é. E sempre que atopalo, vostede trocalo co primeiro valor na array-- ou non o primeiro value-- o seguinte valor na matriz. Legal. 

Entón, como vostedes tipo de viu dun breve reflexo, imos Pseudocódigo iso. Entón, se vostedes nas costas quere formar un grupo, todo nunha mesa pode formar un pequeno compañeiro, eu vou para dar a vostedes como tres minutos só para falar a través a lóxica, en inglés, de como podemos ser capaces de aplicar pseudocódigo para escribir unha especie de selección. E hai doces. Por favor, veña para arriba e obter doces. Se é na parte de atrás e quere doces, podo xogaba caramelos en ti. En realidade, facer legal vocę--. Oh, desculpe. Aceptar. 

Entón, se nós queremos, como unha clase, escrita pseudocódigo por canto se podería achegar este problema, só Sinto-se libre. Vou só ir ao redor e, a fin, peza aos grupos á seguinte liña de o que deberiamos estar facendo. Entón, se vostedes queren comezar fóra, que é o primeiro Que facer cando estás aplicar unha forma de solucionar este programa selectivamente para clasificar a lista? Nós só supor que teño unha matriz, todo ben? 

Audiencia: Quere crear algúns tipo de [inaudível] que é que atravesa toda a súa matriz. 

ANDI Pengo: Correcto. Entón vai querer facer unha iteración a través de cada espazo, non? Entón, gran. Se vós queredes darme o preto linha-- si, na parte de atrás. 

Audiencia: Verifique- todo para o menor. 

ANDI Pengo: Alí imos nós. Por iso, queremos pasar e comprobar a ver que o valor mínimo é, non? Eu estou indo a abreviar que a "min". O que vostedes queren facer despois atopou o valor mínimo? 

Audiencia: [inaudível] ANDI Pengo: Entón vai querer liga-lo co primeiro dese array, non? Ese é o comezo, eu vou dicir. Todo ben. Polo tanto, agora que xa cambiou o primeiro un, o que quere facer despois diso? Polo tanto, agora sabemos que este aquí debe ser o menor valor, non? Entón tes un descanso adicional da matriz que é indiferenciado. Entón, o que quere facer aquí, se caras queren darme a seguinte liña? Audiencia: Entón quere facer unha iteración a través do resto da matriz. ANDI Pengo: Si. E entón o que iterado tipo de implicar probablemente imos ter? Que tipo de-- 

Audiencia: Oh, unha variable adicional? ANDI Pengo: Probablemente outro loop for, non? Entón, nós estamos probablemente vai querer iterado through-- grande. E entón vai volver e probablemente comprobar o mínimo de novo, non? E vai estar repetindo iso, porque os loops só vai para manter funcionando, non? 

Entón, como podedes ver, nós pode ter un pseudocódigo xeral de como queremos que este programa para ollar. Este iterate aquí, que é o que nós tipicamente que escribir no noso código se queremos facer unha iteración a través dun matriz, o tipo de estrutura? Creo que Christabel xa dixen que antes. 

Audiencia: Un lazo for. 

ANDI Pengo: Un loop for? Exactamente. Polo tanto, este é, probablemente, vai ser un loop for. ¿Que é un cheque aquí vai implicar? Normalmente, se quere comprobar se algo é algo else-- 

Audiencia: Se. 

ANDI Pengo: Un se, non? E entón o intercambio aquí, imos pasar por riba máis tarde, porque David pasei por iso na charla tamén. E, a continuación, a segunda iteración implies-- 

Audiencia: Outra loop for. 

ANDI Pengo: --another para loop, exactamente. Entón, se nós estamos mirando neste correctamente, pode ver que estamos, probablemente, Vai ter un lazo é aninhado cunha declaración condicional alí e, a continuación, unha parte real de código que é indo para cambiar os valores. Entón eu só xeralmente escrito un código de pseudocódigo aquí. E entón imos realmente fisicamente, como unha clase, tentar implementar isto hoxe. Imos volver a este IDE. 

Uh-oh. Por que não-- aí está. Aceptar. Sentímolo, déixeme tentar ampliar un pouco máis. Alí imos nós. Todo o que eu estou facendo aquí é que eu creei un programa chamado "selección / sort.c." Eu creei unha matriz de nove valores, 4, 8, 2, 1, 6, 9, 7, 5, 3. Actualmente, como pode ver, son non-ordenada. n vai ser o número que dille a cantidade de valores ten na súa matriz. Neste caso, temos nove valores. E eu só teño un loop for aquí que imprime a matriz indiferenciados. 

E ao final, eu tamén teño un para loop que imprime-lo de novo. Entón, en teoría, se este programa funciona correctamente, ao final, ten que ver un impreso para o lazo en que 1, 2, 3, 4, 5, 6, 7, 8, 9 son todos correctamente en orde. 

Entón, nós temos o noso pseudocódigo aquí. Alguén quere para-- Eu son só indo a ir pedir volunteers-- me diga o que escribir se queremos, en primeiro lugar, só unha iteración ata o inicio deste array? Cal é a liña de código que eu son probablemente vai ter aquí? 

Audiencia: [inaudível] 

ANDI Pengo: Si, sinto libre a-- Sentímolo, vostede Non ten que estar up-- sensación libre para levantar a súa voz un pouco. 

Audiencia: Para int i é igual a 0-- 

ANDI Pengo: Si, boa. 

Audiencia: i é menor que a lonxitude de matriz. 

ANDI Pengo: Entón Lembre importa aquí, porque non ten unha función que dinos a lonxitude dunha matriz, nós xa temos un valor que almacena iso. Non? Outro aspecto a ter en mente-- nunha matriz de nove valores, cales son os índices? Nós só dicir que esta matriz era 0-3. Ve que a última índice é, en realidade, tres. Non é 4, aínda que non haxa catro valores na matriz. 

Entón aquí, temos que ter moito coidado que a nosa condición para a lonxitude vai ser. 

Audiencia: Non sería n menos 1? ANDI Pengo: Vai n menos 1, exactamente. Isto ten sentido, porque é n menos 1, todo o mundo? É porque as matrices son indexados cero. Comezan en 0 e executar ata n menos 1. Si, é un pouco complicado. Aceptar. E logo-- Audiencia: Isnt'1 que xa tomado coidado, porén, só por non dicir "inferior ou igual "e só dicir" menos que? " 

ANDI Pengo: Isto é un pregunta moi boa. Entón, si. Pero tamén, o xeito que somos aplicar o dereito de comprobar, precisa para comparar dous valores. Entón realmente quere deixar o "a" baleiro. Porque se comparar este, non vai ten algo despois que para comparar, non? Si. Entón i ++. Imos engadir nosos soportes en. Whoops. Gran. Polo tanto, temos o inicio do noso circuíto externo. Entón, agora nós probablemente quere crear unha variable para manter a par de menor valor, non? Alguén quere me dar o liña de código que faría iso? O que necesitamos se imos querer almacenar algo? 

Dereita. Quizais un nome mellor para que sería ser-- "temp" totalmente works-- quizais un máis apropiadamente chamado sería, se queremos que a menor value-- 

Audiencia: Min. ANDI Pengo: min, alí imos nós. min sería bo. E aquí, o que quere arrinque-lo para? Isto é un pouco complicado. Porque agora no inicio desta matriz, aínda non mirou para nada, non? Entón, o que, automaticamente, se estamos só no i é igual a 0, o que queremos para arrincar noso primeiro valor mínimo para? Audiencia: i. ANDI Pengo: i, exactamente. Christabel, por que queremos para iniciar-lo para min? 

Audiencia: Porque ben, estamos empezando 0. Entón, por que non temos nada para comparar que, o mínimo vai acabar sendo 0. 

ANDI Pengo: Exactamente. Entón, ela é exactamente correcto. Porque non temos realmente mirou para nada aínda, Non sabemos o que o seu valor mínimo é. Queremos só arrincar-lo para i, que, actualmente, está ben aquí. E mentres seguimos a baixar esa matriz, veremos que, con cada pase adicional, incrementa i. E así, nese punto, i seguramente a querer ser o menos, porque vai ser o que quere é o inicio da matriz sen clasificar. Legal. 

Entón, agora queremos engadir un loop for aquí que é vai percorrer a non clasificado, ou o resto da matriz. Alguén quere me dar un liña de código que faría iso? Hint-- o que necesitamos aquí abaixo? O que vai facer no presente para loop? Si. Audiencia: Entón nós quereríamos teñen un número enteiro diferente, porque estamos correndo o resto da matriz en vez do i, quizais por iso j. 

ANDI Pengo: Si, j soa ben para min. É igual? 

Audiencia: Entón sería eu máis 1, porque está comezando o próximo valor. E, a continuación, para o end --- novo, j é menos de n menos 1, e despois j ++. ANDI Pengo: Grande. 

E, a continuación, aquí, imos querer comprobar a ver se a nosa condición de ser cumprida, non? Porque quere cambiar o valor mínimo se é realmente menor que o que está comparando-a, non? Entón, o que imos querer aquí? Comproba a ver. Que tipo de declaración estamos probablemente vai ti quere empregar, se nós querer comprobar algo? 

Audiencia: Unha instrución if. 

ANDI Pengo: Unha instrución if. Entón se-- eo que será a condición de que queremos dentro do noso if? 

Audiencia: O valor de j é menor que o valor de i-- 

ANDI Pengo: Exactamente. Entón se-- de xeito que este conxunto é chamado de "matriz". Gran. Entón, se array-- que foi iso? Diga iso de novo. 

Audiencia: Se matriz-j é menor que matriz-i, entón poderiamos cambiar o min. Así, a min sería j. 

ANDI Pengo: Isto ten sentido? Aceptar. E agora aquí abaixo, nós, en realidade, quere aplicar o intercambio, non? Así recordar, a charla, que David, cando estaba tentando cambiar as-- o que era zume de laranxa ele-- e milk-- 

Audiencia: Iso foi gross. 

ANDI Pengo: Si, iso foi tipo de Gross. Pero foi unha boa fermosa concepto demostrando tempo. Entón, pense de seus valores aquí. Ten unha matriz de minutos, unha serie de i, ou o que estabamos intentando cambiar aquí. E probablemente non pode derramar-los entre eles, á vez, a dereita? Entón, o que imos a necesidade de crear aquí a fin de cambiar os valores correctamente? 

Audiencia: Unha variable temporal. 

ANDI Pengo: Unha variable temporal. Entón imos facer int temporal. Mira, iso sería unha mellor tempo a-- Whoa, o que foi iso? Aceptar. Polo tanto, esta sería unha mellor tempo para nomear o "tempo." variable Entón imos facer int temporal. Que imos Definir temp igual a aquí? Audiencia: Min? ANDI Pengo: É un pouco complicado. Realmente non importa ao final. Non importa o que orde que escoller para intercambiar en desde que está facendo certo que é manter o control do que está cambiando. 

Audiencia: Podería ser gama-i. 

ANDI Pengo: Si, imos facer matriz-i. E entón, cal é a seguinte liña de código que queremos ter aquí? Audiencia: array-i é igual a matriz de j. ANDI Pengo: E para rematar? Audiencia: array-j é igual a matriz-i. Audiencia: Ou matriz j iguais matriz de temp-- ou, temporal. 

ANDI Pengo: Aceptar. Entón, imos realizar este e mira se está indo para o traballo. Onde é que está a suceder? Oh, iso é un problema. Vexa, na liña 40, estamos intentando usar matriz-j? Pero onde é que j só existen en? 

Audiencia: Con loop for. ANDI Pengo: Correcto. Entón que é o que imos facer? 

Audiencia: Establecer fóra as-- Audiencia: É, eu creo que ten para usar outra instrución if, non? Así como, se o minimum-- todo ben, déixeme pensar. 

ANDI Pengo: Caras, proba para dar un ollo Déixanos Mira, o que é algo que podemos facer aquí? 

Audiencia: Aceptar. Polo tanto, se o mínimo non é igual j-- así aínda que o mínimo é i-- non teriamos que cambiar. 

ANDI Pengo: Será que a igualdade i? O que quere dicir aquí? 

Audiencia: Ou si, se o mínimo non é igual a min, si. ANDI Pengo: Aceptar. Ben, iso resolve, tipo, os nosos problemas. Pero iso non resolve o problema que acontece se j-- desde j non existe fóra del, o que vostede que queremos facer con el? Declaralo la fóra? Imos tentar executar este. Uh-oh. Nosa especie non funciona. 

Como verás, o noso principal matriz tiña eses valores. E despois, debe ter foi o 1, 2, 3, 4, 5, 6, 7, 8, 9. Non funciona. Ahh. O que imos facer? Audiencia: Debug. ANDI Pengo: Todo ben, podemos tentar iso. Podemos depurar. Aumentar un pouco. Imos definir o noso punto de interrupción. Imos Aceptar como--. 

Entón, por que xa sabemos que estas liñas, 15 a 22, son working-- porque todo o que eu estou facendo é só iterado e printing-- I pode ir adiante e ignorar isto. Imos comezar na liña 25. Oop, deixe-me librar diso. 

Audiencia: Entón, desde o punto de interrupción onde a depuración comeza? ANDI Pengo: ou para. Audiencia: ou para. ANDI Pengo: Si. Podes establecer varios puntos de interrupción e pode simplemente saltar dun a outro. Pero neste caso non sabemos onde o erro está pasando. Entón, nós só queremos comezar de arriba abaixo. Yep. Aceptar. 

Entón esta liña aquí, podemos intervir. Podes ver aquí en baixo, temos unha matriz. Estes son os valores que están na matriz. Ve que, como índice de 0, el corresponde ao value-- oh, Vou tentar facer zoom. Sentímolo, é realmente difícil para see-- na matriz índice 0, que ten un valor de 4 e entón así por diante e así por diante. Temos as nosas variables locais. Agora é igual a 0, o que queremos que sexa. 

E así imos seguir percorrendo. O noso mínima é igual a 0, que nós tamén queremos que sexa. E, entón, entrar no noso segundo para ciclo, a matriz-j é inferior a matriz-i, que non era. Entón, se ves como que pulou iso? 

Audiencia: Entón debe ser o caso mínimo, todo isso-- que non debe estar dentro do primeiro para o loop? ANDI Pengo: Non, porque aínda quere probar. Quere facer unha comparación cada tempo, mesmo despois de pasar por ela. Non só quere facelo na primeira pasaxe. Quere facelo con cada paso adicional de novo. Entón quere comprobar a súa condición dentro. Entón, nós só estamos indo a continuar executando por aquí. Vou dar a vostedes unha información. Ten que ver co feito de que, cando está comprobando a súa condicional, non está comprobando ao índice correcto. Entón, agora está comprobando a índice de matriz de j é inferior a matriz Índice de i. Pero o que está facendo enriba o inicio do loop for? Non está definindo j igual a min? 

Si, para que poidamos realmente saír do depurador aquí. Entón, imos dar un ollo ao noso pseudocódigo. For-- imos comezan en i é igual a 0. Estamos indo para ir ata n menos 1. Imos comprobar si temos ese dereito? Si, iso era certo. 

Así, pois, aquí dentro, estamos vai crear un valor mínimo e establecer que igual a i. Será que imos facelo? Si, fixen iso. Agora, no noso interior loop for, estamos vai facer j é igual a i n menos 1. Será que imos facelo? En realidade, nós fixemos iso. 

Entón, con todo, o que estamos comparando aquí? 

Audiencia: j +1. ANDI Pengo: Exactamente. E entón vai querer definir o mínimo igual a 1 j máis ben. Entón eu pase por iso moi rapidamente. Vostedes entenden por iso que é j + 1? Aceptar. 

Así, na súa matriz, en súa primeira pasaxe, o loop for, por int i é igual a 0, imos só asumir este non cambiou aínda. Temos unha matriz de, por completo, só catro elementos non ordenados, non? Por iso, queremos iniciar i igual a 0. E eu vai só percorrer este loop. E así na primeira pasaxe, imos para iniciar unha variable chamada "min" que tamén é igual a I porque non temos un valor mínimo. Entón, iso é actualmente igual a 0 tamén. E entón nós imos pasar. E queremos facer unha iteración novo. Agora que descubrimos que o noso mínimo é, queremos para percorrer de novo para ver se está comparando, non? Entón, j, aquí, vai igual a I, o cal é 0. E, a continuación, a matriz j máis eu, que é o que é o seguinte máis, como menos que o seu mínimo actual valor é, quere cambiar. 

Entón, imos só dicir que temos ten, como, 2, 5, 1, 8. Agora, i é igual a 0 e j é igual a 0. E ese é o noso valor mínimo. Se matriz-j máis i-- polo que se o iso é despois que nós estamos mirando para é maior que o anterior, que vai chegar a ser o mínimo. 

Entón aquí vemos que 5 non é menos que iso. Entón, que vai non ser 5. Vemos que 1 sexa inferior a 2, non? Polo tanto, agora sabemos que o noso mínimo é será o valor do índice 0, 1, 2. Si? E entón cando chegar aquí, podes cambiar os valores correctos. 

Entón, cando vostedes estaban só tendo o j antes, non estaban mirando para o despois dela. Estabas buscando o mesmo valor, que É por iso que, sinxelamente, non estaba facendo nada. Isto ten sentido para todos, por iso que necesitamos que máis dun alí? Aceptar. Agora imos correr con el para facer seguro de que o resto do código é correcto. Por que é que pasa? Ah, é o min aquí. Que estaban comparando o valor incorrecto. Oh, non. 

Ah, si, aquí nós trocando os valores errados ben. Porque estabamos buscando i e j. Estes son os que foron merecen unha visita. Nós realmente quere cambiar o mínimo, o mínimo actual, co que o exterior é. E, como podedes ver a continuación aquí temos unha matriz clasificada. El só tiña que ver con o feito de que cando estabamos comprobando o valores que foron comparando, nós non estabamos mirando para os valores correctos. Que estaban mirando para a mesma aquí, non, en realidade, cambiando-lo. Ten que mirar para un lado para el e, a continuación, pode cambiar. Entón é iso que era unha especie de incomodando noso código antes. E o que eu fixen aquí é todo o depurador podería facer para ti Eu só fixen isto no tarxeta, porque é máis fácil para ver en vez de tratar de para facer zoom e depurador. Isto ten sentido para todos? Legal. 

Todo ben. Podemos pasar falar notación asintótica, que é só un xeito elegante de dicir o tempos de execución de todo tipo desas. Entón eu sei David, en charla, aflorados tempos de execución. E pasou por toda a fórmula de como calcular os tempos de execución. Non se preocupa con iso. Se vostede é realmente curioso sobre como funciona isto, sexa a vontade para falar comigo despois sección. Podemos camiñar por as fórmulas xuntos. Pero todos vós ten que realmente sei é que n ao cadrado sobre 2 é o mesmo que n ao cadrado. Debido ao maior número o expoñente máis crece. E así para os nosos propósitos, todos nos preocupa é que o número xigante que é evidente. 

Entón, cal é o mellor caso runtime de selección tipo? Se indo para ter para percorrer unha lista e entón percorrer resto da lista, cantas veces son vai probablemente no peor na case-- mellor caso, sorry-- percorrer? Quizais a mellor pregunta é para preguntar, o que é o peor caso runtime de selección de clasificación. Audiencia: n ao cadrado. ANDI Pengo: É n ao cadrado, certo. Entón, un xeito doado de pensar niso é como, calquera momento ten dúas noutras citas para loops, que vai ser n ao cadrado. Porque non só é vostede que funciona a través de unha vez, ten que volver volta e correr con el unha vez dentro de cada valor. Entón, nese caso, está executando n veces n ao cadrado, que é-- sorry, n veces n, o que equivale n ao cadrado. 

E tipo é tamén un pouco única no sentido que non importa se estes valores xa están en orde. Aínda vai correr a través de calquera maneira. Nós só dicir que este foi de 1, 2, 3, 4. Independentemente de que estean ou non foi en fin, aínda tería percorreu e aínda verificou o valor mínimo. El faría o mesmo número de cheques en cada momento, aínda que non chegou a tocar nada. 

Así, en tal caso, o mellor eo peor tempos de execución son realmente equivalentes. Así, o tempo de execución espera selección de tipo, que designamos polo símbolo de teta, teta, neste caso, tamén sería n ao cadrado. Os tres destes serían n ao cadrado. Claro que todos de por o tempo de execución é n ao cadrado? 

Todo ben. Entón, eu estou indo só para executar rapidamente polo resto das sortes. O algoritmo para burbulla sort-- lembre, este foi o primeiro David, pasando en charla. Esencialmente, pisa a listaxe e swap-- só comparar dous á vez. E se un é maior, que acaba de trocalos. Entón, se estes son grandes, vostede trocaría. Teño oficial aquí. 

Entón, imos só dicir que tiña 8, 6, 4, 2. Ía comparar a 8 e un 6. Necesitará trocalos. Podería comparar a 8 e un 4. Necesitará trocalos. Se ten que trocar a 8 e 2, cambia-los tamén. Así, en tal sentido, verás, vai fóra ao longo dun longo período de tempo, como o tipo de burbulla de valores os extremos, o que é por iso que chamamos bubble sort. 

Nós só ía percorrer de novo en nosa segunda pasaxe, ea nosa terceira paso, ea nosa cuarta pasaxe. Esencialmente, bubble sort só corre ata que non facer máis swaps. Entón, nese sentido, este é só o pseudocódigo xeral para el. Non te preocupes, estes serán todos liña. Non temos que ir realmente sobre iso. 

Nós só arrincar un contador variable que comeza en 0. E nós iterado a través de toda a matriz. E se un valor é-- este valor é maior que aquel valor, está indo para trocalos. E entón é só continuará. E está indo a contar. E está indo só para seguir facendo este mentres o contador é maior a 0, o que significa que cada vez que ten que cambiar, vostede sabe que quere ir cara atrás e comprobar de novo. Quere manter a verificación ata que vostede sabe que non ten que cambiar máis. 

Entón, cales son os mellores e peores caso tempos de execución para bubble sort? E hint-- esta é realmente diferente tipo de selección no sentido que estas dúas respostas non son os mesmos. Pense sobre o que acontecería en un caso, se xa foi resolto. E pensar sobre o que que acontecería se fose no caso de que non foi resolto. E pode tipo de correr través de por que isto está a suceder. Vou dar a vostedes, tipo, 30 segundos para pensar sobre iso. 

Aceptar. Alguén ten un palpite sobre o que o peor caso de tempo de execución de bubble sort é? Si. 

Audiencia: sería, como, n veces n menos 1 ou algo así? Como cada vez que se executa, é só como un intercambio de menos que quere que fose. 

ANDI Pengo: Si, entón está totalmente certo. E este é un caso en que a súa resposta foi realmente máis complexo que o que ten que dar. Entón vai para run-- son vai borrar todo isto aquí. Está todo o mundo ben? Podo borrar isto? Aceptar. Vai percorrer n veces por primeira vez, non? E eles están indo a ser executado a través n menos 1 segundo tempo, non? E entón está indo a mantê- indo, n mina 2, etcétera. David fixo nunha charla, onde, se engadiu-se todos estes valores, comeza algo que é como-- yeah-- máis de 2, que, esencialmente, só reduce ata n ao cadrado. Está indo a obter un fracción estraño dentro. E así só sei que a n ao cadrado sempre ten precedencia sobre a fracción. E así, neste caso, o peor tempo de execución sería n ao cadrado. Se fose descendente fin, pense, vostede Ten que facer un intercambio de cada vez. 

Cal sería, potencialmente, o mellor caso de tempo de execución? Nós só dicir que, se a lista xa foi en orde, o que podería ser o tempo de execución? 

Audiencia: n. ANDI Pengo: É n, exactamente. E por que é n? Audiencia: Porque só ten que comprobar en cada vez. ANDI Pengo: Exactamente. Así, no mellor execución posible, se esta lista xa foi sorted-- digamos 1, 2, 3, 4-- vostede sería só pasar, que ía comprobar, ía ver, oh, todos eles pan out. Eu non tiven que cambiar. Rematei. Entón, nese caso, é só n ou o número de pasos que acaba tiña que comprobar na primeira lista. 

E despois, xa alcanzou tipo de inserción, onde o algoritmo é esencialmente a dividir Lo nunha parte clasificada e indiferenciados. E a continuación, un por un, os valores son indiferenciados inserida na súa axeitada posicións no inicio da lista. 

Así, por exemplo, temos unha Lista de 3, 5, 2, 6, 4 de novo. Sabemos que é actualmente indiferenciados porque temos só comecei a ollar para el. Imos dar un ollo e sabemos que o primeiro valor é ordenada, non? Se vostede está só mirando para unha variedade de tamaño un, xa sabe que está clasificada. 

Entón sabemos que o outros catro son indiferenciados. Pasamos por e vemos ese valor. Imos volver. Mira que o valor de 5? Imos dar un ollo niso. Nós comparalos-lo a 3. Sabemos que é maior que 3, polo que sabemos que isto está clasificado. Polo tanto, sabemos que os dous primeiros son clasificadas e os tres últimos non son. 

Imos dar un ollo a dous. Primeiro imos comprobar iso con cinco. É menos que 5? Non é. Entón temos que estar mirando cara a abaixo. A continuación, comprobar 2 off 3. É menos que? Non. Entón, vostede sabe a 2 ten que ser inserido na parte de diante e 3 e 5 ambos teñen que ser empurrados para fóra. Faino novo con 6 e 4. E nós só manter a verificación, esencialmente, onde pode comprobar, comprobación, verificación. E ata que sexa na dereita posición, que tipo de só introduza o na posición correcta, que é onde o nome veu. 

Entón, iso é só o algoritmo, pseudocódigo per se, tipo, en como iríamos aplicar un tipo de inserción. Pseudocódigo é aquí. É todo en liña. Non te preocupes se vostedes son intentando copiar este abaixo. Entón unha vez máis, aínda que question-- sería a mellor e peor tempos de execución para inserción tipo? É moi semellante á última pregunta. Vou dar a vostedes, tipo, 30 segundos para pensar sobre iso tamén. 

Aceptar Alguén quere dáme o peor tempo de execución? Si. 

Audiencia: n ao cadrado. 

ANDI Pengo: É n ao cadrado. E por que n ao cadrado? 

Audiencia: Porque en orde inversa, ten pasar por n veces n, que é-- ANDI Pengo: Si, exactamente. Entón, aínda que na bubble sort. Se esta lista está orde decrecente, es terá que comprobar primeiro posto. E, a continuación, con toda valor adicional, está terá que comprobar se contra cada valor único, non? E así por completo, está indo facer un n veces pasar outro n pasou, e que n é cadrado. E sobre o mellor caso? Si. 

Audiencia: n menos 1, xa que o primeiro xa é elevado ao cadrado. 

ANDI Pengo: Entón, pechar. A resposta é, en realidade, n. Porque mentres a primeira é clasificadas, non pode Actually --- lo nós só tivemos sorte, en Nese exemplo que dous pasou a ser o menor número. Pero isto non sempre será así. Se 2 xa está clasificado no inicio pero mira e hai un un aquí, o 1 vai bater-lo. E iso vai acabar sendo chocar de calquera maneira. 

Así, no mellor dos casos, é realmente só vai ser n. Se ten 1, 2, 3, 4, 5, 6, 7, 8, está vai percorrer que lista enteira xa para comprobar a ver se está todo ben. Claro que todos na carreira tempos de selección tamén? Sei que estou pasando estes realmente rápido. Pero só sei que se sabe o conceptos xerais, ten que ser bo. Aceptar. Entón eu vou dar a vostedes quizais, como, un minuto para falar cos seus veciños sobre o que son só algunhas das principais diferenzas entre estes tipos de tipos. Nós falaremos sobre iso en breve. Audiencia: Oh, Aceptar. ANDI Pengo: Si. Aceptar. Cool, imos reunir de novo coa clase. Aceptar. Polo tanto, este foi un tipo de pregunta aberta cara que hai moitas respostas a elas. E nós imos pasar por riba de algúns deles brevemente. Eu só quería que obteña caras pensar sobre o que diferenciou os tres tipos de tipos. E oín, tamén, unha gran question-- o que merge sort facer? Boa pregunta, porque iso o que estamos cubrindo seguinte. 

Así é o merge sort un tipo que funciona moi diferente dos outros tipos. Como podedes see-- David fixo aquela demo onde tiña todo o legal ruídos de ver como mesturar tipo foi, como, infinitamente máis rápido que os outros dous tipos? Aceptar. Entón, iso é debido a fusión tipo aplica esa división e conquistar concepto que temos falou sobre unha morea na charla. Neste sentido que nos gusta de traballar máis intelixente, non máis difícil, cando divide e conquistar problemas, e rompe-las abaixo, e, a continuación, poñelos xuntos, cousas boas sempre acontecen. 

Así, a forma que se funden tipo esencialmente funciona é que divide un matriz sen clasificar á metade. E entón el ten dúas metades de matrices. E só clasifica estas dúas metades. El só segue dividindo á metade, en metade, polo medio ata que todo está clasificada e, a continuación, de forma recursiva pon todo iso xunto. 

Entón iso é moi abstracto. Polo tanto, este é só un pouco de pseudocódigo. Isto ten sentido en o xeito no que está en execución? Entón, imos só dicir que ten un matriz de n elementos, non? Se n é inferior a 2, pode voltar. Porque sabe que, se hai só unha cousa, debe ser clasificado. Senón, clasificar a metade esquerda, e entón clasificar a metade dereita, e entón fundirse. 

Así, mentres que parece realmente fácil, en realidade, a pensar que é tipo de difícil. Porque é como, ben, este é o tipo de execución en si. Non? Funciona en si. Entón, nese sentido, David tocou sobre a recursividade en clase. E iso é un concepto imos falar máis. É que este, estas dúas liñas aquí, en realidade, é só o programa dicindo que sexa executado en si con entrada diferente. Entón en vez de executar-se con a totalidade de n elementos, pode rompe-lo para abaixo na metade esquerda e metade dereita e, a continuación, executa-lo de novo. 

E entón nós imos ollalo visualmente, porque son un aprendiz visual. Funciona mellor para min. Entón, imos ollar para un exemplo visual aquí. 

Imos dicir que temos unha matriz, seis elementos, 3, 5, 2, 6, 4, 1, non clasificados. Todo ben, hai moita cousa nesta páxina. Entón, se podedes mirar o primeiro paso aquí, 3, 5, 2, 6, 4, 1, podes división lo ao medio. Ten 3, 5, 2, 6, 4, 1. Vostede sabe que estes aren't-- vostede Non sei se eles están ou non clasificados, para que manteña dobres-as, polo medio, no medio, á metade, ata que finalmente, só ten un elemento. E un elemento sempre clasificada, non? 

Entón, nós sabemos que 3, 5, 2, 4, 6, 1, por si só, son clasificadas. E agora podemos xunto a eles de novo. Entón, nós sabemos a 3, 5. Poñemos estes xuntos. Sabemos que é clasificada. Os 2 aínda está alí. Podemos poñer o 4 eo 6 xuntos. Sabemos que isto está clasificado, por iso, poñer isto en conxunto. E a 1 existe. 

E entón simplemente ollar para estas dúas metades dereita aquí. Ten a 3, 5, 2, 2, 3, 5. Pode simplemente comparar o comezo de todo. Porque sabe que isto é separado e vostede sabe que isto está clasificado. Entón non ten que mesmo comparar a 5, que acaba de comparar a 3. E o 2 é inferior a 3, así vostede sabe que 2 debe ir ao final. 

O mesmo por alí. A 1 debe ir aquí. E entón, cando vai para poñer estes dous valores, vostede sabe que isto é separado e vostede sabe que que está clasificada. Entón a 1 eo 2, o 1 sexa inferior a 2. Isto dille que o 1 debe percorrer a finais desta sen sequera ollar para 3 ou 5. E entón a 4, pode só vaia, que vai cara a dereita aquí. Non ten que mirar para o 5. Mesmo co 6. Vostede sabe que a 6-- só Non ten que ser ollado. 

E así, desa forma, é salvándose só unha morea de pasos cando está comparando. Non ten que comparar cada elemento contra outros elementos. Só comparar contra os que precisa para comparar contra. Entón, ese é o tipo de un concepto abstracto. Non te preocupes se non é bastante baterlle aínda dereita. Pero, xeralmente, este é como unha especie de fusión funciona. Preguntas, preguntas rápidas, antes de seguir adiante? Si. 

Audiencia: Entón dixo que se toma a 1, e logo a 4, eo 6 e poñer-los en. Polo tanto, non son non son those-- ollar para eles como elementos separados, e non como o todo? ANDI Pengo: Si. Entón, o que está pasando é que, basicamente, está creando unha nova matriz. Entón vostede sabe que, aquí, eu teño dúas matrices de tamaño 3, non? Entón, vostede sabe que a miña matriz clasificada ten que ter seis elementos. Entón acaba de crear unha nova cantidade de memoria. Entón é tipo como de sendo unha perda de memoria, pero iso non importa porque é tan pequeno. Entón mira para o 1 e mira para o 2. E vostede sabe que o 1 sexa inferior a 2. Entón vostede sabe que un debe ir o inicio de todo isto. 

Non precisa aínda de ollar para a 3 e 5 a. Entón vostede sabe que un vai alí. Entón basicamente cortar a 1. É, tipo, morto para nós. Entón só temos 2, 3, 5, e, a continuación, 4 e 6. E entón vostede sabe que, comparar a 4 ea 2, Oh, o 2 debe ir máis alá. Entón plop a 2 para abaixo, corte-lo. Entón, polo que só ten a 3 eo 5 no 4 e 6 a. E continúa cortando-off ata que colocalos na matriz. 

Audiencia: Entón é só sempre comparando o [inaudível]? 

ANDI Pengo: Exactamente. Entón, nese sentido, é só comparando, esencialmente, un número contra o outro número. E porque sabe que está clasificada, vostede Non ten que ollar a través de todos os números. Vostede só ten que ollar para o primeiro. E entón podes só plop Los abaixo, porque sabe pertencen a onde se deben de pertencer. Si. Boa pregunta. 

E, a continuación, se algún de vós son un pouco ambicioso, Sinto-se a liberdade de ollar para este código. Esta é realmente a implantación física de como ía escribir merge sort. E podes ver, é moi curto. Pero as ideas detrás que son moi complexas. Entón, se pensas vontade de deseñar iso na súa lección de casa esta noite, Sinto-se libre para. 

Aceptar. Entón David tamén pasou por iso na charla. O que é o mellor caso tempos de execución, peores tempos de execución de caso, e os tempos de execución esperadas merge sort? Un par de segundos para pensar. Iso é moi difícil, pero o tipo de intuitiva se pensar sobre iso. Todo ben. 

Audiencia: É o peor caso n log n? ANDI Pengo: Exactamente. E por que é n log n. 

Audiencia: Non é porque faise máis rápido de forma exponencial, polo que é como unha función que en vez de simplemente ser n cadrado ou algo así? ANDI Pengo: Exactamente. Así, a razón pola que o runtime sobre iso é log n n é porque-- o que é vostede facendo en todos estes pasos de? Só está cortando-o ao medio, non? E así, cando estamos facendo o rexistro, todo o que está facendo está dividindo un problema no medio, polo medio, na metade, en máis metades. E, nese sentido, pode tipo de eliminar o modelo lineal que temos que chegou a empregar. Porque cando chop cousas pola metade, é un rexistro. Isto é só a matemática xeito de representalo. 

E entón, finalmente, ao final, é só facendo unha última pasaxe para poñer todos eles en orde, non? E por iso, se só ten que comprobar unha cousa, que é n. E entón está tipo de multiplicando os dous xuntos. Entón, é como ten que Final vaia n abaixo aquí cun rexistro de n aquí enriba. E se multiplicar eles, que é n log n. 

E así o mellor eo peor caso caso e espera son todos n log n. Tamén como outro tipo. É como especie selección no sentido de que Non importa o que o seu lista é, el só vai para facer o mesmo en cada momento. Aceptar. Entón, como podedes ver, aínda que tipo que temos ido through-- n cadrado, non é moi eficiente. E mesmo ese log n n é non é o máis eficiente. Se vostedes son curiosos, hai mecanismos de ordenación que son tan eficaces que son case esencialmente plana en tempo de execución. 

Ten un pouco de rexistro n. Ten algunha rexistro log n de. Non toque sobre eles nesta clase agora. Pero se vostedes están curiosos, Sinto-se libre para Google, o que é os mecanismos de selección máis eficientes. Non sei, hai algúns realmente divertido, como-- hai algúns realmente máis divertido que as persoas fan. E quere saber como Nunca pensei niso. Entón, Google, se ten algunha reposición tempo, en, cales son algunhas formas divertidas que así como pessoas-- eficientes persoas ways-- foron capaces de aplicar os tipos. Aceptar. E aquí está un pouco gráfico útil. Sei que todos vostedes, antes de que proba 0, estará no seu cuarto, probablemente, intentando para memorizar que. Entón, iso é bo alí para vós. Só non esqueza a lóxica que made-- por que estas cifras estaban ocorrendo. Se está sempre perdido, pode facer se sabe o que tipo son. E pode realizar a través los na súa mente para descubrir por que os respostas son esas respostas. 

Todo ben. Entón, nós estamos indo a ir en fin, para a investigación. Porque, como aqueles de vostedes que leron o pset, investigación tamén forma parte da problema desta semana define. Lle será solicitada a aplicar dous tipos de investigación. Un deles é unha investigación lineal e é unha investigación binaria. 

Así, a procura lineal é moi fácil. Só quere buscar elemento dunha lista para ver se obtelo. Só ten para percorrer. E se é igual a algo, pode simplemente devolve-lo, non? Pero o que somos máis interesado en falar é a procura binaria, á dereita, que é a dividir e conquistar mecanismo que David estaba demostrando en conferencia. 

Teña en conta que o exemplo do libro de teléfono que segue traendo á tona, o que medio que se esforzou un pouco sobre o ano pasado, onde dividir o problema á metade, ao medio, polo medio, unha e outra vez, ata atopar o que estás buscando? E ten o runtime que ben. E podes ver, é significativamente máis eficiente do que calquera outro tipo de investigación. 

Así, a forma que nós ía sobre execución dunha investigación binaria é, se nós tivésemos unha matriz, índice de 0 a 6, sete elementos, podemos ollar no medio, direita-- Sentímolo, se a nosa pregunta first-- se queremos facer a pregunta de, fai a matriz conter o elemento de 7, Obviamente, sendo o ser humano, e tendo tales unha pequena variedade, é fácil para nós para dicir si. Pero o xeito de aplicar un binario busca sería a de mirar no medio. 

Sabemos que o índice 3 é no medio, porque sei que hai sete elementos. O 7 dividido por 2? Pode cortar ese extra 1. Ten tres no medio. Entón é matriz de 3 igual a 7? Non é, non? Pero podemos facer un par de cheques. É gama de 3 a 7 ou menos 3 é de matriz maior que 7? 

E sabemos que é inferior a 7. Entón, nós sabemos que, oh, debe non estar na metade esquerda. Sabemos que debe ser na metade dereita, non? Así, podemos só cortar a metade do array. Nós nin sequera teñen que máis ollar para ela. Porque sabemos que metade do noso problema-- sabemos que a resposta está a metade dereita do noso problema. Polo tanto, basta ollar para iso agora. 

Entón, agora miramos para o medio do que restou. Este índice 5. Nós facemos a mesma verificación de novo e vemos que é menor. Entón, nós miramos á esquerda do que iso. E entón vemos que cheque. É o valor da matriz en índice 4 igual a 7? É. Así, podemos volver certo, porque atopamos o valor da nosa lista. Será que a forma que eu atravesei que ten sentido para todos? Aceptar. Vou dar a vostedes quizais, como, tres, catro minutos para descubrir Pseudocódigo como este no. 

Entón imaxine eu lle pedín para escribir chamado función search () que retornaron un valor, un valor booleano, iso era verdade ou false-- como, certo se atopou a valor, falso se non fixo. E entón estaba pasou por valor ti busca en valores, que é o array-- Oh, eu sempre poñer que no lugar incorrecto. Aceptar. En calquera caso, que debe ter foi á dereita de valores. E, a continuación, int n é o número de elementos desa matriz. Como ía sobre o intento Pseudocódigo para este problema en? Vou dar a vostedes como tres minutos para facelo. Non, eu creo que hai only-- si, hai un aquí enriba. Audiencia: Podo? ANDI Pengo: Si, eu teño ti. É que traballar? OK, legal. 

Aceptar. Todos os mozos certos, somos vai control-lo. Aceptar. Entón asumir que temos esta linda pouco matriz con valores de n na mesma. Non deseñar as liñas. Pero como é que imos sobre intentando escribir isto? Alguén quere dáme a primeira liña? Se quere me dar o primeira liña deste pseudocódigo. 

Audiencia: [inaudível] Audiencia: Vostede vai querer iterado through-- Audiencia: Só un para loop? Audiencia --para. 

ANDI Pengo: Entón, este é un pouco complicado. Pense about-- quere para continuar executando ese loop unha e outra vez ata cando? 

Audiencia: Ata o [inaudível] valor que é igual ao valor. ANDI Pengo: Exactamente. Entón pode realmente só write-- podemos incluso simplifica-lo máis. Podemos só facer un loop while, non? Entón podes só ter loop-- sabemos que é un tempo. Pero, por agora, eu vou para dicir "lazo" - a través do que? Lazo que é until-- nosa condición terminando? Creo que oín-lo. Oín a alguén dicir iso. 

Audiencia: Valores iguala medio. ANDI Pengo: Diga iso de novo. Audiencia: Ou, ata o valor que está a buscar para coincide co valor medio. 

ANDI Pengo: O que se non está alí? E se o valor que está a buscar para non é realmente nesa matriz? Audiencia: Vostede retorna 1. 

ANDI Pengo: Pero o que queremos loop ata que se nos ten unha condición? Si. 

Audiencia: Ata que haxa só un valor? ANDI Pengo: Pode facer un loop until-- para que vostede sabe que é terá un valor máximo, non? E vostede sabe que está indo para ter un valor min, non? Porque tamén, iso é algo Eu esquezo de dicir antes, que algo que é crítica sobre busca binaria é que a súa matriz xa está clasificado. Porque non hai ningunha forma de fazê- iso se son só valores aleatorios. Non sabe se é maior que o outro, non? 

Entón, vostede sabe que o seu máximo e seus mins está aquí, non? Se vai estar adaptándose seu máximo nos seus minutos e os mid-- imos asumir o seu valor medio é aqui-- dereita está indo a basicamente loop ata a súa mínima é de sobre o mesmo como o seu máximo, á dereita ou se o máximo non é o mesmo que o seu min. Non? Porque cando isto ocorre, xa sabe que ti, finalmente, acadar o mesmo valor. Entón quere facer un loop ata que o seu min é inferior ou igual a-- oops, non menos que ou igual a, a outra forma é circundar-- max. 

Será que isto ten sentido? I levou algúns intentos para obter este dereito. Pero loop ata que o seu valor máximo é esencialmente case menos ou igual a seu mínimo, non? Isto é cando vostede sabe que xa converxer. Audiencia: Cando sería o seu máximo valor pode ser inferior ao mínimo? ANDI Pengo: Se mantén axustándose o, o que é o que nós estamos indo estar facendo neste. Isto ten sentido? Mínimo e máximo son só enteiros que son, probablemente, Vai querer crear para manter o control de onde nós estamos mirando. Como a matriz existe independentemente do que estamos facendo. Como, non estamos fisicamente decepar a matriz, non? Estamos só axustando onde estamos mirando. Isto ten sentido? 

Audiencia: É. 

ANDI Pengo: Aceptar. Entón, se esa é a condición para o noso loop, o que queremos dentro deste loop? O que imos estar querendo facer? Entón, agora, temos un máximo e un mínimo, dereito, Probablemente creouse aquí nalgún lugar. Nós imos probablemente quere para atopar un medio, non? Como é que vai ser capaz de atopar o medio? Cal é a mathematical-- Audiencia: Max ademais min divididos por dous. ANDI Pengo: Exactamente. Isto ten sentido? E que vós ver porque non só use-- por que fixemos iso no canto de facer só n dividido por 2? É porque n é un valor que se ve na mesma. Non? Pero porque axustamos nosa mínimo e valores máximos, van cambiar. E, como resultado, o noso medio vai cambiar tamén. Entón é por iso que queremos para facelo aquí. Aceptar. 

E entón, agora que atopamos our-- si. 

Audiencia: Só un question-- rápida cando di min e max, asumindo que estamos xa está clasificado? 

ANDI Pengo: Si, iso é realmente unha condición previa para unha busca binaria, que ten que saber que está clasificada. É por iso que tipo, escribe no seu conxunto de problemas antes da súa procura binaria. Aceptar. Polo tanto, agora que sabemos onde noso punto medio é, o que quere facer aquí? 

Audiencia: Queremos comparar que para o outro. ANDI Pengo: Exactamente. Entón está indo para comparar mediados de valor, non? E que dicir iso nós cando se comparan? O que queremos facer despois? 

Audiencia: Se o valor é maior de mediados dos anos, queremos corte-lo. ANDI Pengo: Exactamente. Entón, se o valor é maior de mediados dos anos, estamos Vai querer cambiar esas Maxes mínimo e, non? O que queremos cambiar? Entón, se sabemos o valor está nalgún lugar aquí, o que que cambiar? Queremos cambiar a nosa mínimo a ser mid, non? E entón outra cousa, se é neste metade, o que queremos cambiar? 

Audiencia O seu máximo. ANDI Pengo: Si. E entón só vai para manter looping, non? Porque agora, despois dunha iteración través, ten un máximo aquí. E entón podes recalcular un mid. E entón podes comparar. E está indo a seguir ata os minutos e as Maxes ter esencialmente converxentes. E iso é cando vostede sabe que bateu o fin de todo. E quere vostede encontrou- ou non ten nese momento. 

Será que isto ten sentido para todos? Aceptar. Isto é moi importante, porque vai ter para escribir isto no seu código de esta noite. Pero vós teñen unha boa sensación de que debería estar facendo, o que é bo. Aceptar. Entón, nós temos uns sete minutos sección esquerda. Entón, nós estamos indo falar este pset que estaremos facendo. Así, o pset divídese en dúas metades. A primeira parte implica a posta en marcha dun find no que escribe unha busca lineal, un busca binaria, e un algoritmo de ordenación. 

Polo tanto, este é o primeiro tempo nun pset onde estaremos dando a vostedes o que se chama código de distribución, que é o código que temos pre-escrito, pero só deixou algunhas pezas off para que termine de escribir. Entón vós, cando mira para esta código, pode ser realmente asustado. Se vostede está só como, ahh, eu non sei o que está facendo, Non sei como, que parece tan complicado, ahh, relaxarse. Está ben. Ler o spec. A especificación pode explicar-lle exactamente o que todos estes programas están facendo. 

Por exemplo, é un programa generate.c que virá coa súa pset. Realmente non ten que tocalo, pero ten que entender o que está facendo. E generate.c, todo o que está facendo é quere xerar números aleatorios ou pode darlle unha semente, como un número preestabelecido que leva, e xera máis números. Polo tanto, hai un xeito específico para aplicar no que generate.c pode só facer unha chea de números para probar os seus outros métodos diante. 

Entón, se quería, para exemplo, probar o seu descubrimento, vostede vai querer executar generate.c, xerar unha morea de números, e logo realizar a función de axudantes. A súa función axudantes é onde está realmente escribir fisicamente código. E pensar axudantes como un arquivo de biblioteca está escribindo que find está chamando. E así dentro helpers.c, vai facer investigación e clasificación. 

E entón vai, esencialmente, só poñer-los todos xuntos. A especificación ha dicir-lle como poñer isto na liña de comandos. E vai ser capaz de probar ou non o seu tipo e de investigación están a traballar. Legal. Alguén xa comezou e problemas atopados ou preguntas teñen agora con iso? Aceptar. 

Audiencia: Espera. Teño unha pregunta. 

ANDI Pengo: Si. 

Audiencia: Entón eu comece a facer a procura lineal en helpers.c e non foi realmente funciona. Pero, a continuación, máis tarde, descubrín que acabamos ten que borrar-lo e facer busca binaria. Entón, non importa se non funciona? 

ANDI Pengo: resposta curta é non. Pero xa que estamos não-- Audiencia: Pero ninguén de realmente comprobar. ANDI Pengo: Nunca somos Vai ver isto. Pero probablemente vai querer facer Comproba se a súa procura funciona. Porque se o seu lineal Busca non funciona, entón as posibilidades son o seu par busca non vai funcionar tan ben. Porque ten similar lóxica en ambas. E non, iso realmente non importa. Entón, os únicos que vai virar en son unha especie e busca binaria. Si. 

E tamén, unha morea de nenos foron tentar compilar helpers.c. Non está realmente permitido para facelo, porque helpers.c non ten unha función principal. E para que só debe ser realmente compilando xerar e atopar, porque atopar chamadas helpers.c e as funcións dentro dela. Así que fai a depuración unha dor na bunda. Pero iso é o que temos que facer. Audiencia: Acaba de facer todo, non? ANDI Pengo: pode só facer todo ben, si. Aceptar. Entón é iso en termos do que o pset pide que todos vostedes fagan. Se ten algunha dúbida, sinta- a liberdade de me preguntar despois sección. Eu vou estar aquí para, como, 20 minutos. 

E si, os PSet de non é realmente tan malo así. Vostedes deben estar OK. Estes, basta seguir as orientacións. Tipo de ter un sentido de, loxicamente, o que debería estar pasando e vai estar ben. Non sexa moi asustado. Hai unha morea de código xa escrito alí. Non moito medo se non fai entender o que todo isto significa. Se é moito, é totalmente ben. E chegar a horas de expediente. Nós imos axudar a dar un ollo. 

Audiencia: Coa adicional funcións, parecemos os anteriores? 

ANDI Pengo: Si, esas son no código. No xogo de 15, a metade dos xa está escrito para ti. Así, estas funcións se xa no código. Yep. Todo ben. Ben, mellor sorte. É un día nojento. Polo tanto, esperamos que vós non me sinto moi mal por estar dentro e codificación.