[Música tocando] 

ANDI Peng: Bem-vindo à semana 3 da secção. Obrigado, rapazes, para tudo que vem a esta hora de início mais cedo hoje. Temos uma nice, pouco grupo íntimo hoje. Portanto, esperamos que nós vamos chegar a acabamento, talvez, cedo, um pouco mais cedo hoje. Então, rapidamente, apenas alguns anúncios para a agenda de hoje. Antes de começar, estamos indo para ir um pouco mais algumas breves questões logísticas, pset perguntas, interrogue, coisas assim. E então nós vamos mergulhar na direita. Vamos usar um depurador chamado GDB começar a desbancar o nosso código, que David explicou em conferência no outro dia. Nós falaremos sobre os quatro tipos de tipos. Nós vamos passar por cima deles muito rapidamente uma vez que eles são muito intensivos. Mas sei que todos os slides e código-fonte estão sempre online. Então, sinta-se livre, na sua leitura, a voltar e dar uma olhada nisso. 

Nós vamos passar por notação assintótica, que é apenas uma maneira elegante de dizer "tempos de execução", onde temos a grande O, que David explicou em conferência. E também temos Omega, que é o tempo de execução limite inferior. E vamos falar um pouco mais em profundidade a respeito de como os trabalhos. E, finalmente, nós vamos passar por cima de busca binária, porque muitos de vocês que já têm olhou para seus Série de Exercícios provavelmente sabe que que é uma questão que está em seu pset. Então você vai ser feliz todos que nós cobrimos isso hoje. 

E, por último, por sua o feedback seção, eu realmente deixou cerca de 15 minutos a o fim de ir um pouco mais logística de pset3, dúvidas, talvez um pouco de orientação, se quiser, antes de iniciar a programação. Então, vamos tentar passar o material muito rapidamente. E então podemos passar algum tempo tendo mais perguntas para o pset. ESTÁ BEM. 

Rapidamente, assim que apenas alguns anúncios antes de começarmos hoje. Em primeiro lugar, bem-vindo a fazer -lo através de dois dos seus Série de Exercícios. Eu dei uma olhada no your-- Sim, vamos obter uma salva de palmas para que um. Na verdade, eu estava realmente, realmente impressionado. I classificado o primeiro pset para vocês na semana passada e que vocês fizeram incrível. 

Estilo estava no ponto além de alguns comentários. Certifique-se de que você está sempre comentando seu código. Mas seus Série de Exercícios foram no ponto. E mantê-lo. E é bom para o aluno a ver que vocês estão colocando em tanto esforço em seu estilo e seu projeto em seu código que gostaríamos para você ver. Então, eu estou passando ao longo de minha gratidão para o resto dos TAs. 

No entanto, há um algumas perguntas Debrief Eu só quero passar por cima desse faria tanto a minha vida e um monte de outro TAs "vive um pouco mais fácil. Em primeiro lugar, eu tenho notado isso passado week-- quantos de vocês já estão a funcionar em check50 seu código antes de enviar? ESTÁ BEM. Então, todos devem estar fazendo check50, porque-- um secret-- nós realmente executar check50 como parte de nossa correção scripts para testar o seu código. Portanto, se seu código está falhando check50, com toda a probabilidade, ele provavelmente vai falhar nosso check também. Às vezes, vocês ter as respostas certas. Como, em gananciosos, alguns dos você tem os números certos, você só imprimir algum material extra. E esse material extra realmente falhar a verificação, porque o computador não faz realmente sabe o que ele está procurando. E assim ela só vai percorrer, ver que sua saída não corresponder ao que esperamos que a resposta para ser, e marcá-lo é errado. 

E eu sei que aconteceu em alguns de seus casos esta semana. Então, eu fui para trás e manualmente Reclassificados código de todos. No futuro, porém, por favor, por favor, certifique- que você está executando verificar 50 em seu código. Porque é um tipo de dor para o TA ter que voltar e manualmente regrade cada pset único para cada instância única, pouco perdida. Então eu não tirar quaisquer pontos. Acho que eu tirei talvez um ou dois para o projeto. No futuro, embora, se você está falhando check50, Os pontos serão tomadas off para correção. 

Além disso, são Série de Exercícios devido sextas-feiras ao meio-dia. Eu acho que há uma de sete minutos período de carência tarde que nós lhe damos. Por tempo de Harvard, eles estão autorizados a ser de sete minutos de atraso para tudo. Então, aqui em Yale, vamos aderir a isso também. Mas praticamente, às 12:07, se o seu não está na pset, ele vai ser marcado como final. E assim, enquanto ele é marcado tão tarde, o TA-- eu sou ainda vai ser grading seus Série de Exercícios. Então, você ainda verá um grau aparecer. No entanto, sabemos que a o final do semestre, todas Série de Exercícios final será apenas zerada automaticamente pelo computador. 

Fazemos isso por duas razões. Um deles, às vezes ficamos desculpado, como desculpas de Dean, mais tarde que eu não sei sobre isso ainda. Por isso, gostaria de ter certeza que estamos classificação tudo apenas no caso, como, eu sou faltando a desculpa de um reitor. E em segundo lugar, lembre- mente, você ainda pode soltar um pset que tem pontos de escopo completo. E assim nós gostamos de grau todos os seus Série de Exercícios apenas para se certificar de que o seu âmbito de lá e você está tentando eles. Assim, mesmo se é tarde, você ainda obter crédito para pontos de escopo, eu acho. 

Então moral da história é, torná- se de seus Série de Exercícios estão em dentro do prazo. E se eles não estão em on-tempo, sei que não é grande. Sim, antes de eu seguir em frente, alguém tem qualquer dúvida sobre o feedback pset? Sim. 

AUDIÊNCIA: Você disse que pode soltar uma das Série de Exercícios? 

ANDI Peng: Sim. Portanto, há nove Série de Exercícios geral ao longo do semestre. E se você tem escopo points-- tão escopo é justo, muito bonito, que você está tentando a problema, você está colocando no tempo, você está mostrando que você tem demonstrada você leu o spec. Isso é muito bonito escopo. E se você está cumprindo Os pontos de escopo, nós pode soltar o menor um fora de alcance global. Então essa é a sua vantagem para preencher e tentar todos os pset. 

Mesmo se nenhum dos upload-- -los trabalhar, fazer upload de todos eles. E então nós esperamos ser capazes de dar-lhe alguns desses pontos de volta. Legal. Alguma outra pergunta? Ótimo. 

Em segundo lugar, escritório horas-- alguns notas rápidas sobre o horário de expediente. Então, primeiro, entrar no início da semana. Ninguém está sempre em o horário de expediente às segundas-feiras. Christabel veio a o horário de expediente na noite passada. Sim, Christabel. E o que temos no escritório horas na noite passada, Christabel? 

AUDIÊNCIA: Nós tivemos sorvete. 

ANDI Peng: Então, isso é certo, tivemos sorvete no horário de expediente na noite passada. Enquanto eu não posso prometer-lhe que teremos sorvete no horário de expediente a cada semana, o que posso prometer-lhe é que haverá um aumento significativamente melhor relação de alunos por TA. Como legítimo, é como 3-1. Considerando que, contrastam com que Quinta-feira, você tem cerca de 150 realmente estressado crianças e não sorvete. E não é apenas produtivo para ninguém. Então moral da história é, chegou cedo para as horas de expediente e coisas boas acontecerá. 

Além disso, venha preparado para fazer perguntas. Você sabe? Independentemente do que TAs, I pensam, têm vindo a dizer, temos recebido um par de estudantes que entram em na quinta-feira, como, 10:50 não ter lido a especificação sendo como me ajude, me ajude. Infelizmente, neste ponto, não há Não muito que podemos fazer para ajudá-lo. Então, por favor, venha no início da semana. Chegue mais cedo para o horário de expediente. Venha preparado para fazer perguntas. Certifique-se de que você, como um estudante, onde são você precisa ser para que o TAs podem orientá-lo junto, que é o que o horário de expediente deve ser alocado para. 

Em segundo lugar, então eu sei professores gostaria de nos surpreender com os testes. Eu tinha um professor aqueles como, yo, a propósito, lembre-se que intercalar você tem próxima segunda-feira. Sim, eu não sei nada sobre isso intercalar. Então, eu estou indo ser que TA que você lembra tudo o que teste 0-- porque, você sabe, nós somos CS. Agora que nós temos matrizes feito, você começa por isso que é teste 0, não quiz-1, eh? ESTÁ BEM. Oh, eu tenho algumas risadas sobre isso. ESTÁ BEM. 

Então questionário 0 será 14 de outubro se você está na seção de segunda a quarta-feira e 15 de Outubro, se você estiver em a seção de terça a quinta-feira. Isto não se aplica para aqueles de vocês em Harvard who-- Eu acho que você vai ser todos tendo seus testes no dia 14. 

Então, sim, na próxima semana, se David, em palestra, vai, sim, então com isso teste na próxima semana, todos vocês não ficará chocado porque você veio para a seção e você sabe que o seu 0 teste é em duas semanas. E teremos avaliação sessões e tudo mais. Assim, não se preocupa com estar com medo por isso. Todas as perguntas antes-- dúvidas em todas as questões logísticas relativas, classificação, o horário de expediente, seções? Sim. 

AUDIÊNCIA: Então o teste é vai ser durante a palestra? 

ANDI Peng: Sim. Então o quiz, eu acho, é 60 minutos atribuídos em que intervalo de tempo que você só vai tomar na sala de aula. Então você não tem que vir em em, tipo, um aleatória 19:00. Está tudo bom. Sim. Legal. 

