COLUNA 1: Olá a todos! Bem-vindo de volta à seção. Tão feliz de ver tantos de vocês, tanto aqui, e todo mundo que está assistindo online. Assim, como bem-vindo de volta habitual. Espero que todos tenham tido um lindo fim de semana, cheio de descanso, relaxamento. Foi lindo ontem. Então, espero que tenham gostado do ar livre. 

Então, primeiro de um par de anúncios. Grading. Assim, a maioria de vocês deve ter ficado um enviar e-mail de mim sobre o seu Pset Scratch bem como classificação para Pset 1. Assim, apenas um par de coisas. Certifique-se de usar check50 em style50. Estas são destinadas a ser recursos para vocês, para se certificar de que você está recebendo tantos pontos como você pode sem perdê-los desnecessariamente. Então, coisas como estilo são muito importantes. Nós estamos indo para decolar para ele. Alguns de vocês já podem ter notado que a partir de seu Pset. E check50 é apenas um maneira muito fácil de se certificar que na verdade estamos devolvendo o que necessita de ser devolvida para o utilizador, e que tudo está funcionando corretamente. 

Na segunda nota, certifique-se o seu upload coisas para a pasta correta. Faz minha vida apenas um pouco mais difícil se você carregar Pset 2 em 1 Pset porque quando eu baixar coisas, eles não baixar corretamente. E eu sei que é um pouco instável, em um sistema para se acostumar, mas apenas ser super cuidado, se só para mim, de modo que quando você está recebendo e-mails em como 2:00 e eu sou de classificação. Se não causar eu tenho que olhar tudo em torno de sua Pset. Legal. 

Eu sei que é cedo, mas eu totalmente fui pego de surpresa por um ensaio que é devido esta sexta-feira, que meus professores foram apenas como, oh sim. Lembre-se, você tem um ensaio devido na sexta-feira. Então, eu sei que ninguém gosta para pensar midterms, mas seu primeiro teste é em 15 de outubro, que outubro é a partir desta semana. Assim, pode ser mais cedo do que o esperado é tudo. Assim que você não está jogado de surpresa quando Menciono seção da próxima semana que oh, seu teste na próxima semana, eu pensei Eu te daria um pouco mais de um heads-up agora. 

Assim, seu conjunto de problemas, o número três. Como as pessoas leram o especificação por curiosidade? Está bem. Temos um casal. Tipo de baixo da última semana, mas isso é OK. Eu sei que era belo fora. Então Break Out. Definitivamente depois de ter feito ler hoje a sua especificação, pelo menos, tente como download código de distribuição e execução como a primeira inicial coisa que pedir para você. Como estamos usando código de distribuição e uma biblioteca que só tenho using-- --É só é a segunda vez que fiz isso Pset, coisas malucas pode acontecer com o seu aparelho, e você quer descobrir que para fora agora contra mais tarde. 

Porque se é noite de quinta ou é Quarta-feira e, por algum motivo o aparelho simplesmente não faz quero correr com a biblioteca ou com a distribuição código, o que significa você não pode sequer começar a fazer a codificação. Porque você não pode verificar para ver se funciona. O seu não vai ser capaz para ver se ele compila. Você quer cuidar das pessoas no início semana, quando você ainda pode enviar e-mail me ou um dos outros FT, e podemos obter os fixados. Porque essas são questões que vão pará-lo de fazer qualquer progresso real. Não é como um bug, que você pode apenas uma espécie de pular. Se você está tendo problemas com o seu aparelho ou código de distribuição, você realmente quiser se que tomadas cuidar de, mais cedo ou mais tarde. Assim, mesmo se você não está indo realmente iniciar a codificação, baixar a distribuição código, leia a especificação, certifique-se tudo está funcionando lá. Ok? Se você só pode fazer isso, eu prometer sua vida será mais fácil. E assim, você provavelmente vai para fazê-lo agora certo? Está bem. Assim, todas as perguntas lá? Quaisquer coisas de logística? Todo mundo é bom? Está bem. 

Disclaimer para aqueles de você no quarto e online. Vou estar tentando mudar entre PowerPoint no aparelho porque nós estamos indo estar fazendo alguma codificação hoje pela demanda popular do anonymous sugestão enquete eu enviei na semana passada. Então, vamos fazer alguma codificação. Então, se vocês também querem ao fogo até seus aparelhos, e você deve ter conseguido um e-mail de mim, com um arquivo de exemplo. Por favor, sinta-se livre para fazer isso. 

Então, vamos falar sobre GDB, que é um depurador. Ele vai ajudar você tipo de descobrir onde as coisas vão mal no seu código. É realmente apenas uma maneira de você para a etapa através de seu código que está acontecendo, e ser capaz de imprimir variáveis ou ver o que está realmente acontecendo sob o capô versículos seu programa apenas correr, é como falha, e você fica tipo, nenhuma idéia o que aconteceu aqui. Eu não sei o que ele falhou na linha. Eu não sei onde ele errou. Então, GDB vai te ajudar com isso. Além disso, se você decidir continuar sim, e ter 61, ele vai realmente ser o seu melhor amigo, porque eu posso te dizer porque eu estou passando por essa classe. 

Nós vamos olhar para binário pesquisa, que se vocês se lembrar o grande exemplo de catálogo telefônico espetáculo de classe. Nós estaremos implementando isso, e caminhando por isso um pouco mais, e então nós estamos passando por quatro diferentes tipos, que são bolha, Seleção, Inserção, e mesclar. Legal. Então, GDB como mencionei, é um depurador. E estes são uma espécie de grande coisas, as grandes funções ou comandos que você usa dentro GDB, e eu andarei você através de uma demonstração de que em um segundo. 

Portanto, este não é apenas vai ficar abstrato. Vou tentar fazê-lo como concreto possível para vocês. Então, quebrar. Ele quer estará pausa como, um número, que representa uma linha em seu programa, ou pode nomear uma função. Então, se você diz quebrar principal, ele vai parar em principal, e deixá-lo andar por essa função. 

Da mesma forma, se você tem alguma externo funcionam como Trocar ou Cube, que olhou para a semana passada. Se você disser que quebrar um daqueles, sempre que o seu programa de bate que, ele vai esperar para você diga a ele o que fazer. Antes ele só vai executar para que você realmente pode pisar dentro da função e ver o que está acontecendo. Então, da próxima, apenas ignora o próxima linha, vai mais funções. Step. Estas são todas pouco abstrato. Então, eu estou indo só para passar por eles, mas você vai vê-los em uso em um segundo. 

Entrar em uma função. Então, como eu estava dizendo, como com swap, que seria permitem que você, na verdade, se você estiver como entrar fisicamente no interior, você pode mexer com essas variáveis, impressão o que eles são, ver o que está acontecendo. Lista vai literalmente apenas imprimir o código circundante. Então, se você tipo de esquecer onde você está no seu programa, ou você está se perguntando o que está acontecendo ao seu redor, isso só vai imprimir um segmento de como cinco ou seis linhas em torno dele. Assim, você pode se orientar sobre onde você está. 

Imprimir alguma variável. Então, se você tem a chave como em César, que vamos olhar. Você pode dizer-chave impressão em qualquer ponto. Ele vai dizer-lhe que o valor é tão que, talvez em algum lugar ao longo do caminho, você substituiu a sua chave. Você pode realmente dizer que, por causa você pode realmente observar esse valor. 

Nos locais, apenas impressões as suas variáveis ​​locais. Então, quando você está dentro de um loop, e você só quer ver como, oh. Qual é o meu eu? O que é este valor de chave que eu inicializar aqui? Qual é a mensagem neste momento? Ela só vai imprimir tudo daqueles, de maneira a ficar não tem que individualmente dizer, I. Imprimir Imprimir mensagem. Imprimir Key. E em seguida, exibir. O que faz é como você passo através do programa, ele só vai ter certeza de que ele é exibindo alguns determinada variável em todos os pontos. Para que você Também-- --é uma espécie de atalho, onde você não tem que continuar assim, oh. Chave de impressão ou impressão I. Ele só irá automaticamente fazer isso por você. 

Então, com isso, vamos para ver como isso vai. Eu vou tentar e interruptor para o meu aparelho. Veja se eu posso fazer isso. All. Nós apenas estamos indo para espelhar-lo. Não há nada de louco no meu laptop de qualquer maneira. Está bem. Isso precisa ser um presente. É tão pequena. Vamos ver se podemos fazer isso. 

Está bem. Alice está obviamente lutando aqui só um pouco, mas nós vamos buscá-la em um momento. Está bem. Nós apenas estamos indo para aumentar isso. Está bem. Todos podem ver que tipo de? Talvez um pouco? Eu sei que é um pouco pequeno. Você não consegue descobrir como fazer esta maior. Se alguém souber. Alguém sabe como fazê-lo maior? Está bem. Nós vamos rolar com ele. Não importa de qualquer maneira, porque é só esse é o código que vocês deveriam ter. 

O que é mais importante é o terminal aqui. E nós temos aqui Por que é tão pequeno? Configurações. Oh. Verdadeiro Ike. Como é isso? Fora de lá. Isso é melhor para todos? Está bem ,. Legal. 

Sabe quando você está em um CS classe dificuldades técnicas são uma espécie de parte de as-- Então, vamos esclarecer isso. Está bem. Então, aqui na seção, que tivemos aqui. César é um arquivo executável. Então eu fiz isso. Então, uma coisa a perceber é com o GDB que ele só funciona em arquivos executáveis. Então, você não pode executá-lo em um Dotsy. Você tem que realmente fazer Certifique-se de que o seu código é compilado, e que, na verdade, pode ser executado. 

Então, certifique-se de que, se isso não acontecer compilar, obtê-lo para compilar, de modo que você pode tipo de correr com ele. Então, para começar GDB, tudo que você faz, Gloria tipo GDB, e então apenas o arquivo que você deseja. Eu sempre cometer erros de ortografia César. Mas você quer ter a certeza já que é um executável, Flash ponto de ti para que significa que você vai para executar CSI você está indo para executar este arquivos ou com o depurador. Está bem. Então, você que, você começa este tipo de rabiscos. É apenas sobre todas as coisas depurador. Você realmente não tem que se preocupe com isso agora. E como você pode ver, temos esta parênteses em aberto, o PIB, parênteses próximos, e apenas se parece com nossa linha de comando, certo? 

Então, o que nós queremos fazer-- --So, A primeira coisa é que nós queremos escolher um lugar para quebrá-lo. Então, há um bug neste programa Caesar que apresento, que vamos descobrir. É o que faz é que leva a entrada Barfoo em todas as tampas, e por alguma razão isso não muda A. Ele só deixa sozinho, é tudo mais correta, mas a segunda letra A permanece inalterado. Então, nós estamos indo para tentar descobrir por que isso acontece. Então, a primeira coisa que você normalmente quero fazer sempre que você começar em GDB é descobrir onde a quebrá-lo. 

Então, César é um pequena programa. Nós só temos uma função, certo? Qual foi a nossa função no Caesar? Há apenas uma função, certo Main? Principal é uma função para todos os seus programas. Se você não tem Main, eu poderia ser um pouco preocupado agora, mas espero que todos tenham tido principal lá. Então, o que podemos fazer é que podemos apenas quebrar principal, apenas como aquele. Assim, ele diz, OK. Montamos nosso único breakpoint lá. 

Então, agora a coisa a lembrar é de César leva um argumento de linha de comando para a direita e nós não temos feito isso em qualquer lugar ainda. Então, o que você faz é quando você realmente ir a correr o programa, qualquer programa que você está funcionando em GDB que precisa de linha de comando argumentos, você está indo para a entrada quando você começar a executá-lo. Então, neste caso, o que fazemos Corra com uma chave de três. E ele vai realmente começar. 

Então, se você vê aqui, temos Se RC não é igual a 2. Então, se vocês todos têm esse arquivo que eu enviei-se você vai ver que isso é como o primeira linha a nossa função principal, certo? Ele está verificando para ver se temos o número correto de argumentos. Então, se você está se perguntando RC se está correto, você pode fazer algo como impressão RC. RC é de dois, que é o que esperávamos, certo? 

Então, podemos ir Em seguida, e continuam até. Então, nós temos alguma chave lá. E podemos imprimir nossa chave para se certificar de que está correto. Interessante. Não é bem o que esperávamos. Então, uma coisa a perceber com o GDB também, é que não é até que você realmente acertar Em seguida, que a linha que você acabou de ver é realmente executada. Assim, neste caso Key não tenha ainda sido atribuído. Então, Key é algum valor de lixo que você vê na parte inferior lá. Negativo $ 120-- --é um bilhão e algo que coisas estranhas certo? Não é a chave que esperávamos. Mas se nós batemos em Avançar e, em seguida, tentar chave de impressão, é três. 

Todo mundo vê isso? Então, se você conseguir alguma coisa que você gosta, espere. Isto é completamente errado, e eu não sei como isso iria acontecer, porque tudo que eu quero fazer é atribuir um número, uma variável, tentar bater seguida, tente imprimir de novo, e ver se isso funciona. Porque ele só vai executar e na verdade, atribuir alguma coisa depois que você clique em Next. Fazer sentido para todos? Uh huh? 

COLUNA 2: Quando você aleatório números o que isso significa? 

COLUNA 1: É apenas aleatória. É apenas lixo. É apenas algo que o seu computador irá atribuir ao acaso. Legal. Então, agora podemos passar através, e assim por agora temos este GetString texto simples. Então, deixe-me apresentar o que vai acontecer quando nós batemos seguida aqui. Nossa GDB tipo de desaparece, certo? Isso porque GetString agora está em execução, certo? Então, quando vimos texto simples é igual a GetString, parênteses abertos e parênteses, e clique em Next, que tem realmente executada agora. Então, ele está esperando por nos a entrada de algo. 

Então, nós estamos indo para a entrada a nossa comida que é o que está falhando, como eu disse a você e que apenas diz que é terminar a execução, que o fechou suporte significa que é sai fora desse circuito. Assim, podemos bater seguida, e agora, como eu sou certeza de que está familiarizado de César, isto é, o que é esta linha vai fazer. É para Int I é igual a 0, N é igual a Strlen, texto simples e, em seguida, I é menor que n, I, plus, plus. O que é este laço vai fazer? Abra a sua mensagem. Legal. Então, vamos começar a fazer isso. 

Assim, se esta condição corresponder, para o nosso primeiro? Se é um B, é texto simples I. pode obter informações sobre os nossos moradores. Assim, I é zero, e se seis, que esperamos, e nossa chave é três. Tudo o que faz sentido, certo? Esses números são todos exatamente o que deve ser. Então, hum? COLUNA 3: Eu tenho números aleatórios para mim. COLUNA 1: Bem, podemos check-- --nós pode conversar sobre isso em um segundo. Mas você deve estar recebendo este. Então, se temos um capital B para o nosso primeiro, esta condição deve pegá-lo, certo? Então, se nós batemos Em seguida, vemos que esta Se realmente executa. Porque se você está seguindo ao longo de seu código, essa linha aqui, onde texto simples I é substituído com esta aritmética, só é executado caso a caso condição é certo correto? 

GDB só vai mostrar-lhe as coisas que são realmente execução. Então, se essa condição Se não foi cumprida, é só vai pular para a próxima linha. Ok? Então, nós temos que. Este suporte significa que é fechado fora desse ciclo agora. Então, ele vai começar de novo. Apenas isso. Então, que possamos obter informações sobre nossos moradores aqui, e vemos que o nosso primeiro letra mudou, certo? É agora um E, como deveria ser. Assim, podemos continuar. 

E nós temos essa verificação. E essa verificação deve funcionar, certo? É A. Deve ser mudado três cartas para a frente. Mas se você observar, nós obter algo diferente. Portanto, neste caso aqui em cima, ele pegou -lo, e assim que esta linha executada, que modificou a nossa B. Mas, neste caso aqui, temos que simplesmente ignorados, e fui para o [? L Siff. ?] Então, alguma coisa está acontecendo lá. O que está dizendo é que, sabemos que ele deve pegar aqui, mas não é. Qualquer um pode ver o que o nosso problema é nessa linha? É uma coisa muito minuto. E você também pode olhar para o seu código. É também linha-- esquecer que linha é em há-- mas é no [inaudível]. Sim? 

COLUNA 4: É no maior do que página, se você lê-lo no livro. COLUNA 1: Exatamente. Assim, o depurador não poderia dizer isso, mas o depurador poderia fazê-lo para baixo a uma linha que você sabe que não está funcionando. E às vezes, quando especialmente no final do semestre, quando você está lidando com uma centena, uma centena de algumas linhas de código, e você Não sei onde ele está falhando, esta é uma ótima maneira de fazê-lo. Assim, encontramos o nosso erro. Você pode corrigi-lo em seu arquivo, e, em seguida, você pode executá-lo novamente, e tudo funcionaria perfeitamente. E a coisa mais importante é isso pode parecer, OK. Sim. Legal. Você sabia que você está procurando. Então, você sabia o que fazer. 

GDB pode ser super útil porque você pode imprimir todas essas coisas que você não o faria. É muito mais útil do que printf. Quantos de vocês usam como declarações printf para descobrir onde um erro foi, certo? Então, com isso, você não tem que manter a voltar, e gosta de comentar em Printf, ou comentar, e descobrir o que você deve ser a impressão. Este, na verdade, apenas permite que você percorrer, imprimir coisas como você está passando, por isso, você pode observar como eles mudam em tempo real, como o programa está sendo executado. 

E isso leva um pouco pouco de tempo para se acostumar. Eu recomendo apenas uma espécie de ser um pouco frustrado com isso para agora. Se você passar uma hora sobre o próxima semana aprendendo a usar o GDB, você vai salvar tanto tempo mais tarde. E literalmente. dizemos isso para as pessoas a cada ano, e eu me lembro quando eu tirei o classe, eu era como, eu vou ficar bem. Não. Pset 6 chegou e eu estava como, eu vou aprender como usar o GDB porque eu não saber o que está acontecendo aqui. 

Então, se você tomar o tempo para usá-lo em programas menores que você está indo para ser trabalhando, como trabalhar por algo como Visionare, como este. Ou se você quiser prática extra, tenho certeza Eu poderia vir acima com programas de buggy, para que você possa depurar se você gostaria. 