Tudo certo. Então, nós estamos indo para introduzir um conceito para você esta semana que David já tem tipo de abordou em palestra na semana passada. É chamado de GDB. E como muitos de vocês, enquanto em o curso de escrever suas Série de Exercícios, ter notado um grande botão que diz "Debug" na parte superior do seu IDE? ESTÁ BEM. Então agora nós vamos realmente começar a desenterrar o mistério do que aquele botão, na verdade, faz. E eu garanto que você, é uma bonito, coisa linda. 

Então, até agora, eu acho houve duas coisas os alunos têm sido tipicamente fazendo quando depuração Série de Exercícios. Um deles, eles quer adicionar em printf () - por isso a cada poucas linhas, eles adicionar em um printf () - oh, o que é essa variável? Oh, o que é essa variável agora-- e você tipo de ver a progressão do seu código como ele é executado. Ou o segundo método é fazer as crianças que eles simplesmente escrever a coisa toda e depois ir como este no final. Esperemos que ele funciona. Eu garanto que você, é melhor GDB de ambos os métodos. Sim. Portanto, este será o seu novo melhor amigo. Porque é uma coisa bonita monitores que tanto visualmente o que seu código está fazendo em um ponto específico bem como o que todo o seu variáveis ​​estão levando, como quais são seus valores, nesse ponto específico. E, desta forma, você pode realmente definir pontos de interrupção em seu código. Você pode executar através de linha por linha. GDB e só vai ter para você, exibido para você, que todas as suas variáveis estão, o que estão fazendo, o que está acontecendo no código. E, de tal maneira, que é muito mais fácil de ver o que está acontecendo em vez de printf-ing ou escrever para baixo suas declarações. 

Então, vamos fazer um exemplo disso mais tarde. Então, isso parece um pouco abstrato. Não se preocupe, nós vamos fazer exemplos. E assim, essencialmente, as três maiores, funções mais usadas que você precisa em GDB são os próximos, Passa, e Entre em botões. Eu vou de cabeça há, na verdade, no momento. 

Então vocês todos podem ver que ou eu deveria ampliar um pouco? Na parte de trás, você pode ver isso? Devo fazer zoom? Só um pouco? OK legal. Aí vamos nós. ESTÁ BEM. 

Então, eu tenho, aqui, a minha implementação para ganancioso. E enquanto um monte de vocês escreveu ganancioso em loop while que form-- é uma maneira perfeitamente aceitável para fazer ele-- outra maneira de fazer isso é simplesmente dividir no módulo. Porque então você pode ter o seu valor e, em seguida, ter seu restante. E então você pode apenas adicioná-lo todos juntos. Será que a lógica do que eu estou fazendo aqui fazer sentido para todos, antes de começarmos? Mais ou menos? Legal. Ótimo. É uma peça muito sexy de código, eu diria. Como eu disse, David, em palestra, depois de um tempo, tudo que você vai começar a ver código como algo que é bonito. E às vezes quando você vê bonita código, é uma sensação maravilhosa. 

Então, no entanto, enquanto este código é muito bonito, ele não funciona corretamente. Então, vamos correr check50 sobre este assunto. Confira 50 20-- oop. 2? É que pset2? Sim. Oh, pset1. ESTÁ BEM. Então corremos check50. 

E, como vocês podem ver aqui, ele está falhando um par de casos. E para alguns de vocês, no curso de fazer os seus conjuntos de problemas, você é como, ah, por que não está funcionando. Por que é trabalhar para alguns valores, mas não para outros? Bem, GDB vai ajudá-lo a figura por que essas entradas não estavam funcionando. 

ESTÁ BEM. Então vamos ver, um dos cheques que eu estava falhando em check50 o valor de entrada foi de 0,41. Portanto, a resposta correta que você deve estar recebendo é um 4. Mas em vez disso o que estou imprimindo é o 3-N, que está incorrecta. Então vamos executar isso manualmente, apenas certifique-se de que check50 está funcionando. Vamos fazer ./greedy. Opa, eu tenho que fazer ganancioso. Aí vamos nós. Agora ./greedy. 

Quanto é devido? Vamos fazer 0,41. E sim, nós vemos aqui que é a saída 3 quando a resposta correta, na verdade, deve ser de 4. Então, vamos entrar GDB e ver como nós pode ir sobre como corrigir este problema. 

Assim, o primeiro passo na sempre depuração do código é definir um ponto de interrupção, ou um ponto no qual você deseja que o computador ou o depurador para começar a olhar para. Então, se você realmente não sabe qual é seu problema, Normalmente, a coisa típica queremos fazer é definir o nosso ponto de interrupção na principal. Então, se vocês podem ver isso botão vermelho ali mesmo, Sim, isso foi me estabelecendo um breakpoint para a função principal. Eu clique isso. 

E então eu posso ir até meu botão Debug. Eu bater esse botão. Deixe-me zoom out se eu puder. Aí vamos nós. Portanto, temos, aqui, um painel à direita. Sinto muito, pessoal na parte de trás, você não pode realmente ver muito bem. Mas, essencialmente, todos este painel direita está fazendo é manter o controle de ambos os destaque A linha, que é a linha de código que o computador está sendo executado, bem como todas as suas variáveis aqui embaixo. 

Então você tem centavos, moedas, n, todos declararam a coisas diferentes neste ponto. Não se preocupe, porque não temos, na verdade, inicializado-los a quaisquer variáveis ​​ainda. Assim, no seu computador, o seu computador só está vendo, oh, 32767 foi a última função utilizada de que o espaço de memória no meu computador. E assim que é onde atualmente é centavos. Mas não que uma vez que você executar o código, deve tornar-se inicializado. 

Então, vamos passar por, linha por linha, o que está acontecendo aqui. ESTÁ BEM. Então, aqui estão os três botões que eu só explicada. Você tem o Play, ou a função Run, botão, você tem a Passo sobre o botão, e você também tem o botão Step Into. E essencialmente, todos os três eles apenas passar por seu código e fazer coisas diferentes. 

Então, normalmente, quando você está depurando, nós não queremos é só apertar Play, porque o jogo só vai funcionar seu código para o fim de tudo. E então você não vai realmente sei qual seu problema é a menos que você definir vários pontos de interrupção. Se você definir vários pontos de interrupção, Ela só vai automaticamente executado a partir de um ponto de interrupção, para o próximo, para o próximo. Mas neste caso nós temos só que um, porque nós quer trabalhar nosso caminho de cima para baixo para baixo. Então, vamos ignorar esse botão agora para os fins deste programa. 

Assim, o Passo sobre a função apenas etapas, ao longo de cada linha única e diz-lhe o que o computador está fazendo. O Passo em função vai para a função real que está em sua linha de código. Assim, por exemplo, como printf (), que é uma função, certo? Se eu quisesse fisicamente passo para a função printf (), Eu gostaria realmente ir para o pedaço de código onde printf () foi escrito e veja o que está acontecendo lá. 

Mas, normalmente, assumimos que o código que nós damos-lhe trabalha. Assumimos o printf () está funcionando. Assumimos que GetInt () está funcionando. Portanto, não há necessidade de passo para essas funções. Mas se há funções que você escreve-se que você deseja verificar o que está acontecendo, você iria querer passo em que a função. 

Então, agora nós apenas estamos indo de passar por cima este pedaço de código. Então vamos ver. Oh, impressão, "Oh hai, como muita mudança é devido? " Nós não nos importamos. Sabemos que está trabalhando, por isso, passar por cima dela. 

Então n, que é o nosso flutuador que temos initialized-- ou declared-- no topo, estamos agora igualando que a GetFloat (). Então, vamos passar por cima disso. E vemos no inferior aqui, o programa está me levando para introduzir um valor. Então entrada de deixar o valor que queremos para testar aqui, que é 0,41. Ótimo. 

Então agora n-- fazer vocês ver aqui, no bottom-- é stored-- porque ainda não arredondados, é armazenados neste gigante como flutuador que é 0,4099999996, que é perto o suficiente para o nosso propósitos, agora, para 0,41. E então nós vamos ver mais tarde, como nós continuar pisando sobre o programa, depois aqui, n se tornou arredondado e centavos tornou-se 41. Ótimo. Então, nós sabemos que o trabalho do nosso arredondamento. Sabemos que temos a número correto de centavos, por isso sabemos que isso é não é realmente o problema. 

Então, nós continuamos pisando em neste programa. Vamos aqui. E assim, depois desta linha de código, deve saber quantos quartos que temos. Nós passar por cima. E você vê o que fazemos, na verdade, tem um trimestre porque temos subtraído 25 do nosso valor inicial de 41. E nós temos 16 esquerda para nossos centavos. 

Será que todo mundo entender como o programa está percorrendo e por centavos, passou a ser 16 e por que, agora, as moedas tornou-se um? Todos estão seguindo essa lógica? Legal. Assim, a partir deste ponto, o de trabalho do programa, certo? Sabemos que ele está fazendo exatamente o que quer que seja. E nós não o fez, na verdade, tem que imprimir, oh, o que é centavos, neste ponto, o que é moedas neste momento. 

Continuamos a atravessar o programa. Passar por cima. Legal. Nós passar por cima de moedas de dez centavos. Ótimo. Nós vemos que ele é tomado fora de $ 0,10 para um centavo. E agora temos duas moedas. Está certo. 

Nós passar por cima de moedas de um centavo e nós vemos que temos de sobra centavos. Hmm, isso é estranho. Até aqui no programa, eu deveria ter subtraído meus tostões. Talvez eu só não foi fazendo esse direito linha. E, infelizmente, você pode ver aqui, porque nós sabemos que estamos pisando através das linhas 32 e 33, que é onde o nosso programa impropriamente teve variáveis ​​executado. Assim, podemos olhar e ver, oh, Eu estou subtraindo centavos aqui, mas eu não sou realmente adicionando a minha valor da moeda. Eu estou adicionando ao centavos. E eu não quero adicionar centavos, eu quero adicionar a moedas. Então, se nós mudar isso para moedas, nós temos um programa de trabalho. Eu posso correr check50. Você pode simplesmente sair do GDB direita aqui e depois executar check50 novamente. Eu poderia apenas fazer isso. Eu tenho que fazer ganancioso. 0.41. E aqui, é impressão a resposta certa. 