Mas se você apenas levar algum tempo para chegar acostumar com isso, apenas brincar com ele, ele realmente vai atendê-lo bem. E é realmente uma das aquelas coisas que você só tem que tentar, e sujar as mãos com, antes de realmente entendê-la. Eu realmente só entendi uma vez Eu tinha de depuração coisas com ele, e é muito mais agradável para ter uma idéia do como depurar, mais cedo ou mais tarde. Está bem. Legal. Eu sei que é tipo como um curso intensivo de GDB, e com certeza vou trabalhar para ter estes para parecer maior da próxima vez. Legal. 

Assim, se voltarmos para o nosso PowerPoint. Será que isso vai funcionar? Awh. Sim. Está bem. Então, se você precisar de qualquer um dos aqueles novamente, há a lista. Pesquisa Então binário, que todos lembra o grande espetáculo de David rasgando telefone livros pela metade. Eu realmente não entendo o livros de telefone mais, porque, como onde você obter livros de telefone nos dias de hoje? Eu realmente não sei. A busca binária. Alguém se lembra Como Binary trabalhos de pesquisa? Qualquer um em tudo? Sim? COLUNA 5: Você sabe quando você olhar para que metade seria em, Com base nisso, e livrar-se da outra metade. 

COLUNA 1 Exatamente. Então, Pesquisa Binária, é uma espécie de a-- --nós gostamos de chamá-lo de dividir e conquistar. Então, o que você vai fazer é você vai olhar no meio, e você vai ver se ele corresponde o que você está procurando. E se isso não acontecer, então você tenta descobrir, é que vai ser deixado metade ou a metade direita. Então, isso pode ser se você está procurando em algo que está em ordem alfabética, veja você, oh. Será que Allison vir antes M? Sim. Então, nós estamos indo para olhar para o primeiro semestre. 

Ou pode ser como com os números. Qualquer coisa que você puder comparar, ele pode ser resolvido. Você pode usar a pesquisa binária em. Então, alguém se lembra deste gráfico ou o que é isso? É Complexidade assintótica. Assim, este gráfico apenas descreve o tempo que leva você para resolver um problema como você aumenta o número de coisas que você está usando. 

Então, nós temos N, que é o tempo linear. Se N ao longo de dois, o que é ligeiramente melhor, ainda cresce super rápido. E então temos de login, que é o que consideramos Binary Search. Se notarmos, como o seu problema fica muito mais e muito maior, o tempo que você leva para resolvê-lo não vai aumentar muito. É como comparável aqui no início. Você é como, OK. Qualquer coisa aqui realmente não importa qual nós usamos, mas você sair de um milhão, um bilhão. Você está tentando encontrar some-- --you're tentando encontrar uma agulha num palheiro. 

Eu acho que você quer este problema. Você quer que esta complexidade, não linear porque para tudo o que você conhecer o seu vai estar procurando por cada agulha indivíduo, coisa de feno, tentando olhar para a agulha. E isso não é muito divertido, na minha opinião. Gosto rápido. Eu gosto eficiente. E estudantes, trabalhadoras você caras são, sabem trabalhar de forma mais inteligente, não mais difícil tipo de coisa, como você pode tornar-se estes algoritmos. 

Então, nós estamos indo a pé através de apenas um exemplo rápido. Eu acho que vocês devem ter uma mão em Pesquisa Binária, mas no caso de alguém é um pouco difusa, quer reforçá-lo, vamos apenas ir através de um exemplo aqui. Então, a gente está procurando se a matriz contém sete. 

Então, a primeira coisa que fazemos é olhar no meio, certo? E também você vai ser a codificação Pesquisa Binária em apenas um segundo. Então, isso vai ser divertido. Então, nós olhamos no matrizes pequenas médias 3. Faz três igualar 7? Não. É seis. Então, é menor do que ou maior do que sete? Menor que. Sim. Caras bom trabalho. Eu sinto que como eu deveria temos doces porque eu quer jogá-lo fora para os estaleiros. É o que eu vou fazer na próxima semana. Ele vai manter vocês afiada. 

Então, nós jogamos fora que primeiro semestre, certo? foi menor do que. sabemos que tudo em que lado esquerdo vai ser menos do que o que estamos realmente procurando. Assim, não há necessidade de prestar atenção a ela. Apenas esqueça sobre isso. Então, agora olhamos para o nosso lado direito, e olhamos para o meio ali, e agora são nove. Então, 9 é-- --Everyone? Maior do que o que nós somos procurando, certo? Então, nós estamos indo jogar fora tudo para a direita. Como aquele. Agora, todos nós é deixado com um. Então, vamos verificar, é este o que que estamos procurando? ele é. Nós encontramos o que queríamos. Por isso, está feito. Bilinear Search. 

E se você observar, nós tinha sete entradas de lá. Levou apenas nós como três vezes, mas se você está fazendo como um bilhão, vocês sabem quantos passos que faria ter se tivéssemos quatro bilhões de coisas? Algum palpite? É 32. 32 passos para encontrar algo em quatro bilhões elemento da matriz por causa de potências de dois. Então, dois é a 32, é de quatro bilhões. 

Assim como muito louco você ainda está dentro como um relativamente pequeno número de passos para encontrar algo em quatro bilhões de elementos. Então, nessa nota, estamos vai codificar isso para que vocês possam realmente tipo de ver como isso funciona. Tudo bem, então vocês podem codificar. Vou deixar vocês conversar um pouco. Conheça pessoas ao seu redor, o que é o que alguém queria da última seção. 

Então, para conhecer as pessoas ao seu redor. Fale um pouco. E tudo que eu quero de você caras agora é apenas tentar criar um esboço de pseudocódigo. Ok? Whoa. Tudo que eu quero de vocês é que você está só vai preencher neste caso enquanto. Então, eu tenho definir essas superior e limites inferiores que representam o início e no final de nossa matriz. E você vai, na verdade, loop através de e descobrir o que estamos fazendo dentro deste loop while. 

Então, se você pode descobrir out-- tenho uma dica há-- quais são os casos que temos aqui? Então, se você quiser descobrir a casos, vamos Pseudocódigo aqueles e depois vamos realmente codificá-las. E vai ser, eu acho, espero que ele vai ser um pouco mais fácil do que você espera. Porque não é que muito código, na verdade, o que é muito legal. 

Mm-hm? 

Estudante: [inaudível]? INSTRUTOR: Sim. Havia algo para encontrar no meio. 

ALUNO: Assim, podemos usar isso. Está bem. 

INSTRUTOR: Perfeito. Então essa é a primeira coisa que precisamos fazer. Então, encontrar o meio. Grande. Então você tem uma idéia de como poderíamos realmente encontrar o meio com código? 

Estudante: Sim. n mais de 2? INSTRUTOR: Então n mais de 2. Então, uma coisa a lembrar é que seus limites superiores e inferiores mudar. Continuamos a constrição da parte da matriz nós estamos olhando para. Então n mais de 2 só vai funcionar para a primeira coisa que fazemos. Assim, tendo superior e inferior em conta, como podemos obter esse elemento do meio? Porque queremos que a média entre superior e inferior, certo? Mm-hm? 

Estudante: [inaudível]. 

INSTRUTOR: Então nós temos algum meio. E vai ser superior mais baixa superior a 2. Impressionante. Lá vamos nós. Um para baixo da linha. Vocês estão no seu caminho. Portanto, agora que temos o nosso meio, o que nós queremos fazer? Só em geral. Você não tem que codificá-lo. Sim. Estudante: [inaudível]? INSTRUTOR: Então é mais porque você é achando a média entre os dois deles. Então, se você pensar neles como tipo de aumentar a partir dos lados, pensar sobre isso quando você se aproxima no meio, você quer assim. Então, se você estivesse em ambos os lados da meio, e temos como 5 e 7. Quando você adiciona-los juntos você obter 12, você divide por 2, é 6. 

Às vezes é difícil explicar por que funciona, mas se você trabalha com um exemplo, às vezes, ele vai ajudar você a descobrir se ele deve ser mais ou menos. Sim. 

Estudante: [inaudível] exatamente no meio se tivessem um caso onde há um monte de números menores e como um número grande? 

INSTRUTOR: Então, tudo que você precisa é o meio da matriz. Então, se você tinha um monte de números pequenos e, em seguida, um número muito grande no final, não importa. Tudo o que importa é que eles estão classificadas, você só quero olhar para o meio do a matriz, porque você ainda está fatiar o seu problema pela metade. Legal. Portanto, agora que temos a meio, o que vamos fazer a seguir? 

ALUNO: Compare. INSTRUTOR: The comparar. Então, comparar a média value_wanted. Legal. Então você vê aqui, temos este valor que queremos aqui. Lembre-se esta é uma matriz. Assim, refere-se a média do índice. Por isso, queremos fazer valores de média. Não se esqueça, se você quiser comparar, de dois iguais. Você faz única igual a você só vai transferir-lo, e depois, é claro, é vai ser o valor que você deseja. Portanto, não faça isso. 

Então vamos ver se os valores no meio é igual ao valor que queremos. Não se esqueça de suas chaves. Dropbox deve ir embora. Então, o que vamos fazer neste caso? Se é o que queremos para voltar? Nós estamos tentando dizer. 

ALUNO: Imprima. 

INSTRUTOR: Bem, nós não quer imprimir. Portanto, este é um bool aqui, portanto, quer retornar verdadeiro ou falso. Nós estamos dizendo, é esse número um [? RRA? ?] Então, se é, nós simplesmente devolvê-lo verdadeiro. Se eu posso soletrar verdade. 

ALUNO: Por que você não retornar zero? INSTRUTOR: Então você poderia retornar zero se você quisesse. Mas neste caso, porque nossa função retorna um bool, precisamos voltar verdadeira ou falsa. ALUNO: Quando você estiver dizendo expressão booleana, você pode configurá-lo igual a falso? Como se eu quero dizer, se esta condição não for cumprida, como é superior é igual a falso. Será que vai entender se você apenas colocar falso do outro lado? INSTRUTOR: Yeah. Então, na verdade, se você estiver sempre fazendo alguma coisa como é superior ou é menor, que retorna verdadeiro ou falso e é realmente um estilo ruim para digamos igual a igual a true ou iguais é igual a falso. Você quer usar esse resultado como o próprio como o seu cheque. Não é o que eu queria. Isso é o que eu queria. Assim, no caso de você está pedindo sobre algo como salvar isso em c. 

Então, se temos int main (void) e algo como isso. E você tem, se é superior de alguma entrada e você está perguntando se você pode fazer algo parecido com isto? Certo? ESTUDANTE: Eu estava tentando para fazê-lo [inaudível]. Porque se it's-- INSTRUTOR: Certo. Então você quer que isso seja falso, certo? Estudante: Sim. INSTRUTOR: Então, nesse caso você quero que ele execute, se isso não é verdade. Então, a coisa legal você fazer lá é esta. Então lembre-se de exclamação ponto nega coisas? Ele diz que [inaudível] não significa. Portanto, se olharmos apenas esta parte aqui, você dizem que avalia a falso como você quer que ele. Não falsa é verdade que significa que este seria executado. Será que isso faz sentido? Estudante: Sim. INSTRUTOR: Awesome. Está bem. Então, nós poderíamos apenas retornar verdade neste caso. Portanto, agora temos dois outros casos neste caso. Quais são os nossos outros dois casos? Vamos apenas fazê-lo desta forma. Então vamos começar com outra coisa se os valores no meio é menor do que o valor que queremos. Assim, o nosso valor no meio é menos que o valor que estamos procurando. 

Assim que ligado você acho que quer atualizar? Superior ou inferior? Superior? Assim que lado da matriz vamos estar olhando? 

ALUNO: A mais baixa. 

INSTRUTOR: Nós estamos indo estar olhando para a esquerda. Então, outra coisa se pouco valor é menor. Portanto, o seu valor médio aqui é menor do que o que nós queremos. Por isso, queremos levar o lado direito da nossa matriz. Então, nós estamos indo para atualizar nosso limite inferior. Então, vamos transferir nossa inferior. E o que você acha que deve ser menor? ESTUDANTE: O valor médio? INSTRUTOR: Então o value-- meio ALUNO: Plus 1. INSTRUTOR: --plus 1. Alguém pode me dizer por que temos que mais uma? 

Estudante: [? Nenhum valor?] é mais igual a ele. 

INSTRUTOR: Certo. Porque já sabemos que nosso valor médio não é igual a isso e queremos excluí-lo a partir de todas as pesquisas subsequentes. Se você esquecer de que mais 1, esta vai gostar de loop indefinidamente. E você só vai ser pego em uma loop infinito e então você vai segfault e as coisas vão mal. Então, certifique-se sempre que você não está incluindo o valor que você acabou de olhou. Então, nós cuidamos do que com um plus 1. 

Portanto, agora temos nossa última condição que eu sempre por razões de segurança você pode conferir aqui, mais se o valor em o meio é maior do que o valor nós queremos. Isso significa que nós queremos a metade do lado esquerdo. Então, qual deles é que vamos atualizar? Superior. E o que é este vai ser igual? Médio menos 1 porque, é claro, que queremos para se certificar de que não estamos olhando para o valor médio novamente. E então nós temos isso. É isso aí. Isso é tudo de busca binária é. Não é tão ruim, certo? É como se 10 linhas de código com espaço em branco. Então, muito poderoso, muito útil, você vai estar a usá-lo em um de seus Série de Exercícios posteriores. Talvez não este, mas mais tarde. Assim, aprendê-la. Adoro. Ele vai te tratar bem. Então, alguém tem alguma perguntas sobre busca binária? Sim. 

ALUNO: Será que isso importa se o seu n é par ou ímpar? 

INSTRUTOR: Não. Porque nós lançá-lo para o meio como um int, ela só vai truncar-lo. Então, ele vai ficar um inteiro e ele vai eventualmente classificar através de tudo. Assim você não precisa se preocupar com isso. Todo mundo bom? Impressionante. Legal. Então, vocês tem isso. Slideshow. Assim como nós estávamos falando sobre, eu sei David mencionou tempos de execução de complexidade. 

Assim, na melhor das hipóteses, é apenas um, o que chamamos de tempo constante. Alguém pode me dizer por que isso pode ser? Que tipo de cenário que isso implica? Mm-hm. 

Estudante: [inaudível] first-- INSTRUTOR: Então no meio sendo o primeiro elemento que vem, certo? Assim, ou um conjunto de um ou tudo o que está procurando apenas passa a ser bem no meio. Então, essa é a nossa melhor caso. Você começa em problemas reais, provavelmente não vai chegar [inaudível] que muitas vezes. E o nosso pior caso? Nosso pior caso é log n. E isso tem a ver com o todo potências de dois coisa que eu falei. 

Assim, no pior caso, isso significaria que tivemos de cortar a matriz para baixo até que era um elemento de um. Então tivemos que cortá-la pela metade tantas vezes quanto nós podia. É por isso que é log n porque você continua dividindo por dois. Assim pressupostos, coisas que você Preciso saber se você está sempre vai usar uma busca binária. Seus elementos devem ser ordenados. Eles têm de ser resolvidas, porque essa é a única maneira que você pode saber se você é capaz para jogar fora metade. 

Se você tivesse esta bolsa confusa de números e você está dizendo, OK, eu vou verificar o meio número eo número que eu estou procurando é menos do que isso, eu só vou para atirar arbitrariamente fora metade. Você não sabe se o seu os números em que a outra metade. Sua lista tem de ser resolvida. Assim, este pode ser indo adiante um pouco, mas você precisa ter acesso aleatório. Você precisa ser capaz de apenas ir para aquele elemento do meio. Se você tiver que atravessar por algo ou você leva etapas extras para chegar a esse elemento do meio, não é log n mais porque você está adicionando mais trabalho para ele. E isso vai fazer um pouco de mais sentido em duas semanas, mas eu meio que queria prefácio, dar a vocês uma idéia do que é para vir. Mas esses são os dois premissas importantes que você precisa para uma lista de binário. Certifique-se de que está classificado. Esse é o grande problema para vocês agora mesmo. E em que podemos entrar em o resto de nossas sortes. Então, quatro bolha sorts--, inserção, seleção e merge. Eles estão todos bem legal. Se vocês decidem tomar CS 124, você vai aprender sobre todos os tipos de tipos. E se você é um fã XKCD, não é um sobre quadrinhos muito legal como os tipos realmente ineficazes, o que eu recomendo que você vai olhar. Um deles é como espécie de pânico, que é como, oh não, retornar disposição aleatória. Sistema de desligamento. Deixar. Então, humor geeky é sempre bom. 

Então, alguém se lembra tipo de como apenas uma idéia geral de como bubble sort funciona. Você se lembra? 

Estudante: Sim. 

INSTRUTOR: Vá em frente. 

Estudante: Então você está passando e se for maior, então você trocar os dois. 

INSTRUTOR: Mm-hm. Exatamente. Então você só iterar. Você verifica dois números. Se o anterior é maior depois do que aquele, você só trocá-los de forma que em Desta forma, todos os números mais elevados bolha-se para o fim da lista e todos os números mais baixos bolha para baixo. 

Será que ele mostrar a vocês o frio efeito sonoro triagem vídeo? É bem legal. Assim como Robert disse, o algoritmo que você acabou de percorrer a lista, trocando os valores adjacentes se eles não estão em ordem. E depois é só ficar repetindo até que você não faça nenhuma swaps. Então, não é ruim, certo? Então, só temos um exemplo rápido aqui. Então, isso vai classificar los em ordem crescente. Então, quando nós passamos a primeira tempo, olhamos a oito e seis não são, obviamente, em ordem, nós trocá-los. 

Então olhe para a próxima. Oito e quatro não em ordem. Trocá-los. E depois de oito e dois, trocá-los. Lá vamos nós. Então, depois de sua primeira passagem, você sabe que seu maior número vai ser todo o caminho no topo, porque é só vai ser constantemente maior do que tudo o resto e ele só vai para bolha até todo o caminho até a final lá. Será que isso faz sentido para todos? Legal. 

Então olhamos para a nossa segunda passagem. Seis e quatro, interruptor. Seis e dois, switch. E agora nós temos algumas coisas em ordem. Assim, para cada passagem que fazer através de nossa lista inteira, sabemos que como que muitos números no final terá sido classificados. Então nós fazemos uma terceira passagem, que é um swap. E, em seguida, na nossa quarta passar, temos zero slots. E assim sabemos que a nossa matriz tiver sido resolvido. 