Então, como vocês podem ver, GDB é uma ferramenta muito poderosa para quando temos tanto código acontecendo e tantas variáveis que é difícil para nós, como um ser humano, para acompanhar. O computador, no GDB depurador, tem a capacidade manter o controle de tudo. Eu sei, em Visionaire, vocês provavelmente pode ter atingido algumas falhas de segmentação porque você estava executando fora dos limites de sua matriz. No exemplo de César, que é exatamente o que eu tenho implementado aqui. 

Então, eu esqueci de verificar se há o que aconteceria se eu não ter dois argumentos de linha de comando. Eu só não colocar nessa seleção. E assim se eu executar Debug-- eu definir meu ponto de interrupção para a direita lá. Eu corro Debug. 

ESTÁ BEM. Sim. Então, na verdade, era suposto GDB ter me disse que não Foi há uma falha de segmentação. Eu não sei o que estava acontecendo ali mesmo, mas quando eu corri, que estava trabalhando. Quando você executa linhas de código através de e GDB pode de repente parar em você, ir para cima e veja o que o erro é vermelho. Ele vai dizer-lhe, hey, você teve uma falha de segmentação, o que significa que você tentou acessar espaço em uma matriz que não existia. Sim. 

Assim, no próximo problema definir esta semana, vocês provavelmente vai ter um monte de variáveis ​​flutuando. Você não vai ter a certeza de que todos eles significam em um determinado ponto. Então GDB vai realmente ajudá-lo em descobrir o que eles estão todos igualando e ser capaz de ver que visualmente. Alguém está confuso sobre como qualquer um que estava trabalhando? Legal. Tudo certo. Então, depois disso, estamos vai mergulhar na direita em são quatro diferentes tipos de tipos para esta semana. Como muitos de vocês, em primeiro lugar de tudo, antes de começarmos, li toda a especificação para pset3? ESTÁ BEM. Estou orgulhoso de vocês. Isso é como a metade da classe, que é significativamente mais do que da última vez. 

Então, isso é ótimo, porque quando falamos sobre o conteúdo em lecture-- ou desculpe, em section-- eu gosto para relacionar um monte de que de volta para o que o pset é e como você deseja implementar isso no seu pset. Então, se você vem tendo ler a especificação, ele vai ser muito mais fácil para você entender o que eu estou falando sobre quando eu digo, oh hey, isso pode ser um realmente bom lugar para implementar este tipo. Assim, aqueles de vocês que leram o especs saber que, como parte de sua pset, você vai ter que escrever um tipo de espécie. Então, isso pode ser muito útil para um monte de você hoje. 

Então, vamos começar com, Essencialmente, o tipo mais simples do tipo, o tipo de seleção. O algoritmo típico para como iríamos fazer isto é-- David passou por todas de palestra, então eu vou mover-se rapidamente ao longo aqui-- é essencialmente, você tem uma matriz de valores. E então você encontrar o menor valor não triados e você trocar esse valor com o primeiro valor indiferenciados. E então você simplesmente continuar a repetir com o resto da sua lista. 

E aqui está uma explicação visual de como isso funciona. Assim, por exemplo, se tivéssemos de começar com uma série de cinco elementos, índice 0 a 4, com 3, 5, 2, 6 e 4 valores colocado no array-- então agora, nós apenas estamos indo para assumir que todos eles são indiferenciados porque nós não testei o contrário. 

Então, como uma espécie de seleção faria trabalho é que ele iria primeiro executado através da totalidade da matriz indiferenciados. Ele escolhia o menor valor. Neste caso, 3, direita agora, é o menor. Ele fica a 5. Não, 5 não é maior than-- ou desculpe, não é menos than-- 3. Assim, o valor mínimo é ainda 3. E então você começa a 2. O computador vê, oh, 2 é inferior a 3. 2 agora deve ser o valor mínimo. E assim 2 swaps com que o primeiro valor. 

Então, depois de um passe, nós realmente ver que os 2 e os 3 são trocados. E nós apenas estamos indo para continuar a fazê- este novamente com o resto da matriz. Então, nós estamos indo apenas para percorrer os últimos quatro índices da matriz. Vamos ver o que é 3 o valor mínimo seguinte. Então vamos trocar isso com 4. E então nós apenas estamos indo para mantê- que atravessa até que, eventualmente, você chegar a uma matriz classificada em que 2, 3, 4, 5, e 6 são todos classificados. Será que todo mundo entender a lógica de como uma espécie de seleção funciona? 

Você apenas tem algum tipo de um valor mínimo. Você está mantendo o controle de o que é. E sempre que você encontrá-lo, você trocá-lo com o primeiro valor na array-- ou, não o primeiro value-- o próximo valor na matriz. Legal. 

Então, como vocês tipo de viu de um breve vislumbre, vamos Pseudocódigo isso. Então, se vocês nas costas quiser formar um grupo, todos em uma mesa pode formar um pequeno parceiro, eu vou para dar a vocês como três minutos apenas para falar através a lógica, em Inglês, de como podemos ser capazes de implementar pseudocódigo para escrever uma espécie de seleção. E há doces. Por favor, venha para cima e obter doces. Se você é na parte de trás e você quer doces, eu posso jogava balas em você. Na verdade, fazer legal vocę--. Oh, desculpe. ESTÁ BEM. 

Então, se nós gostaríamos de, como uma classe, escrita pseudocódigo por quanto se poderia aproximar este problema, apenas sinta-se livre. Vou apenas ir ao redor e, a fim, peça aos grupos para a próxima linha de o que deveríamos estar fazendo. Então, se vocês querem começar fora, qual é a primeira coisa que fazer quando você está tentando implementar uma maneira de resolver este programa seletivamente para classificar uma lista? Vamos apenas supor que tenho uma matriz, tudo bem? 

AUDIÊNCIA: Você quer criar alguns tipo de [inaudível] que você é que atravessa toda a sua matriz. 

ANDI PENG: Certo. Então você vai querer fazer uma iteração através de cada espaço, certo? Muito bom. Se vocês querem me dar o próximo linha-- sim, na parte de trás. 

AUDIÊNCIA: Verifique- tudo para o menor. 

ANDI Peng: Lá vamos nós. Por isso, queremos passar e verificar a ver o que o valor mínimo é, certo? Eu estou indo para abreviar que a "min". O que vocês querem fazer depois você encontrou o valor mínimo? 

AUDIÊNCIA: [inaudível] ANDI Peng: Então você vai querer ligá-lo com o primeiro desse array, certo? Esse é o começo, eu vou dizer. Tudo certo. Portanto, agora que você já trocou o primeiro um, o que você quer fazer depois disso? Portanto, agora sabemos que este aqui deve ser o menor valor, certo? Então você tem um descanso adicional da matriz que é indiferenciado. Então, o que você quer fazer aqui, se você caras querem me dar a próxima linha? AUDIÊNCIA: Então você quer fazer uma iteração através do restante da matriz. ANDI Peng: Sim. E então o que iterar tipo de implicar provavelmente vamos precisar? Que tipo de-- 

AUDIÊNCIA: Oh, uma variável adicional? ANDI Peng: Provavelmente outro loop for, certo? Então, nós estamos provavelmente vai querer iterar through-- grande. E então você vai voltar e provavelmente verificar o mínimo de novo, certo? E você vai ficar repetindo isso, porque os loops só vai para manter funcionando, certo? 

Então, como vocês podem ver, nós basta ter um pseudocódigo geral de como nós queremos que este programa para olhar. Este iterate aqui, o que é que nós tipicamente precisa escrever no nosso código se queremos fazer uma iteração através de um matriz, o tipo de estrutura? Eu acho que Christabel já disse isso antes. 

AUDIÊNCIA: Um laço for. 

ANDI Peng: Um loop for? Exatamente. Portanto, este é, provavelmente, vai ser um loop for. O que é um cheque aqui vai implicar? Normalmente, se você quiser verificar se algo é algo else-- 

AUDIÊNCIA: Se. 

ANDI Peng: Um se, certo? E então o swap aqui, vamos passar por cima mais tarde, porque David passei por isso na palestra também. E, em seguida, a segunda iteração implies-- 

AUDIÊNCIA: Outra loop for. 

ANDI Peng: --another para loop, exatamente. Então, se nós estamos olhando neste corretamente, pode ver que estamos, provavelmente, vai precisar de um laço for aninhado com uma declaração condicional lá e, em seguida, uma parte real de código que é indo para trocar os valores. Então eu apenas geralmente escrito um código de pseudocódigo aqui. E então nós estamos indo realmente fisicamente, como uma classe, tentar implementar isso hoje. Vamos voltar a este IDE. 

Uh oh. Por que é que não-- aí está. ESTÁ BEM. Desculpe, deixe-me tentar ampliar um pouco mais. Aí vamos nós. Tudo o que eu estou fazendo aqui é que eu criei um programa chamado "seleção / sort.c." Eu criei uma matriz de nove valores, 4, 8, 2, 1, 6, 9, 7, 5, 3. Atualmente, como você pode ver, eles são não-ordenada. n vai ser o número que diz-lhe a quantidade de valores você tem em sua matriz. Neste caso, temos nove valores. E eu só tenho um loop for aqui que imprime a matriz indiferenciados. 

E no final, eu também tenho um para loop que apenas imprime-lo novamente. Então, teoricamente, se este programa está funcionando corretamente, no final, você deve ver um impresso para o laço em que 1, 2, 3, 4, 5, 6, 7, 8, 9 são todos corretamente em ordem. 