E essa é a grande coisa com bubble sort. Nós sabemos que quando nós ter zero swaps, que significa que tudo está em ordem completa. É uma espécie de como podemos verificar. Então, nós também estamos indo para codificar bolha tipo o que também não é tão ruim assim. Nenhum destes são tão ruins. Sei que pode parecer um pouco assustador. Eu sei que quando eu tirei a classe, mesmo quando eu estava ensinando a classe para Pela primeira vez no ano passado, Eu estava tipo, como eu faço isso? Faz sentido na teoria, mas como é que vamos realmente fazer isso? É por isso que eu também quero andar por meio de código com vocês aqui. Então, eu tenho um pseudocódigo para vocês neste momento. Então, basta manter isso em mente como estamos prestes a fazer a transição mais. Portanto, temos alguns contador que mantém o controle de nossos swaps, porque precisamos ter certeza de que estamos verificando isso. E iteramos toda a matriz como acabamos de fazer com este exemplo. Se o elemento é maior do que antes o elemento depois de onde estamos, nós trocá-los e incrementamos nossa contador, porque assim que trocar, queremos deixar o nosso contador de saber disso. Qualquer dúvida lá? Algo parece engraçado aqui. ALUNO: Você colocar o contador a zero cada vez que você passar pelo loop? Você não vai manter de volta a zero todas as vezes? INSTRUTOR: Não necessariamente. Então, o que acontece é que passamos aqui. Então faça enquanto, lembre-se, este será executado uma vez, sem falhar. Então ele vai definir o contador igual a zero, em seguida, ele vai para percorrer. Como se repete através de, ele irá atualizar balcão. Como ele atualiza balcão, quando ele é feito, quando é atingido o final da matriz, se a nossa lista não tenha sido resolvido, contador foram atualizados. 

Então ele verifica o estado de conservação e diz, OK, é contador maior que zero. Se for isso, fazê-lo novamente. Você deseja redefinir para que quando você percorrer, contador é igual a zero. Se você passar por uma ordenada array, nada muda, isso falhar, e você voltar a lista ordenada. Será que isso faz sentido? Estudante: Poderia nos um pouco. INSTRUTOR: OK. Se há qualquer outra questão que vem à tona. Sim. 

Estudante: Qual seria a função ser para trocar os elementos? 

INSTRUTOR: Então podemos realmente escrever que, se nós estamos indo agora. Legal. Então, nessa nota, Alison vai para voltar para o aparelho. Vai ser divertido. E nós temos o nosso bom bolha coisa tipo aqui. Então, eu já fiz ciclismo através da matriz. Nós temos nossos swaps que são iguais a zero. Por isso, queremos trocar adjacente elementos se eles estão fora de ordem. Então, a primeira coisa que precisamos não é iterar nossa matriz. 

Então, como você acha que pode iterar nossa matriz? Temos para e i é igual a 0. Queremos i a ser menos que n menos 1 menos k. E eu vou explicar isso em um segundo. Portanto, esta é uma otimização aqui, onde, me lembro como eu disse após cada passagem através da matriz de nós sei que tudo o que é on-- 

Então, depois de um passe de nós sabemos que este é classificado. Após dois passes sabemos que tudo isso está classificada. Depois de três passagens de nós sei que é classificada. Assim, a maneira que eu estou interagindo através da matriz aqui, se ele está certificando-se de ir apenas através do que sabemos é indiferenciado. Ok? Isso é apenas uma otimização. Você pode escrevê-lo apenas ingenuamente iteração através de tudo, seria apenas levar mais tempo. Com este ciclo de quatro é apenas uma boa otimização porque sabemos que após cada cheia iteração através da matriz aqui, como cada ciclo completo aqui, sabemos que um mais destes elementos serão classificados no final. 

Portanto, não precisa se preocupar com aqueles. Será que isso faz sentido para todos? Esse truque pouco fria? Então, nesse caso, se estamos interagindo através, sabemos que queremos verificar se matriz n e n + 1 estão em ordem. Está bem. Então aqui está o pseudocódigo. Queremos verificar se a matriz n e n mais 1 estão em ordem. Então, o que podemos ter lá? Vai ser uma condicional. Será um caso. 

ALUNO: Se array n é inferior a matriz n mais 1. INSTRUTOR: Mm-hm. Bem, inferior ou superior. ALUNO: Maior que. Então eu quero trocá-los. Exatamente. Portanto, agora entramos em qual é a mecanismo para troca-los? Então nós passamos por isso brevemente, um tipo de função swap na semana passada. Alguém se lembra como funcionava? Portanto, não podemos apenas reenviá-los, certo? Porque um deles vai se perder. Se disséssemos A é igual a B e depois B é igual a A, toda uma súbita ambos são apenas igual a B. 

Então o que temos a fazer é que tem uma variável temporária que é vai realizar um dos nossos enquanto estamos no processo de troca. Então, o que temos é que vamos ter alguns int temperatura é igual a-- você pode atribuí-lo para qualquer um que você quiser, basta certifique-se de manter o controle de ele-- portanto, neste caso, eu vou atribuí-la a matriz n + 1. Então, isso vai segurar o que quer valor é nesse segundo bloco que nós estamos olhando. 

E então o que podemos fazer é que podemos ir frente e variedade Reassign n + 1, porque sabemos que que têm valor armazenado. Este é também um dos grandes coisas- Eu não sei se algum de vocês tivemos problemas onde se alternam dois linhas de código, de repente as coisas funcionavam. Ordem é muito importante no CS. Então, certifique-se de diagrama coisas, se possível sobre o que está realmente acontecendo. Então agora nós vamos reatribuir array n + 1, porque sabemos que que têm valor armazenado. 

E podemos atribuir isso a matriz n ou neste caso variedade i. Muitas variáveis. Está bem. Matriz Então agora temos transferido i mais um para igualar o que está na matriz i. E agora podemos voltar e atribuir gama i com o quê? Qualquer um? 

Estudante: 10. 

INSTRUTOR: 10. Exatamente. E uma última coisa. Se temos trocado agora, o que precisamos fazer? O que é a única coisa que vai nos dizer se alguma vez terminar este programa? O que nos diz que tem uma lista ordenada? Se não executar quaisquer swaps, certo? Se permutas é igual de zero no final desta. Assim, sempre que você realizar uma troca, como nós apenas fiz aqui, queremos atualizar swaps. E eu sei que houve uma pergunta anterior sobre você puder usar zero ou um, em vez de verdadeiro ou falso. E isso é o que isso faz aqui. Portanto, este diz que se não swaps. Portanto, se permutas é zero, o que eu é-- sempre chegar em minhas verdades e meus falsos misturados. Queremos nos avaliar a verdade e não é. Então, se é zero, então é falsa. Se negar-o com um [? bater?] torna-se verdade. Então esta linha executa. 

Verdades e falsas e zeros e uns ficar louco. Assim, se você andar devagar por isso ele vai fazer sentido. Mas isso é o que este pequeno pouco de código aqui faz. Portanto, este verifica fizemos quaisquer swaps. Então, se é nada além zero, que vai ser falsa e toda a coisa é indo para executar novamente. Legal? 

Estudante: O que faz pausa fazer? 

INSTRUTOR: Quebre apenas quebra-lo para fora do loop. Portanto, neste caso, seria assim como acabar com o programa e você teria apenas tem sua lista classificada. ESTUDANTE: Amazing. INSTRUTOR: Eu sinto muito? ESTUDANTE: Como previamente usado por escrito sobre um escrito de zero apresentar que, se que vai funcionar ou não. 

INSTRUTOR: Yeah. Assim, você pode retornar zero ou um. Neste caso, porque não estamos realmente fazer qualquer coisa com a função, nós só queremos que quebre. Nós realmente não se preocupam com isso. Brake também é bom se ele é usado para sair de quatro lacetes ou condições que você não quer manter a execução. Ele só leva você para fora deles. É um pouco de uma coisa nuance. Eu sinto que há uma grande quantidade de mão de ondulação, como você vai aprender sobre isso em breve. 

Mas você vai aprender sobre isso em breve. Eu prometo. Está bem. Assim que todos obter bubble sort? Não é tão ruim. Iterar, coisas de swap, utilizando uma variável temp, e que está tudo pronto lá? Legal. Impressionante. Está bem. Voltar para o PowerPoint. Quaisquer dúvidas em geral sobre estes até agora? Legal. Mm-hm. 

Estudante: [inaudível] int main normalmente. Você tem que ter que para isso? 

INSTRUTOR: Então, nós apenas procurando apenas no algoritmo de ordenação real. Se você tivesse que dentro como um programa maior, você teria um lugar principal int. Dependendo de onde você usar este algoritmo, seria determinar o que é sendo devolvido por ela. Mas, para o nosso caso, estamos estritamente olhando como faz isso, na verdade, iterar através de um array. Portanto, não se preocupe com isso. 

Então, nós estávamos falando sobre melhor caso e os piores cenários de busca binária. Por isso, é também importante fazer que, para cada um dos nossos tipos. Então, o que você acha que é o pior caso de execução de bubble sort? Vocês lembram-se? 

ALUNO: N menos 1. INSTRUTOR: N menos 1. Então isso significa que há n menos 1 comparações. Então, uma coisa a perceber é que na primeira iteração, que passamos, nós comparamos estes dois-- de modo que é um. Estes dois, três, quatro. Então, depois de uma iteração nós já tem quatro comparações. Quando eu estou falando de tempo de execução e n. N representa o número de comparações como uma função de quantos elementos temos. Ok? 

Assim que passamos, temos quatro. A próxima vez que você sabe que não fazer tem que cuidar do presente. Nós comparamos os dois, estes dois, estes dois, e se não tivéssemos que a otimização com o ciclo de quatro que eu escrevi, você estaria comparando aqui de qualquer forma. Então você teria que executado através da matriz e fazer comparações n n vezes, porque cada vez que executar, através dele, tipo uma coisa. 

E cada vez que percorrem a matriz, fazemos n comparações. Assim, o nosso tempo de execução para isso é na verdade, n ao quadrado, que é muito pior em nossa log final, porque isso significa se tivéssemos quatro bilhão de elementos, é vai nos levar de quatro bilhões quadrados em vez de 32. Então, não é o melhor tempo de execução, mas para algumas coisas, você sabe, se você estiver dentro um certo intervalo de elementos bubble sort pode ser bom para usar. 

Está bem. Então agora o que é o melhor caso de tempo de execução? ALUNO: Zero? Ou 1? 

INSTRUTOR: Então um faria ser uma comparação. Right. 

ALUNO: N menos 1? 

INSTRUTOR: Então, sim. Então n menos um. Sempre que você tem um conceito como n menos 1, temos a tendência de simplesmente deixá-la e nós apenas dizer n porque você tem comparar cada um dos these-- cada par. Portanto, seria n menos 1, que nós que tinha acabado de dizer é aproximadamente n. Quando você está lidando com tempo de execução, tudo está em aproxima. Contanto que é o expoente correto, você é muito bom. 

Essa é a forma como lidamos com ele. Assim que o melhor caso é n, que significa que a lista já está classificado, e tudo o que fazemos é executado através de e verifique se ele está classificada. Legal. Tudo certo. Então, como você vê aqui, nós só tem mais alguns gráficos. Então n ao quadrado. Fun. Muito pior do que n, como vemos, e muito, muito pior do que 2n log. E então você começa também em registro registros. E você pega 124, você entrar em como a estrela de log, que é como um louco. Então, se você estiver interessado, estrela log de pesquisa. É uma espécie de diversão. Portanto, temos este grande gráfico. Apenas um heads-up, este um gráfico maravilhoso ter para o seu meio-termo, porque nós tempo para perguntar-lhe estas dilui. Assim, apenas a cabeça para cima, tem este em seu intercalar sobre a sua folha de fraude bom lá. Então, nós apenas olhou para bubble sort. Na pior das hipóteses, n ao quadrado, melhor caso, n. E nós vamos olhar para os outros. 

E como você pode ver, a única um que realmente faz bem é merge sort, que nós vamos entrar em porquê. Então, nós estamos indo para ir para o ao lado um tipo de seleção aqui--. Alguém se lembra como seleção espécie trabalhou? Vá em frente. 

ALUNO: Basicamente passar por uma ordem e criar uma nova lista. E assim como você está colocando elementos em, colocá-los no lugar certo na nova lista. 

INSTRUTOR: Assim que os sons mais como ordenação por inserção. Mas você está realmente perto. Eles são muito semelhantes. Mesmo eu pegá-los misturados às vezes. Antes desta seção eu era como, esperar. Está bem. Então, o que você quer fazer é a seleção de classificação, a maneira que você pode pensar sobre o assunto ea forma Eu me certificar de que não tentar obter los misturados, é que atravessa e seleciona o menor número e ele coloca que no início da sua lista. Ele troca-lo com a primeira posição. Eles realmente têm um exemplo para mim. Impressionante. Assim, apenas uma maneira de pensar em seleção ele-- tipo, selecione o menor valor. E nós estamos indo executado através de um exemplo que eu acho que vai ajudar, porque Acho visuais sempre ajudar. Então, vamos começar com algo que é completamente indiferenciados. Red será indiferenciados, verde serão classificados. Tudo fará sentido em um segundo. 

Então nós passamos por e iteramos desde o início até o fim. E nós dizemos: OK, 2 é nosso menor número. Então, nós vamos tomar dois e vamos para movê-lo para a frente da nossa matriz porque é a menor número que temos. Então, isso é o que este está fazendo aqui. Ele só vai trocar os dois. Então agora temos um classificado parte e uma parte não classificado. E o que é bom lembrar sobre a seleção de tipo é que estamos selecionando apenas da parte não classificado. 

A parte ordenada você acabou de sair sozinho. Mm-hm? 

ESTUDANTE: Como ele sabe o que é o menor sem compará-lo para todos os outros valores na matriz. INSTRUTOR: Ele faz compará-lo. Nós gostamos de ignorados. Este é apenas geral global. Sim. Quando escrevemos o código que eu sou certeza que você vai estar mais satisfeito. Mas você guarde este primeiro elemento como a menor. Você compara e você dizer, OK, é menor? Sim. Mantê-lo. Aqui é menor? Não? 

Esta é a sua menor, transferir-lo para o seu valor. E você será muito mais feliz quando vamos através do código. Então nós passamos, nós trocá-lo, por isso, em seguida, olharmos para esta parcela não classificado. Então, nós estamos indo para selecionar três. Nós estamos indo para colocá-lo em pelo o fim da nossa parte ordenada. E nós apenas estamos indo para continuar fazendo que, fazendo isso, e fazendo isso. Portanto, este é o nosso tipo de pseudocódigo aqui. Vamos codificar-lo aqui em um segundo. Mas só uma coisa de andar através de um nível elevado. Você está indo para ir de i é igual a 0 para n menos 2. Essa é outra otimização. Não se preocupe muito com isso. Então, como você estava dizendo. Como Jacob estava dizendo, como nós acompanhar o que o nosso mínimo é? Como sabemos? Nós temos que comparar tudo em nossa lista. 

Então mínimo é igual a i. É só dizer, neste caso, o índice do nosso valor mínimo. Então ele vai para percorrer e ele vai de j é igual a i + 1. Então já sabemos que esse é o nosso primeiro elemento. Nós não precisamos de compará-lo a si mesmo. Então nós começamos a compará-lo com o próximo aquele que é por isso que é i + 1 para n menos 1, que é a final da matriz lá. E nós dissemos, se da matriz em j é inferior a matriz min, então nós realocar onde nossos índices mínimos é. 

E se não min é igual a i, tal como em que estávamos de volta para cá. Assim como quando fizemos primeiro um presente. Neste caso, ele iria começar a zero, ele acabaria sendo dois. Assim, não seria igual min i na final. Isso nos permite saber que precisamos trocá-los. Eu me sinto como um exemplo concreto vai ajudar muito mais do que isso. Então, eu vou codificar isso com vocês agora e eu acho que vai ser melhor. 

Tipos tendem a trabalhar dessa forma em que muitas vezes é melhor só para vê-los. Então, o que nós queremos fazer é queremos primeiro a menor elemento na sua posição na matriz. Exatamente o que Jacob estava dizendo. Você precisa armazenar que de alguma forma. Então, vamos começar aqui iteração sobre a matriz. Nós vamos dizer que é nosso primeiro apenas para começar. Então, nós vamos ter int menor é igual ao da matriz em i. 

Então, uma coisa a notar, cada tempo este loop é executado, estamos começando um passo mais adiante. Quando começamos olhamos para este. A próxima vez que iterar, estamos começando em um presente e atribuindo-lhe o nosso menor valor. Portanto, é muito semelhante ao bubble sort onde sabemos que depois de uma passagem, este último elemento é classificado. Com a seleção de classificação, que é exatamente o oposto. 

Em cada passagem, sabemos que a primeira é classificada. Após a segunda passagem, o segunda será classificada. E como você viu com os exemplos de slides, nossa porção ordenados não para de crescer. Assim, definindo o nosso menor um para matrizes i, tudo o que está fazendo constrição é o que nós estamos olhando de forma para minimizar o número de comparações que fazemos. Isso faz sentido para todos? Você precisa de mim para ser executado através de que novamente mais lenta ou com palavras diferentes? Estou feliz por. Está bem. 

Então, nós estamos armazenando o valor neste ponto, mas também queremos armazenar o índice. Então, nós estamos indo para armazenar o posição da menor um, que só vai ser eu. Então agora Jacob está satisfeito. Nós temos coisas guardadas. E agora temos de olhar através de a parte não separados da matriz. Portanto, neste caso esta seria o nosso indiferenciados. Este é i. Está bem. 

Então o que nós vamos fazer vai ser para um loop. Sempre que você precisar iterar através de um array, a sua mente poderia ir para um loop. Assim, para alguns int k equals-- o que pensamos k vai ser igual a começar com? Isto é o que definimos como o nosso menor valor e queremos compará-lo. O que nós queremos comparar? Vai ser este próximo, certo? Então, nós queremos k ser inicializado para i + 1 para começar. 

E queremos k neste caso, Já tamanho armazenados aqui, para que possamos usar apenas tamanho. Tamanho sendo o tamanho da matriz. E nós só queremos actualizar k por um de cada vez. Legal. Então, agora precisamos encontrar o elemento mais pequeno aqui. Então, se nós iterar, nós quer dizer, se a matriz em k é menor do que a menor value-- este é o lugar onde nós estamos, na verdade, manter o controle do que é a menor aqui- então queremos transferir o nosso menor valor é. 