Então, nós temos o nosso pseudocódigo aqui. Alguém quer para-- Eu sou apenas indo para ir pedir volunteers-- me diga exatamente o que digitar se nós queremos, em primeiro lugar, apenas uma iteração até o início deste array? Qual é a linha de código que eu sou provavelmente vai precisar aqui? 

AUDIÊNCIA: [inaudível] 

ANDI Peng: Sim, sinto livre a-- desculpe, você Não tem que ficar up-- sensação livre para levantar a sua voz um pouco. 

AUDIÊNCIA: Para int i é igual a 0-- 

ANDI Peng: Sim, boa. 

AUDIÊNCIA: i é menor do que o comprimento de matriz. 

ANDI Peng: Então lembre- importa aqui, porque nós não tem uma função que nos diz o comprimento de uma matriz, nós já temos um valor que armazena isso. Certo? Outro aspecto a ter em mente-- em uma matriz de nove valores, quais são os índices? Vamos apenas dizer que essa matriz era 0-3. Você vê que a última índice é, na verdade, três. Não é 4, mesmo que não haja quatro valores na matriz. 

Então aqui, nós temos que ter muito cuidado do que a nossa condição para o comprimento Será. 

AUDIÊNCIA: Não seria n menos 1? ANDI Peng: Vai n menos 1, exatamente. Isso faz sentido, porque é n menos 1, todo mundo? É porque as matrizes são indexados zero. Eles começam em 0 e correr até n menos 1. Sim, é um pouco complicado. ESTÁ BEM. E depois-- AUDIÊNCIA: Isnt'1 que já tomado cuidado, porém, apenas por não dizer "inferior ou igual "e apenas dizer" menos do que? " 

ANDI Peng: Isso é um pergunta muito boa. Então sim. Mas também, a maneira que nós somos implementar o direito de verificar, você precisa para comparar dois valores. Então você realmente quer deixar o "para" vazio. Porque se você comparar este, você não vai tem alguma coisa depois que ele para comparar, certo? Sim. Então i ++. Vamos adicionar nossos suportes em. Whoops. Ótimo. Portanto, temos o início do nosso circuito externo. Então, agora nós provavelmente quer criar uma variável para manter a par de o menor valor, certo? Alguém quer me dar o linha de código que faria isso? O que precisamos se vamos querer armazenar algo? 

Certo. Talvez um nome melhor para que seria ser-- "temp" totalmente works-- talvez um mais apropriadamente chamado seria, se queremos que a menor value-- 

AUDIÊNCIA: Min. ANDI Peng: min, lá vamos nós. min seria bom. E aqui, o que nós quer inicializá-lo para? Isto é um pouco complicado. Porque agora no início desta matriz, você ainda não olhou para nada, certo? Então, o que, automaticamente, se nós estamos apenas no i é igual a 0, o que queremos para inicializar nosso primeiro valor mínimo para? AUDIÊNCIA: i. ANDI Peng: i, exatamente. Christabel, por que queremos para inicializar-lo para mim? 

AUDIÊNCIA: Porque, bem, nós estamos começando com 0. Então, porque não temos nada para comparar que ele, o mínimo vai acabar sendo 0. 

ANDI Peng: Exatamente. Então, ela é exatamente correto. Porque nós não temos realmente olhou para nada ainda, não sabemos o que o nosso valor mínimo é. Queremos apenas inicializar-lo para i, que, atualmente, está bem aqui. E enquanto continuamos a mover para baixo essa matriz, vamos ver que, com cada passe adicional, incrementa i. E assim, nesse ponto, i provavelmente vai a querer ser o mínimo, porque ele vai ser o que quer é o início da matriz não triados. Legal. 

Então, agora nós queremos adicionar um loop for aqui que é vai percorrer a não classificado, ou o resto desta matriz. Alguém quer me dar um linha de código que faria isso? Hint-- o que precisamos aqui em baixo? O que vai fazer no presente para loop? Sim. AUDIÊNCIA: Então nós quereríamos têm um número inteiro diferente, porque nós estamos correndo pelo resto da matriz em vez do i, talvez por isso j. 

ANDI Peng: Sim, j soa bem para mim. É igual? 

AUDIÊNCIA: Então seria eu mais 1, porque você está começando no próximo valor. E, em seguida, para o end---lo novamente, j é menos de n menos 1, e depois j ++. ANDI Peng: Grande. 

E, em seguida, aqui, nós vamos querer verificar para ver se a nossa condição for cumprida, certo? Porque você quer alterar o valor mínimo se é realmente menor do que o que você está comparando-a, certo? Então, o que vamos querer aqui? Verifique para ver. Que tipo de declaração estamos, provavelmente, vai ti deseja usar, se nós querer verificar alguma coisa? 

AUDIÊNCIA: Uma instrução if. 

ANDI Peng: Uma instrução if. Então se-- eo que vai ser a condição de que nós queremos dentro do nosso if? 

AUDIÊNCIA: Se o valor de j é menor do que o valor de i-- 

ANDI Peng: Exatamente. Então se-- de modo que este conjunto é chamado de "matriz". Ótimo. Então, se array-- que foi isso? Diga isso de novo. 

AUDIÊNCIA: Se matriz-j é menor do que matriz-i, então poderíamos mudar o min. Assim, a min seria j. 

ANDI Peng: Isso faz sentido? ESTÁ BEM. E agora aqui em baixo, nós, na verdade, deseja implementar a troca, certo? Assim recordar, a palestra, que David, quando ele estava tentando trocar as-- o que era suco de laranja ele-- e milk-- 

AUDIÊNCIA: Isso foi gross. 

ANDI Peng: Sim, isso foi tipo de Gross. Mas foi uma boa bonita conceito demonstrando tempo. Então, pense de seus valores aqui. Você tem uma matriz de minutos, uma série de i, ou o que nós estávamos tentando trocar aqui. E você provavelmente não pode derramar-los em uns aos outros, ao mesmo tempo, para a direita? Então, o que vamos a necessidade de criar aqui a fim de trocar os valores corretamente? 

AUDIÊNCIA: Uma variável temporária. 

ANDI Peng: Uma variável temporária. Então vamos fazer int temporário. Veja, isso seria uma melhor tempo a-- Whoa, o que foi isso? ESTÁ BEM. Portanto, esta teria sido uma melhor tempo para nomear o "temp." variável Então vamos fazer int temporário. O que é que vamos Definir temp igual a aqui? AUDIÊNCIA: Min? ANDI Peng: É um pouco complicado. Ele realmente não importa no final. Não importa o que ordem que você escolher para trocar em desde que você está fazendo certo que você é manter o controle do que você está trocando. 

AUDIÊNCIA: Poderia ser gama-i. 

ANDI Peng: Sim, vamos fazer matriz-i. E então, qual é a próxima linha de código que nós queremos ter aqui? AUDIÊNCIA: array-i é igual a matriz de j. ANDI Peng: E ​​por último? AUDIÊNCIA: array-j é igual a matriz-i. Audiência: Ou matriz j iguais matriz de temp-- ou, temporário. 

ANDI Peng: OK. Então, vamos executar este e veja se ele está indo para o trabalho. Onde é que está acontecendo? Oh, isso é um problema. Veja, na linha 40, estamos tentando usar matriz-j? Mas onde é que j só existem em? 

AUDIÊNCIA: No loop for. ANDI PENG: Certo. Então o que é que vamos fazer? 

AUDIÊNCIA: Definir fora as-- AUDIÊNCIA: É, eu acho que você tem para usar outra instrução if, certo? Assim como, se o minimum-- tudo bem, deixe-me pensar. 

ANDI Peng: Caras, tente para dar uma olhada Deixe-nos Veja, o que é algo que podemos fazer aqui? 

AUDIÊNCIA: OK. Portanto, se o mínimo não é igual j-- assim ainda se o mínimo é i-- então não teríamos de trocar. 

ANDI Peng: Será que a igualdade de i? O que você quer dizer aqui? 

AUDIÊNCIA: Ou sim, se o mínimo não é igual a mim, sim. ANDI Peng: OK. Bem, isso resolve, tipo, nossos problemas. Mas isso ainda não resolve o problema do que acontece se j-- desde j não existe fora dele, o que você que nós queremos fazer com ele? Declará-la fora? Vamos tentar executar este. Uh oh. Nossa espécie não está funcionando. 

Como você pode ver, nosso inicial matriz tinha esses valores. E depois, ele deve ter foi em 1, 2, 3, 4, 5, 6, 7, 8, 9. Não esta funcionando. Ahh. O que nós fazemos? AUDIÊNCIA: Debug. ANDI Peng: Tudo bem, podemos tentar isso. Podemos depurar. Aumentar um pouco. Vamos definir o nosso ponto de interrupção. Vamos OK como--. 

Então, porque já sabemos que estas linhas, 15 a 22, são working-- porque tudo que eu estou fazendo é apenas iterar e printing-- I pode ir em frente e ignorar isso. Vamos começar na linha 25. Oop, deixe-me livrar disso. 

AUDIÊNCIA: Então, do ponto de interrupção onde a depuração começa? ANDI Peng: ou pára. AUDIÊNCIA: ou pára. ANDI Peng: Sim. Você pode definir vários pontos de interrupção e ele pode simplesmente pular de um para o outro. Mas neste caso nós não sabemos onde o erro está acontecendo. Então, nós apenas queremos começar de cima para baixo. Sim. ESTÁ BEM. 

Então esta linha aqui, podemos intervir. Você pode ver aqui em baixo, nós temos uma matriz. Esses são os valores que estão na matriz. Você vê que, como índice de 0, ele corresponde ao value-- oh, Vou tentar fazer zoom. Desculpe, é realmente difícil para see-- na matriz índice 0, que tem um valor de 4 e então assim por diante e assim por diante. Temos as nossas variáveis ​​locais. Agora eu é igual a 0, o que nós queremos que ele seja. 

E assim vamos continuar percorrendo. O nosso mínima é igual a 0, que nós também queremos que ele seja. E, então, entrar em nosso segundo para ciclo, se a matriz-j é inferior a matriz-i, que não era. Então, se você ver como que pulou isso? 

AUDIÊNCIA: Então deve ser o caso mínimo, tudo isso-- que não deve estar dentro do primeiro para o loop? ANDI Peng: Não, porque você ainda deseja testar. Você quer fazer uma comparação cada tempo, mesmo depois de passar por ela. Você não apenas quer fazê-lo na primeira passagem. Você quer fazê-lo com cada passagem adicional novamente. Então você quer verificar se há sua condição dentro. Então, nós apenas estamos indo para continuar correndo por aqui. Eu vou dar a vocês uma dica. Tem a ver com o fato de que, quando você está verificando sua condicional, você não está verificando para o índice correto. Então, agora você está verificando para índice de matriz de j é inferior a matriz Índice de i. Mas o que você está fazendo em cima o início do loop for? Você não está definindo j igual a mim? 

Sim, para que possamos realmente sair do depurador aqui. Então, vamos dar uma olhada no nosso pseudocódigo. For-- vamos começam em i é igual a 0. Nós estamos indo para ir até n menos 1. Vamos verificar, se temos esse direito? Sim, isso era certo. 

Assim, pois, aqui dentro, estamos vai criar um valor mínimo e definir que igual a i. Será que vamos fazer isso? Sim, fiz isso. Agora, em nosso interior loop for, estamos vai fazer j é igual a i n menos 1. Será que vamos fazer isso? Na verdade, nós fizemos isso. 

Então, no entanto, o que estamos comparando aqui? 

AUDIÊNCIA: j + 1. ANDI Peng: Exatamente. E então você vai querer definir o seu mínimo igual a 1 j mais bem. Então eu passei por isso muito rapidamente. Vocês entendem por isso que é j + 1? ESTÁ BEM. 

Assim, em sua matriz, em sua primeira passagem, o loop for, por int i é igual a 0, vamos apenas assumir este não foi alterado ainda. Nós temos uma matriz de, completamente, apenas quatro elementos não ordenados, certo? Por isso, queremos inicializar i igual a 0. E eu vai apenas percorrer este loop. E assim na primeira passagem, vamos para inicializar uma variável chamada "min" que também é igual a I, porque não temos um valor mínimo. Então, isso é actualmente igual a 0 também. E então nós vamos passar. E nós queremos fazer uma iteração novamente. Agora que nós descobrimos o que o nosso mínimo é, nós queremos para percorrer novamente para ver se ele está comparando, certo? Então, j, aqui, vai igual a I, o qual é 0. E, em seguida, se a matriz j mais eu, que é o que é o próximo mais, como menos do que o seu mínimo atual valor é, você quer trocar. 

Então, vamos apenas dizer que nós temos tem, como, 2, 5, 1, 8. Agora, i é igual a 0 e j é igual a 0. E esse é o nosso valor mínimo. Se matriz-j mais i-- por isso, se o isso é depois do que nós estamos olhando para é maior do que o anterior, que vai tornar-se o mínimo. 

Então aqui nós vemos que 5 não é menos do que isso. Então, ele vai não ser 5. Vemos que 1 é inferior a 2, certo? Portanto, agora sabemos que o nosso mínimo é vai ser o valor de índice 0, 1, 2. Sim? E então quando você chegar aqui, você pode trocar os valores corretos. 

Então, quando vocês estavam apenas tendo o j antes, você não estavam olhando para o depois disso. Você estava olhando o mesmo valor, que É por isso que ele simplesmente não estava fazendo nada. Isso faz sentido para todos, por isso que precisamos que mais um lá? ESTÁ BEM. Agora vamos correr com ele para fazer certeza de que o resto do código está correcto. Por que é que acontece? Ah, é o min aqui. Nós estávamos comparando o valor errado. Ah não. 

Ah, sim, aqui nós trocando os valores errados bem. Porque nós estávamos olhando para i e j. Esses são os que foram merecem uma visita. Nós realmente quiser trocar o mínimo, o mínimo atual, com o que o exterior é. E, como vocês podem ver abaixo aqui, temos uma matriz classificada. Ele só tinha a ver com o facto de que quando estávamos verificando o valores que foram comparando, nós não estávamos olhando para os valores corretos. Nós estávamos olhando para a mesma aqui, não, na verdade, trocando-lo. Você tem que olhar para um lado para ele e, em seguida, você pode trocar. Então é isso que era uma espécie de incomodando nosso código antes. E o que eu fiz aqui é tudo o depurador poderia ter feito para você Eu só fiz isso no placa, porque é mais fácil para ver em vez de tentar para fazer zoom e depurador. Isso faz sentido para todo mundo? Legal. 

Tudo certo. Nós podemos passar para falar sobre notação assintótica, que é apenas uma maneira elegante de dizer o tempos de execução de todos os tipos dessas. Então eu sei David, em palestra, aflorados tempos de execução. E ele passou por toda a fórmula de como calcular os tempos de execução. Não se preocupa com isso. Se você for realmente curioso sobre como isso funciona, fique à vontade para falar comigo depois seção. Podemos caminhar por as fórmulas juntos. Mas todos vocês tem que realmente sei é que n ao quadrado sobre 2 é a mesma coisa que n ao quadrado. Devido ao número maior o expoente, mais cresce. E assim para os nossos propósitos, todos nós nos preocupamos é que o número gigante que está crescendo. 

Então, qual é o melhor caso runtime de seleção tipo? Se você estiver indo para ter para percorrer uma lista e então percorrer o resto da lista, quantas vezes são você vai provavelmente, no pior na case-- melhor caso, sorry-- percorrer? Talvez a melhor pergunta é para perguntar, o que é o pior caso runtime de seleção de classificação. AUDIÊNCIA: n ao quadrado. ANDI Peng: É n ao quadrado, certo. Então, uma maneira fácil de pensar nisso é como, qualquer momento você tem duas aninhadas para loops, ele vai ser n ao quadrado. Porque não só é você que funciona através de uma vez, você tem que voltar volta e correr com ele mais uma vez dentro para cada valor. Então, nesse caso, você está correndo n vezes n ao quadrado, que é-- sorry, n vezes n, o que equivale n ao quadrado. 

E tipo é também um pouco única no sentido que não importa se estes valores já estão em ordem. Ele ainda vai correr através de qualquer maneira. Vamos apenas dizer que este foi de 1, 2, 3, 4. Independentemente de estarem ou não foi em fim, ele ainda teria percorreu e ainda verificou o valor mínimo. Ele teria feito o mesmo número de cheques a cada momento, mesmo que não chegou a tocar em nada. 

Assim, em tal caso, o melhor eo pior tempos de execução são realmente equivalentes. Assim, o tempo de execução esperado seleção de tipo, que designamos pelo símbolo de teta, teta, neste caso, também seria n ao quadrado. Todos os três destes seriam n ao quadrado. É claro que todos sobre o porquê o tempo de execução é n ao quadrado? 

Tudo certo. Então, eu estou indo só para executar rapidamente pelo resto das sortes. O algoritmo para bolha sort-- lembre-se, este foi o primeiro Davi, passando em palestra. Essencialmente, você pisa toda a lista e você swap-- você só comparar dois de cada vez. E se um é maior, que você acabou de trocá-los. Então, se estes são maiores, você trocaria. Eu tenho oficial aqui. 

Então, vamos apenas dizer que você tinha 8, 6, 4, 2. Você iria comparar a 8 e um 6. Você precisaria trocá-los. Você poderia comparar a 8 e um 4. Você precisaria trocá-los. Se tiver de trocar a 8 e o 2, alterá-los também. Assim, em tal sentido, você pode ver, jogado fora ao longo de um longo período de tempo, como o tipo de bolha de valores as extremidades, o que é por isso que chamamos bubble sort. 

Nós só iria percorrer novamente em nossa segunda passagem, e nossa terceira passagem, e nossa quarta passagem. Essencialmente, bubble sort apenas corre até que você não fazer mais swaps. Então, nesse sentido, este é apenas o pseudocódigo geral para ele. Não se preocupe, estes serão todos online. Não temos que ir realmente sobre isso. 

Nós apenas inicializar um contador variável que começa em 0. E nós iterar através de toda a matriz. E se um valor é-- se este valor é maior do que aquele valor, você está indo para trocá-los. E então você é apenas vai continuar. E você está indo para contar. E você está indo só para continuar fazendo este enquanto o contador é maior a 0, o que significa que cada vez que você tem que trocar, você sabe que você quer ir para trás e verificar novamente. Você deseja manter a verificação até que você saiba que você não tem que trocar mais. 

Então, quais são os melhores e piores caso tempos de execução para bubble sort? E hint-- esta é realmente diferente tipo de seleção no sentido que estas duas respostas não são os mesmos. Pense sobre o que aconteceria em um caso, se ele já foi resolvido. E pensar sobre o que que aconteceria se fosse no caso em que não foi resolvido. E você pode tipo de correr através de por que isso está acontecendo. Eu vou dar a vocês, tipo, 30 segundos para pensar sobre isso. 

ESTÁ BEM. Alguém tem um palpite sobre o que o pior caso de tempo de execução de bubble sort é? Sim. 

AUDIÊNCIA: seria, como, n vezes n menos 1 ou algo assim? Como, cada vez que ele é executado, é apenas, como, um swap de menos que quer que fosse. 