Isto significa que, oh, nós somos iteração por aqui. Qualquer valor que está aqui é não a nossa mais pequena coisa. Nós não queremos isso. Queremos transferir-lo. Então, se estamos a reatribuição-lo, o que fazer você acha que pode ser neste código aqui? Queremos transferir menor e posição. Então, o que é menor agora? ESTUDANTE: Array k. INSTRUTOR: Array k. E qual é a posição agora? O que há de os índices de nosso menor valor? É só k. Então matriz k, k, eles combinam. Então, nós queríamos que realocar. E então, depois que encontramos o menor, Assim, no final deste loop aqui nós encontramos o nosso menor valor é, por isso, apenas trocá-lo. Neste caso, como dizer que a nossa menor valor é aqui fora. Este é o nosso menor valor. 

Nós apenas queremos trocá-lo aqui, o que é o que esse função swap na parte inferior fez, que acabamos escreveu-se junto a alguns minutos atrás. Por isso, deve parecer familiar. E então ele só vai iterar por meio até atingir todo o caminho ao final, o que significa que você tem zero elementos que são indiferenciados e tudo o mais foi resolvido. Faz sentido? Um pouco mais concretamente? O código ajuda? 

ALUNO: Para um tamanho, você nunca realmente defini-la ou alterá-la, como ele sabe? 

INSTRUTOR: Então uma coisa a notar-se aqui é o tamanho int. Então, nós estamos dizendo neste tipo sort-- é uma função neste case-- é seleção espécie, é passado na com a função. Então, se não foi aprovada em, você faria algo como com o comprimento da matriz ou você iterar para encontrar o comprimento. Mas porque ele é passado em, podemos usá-lo apenas. Você simplesmente assumir que o usuário deu-lhe um tamanho válido que na verdade representa um tamanho de sua matriz. Legal? 

Se vocês têm algum problema com estes ou quer mais prática de codificação tipos em seu próprio país, você deve ir para study.cs50. É uma ferramenta. Eles têm um verificador que você pode realmente escrever. Eles fazem pseudocódigo. Eles têm mais vídeos e slides incluindo os que eu uso aqui. Então, se você ainda estiver sentindo um pouco confuso, tente isso. Como sempre, venha falar comigo, também. Pergunta? 

Estudante: Você está dizendo que o tamanho é previamente definido? INSTRUTOR: Sim. Tamanho é previamente definido se aqui na declaração da função. Então você assume que ele tenha sido aprovada em pelo usuário, e para simplificar, vamos supor que o usuário nos deu o tamanho correto. Legal. Então, isso é a seleção de classificação. Gente, eu sei que nós estamos aprendendo muito hoje. É uma densa dados para seção. Então, com isso, vamos ir para a ordenação por inserção. 

Está bem. Então, antes que nós temos que fazer nossa análise runtime aqui. Assim, no melhor dos casos, concedida desde que eu mostrei a mesa que eu já tipo de jogou fora. Mas o melhor caso de execução, o que pensamos? Tudo resolvido. N ao quadrado. Alguém tem uma explicação por que você acha? 

Estudante: Você está comparando through-- INSTRUTOR: Certo. Você está comparando através. Em cada iteração, apesar de estamos diminuindo este por um, você ainda está procurando por tudo para encontrar o menor. Assim, mesmo se o seu menor valor É aqui, no início, você ainda está comparando-a contra tudo o resto para ter certeza que é a mais pequena coisa. Então você vai acabar correndo por aproximadamente n vezes ao quadrado. Tudo certo. E o que é o pior caso? Também n ao quadrado, porque você está indo estar fazendo esse mesmo procedimento. Portanto, neste caso, a seleção tipo tem algo que também chamamos de tempo de execução esperado. Assim, nos outros, só sei os limites superiores e inferiores. Dependendo de como o nosso louco lista é ou como indiferenciados é, que variam entre n ou n ao quadrado. Nós não sabemos. 

Mas porque a seleção espécie tem o mesmo pior eo melhor caso, que nos diz que não importa o tipo de entrada que ter, se é completamente classificadas ou completamente reversa classificadas, é vai levar a mesma quantidade de tempo. Então, nesse caso, se você lembre-se da nossa mesa, ele realmente tinha um valor que esses dois tipos não têm, tempo de execução que é o esperado. Então, nós sabemos que sempre que corremos seleção espécie, é garantido que executar um tempo n ao quadrado. Não há variabilidade lá. É só esperar. E, novamente, se você quer aprender mais, tomar CS 124 na primavera. Tudo certo. Nós já vimos este. Legal. Assim, tipo de inserção. E eu estou indo provavelmente para brilhar por isso. Eu não vou ter vocês codificá-lo. Nós vamos apenas passar por ela. Então ordenação por inserção é uma espécie de semelhante à seleção espécie em que temos tanto um indiferenciados e ordenados parte da matriz. 

Mas o que é diferente é que como se passar por um por um, nós apenas tomar qualquer número é o próximo na nossa indiferenciados, e classificá-lo corretamente em nossa matriz classificada. Ela vai fazer mais sentido com um exemplo. Então, tudo começa como indiferenciados, Assim como com a seleção tipo. E nós vamos resolver isso em ordem ascendente como temos sido. Então, na nossa primeira passagem tomamos o primeiro valor e dizemos: OK, você está agora em uma lista por si mesmo. 

Porque você está em uma lista por si mesmo, você está classificado. Parabéns por ser o primeiro elemento desta matriz. Você já está resolvido tudo em seu próprio país. Então agora temos um classificado e um conjunto indiferenciado. Então, agora vamos dar o primeiro. O que acontece entre aqui e aqui está o que nós dizemos, OK, vamos olhar para o primeiro valor da nossa matriz indiferenciados e nós estamos indo para introduzi-lo em seu correto lugar na matriz de classificação. 

Então, o que fazemos é tomar 5 e podemos dizer, OK, 5 é maior que 3, por isso, só inseri-lo direito para a direita do que isso. Nós somos bons. Então vamos para o nosso próximo. E tomamos dois. Dizemos, OK, 2 é menos de 3, por isso sabemos que precisa de estar no frente da nossa lista agora. Então, o que fazemos é empurrar 3 e 5 para baixo e passamos 2 em que o primeiro slot. Então, nós estamos apenas inserindo-o o local correto que deveria ser. 

Então, olhamos para o nosso próximo, e nós dizemos seis. OK, é maior do que 6 tudo em nossa matriz classificada, por isso, só marcá-lo até o fim. E então olhamos para quatro. 4 é inferior a 6, é menos que 5, mas é maior do que 3. Por isso, basta inseri-lo para a direita em a meio entre 3 e 5. Que um pouco de modo a tornar pouco mais concreto, aqui é o tipo de idéia do que aconteceu. Assim, para cada elemento não classificado, que determinar onde na parcela classificada ele é. 

Assim, tendo em mente a classificado e não classificado, temos que atravessar e figura para onde ele se encaixa na matriz de classificação. E nós inseri-lo, deslocando o elementos à direita do que para baixo. E então nós apenas manter iterar até que tem uma lista completamente resolvido onde indiferenciados agora é zero e ordenada retoma a totalidade da nossa lista. Então, novamente, para tornar as coisas ainda mais concreto, temos pseudocódigo. 

Então, basicamente, para i é igual a 0 a n menos 1, isso é apenas o comprimento da nossa matriz. Temos algum elemento que é igual a a primeira matriz ou os primeiros índices. Montamos j igual a isso. Assim, enquanto j é maior do que zero e a matriz, j menos 1 é maior do que o elemento, por isso tudo o que está fazendo é ter certeza de que seu j representa realmente a porção não triados da matriz. 

Assim, enquanto ainda há coisas para classificar e j menos um é-- que é o elemento a ela? J nunca foi definido aqui. É uma espécie de irritante. Está bem. De qualquer forma. Então j menos 1, você está verificando o elemento antes. Você está dizendo, OK, é o elemento antes de onde quer que eu am-- vamos realmente tirar isso. Então, digamos que este é como na nossa segunda passagem. Então eu vai ser igual para 1, que é aqui. 

Então i vai ser igual a 1. Isto seria de 2, 4, 5, 6, 7. Tudo certo. Assim, o nosso elemento, neste caso, vai ser igual a 4. E nós temos alguns j que é vai ser igual a 1. Oh, j está diminuindo. Isso é o que é. Então, j é igual a i, então o que é isso dizendo é que à medida que avançamos, estamos apenas certificando-se que não estamos mais indexação dessa maneira quando estamos tentando para inserir as coisas em nossa lista classificada. 