ANDI Peng: Sim, então você está totalmente certo. E este é um caso em que a sua resposta foi realmente mais complexo do que aquele que precisa dar. Então ele vai para run-- eu sou vai apagar tudo isso aqui. Está todo mundo bem? Posso apagar isso? ESTÁ BEM. Você vai percorrer n vezes pela primeira vez, certo? E eles estão indo para ser executado através n menos 1 segundo tempo, certo? E então você está indo para mantê- indo, n mina 2, et cetera. David fez isso em uma palestra, onde, se você adicionou-se todos esses valores, você começa algo que é como-- yeah-- mais de 2, que, essencialmente, apenas reduz até n ao quadrado. Você está indo para obter um fração estranho lá dentro. E assim só sei que a n ao quadrado sempre tem precedência sobre a fração. E assim, neste caso, o pior tempo de execução seria n ao quadrado. Se fosse descendente fim, pense, você tem que fazer um swap de cada vez. 

Qual seria, potencialmente, o melhor caso de tempo de execução? Vamos apenas dizer que, se a lista já foi em ordem, o que poderia ser o tempo de execução? 

AUDIÊNCIA: n. ANDI Peng: É n, exatamente. E por que é n? AUDIÊNCIA: Porque você apenas tem que verificar em cada vez. ANDI Peng: Exatamente. Assim, na melhor execução possível, se esta lista já foi sorted-- digamos 1, 2, 3, 4-- você seria apenas passar, você iria verificar, você iria ver, oh, todos eles pan out. Eu não tive que trocar. Terminei. Então, nesse caso, é apenas n ou o número de passos que você acabou tinha que verificar na primeira lista. 

E depois, nós já atingiu tipo de inserção, onde o algoritmo é essencialmente a dividir -lo em uma parte classificada e indiferenciados. E em seguida, um por um, os valores são indiferenciados inserido na sua apropriada posições no início da lista. 

Assim, por exemplo, temos uma Lista de 3, 5, 2, 6, 4 novamente. Sabemos que é actualmente indiferenciados porque nós temos apenas comecei a olhar para ele. Vamos dar uma olhada e sabemos que o primeiro valor é ordenada, certo? Se você está apenas olhando para uma variedade de tamanho um, você sabe que ele está classificada. 

Então nós sabemos que o outros quatro são indiferenciados. Passamos por e vemos esse valor. Vamos voltar. Veja que o valor de 5? Vamos dar uma olhada nisso. Nós compará-lo a 3. Sabemos que é maior do que 3, por isso sabemos que isso está classificado. Portanto, sabemos agora que os dois primeiros são classificadas e os três últimos não são. 

Vamos dar uma olhada em dois. Primeiro vamos verificar isso com cinco. É menos do que 5? Não é. Então nós temos que ficar olhando para baixo. Em seguida, você verificar 2 off 3. É menos do que? Não. Então, você sabe a 2 tem que ser inserido na parte da frente e 3 e 5 ambos têm que ser empurrados para fora. Faça isso novamente com 6 e 4. E nós apenas manter a verificação, essencialmente, onde basta verificar, verificação, verificação. E até que seja na direita posição, que tipo de apenas insira-o na posição correta, que é onde o nome veio. 

Então, isso é apenas o algoritmo, pseudocódigo per se, tipo, em como iríamos implementar um tipo de inserção. Pseudocódigo é aqui. É tudo online. Não se preocupe se vocês são tentando copiar este para baixo. Então mais uma vez, mesmo que question-- seria a melhor e piores tempos de execução para inserção tipo? É muito semelhante à última pergunta. Eu vou dar a vocês, tipo, 30 segundos para pensar sobre isso também. 

OK Alguém quer dá-me o pior tempo de execução? Sim. 

AUDIÊNCIA: n ao quadrado. 

ANDI Peng: É n ao quadrado. E por que é que n ao quadrado? 

AUDIÊNCIA: Porque em ordem inversa, você tem passar por n vezes n, que é-- ANDI Peng: Sim, exatamente. Então, mesmo que na bubble sort. Se esta lista está em ordem decrescente, você é vai ter que verificar primeiro uma vez. E, em seguida, com toda valor adicional, você está vai ter que verificar se contra cada valor único, certo? E assim por completo, você está indo fazer um n vezes passar um outro n aconteceu, e que n é quadrado. E sobre o melhor caso? Sim. 

AUDIÊNCIA: n menos 1, porque o primeiro já é elevado ao quadrado. 

ANDI Peng: Então, fechar. A resposta é, na verdade, n. Porque enquanto o primeiro é classificadas, não pode actually---lo nós apenas tivemos sorte, em Nesse exemplo, que dois passou a ser o menor número. Mas isto não será sempre o caso. Se 2 já está classificado no início mas você olha e há um um aqui, o 1 vai bater-lo. E isso vai acabar sendo colidido de qualquer maneira. 

Assim, na melhor das hipóteses, ele é realmente só vai ser n. Se você tem 1, 2, 3, 4, 5, 6, 7, 8, você está vai percorrer que lista inteira uma vez para verificar para ver se está tudo bem. É claro que todos na corrida tempos de seleção também? Eu sei que eu estou passando estes realmente rápido. Mas só sei que se você sabe o conceitos gerais, você deve ser bom. ESTÁ BEM. Então eu vou dar a vocês talvez, como, um minuto para conversar com seus vizinhos sobre o que são apenas algumas das principais diferenças entre esses tipos de tipos. Nós falaremos sobre isso em breve. AUDIÊNCIA: Oh, OK. ANDI Peng: Sim. ESTÁ BEM. Cool, vamos reunir novamente com a classe. ESTÁ BEM. Portanto, este foi um tipo de pergunta aberta no sentido que há muitas respostas para elas. E nós vamos passar por cima de alguns deles brevemente. Eu só queria que você obtenha caras pensando sobre o que diferenciou os três tipos de tipos. E ouvi, também, uma grande question-- o que merge sort fazer? Ótima pergunta, porque é isso o que estamos cobrindo seguinte. 

Assim é o merge sort um tipo que funciona muito diferente dos outros tipos. Como vocês podem see-- Davi fez aquela demo onde ele tinha todo o legal ruídos de ver como mesclar tipo correu, como, infinitamente mais rápido do que os outros dois tipos? ESTÁ BEM. Então, isso é por causa de mesclagem tipo implementa essa divisão e conquistar conceito que nós temos falou sobre um monte na palestra. Nesse sentido que nós gostamos de trabalhar mais esperto, não mais difícil, quando você divide e conquistar problemas, e quebrá-las para baixo, e, em seguida, colocá-los juntos, coisas boas sempre acontecem. 

Assim, a maneira que se fundem tipo essencialmente funciona é que ele divide um matriz não triados pela metade. E então ele tem duas metades de matrizes. E ele só classifica essas duas metades. Ele apenas continua dividindo pela metade, em metade, ao meio até que tudo está classificada e, em seguida, de forma recursiva coloca tudo isso junto. 

Então isso é muito abstrato. Portanto, este é apenas um pouco de pseudocódigo. Isso faz sentido em a forma como ele está sendo executado? Então, vamos apenas dizer que você tem um matriz de n elementos, certo? Se n é inferior a 2, você pode retornar. Porque você sabe que, se houver apenas uma coisa, ele deve ser classificado. Senão, você classificar a metade esquerda, e então você classificar a metade direita, e então você se fundir. 

Assim, enquanto que parece realmente fácil, na realidade, pensando que é tipo de difícil. Porque você é como, bem, esse é o tipo de execução em si. Certo? Está funcionando em si. Então, nesse sentido, David tocou sobre a recursividade em sala de aula. E isso é um conceito vamos falar sobre mais. É que este, estas duas linhas aqui, na verdade, é apenas o programa dizendo que ele seja executado em si com entrada diferente. Então ao invés de executar-se com a totalidade de n elementos, você pode quebrá-lo para baixo na metade esquerda e metade direita e, em seguida, executá-lo novamente. 

E então nós vamos olhá-lo visualmente, porque eu sou um aprendiz visual. Ele funciona melhor para mim. Então, vamos olhar para um exemplo visual aqui. 

Vamos dizer que nós temos uma matriz, seis elementos, 3, 5, 2, 6, 4, 1, não classificados. Tudo bem, há muita coisa nesta página. Então, se vocês podem olhar para o primeiro passo aqui, 3, 5, 2, 6, 4, 1, você pode dividi-lo ao meio. Você tem 3, 5, 2, 6, 4, 1. Você sabe que estes aren't-- você Não sei se eles estão ou não classificados, para que você mantenha quebrando-as, ao meio, no meio, pela metade, até que finalmente, você só tem um elemento. E um elemento é sempre classificada, certo? 

Então, nós sabemos que 3, 5, 2, 4, 6, 1, por si só, são classificadas. E agora podemos juntá-los novamente. Então, nós sabemos a 3, 5. Colocamos esses juntos. Sabemos que é classificada. Os 2 ainda está lá. Podemos colocar o 4 eo 6 juntos. Sabemos que isso está classificado, por isso, colocar isso em conjunto. E a 1 existe. 

E então você simplesmente olhar para estas duas metades direita aqui. Tem a 3, 5, 2, 2, 3, 5. Você pode simplesmente comparar o começo de tudo. Porque você sabe que isto é separado e você sabe que isso está classificado. Então você não tem que mesmo comparar a 5, você acabou de comparar a 3. E o 2 é inferior a 3, assim você sabe que 2 deve ir no final. 

A mesma coisa por lá. A 1 deve ir aqui. E então, quando você vai para colocar esses dois valores, você sabe que isto é separado e você sabe que que está classificada. Então a 1 eo 2, o 1 é inferior a 2. Isso diz-lhe que o 1 deve percorrer no final desta sem sequer olhar para 3 ou 5. E então a 4, você pode apenas vá, ele vai para a direita aqui. Você não tem que olhar para o 5. Mesma coisa com o 6. Você sabe que a 6-- apenas não precisa ser olhado. 

E assim, dessa forma, você é salvando-se apenas um monte de passos quando você está comparando. Você não tem que comparar cada elemento contra outros elementos. Você só comparar contra os que você precisa para comparar contra. Então, esse é o tipo de um conceito abstrato. Não se preocupe se não é bastante bater-lhe ainda direita. Mas, geralmente, este é como uma espécie de mesclagem funciona. Perguntas, perguntas rápidas, antes de eu seguir em frente? Sim. 

AUDIÊNCIA: Então você disse que você toma a 1, e em seguida a 4, e o 6 e colocá-los em. Portanto, não são não são those-- você olhar para eles como elementos separados, e não como o todo? ANDI Peng: Sim. Então, o que está acontecendo é que você, basicamente, está criando uma nova matriz. Então você sabe que, aqui, eu tenho duas matrizes de tamanho 3, certo? Então, você sabe que a minha matriz classificada precisa de ter seis elementos. Então você acabou de criar uma nova quantidade de memória. Então você é tipo como de sendo um desperdício de memória, mas isso não importa porque é tão pequeno. Então você olha para o 1 e você olha para o 2. E você sabe que o 1 é inferior a 2. Então você sabe que um deve ir o início de tudo isso. 

Você não precisa mesmo de olhar para a 3 e 5 a. Então você sabe que um vai lá. Então você basicamente cortar a 1. É, tipo, morto para nós. Então só temos 2, 3, 5, e, em seguida, 4 e 6. E então você sabe que, você comparar a 4 e a 2, oh, o 2 deve ir para lá. Então você plop a 2 para baixo, você cortá-lo. Então, então você apenas tem a 3 e o 5 no 4 e 6 a. E você continua cortando-off até que você colocá-los na matriz. 

AUDIÊNCIA: Então você é apenas sempre comparando o [inaudível]? 

ANDI Peng: Exatamente. Então, nesse sentido, você é apenas comparando, essencialmente, um número contra o outro número. E porque você sabe que está classificada, você não tem que olhar através de todos os números. Você apenas tem que olhar para o primeiro. E então você pode apenas plop -los para baixo, porque você sabe eles pertencem onde eles precisam de pertencer. Sim. Boa pergunta. 

E, em seguida, se algum de vocês são um pouco ambicioso, sinta-se livre para olhar para este código. Esta é realmente a implementação física de como iria escrever merge sort. E você pode ver, é muito curto. Mas as idéias por trás que são bastante complexas. Então, se você sentir vontade de desenhar isso em sua lição de casa esta noite, sinta-se livre para. 

ESTÁ BEM. Então David também passou por isso na palestra. O que é o melhor caso tempos de execução, piores tempos de execução de caso, e os tempos de execução esperadas de merge sort? Um par de segundos para pensar. Isso é muito difícil, mas o tipo de intuitiva se você pensar sobre isso. Tudo certo. 

AUDIÊNCIA: É o pior caso n log n? ANDI Peng: Exatamente. E por que é n log n. 

AUDIÊNCIA: Não é porque torna-se mais rapidamente de forma exponencial, por isso é como uma função do que em vez de simplesmente sendo n quadrado ou algo assim? ANDI Peng: Exatamente. Assim, a razão pela qual o runtime sobre isso é log n n é porque-- o que é você fazendo em todos estes passos de? Você só está cortando-o ao meio, certo? E assim, quando estamos fazendo o log, tudo o que ele está fazendo está dividindo um problema no meio, ao meio, na metade, em mais metades. E, nesse sentido, você pode tipo de eliminar o modelo linear que temos vindo a utilizar. Porque quando você chop coisas pela metade, é um log. Isso é apenas a matemática maneira de representá-lo. 

E então, finalmente, no final, você é apenas fazendo uma última passagem para colocar todos eles em ordem, certo? E por isso, se você só tem que verificar uma coisa, que é n. E então você está tipo de multiplicando os dois em conjunto. Então, é como você tem que Final vá para n para baixo aqui com um registro de n aqui em cima. E se você multiplicar eles, que é n log n. 

E assim o melhor eo pior caso caso e espera são todos n log n. É também como um outro tipo. É como espécie seleção no sentido de que ele Não importa o que o seu lista é, ele só vai para fazer a mesma coisa a cada momento. ESTÁ BEM. Então, como vocês podem ver, mesmo que os tipos que temos ido through-- n quadrado, não é muito eficiente. E mesmo esse log n n é não é o mais eficiente. Se vocês são curiosos, há mecanismos de ordenação que são tão eficientes que eles são quase essencialmente plana em tempo de execução. 

Você tem um pouco de log n. Você tem alguma log log n de. Nós não toque sobre eles nesta classe agora. Mas se vocês estão curiosos, sinta-se livre para o Google, o que é os mecanismos de triagem mais eficientes. Eu não sei, existem alguns realmente engraçado, como-- há alguns realmente mais engraçados que as pessoas fazem. E você quer saber como eles nunca pensei nisso. Então, o Google, se você tem alguma reposição tempo, em, quais são algumas maneiras engraçadas que bem como pessoas-- eficientes pessoas ways-- têm sido capazes de implementar os tipos. ESTÁ BEM. E aqui está um pouco gráfico útil. Eu sei que todos vocês, antes que teste 0, estará em seu quarto, provavelmente, tentando para memorizar que. Então, isso é bom lá para vocês. Só não se esqueça a lógica que made-- por que esses números estavam ocorrendo. Se você está sempre perdido, basta fazer se você sabe o que os tipos são. E você pode executar através los em sua mente para descobrir por que os respostas são essas respostas. 

Tudo certo. Então, nós estamos indo para mover em, finalmente, para a pesquisa. Porque, como aqueles de vocês que leram o pset, pesquisa também faz parte da problema desta semana define. Você será solicitado para implementar dois tipos de pesquisas. Um deles é uma pesquisa linear e é uma pesquisa binária. 

Assim, a busca linear é bastante fácil. Você só quer procurar elemento de uma lista para ver se você obtê-lo. Você apenas tem para percorrer. E se ele é igual a alguma coisa, você pode simplesmente devolvê-lo, certo? Mas o que nós somos mais interessado em falar sobre é a busca binária, à direita, que é a dividir e conquistar mecanismo que David estava demonstrando em conferência. 

Lembre-se o exemplo do livro de telefone que ele continua trazendo à tona, o que ele meio que se esforçou um pouco sobre o ano passado, onde você dividir o problema pela metade, ao meio, ao meio, uma e outra vez, até encontrar o que você está procurando? E você tem o runtime do que bem. E você pode ver, é significativamente mais eficiente do que qualquer outro tipo de pesquisa. 

Assim, a maneira que nós iria sobre execução de uma pesquisa binária é, se nós tivéssemos uma matriz, índice de 0 a 6, sete elementos, podemos olhar no meio, direita-- desculpe, se nossa pergunta first-- se queremos fazer a pergunta de, faz a matriz conter o elemento de 7, Obviamente, sendo os seres humanos, e tendo tais uma pequena variedade, é fácil para nós para dizer sim. Mas a maneira de implementar um binário busca seria a de olhar no meio. 

Sabemos que o índice 3 é no meio, porque nós sei que há sete elementos. O 7 dividido por 2? Você pode cortar esse extra 1. Você tem três no meio. Então é matriz de 3 igual a 7? Não está certo? Mas podemos fazer um par de cheques. É gama de 3 a 7 ou menos 3 é de matriz maior do que 7? 

E nós sabemos que ele é inferior a 7. Então, nós sabemos que, oh, ela deve não estar na metade esquerda. Sabemos que ele deve ser na metade direita, certo? Assim, podemos apenas cortar metade do array. Nós nem sequer têm de mais olhar para ela. Porque nós sabemos que metade do nosso problema-- nós sabemos que a resposta está em a metade direita do nosso problema. Portanto, basta olhar para isso agora. 

Então, agora olhamos para o meio do que restou. Esse índice 5. Nós fazemos a mesma verificação novamente e vemos que ele é menor. Então, nós olhamos para a esquerda do que isso. E então vemos que cheque. É o valor da matriz em índice 4 igual a 7? Isto é. Assim, podemos retornar verdadeiro, porque encontramos o valor em nossa lista. Será que a maneira que eu atravessei que faz sentido para todo mundo? ESTÁ BEM. Eu vou dar a vocês talvez, como, três, quatro minutos para descobrir Pseudocódigo como este no. 

Então imagine eu lhe pedi para escrever uma chamado função search () que retornaram um valor, um valor booleano, isso era verdade ou false-- como, verdadeiro se você encontrou a valor, falso se você não fez. E então você estava passou no valor você estava procurando em valores, que é o array-- oh, eu definitivamente colocá que no lugar errado. ESTÁ BEM. De qualquer forma, que deve ter foi para a direita de valores. E, em seguida, int n é o número de elementos dessa matriz. Como você iria sobre a tentativa Pseudocódigo para esse problema em? Eu vou dar a vocês como três minutos para fazer isso. Não, eu acho que há only-- sim, há um aqui em cima. AUDIÊNCIA: Posso? ANDI Peng: Sim, eu tenho você. É que trabalhar? OK legal. 

ESTÁ BEM. Todos os caras certos, nós somos vai controlá-lo em. ESTÁ BEM. Então assumir que temos esta linda pouco matriz com valores de n na mesma. Eu não desenhar as linhas. Mas como é que nós vamos sobre tentando escrever isso? Alguém quer dá-me a primeira linha? Se você quiser me dar o primeira linha deste pseudocódigo. 

AUDIÊNCIA: [inaudível] AUDIÊNCIA: Você iria querer iterar through-- AUDIÊNCIA: Só mais um para loop? AUDIÊNCIA --para. 

ANDI Peng: Então, este é um pouco complicado. Pense about-- você quer para continuar correndo esse loop uma e outra vez até quando? 