Portanto, quando j é igual a 1 e, neste caso matriz j menos um-- tão matriz j menos 1 é 2 neste case-- se é isso maior do que o elemento, então tudo isso está fazendo está mudando as coisas. Portanto, neste caso, uma matriz j menos Seria matriz de zero, o que é 2. 2 não é maior do que 4, de modo que este não é executado. Assim, a mudança não se move para baixo. O que isto faz aqui é apenas movendo o array ordenado baixo. Neste caso, na verdade, nós poderia fazer-- vamos fazer isso três. Então, se estamos a caminhar através de Neste exemplo, agora estamos aqui. Esta é classificada. Este é indiferenciado. Legal? Então, i é igual a 2, assim nosso elemento é igual a 3. E o nosso j é igual a 2. Então olhamos através e nós dizer, OK, é matriz j menos um maior do que o elemento que nós estamos olhando? E a resposta é sim, certo? 4 é maior do que 3 e j é 2, portanto, esse código é executado. 

Então, agora o que nós fazemos uma série de 2, por isso aqui, nós trocá-los. Então, nós apenas dizer, OK, array em 2 agora vai ser 3. E j vai ser igual j menos 1, que é 1. Isso é horrível, mas vocês a idéia. J é agora igual a 1. E matriz j é apenas vai ser igual ao nosso elemento, que foi de 4. Eu apaguei algo que não devia tem ou algo miswrote, mas vocês começa a idéia. 

É mover-se em n. E então, se isso fosse, seria laço novamente e ele dizia: OK, j é um agora. E matriz j menos 1 é agora 2. É de 2 a menos de nosso elemento? Não? Isso significa que nós temos este elemento inserido no ponto correto em nossa matriz classificada. Então nós podemos levar isso e dizemos: OK, a nossa matriz classificada está aqui. E levaria esse número 6 e ser como, OK, é de 6 inferior a esse número? Não? Legal. Nós estamos bem. 

Fazê-lo novamente. Dizemos 7. É menos do que 7 o final da nossa matriz classificada? Não. Então, nós estamos bem. Então, isso seria resolvido. Basicamente tudo isso faz se ele está dizendo take o primeiro elemento sua matriz não classificado, descobrir para onde vai em sua matriz de classificação. E isso só se encarrega de swaps de fazer isso. Você está basicamente apenas trocando até que esteja no ponto certo. A imagem visual é que você é movendo tudo para baixo, fazendo isso. 

Então, é como metade bubble sort-esque. Confira estudo 50. Eu recomendo tentar codificar isso em seu próprio país. Se você tiver quaisquer problemas ou se você quiser ver código de exemplo para um tipo de inserção, por favor, me avise. Estou sempre por perto. Então, o pior caso de tempo de execução e melhor caso de execução. Como você viu cara da mesa eu já mostrei, é tanto n ao quadrado e n. 

Assim, tipo de ir fora do que nós falamos sobre com os nossos tipos anteriores, pior caso de tempo de execução é que, se é completamente não separados, temos que comparar todos esses n vezes. Nós fazemos um monte de comparações porque se está em ordem inversa, vamos dizer, OK, este é a mesma, isto é boa, e este terá que ser comparados contra o primeiro a ser movido para trás. E à medida que direção o fim da cauda, ​​temos comparar, comparar e comparar contra tudo. 

Então, ele acaba sendo cerca de n ao quadrado. Se é correto, então você dizer, OK, 2, você é bom. 3, você está em relação a dois. Você é bom. 4, basta comparar com a cauda. Você é bom. 6, comparar com a cauda, ​​você está bem. Assim, para cada ponto, se ele já está classificadas, você está fazendo uma comparação. Então é só n. E porque nós temos um melhor caso de execução de n e um caso pior tempo de execução de n quadrado, não temos tempo de execução esperado. 

Ela só depende do caos da nossa lista lá. E, novamente, outra gráfico e outra tabela. Assim, as diferenças entre os tipos. Eu estou indo só para brisa através, eu sentir como nós falamos extensivamente sobre como eles todo o tipo de variar e link juntos. Então, merge sort é o último Vou te aborrecer com caras. Nós temos um quadro bastante colorido. Então, merge sort é um algoritmo recursivo. Então, vocês sabem o que uma função recursiva é? 

Alguém quer dizer? Você quer tentar? Assim, uma função recursiva é apenas uma função que chama a si mesmo. Então, se vocês estão familiarizados com a seqüência de Fibonacci, que é considerado recursivo porque você levar os dois anteriores e adicioná-los juntos para obter o seu próximo. Então recursiva, eu sempre penso de recursividade como como uma espiral então você é como a espiral para baixo para ele. Mas é apenas uma função que chama a si mesmo. 

E, na verdade, muito rapidamente eu pode mostrar-lhe o que parece. Então recursiva aqui, se olharmos, este é a forma recursiva para resumir em uma matriz. Então, tudo o que fazemos é temos a função soma soma que leva um tamanho e uma matriz. E se você observar, o tamanho decréscimos de um em um. E tudo que ele faz é se x é igual a zero-- isso, se o tamanho da matriz é igual a zero-- ele retorna a zero. 

Caso contrário, ele resume este último elemento da matriz, e, em seguida, leva uma soma de o resto da matriz. Então, é só quebrá-lo para baixo em problemas cada vez menores. Longa história curta, recursão, função que chama a si mesmo. Se isso é tudo que você tem fora deste, isso é o que uma função recursiva é. Se você tomar 51, você vai ficar muito, muito confortável com recursividade. É muito legal. Fazia sentido em como 03:00 uma noite fora. E eu era como, por que eu nunca uso isso? 

Assim, para merge sort, basicamente o que ele vai fazer é que é vai quebrá-lo e quebrá-lo para baixo até que ele é apenas elementos individuais. Os elementos individuais são fáceis de classificar. Vemos isso. Se você tem um elemento, é já considerada classificada. Então, em uma entrada de n elementos, se n é inferior a 2, basta retornar porque isso significa é 0 ou 1, como vimos. Aqueles são considerados elementos ordenados. 

Caso contrário, quebrá-lo ao meio. Classificar a primeira metade, classificar o segundo metade, em seguida, fundi-las. Por que ele é chamado merge sort. Portanto, temos aqui nós vamos resolver estes. Assim, mantemos tê-los até que o tamanho da matriz é 1. Então, quando ele é um, nós apenas voltar porque este é um array ordenado, e este é um array ordenado, e isso é um array ordenado, todos nós estamos classificadas. Então, o que fazemos é começar a fundir-los juntos. 

Assim, a maneira que puder pensar em fusão é você acabou de remover a menor número de cada uma das sub-matrizes e apenas anexá-lo para a matriz emergiu. Então, se você olhar aqui, quando temos esses conjuntos temos 4, 6 e 1. Quando queremos mesclar estes, olharmos para estes dois primeiros e dizemos: OK, um é menor, ele vai para a frente. 4 e 6, não há nada para comparar que ele, só marcá-lo até o fim. 

Quando combinamos esses dois, nós apenas levar a uma menor destes dois, por isso é um. E agora nós tomamos a menor destes dois, então 2. Menor destes dois, três. Menor destes dois, 4, 5, 6. Então, você está apenas tirando estes. E porque eles têm foram classificadas anteriormente, você só tem uma Comparação de cada vez que há. Então, mais código aqui, apenas representação. Então você começa no meio e você classificar esquerda e à direita e então você só mesclar aqueles. 

E não temos código para fundir aqui. Mas, novamente, se você vai em estudar 50, ele vai estar lá. Caso contrário, vir falar comigo Se você ainda está confuso. Então coisa legal aqui é que melhor caso, pior caso, e tempo de execução esperado são todos no registo n, que é muito melhor do que nós temos visto para o resto de nossas sortes. Vimos n ao quadrado eo que realmente chegar aqui é n log n, o que é ótimo. 

Olha como muito melhor que é. Tal curva agradável. Portanto, muito mais eficiente. Se você já se puder, uso merge sort. Ela vai lhe poupar tempo. Então, novamente, como dissemos, se você está para baixo nesta região mais baixa, não que fazer muita diferença. Você se levanta para milhares e milhares de entradas, você definitivamente quer um algoritmo mais eficiente. E, mais uma vez, a nossa mesa linda de todas tipos que vocês aprenderam hoje. 

Então, eu sei que tem sido um dia denso. Isso não vai necessariamente para ajudá-lo com seu pset. Mas eu só quero fazer um disclaimer essa seção não é apenas sobre Série de Exercícios. Todo esse material é justo jogo para seus exames semestrais. E também se você continuar com CS, estes são os fundamentos realmente importantes que você precisa saber. Assim, alguns dias serão um pouco mais pset ajuda, mas algumas semanas será teor muito mais efectiva que pode não parecer super útil para você agora, mas eu prometo que se você continuar no vai ser muito, muito útil. 

Então é isso por seção. Down to the wire. Eu fiz isso em um minuto. Mas lá vai. E eu vou ter donuts ou doces. Tem alguém alérgico a nada, pelo caminho? Ovos e leite. Então, donuts são um não? Está bem. Tudo certo. Sem chocolate? Starburst. Starbursts são boas. Está bem. Nós vamos ter Starburst próxima semana seguida. Isso é o que eu vou chegar. Vocês têm uma ótima semana. Leia o seu spec. 

Deixe-me saber se você tiver quaisquer perguntas. PSet duas classes devem ser para você até quinta-feira. Se você tiver alguma dúvida sobre como eu graduada algo ou porque eu graduada algo do jeito que eu fez, por favor me escreva, venha falar comigo. Estou um pouco esse louco semana, mas prometo Eu ainda vou responder no prazo de 24 horas. Então, tem uma ótima semana a todos. Boa sorte em sua pset.