AUDIÊNCIA: Até o [inaudível] valor que é igual ao valor. ANDI Peng: Exatamente. Então você pode realmente apenas write-- podemos até mesmo simplificá-lo mais. Nós podemos apenas fazer um loop while, certo? Então você pode apenas ter loop-- sabemos que é um tempo. Mas, por agora, eu vou para dizer "laço" - através do que? Laço que é until-- nossa condição terminando? Acho que ouvi-lo. Ouvi alguém dizer isso. 

Audiência: Valores iguala meio. ANDI Peng: Diga isso de novo. AUDIÊNCIA: Ou, até o valor que você está procurando para é igual ao valor médio. 

ANDI Peng: O que se ele não está lá? E se o valor que você está pesquisando para não é realmente nessa matriz? AUDIÊNCIA: Você retorna 1. 

ANDI Peng: Mas o que queremos loop até que se nós tem uma condição? Sim. 

AUDIÊNCIA: Até que haja apenas um valor? ANDI Peng: Você pode fazer um loop until-- para que você saiba que você é vai ter um valor máximo, certo? E você sabe que você está indo para ter um valor min, certo? Porque também, isso é algo Eu esqueci de dizer antes, que algo que é crítica sobre busca binária é que sua matriz já está classificado. Porque não há nenhuma maneira de fazê- isso se eles são apenas valores aleatórios. Você não sabe se é maior que o outro, certo? 

Então, você sabe que o seu máximo e seus mins está aqui, certo? Se você vai estar se adaptando seu máximo em seus minutos e os mid-- vamos assumir o seu valor médio é aqui-- direita você está indo para, basicamente, loop até sua mínima é de sobre o mesmo como seu máximo, à direita ou se o seu máximo não é o mesmo que o seu min. Certo? Porque quando isso acontece, você sabe que você, eventualmente, acertar o mesmo valor. Então você quer fazer um loop até que o seu min é inferior ou igual a-- oops, não menos do que ou igual a, a outra maneira é circundar-- max. 

Será que isso faz sentido? I levou algumas tentativas para obter esse direito. Mas loop até que o seu valor máximo é essencialmente quase menos ou igual a seu mínimo, certo? Isso é quando você sabe que você já convergiram. AUDIÊNCIA: Quando seria o seu máximo valor pode ser inferior ao mínimo? ANDI Peng: Se você mantiver ajustando-o, o que é o que nós estamos indo estar fazendo neste. Isso faz sentido? Mínimo e máximo são apenas inteiros que são, provavelmente, vai querer criar para manter o controle de onde nós estamos olhando. Como a matriz existe independentemente do que estamos fazendo. Como, nós não estamos fisicamente decepar a matriz, certo? Estamos apenas ajustando onde nós estamos olhando. Isso faz sentido? 

AUDIÊNCIA: É. 

ANDI Peng: OK. Então, se essa é a condição para o nosso loop, o que queremos dentro deste loop? O que vamos estar querendo fazer? Então, agora, nós temos um máximo e um mínimo, direito, Provavelmente criou-se aqui em algum lugar. Nós vamos provavelmente quer para encontrar um meio, certo? Como é que vai ser capaz de encontrar o meio? Qual é a mathematical-- AUDIÊNCIA: Max além min divididos por dois. ANDI Peng: Exatamente. Isso faz sentido? E que vocês ver porque nós não apenas use-- por que fizemos isso em vez de fazer apenas n dividido por 2? É porque n é um valor que vai ficar na mesma. Certo? Mas porque nós ajustamos nossa mínimo e valores máximos, eles vão mudar. E, como resultado, o nosso meio vai mudar também. Então é por isso que queremos para fazer isso aqui mesmo. ESTÁ BEM. 

E então, agora que nós encontramos our-- sim. 

AUDIÊNCIA: Apenas um question-- rápida quando você diz min e max, assumindo que estamos ele já está classificado? 

ANDI Peng: Sim, isso é realmente uma condição prévia para uma busca binária, que você tem que saber que está classificada. É por isso que tipo, você escreve no seu conjunto de problemas antes de sua busca binária. ESTÁ BEM. Portanto, agora que sabemos onde nosso ponto médio é, o que você quer fazer aqui? 

AUDIÊNCIA: Queremos comparar que para o outro. ANDI Peng: Exatamente. Então você está indo para comparar meados de valor, certo? E o que dizer isso nós quando se comparam? O que nós queremos fazer depois? 

AUDIÊNCIA: Se o valor for maior de meados dos anos, queremos cortá-lo. ANDI Peng: Exatamente. Então, se o valor for maior de meados dos anos, estamos vai querer alterar essas Maxes mínimo e, certo? O que nós queremos mudar? Então, se nós sabemos o valor está em algum lugar aqui, o que você que mudar? Nós queremos mudar a nossa mínimo a ser mid, certo? E então outra coisa, se é neste metade, o que nós queremos mudar? 

AUDIÊNCIA: O seu máximo. ANDI Peng: Sim. E então você só vai para manter looping, certo? Porque agora, depois de uma iteração através, você tem um máximo aqui. E então você pode recalcular um mid. E então você pode comparar. E você está indo para continuar até os minutos e as Maxes ter essencialmente convergentes. E isso é quando você sabe que você bateu o fim de tudo. E quer você encontrou- ou você não tem nesse momento. 

Será que isto faz sentido para todo mundo? ESTÁ BEM. Isso é muito importante, porque você vai ter para escrever isso em seu código de hoje à noite. Mas vocês têm uma boa sensação de que você deveria estar fazendo, qual é bom. ESTÁ BEM. Então, nós temos cerca de sete minutos seção esquerda. Então, nós estamos indo falar sobre este pset que nós estaremos fazendo. Assim, o pset é dividido em duas metades. A primeira metade envolve a implementação de um find no qual você escreve uma busca linear, um busca binária, e um algoritmo de ordenação. 

Portanto, este é o primeiro tempo num pset onde estaremos dando a vocês o que é chamado código de distribuição, que é o código que temos pré-escrito, mas apenas deixou algumas peças off para que você terminar de escrever. Então vocês, quando você olha para esta código, você pode ficar realmente assustado. Se você está apenas como, ahh, eu não sei o que está fazendo, Eu não sei, como, que parece tão complicado, ahh, relaxar. Está certo. Leia o spec. A especificação irá explicar-lhe exatamente o que todos esses programas estão fazendo. 

Por exemplo, é um programa generate.c que virá com sua pset. Você realmente não tem que tocá-lo, mas você deve entender o que está fazendo. E generate.c, tudo o que está fazendo é quer gerar números aleatórios ou você pode dar-lhe uma semente, como um número preestabelecido que leva, e gera mais números. Portanto, há uma maneira específica para implementar no qual generate.c você pode apenas fazer um monte de números para você testar seus outros métodos diante. 

Então, se você queria, para exemplo, testar a sua descoberta, você iria querer correr generate.c, gerar um monte de números, e em seguida, executar a função de ajudantes. Sua função ajudantes é o lugar onde você está realmente escrever fisicamente código. E pensar ajudantes como um arquivo de biblioteca você está escrevendo que find está chamando. E assim dentro helpers.c, você vai fazer pesquisa e classificação. 

E então você vai, essencialmente, apenas colocá-los todos juntos. A especificação irá dizer-lhe como colocar isso na linha de comando. E você vai ser capaz de testar se ou não o seu tipo e de pesquisa estão trabalhando. Legal. Alguém já começou e problemas encontrados ou perguntas eles têm agora com isso? ESTÁ BEM. 

AUDIÊNCIA: Espere. Eu tenho uma pergunta. 

ANDI Peng: Sim. 

AUDIÊNCIA: Então eu comecei a fazer a busca linear em helpers.c e não foi realmente funcionando. Mas, em seguida, mais tarde, descobri que acabamos tem que excluí-lo e fazer busca binária. Então, não importa se ele não funcionar? 

ANDI Peng: resposta curta é não. Mas já que estamos não-- AUDIÊNCIA: Mas ninguém de realmente verificar. ANDI Peng: Nós nunca somos vai ver isso. Mas você provavelmente vai querer fazer Certifique-se a sua pesquisa está funcionando. Porque se seu linear Pesquisa não funciona, então as chances são o seu binário pesquisa não vai funcionar tão bem. Porque você tem semelhante lógica em ambas. E não, isso realmente não importa. Então, os únicos que você vai virar em são uma espécie e busca binária. Sim. 

E também, um monte de crianças foram tentar compilar helpers.c. Você não está realmente permitido para fazer isso, porque helpers.c não tem uma função principal. E assim você só deve ser realmente compilando gerar e encontrar, porque encontrar chamadas helpers.c e as funções dentro dela. Assim que torna a depuração uma dor na bunda. Mas isso é o que temos que fazer. AUDIÊNCIA: Você acabou de fazer tudo, certo? ANDI Peng: você pode apenas fazer tudo bem, sim. ESTÁ BEM. Então é isso em termos do que o pset está pedindo que todos vocês façam. Se você tiver alguma dúvida, sinta- livre para me perguntar depois seção. Eu vou estar aqui para, como, 20 minutos. 

E sim, os PSet de não é realmente tão ruim assim. Vocês devem estar OK. Estes, basta seguir as orientações. Tipo de ter um senso de, logicamente, o que deveria estar acontecendo e você vai ficar bem. Não fique muito assustado. Há um monte de código já escrito lá. Não tenha muito medo se você não faz entender o que tudo isso significa. Se é muito, é totalmente bem. E chegar a horas de expediente. Nós vamos ajudá-lo a dar uma olhada. 

AUDIÊNCIA: Com a adicional funções, parecemos aqueles acima? 

ANDI Peng: Sim, essas são no código. No jogo de 15, metade dos ele já está escrito para você. Assim, estas funções sejam já no código. Sim. Tudo certo. Bem, melhor sorte. É um dia nojento. Portanto, esperamos que vocês não me sinto muito mal por ficar dentro e codificação.