COLUMNA 1: Hola a todos! Benvido de volta á sección. Tan feliz de ver tantos de vós, tanto aquí, e todo o mundo que está a asistir en liña. Así, como benvido de volta habitual. Espero que todos tiveron un lindo fin de semana, cheo de descanso, relax. Foi fermoso onte. Entón, espero que teñan gusto do aire libre. Entón, primeiro de un par de anuncios. Grading. Así, a maioría de vostedes debe ficar un enviar correo-e de min sobre o Pset Scratch así como clasificación para Pset 1. Así, só un par de cousas. Asegúrese de usar check50 en style50. Estas están destinadas a ser recursos para vós, para asegurarse de que está a recibir tantos puntos como pode sen perdelos innecesariamente. Entón, cousas como estilo é moi importante. Estamos indo a despegar para el. Algúns de vós xa poden ter notado que a partir do seu Pset. E check50 é só un xeito moi doado de asegurarse que en realidade estamos devolvendo o que necesita ser devolta ao usuario, e que todo funciona correctamente. Na segunda nota, asegúrese de que o seu subida cousas para o cartafol correcta. Fai miña vida só un pouco máis difícil se premer Pset 2 en 1 Pset porque cando baixar cousas, non baixar correctamente. E sei que é un pouco inestable, nun sistema para acostumar, pero só ser super coidado, só para min, de xeito que cando está a recibir correos electrónicos en como 2:00 e eu son de clasificación. Se non causar teño que ollar todo en torno a súa Pset. Legal. Sei que é pronto, pero eu totalmente fun pego de sorpresa por un ensaio que é debido este venres, que meus profesores foron só como, oh si. Lembre, ten un ensaio debido o venres. Entón, sei que ninguén gusta para pensar midterms, pero a súa primeira proba é o 15 de outubro, que outubro é dende esta semana. Así, pode ser máis cedo do esperado é todo. Así que non está xogado por sorpresa cando Menciono sección da semana que oh, súa proba a próxima semana, eu penso Eu te daría un pouco máis dun heads-up agora. Así, o seu conxunto de problemas, o número tres. Como a xente leron o especificación por curiosidade? Está ben. Temos unha parella. Tipo de baixo da última semana, pero iso é OK. Sei que era fermoso fóra. Entón Break Out. Definitivamente despois de ter feito ler hoxe a súa especificación, polo menos, tente como descargar código de distribución e execución como a primeira inicial cousa que pedir para ti. Como estamos usando código de distribución e unha biblioteca que só teño using-- -É só é a segunda vez que fixen iso Pset, cousas malucas pode ocorrer co seu dispositivo, e quere descubrir que a fóra agora contra máis tarde. Porque se é noite de quinta ou é Mércores e, por algún motivo o aparello simplemente non fai quero correr coa biblioteca ou coa distribución código, o que significa non pode sequera comezar a facer a codificación. Porque non pode comprobar a ver se funciona. O seu non vai ser capaz para ver se compila. Quere coidar das persoas no inicio semana, cando aínda pode enviar correo-e me ou un dos outros FT, e podemos obter os fixados. Porque esas son cuestións que van para-lo de facer calquera progreso real. Non é como un erro, que pode só unha especie de saltar. Se está a ter problemas co seu aparello ou código de distribución, realmente quere que toman coidar, máis cedo ou máis tarde. Así, mesmo se non está indo realmente iniciar a codificación, baixar a distribución código, lea a especificación, asegúrese de todo funciona alí. Ok? Se só pode facelo, eu prometer a súa vida será máis fácil. E así, probablemente vai para facelo agora non? Está ben. Así, todas as preguntas alí? Calquera cousas de loxística? Todo o mundo é bo? Está ben. Disclaimer para aqueles de vostede no cuarto e en liña. Vou estar tentando cambiar entre PowerPoint no dispositivo porque nós estamos indo estar facendo algunha codificación hoxe pola demanda popular do anonymous suxestión enquisa eu enviei a semana pasada. Entón, imos facer algunha codificación. Entón, se vostedes queren ao lume ata os seus aparellos, e ten que conseguir un correo electrónico de min, cun arquivo de exemplo. Por favor, Sinto-se libre para facelo. Entón, imos falar GDB, que é un depurador. El vai axudar tipo de descubrir onde as cousas van mal no seu código. É realmente só un xeito de ti para a etapa a través do seu código que está pasando, e ser capaz de imprimir variables ou ver o que está realmente a suceder baixo o capó versículos seu programa só correr, é como fallo, e queda tipo, ningunha idea o que pasou aquí. Non sei o que fallou en liña. Non sei onde errou. Entón, GDB vai te axudar con iso. Ademais, se decide seguir si, e ter 61, vai realmente ser o seu mellor amigo, porque eu te podo dicir porque eu estou pasando por esa clase. Nós imos ollar para binario investigación, que se vostedes lembrar o gran exemplo de catálogo telefónico espectáculo de clase. Estaremos aplicando iso, e camiñando por iso un pouco máis, e entón nós estamos pasando por catro distintos tipos, que son burbulla, Selección, Inserción, e mesturar. Legal. Entón, GDB como mencionei, é un depurador. E estes son unha especie de gran cousas, as grandes funcións ou comandos que utiliza dentro GDB, e eu andarei vostede a través dunha demostración de que en un segundo. Polo tanto, este non é só se ve abstracto. Vou tentar facelo como formigón posible para vós. Entón, romper. El quere estará pausa como, un número, que representa unha liña no seu programa, ou pode nomear unha función. Entón, se di romper principal, vai parar en principal, e deixalo andar por esa función. Do mesmo xeito, se tes algunha externo funcionan como Cambiar ou Cube, que mirou para a semana pasada. Se digo que romper un deses, sempre que o seu programa de chat que, vai esperar para ti diga a el o que facer. Antes el só vai realizar para que realmente pode pisar dentro da función e ver o que está pasando. Entón, a próxima, só ignora o seguinte liña, vai máis funcións. Step. Estas son todas pouco abstracto. Entón, eu estou indo só para pasar por eles, pero vai velos en uso en un segundo. Entrar nunha función. Entón, como eu estaba dicindo, como con intercambio, que sería permiten que, en realidade, se está como entrar fisicamente no interior, pode xogar con estas variables, impresión o que son, ver o que está pasando. Lista vai literalmente só imprimir o código circundante. Entón, se tipo de esquecer onde está o seu programa, ou está a se pregunta o que está a ocorrer ao seu redor, iso só vai imprimir un segmento de como cinco ou seis liñas en torno a el. Así, pode orientarse sobre onde está. Imprimir algunha variable. Entón, se ten a clave como en César, que imos ollar. Pode dicir clave impresión en calquera punto. El vai dicir-lle que o valor é tan que quizais nalgún lugar ao longo do camiño, vostede substituíu a súa chave. Pode realmente dicir que, debido realmente pode observar ese valor. Nos locais, só impresións as variables locais. Entón, cando está dentro dun loop, e só quere ver como, oh. Cal é o meu eu? ¿Que é este valor de clave que eu arrincar aquí? Cal é a mensaxe neste momento? Ela só vai imprimir todo daqueles, de modo a estar Non ten que individualmente dicir, I. Imprimir Imprimir mensaxe. Imprimir Key. E logo amosar. O que fai é como paso a través do programa, el só vai estar seguro de que é mostrando algúns determinada variable en todos os puntos. Para que Também-- -É unha especie de acceso directo, onde non ten que seguir así, oh. Chave de impresión ou impresión I. El só ha automaticamente facelo por vostede. Entón, con iso, imos para ver como isto vai. Vou probar e chave para o meu aparato. Vexa se podo facelo. All. Nós só estamos indo a reflictir-lo. Non hai nada de tolo no meu portátil de calquera maneira. Está ben. Isto ten que ser un regalo. É tan pequena. A ver se podemos facelo. Está ben. Alice está obviamente loitando aquí só un pouco, pero nós imos busca-la en un momento. Está ben. Nós só estamos indo a aumentar iso. Está ben. Todos poden ver que tipo de? Quizais un pouco? Sei que é un pouco pequeno. Non pode descubrir como facer esta grande. Se alguén sabe. Alguén sabe como facelo máis grande? Está ben. Nós imos rodar con el. Non importa de calquera maneira, porque é só ese é o código que vostedes deberían ter. O que é máis importante é o terminal aquí. E nós temos aquí Por que é tan pequeno? Configuración. Oh. Certo Ike. Como é iso? Fóra de alí. Isto é mellor para todos? Está ben,. Legal. Sabe cando está nun CS clase dificultades técnicas son unha especie de parte as-- Entón, imos aclarar iso. Está ben. Entón, aquí na sección, que tivemos aquí. César é un ficheiro executábel. Entón eu fixen iso. Entón, unha cousa a entender é co GDB que só funciona en ficheiros executábeis. Entón, non pode executa-lo nun Dotsy. Ten que realmente facer Asegúrese de que o seu código é compilado, e que, en realidade, pode ser executado. Entón, asegúrese de que, se iso non acontecer compilar, obtelo para compilar, de modo que pode tipo de correr con el. Entón, para comezar GDB, todo o que fai, Gloria tipo GDB, e entón só o ficheiro que quere. Sempre cometer erros César. Pero quere estar seguro xa que é un executable, Flash punto de ti para que significa que vai para realizar CSI está indo a executar este ficheiros ou co depurador. Está ben. Entón, ten que, comeza este tipo de rabiscos. É só sobre todas as cousas depurador. Realmente non ten que hai problema con iso agora. E como podes ver, temos esta parénteses en aberto, o PIB, parénteses próximos, e só se parece nosa liña de comandos, non? Entón, o que queremos fazer-- -Só, O primeiro é que queremos elixir un lugar para rompe-lo. Entón, hai un erro neste programa Caesar que presento, que imos descubrir. É o que fai é que leva a entrada Barfoo en todas as tapas, e por algunha razón iso non cambia A. El só deixa só, é todo máis correcta, pero a segunda letra A permanece inalterado. Entón, nós estamos indo a tentar descubrir por que isto ocorre. Entón, o primeiro que normalmente quero facer sempre que comezar en GDB é descubrir onde a rompe-lo. Entón, César é un pequeno programa. Nós só temos unha función, non? Cal foi a nosa función no Caesar? Hai só unha función, non Main? Home é unha función para todos os seus programas. Se non ten Main, eu podería ser un pouco preocupado agora, pero espero que todos tiveran principal alí. Entón, o que podemos facer é que podemos só romper principal, só como aquel. Así, el di, Aceptar. Montar noso único breakpoint alí. Entón, agora a cousa a lembrar de César leva un argumento de liña de comandos para a dereita e nós non fixemos iso en calquera lugar aínda. Entón, o que fai é cando realmente ir a correr o programa, calquera programa que está funcionando en GDB que precisa de liña de comandos argumentos, está indo a entrada cando comezar a executa-lo. Entón, neste caso, o que facemos Execute cunha chave de tres. E que vai realmente comezar. Entón, se ve aquí, temos Se RC non é igual a 2. Entón, se vostedes todos teñen o ficheiro que eu enviei-se vai ver que iso é como o primeira liña a nosa función principal, non? Está comprobando a ver se temos o número correcto de argumentos. Entón, se está a se pregunta RC se é correcta, pode facer algo como impresión RC. RC é de dous, que é o que esperabamos, non? Entón, podemos ir Logo e continúan ata. Entón, nós temos algunha clave alí. E podemos imprimir nosa clave para asegurarse de que é correcta. Interesante. Non é así o que esperabamos. Entón, unha cousa a entender co GDB tamén, é que non é ata que realmente acertar Logo que a liña que acaba de ver é realmente executada. Así, neste caso Key non teña aínda foi asignado. Entón, Key é algún valor de lixo que ve na parte inferior alí. Negativo $ 120-- -É mil millóns e algo que cousas estrañas non? Non é a clave que esperabamos. Pero se se loita en Seguinte e, a continuación, tentar clave de impresión, é tres. Todo o mundo ve isto? Entón, se conseguir algo que lle gusta, espere. Isto é completamente mal, e eu non sei como iso ía acontecer, porque todo o que quero facer é asignar un número, unha variable, tentar bater continuación, proba imprimir de novo, e ver se funciona. Porque só vai executar e de feito, asignar algo despois que prema en Next. Ter sentido para todos? Uh huh? COLUMNA 2: Cando chou números o que significa isto? COLUMNA 1: É só aleatoria. É só lixo. É só algo que o seu ordenador pode atribuír ao acaso. Legal. Entón, agora podemos pasar a través, e así por agora temos este GetString texto simple. Entón, deixe-me presentar o que ocorrerá cando se loita continuación aquí. A nosa GDB tipo de desaparece, non? Isto porque GetString agora está en execución, non? Entón, cando vimos texto é igual a GetString, parénteses abertos e parénteses, e prema en Next, que ten realmente executada agora. Entón, está esperando por nos a entrada de algo. Entón, nós estamos indo a entrada a nosa comida que é o que está fallando, como dixen a vostede e que só di que é rematar a execución, que o pechou soporte significa que é sae fóra dese circuíto. Así, podemos bater continuación, e agora, como eu son seguro de que está familiarizado de César, é dicir, o que é esta liña vai facer. É para Int I é igual a 0, N é igual a Strlen, texto simple e, a continuación, I é menor que n, I, plus, plus. ¿Que é este lazo vai facer? Abre a mensaxe. Legal. Entón, imos comezar a facelo. Así, se esta condición corresponden, para o noso primeiro? Se é un B, é texto simple I. Pode obter información sobre os nosos veciños. Así, I é cero, e se seis, que Esperamos, ea nosa clave é tres. Todo o que ten sentido, non? Estes números son todos o que debe ser. Entón, hum? COLUMNA 3: Eu teño números aleatorios para min. COLUMNA 1: Ben, podemos check-- --nós pode falar sobre iso nun segundo. Pero ten que estar recibindo este. Entón, se temos un capital B ao noso primeiro, esta condición debe pegalo, non? Entón, se se loita Logo vemos que esta Se realmente executa. Porque se está seguindo ao longo do seu código, esta liña aquí, onde texto I substitúese con esta aritmética, só é executado cada caso condición é correcto correcto? GDB só vai amosar-lle as cousas que son realmente execución. Entón, se esa condición Se non foi cumprida, é só vai saltar á seguinte liña. Ok? Entón, nós temos que. Este soporte significa que é pechado fóra dese ciclo agora. Entón, que vai comezar de novo. Só iso. Entón, que poidamos obter información sobre os nosos veciños aquí, e vemos que o noso primeiro letra cambiou, non? É agora un E, como debería ser. Así, podemos continuar. E nós temos esa comprobación. E esa comprobación debe funcionar, non? É A. Debe ser cambiado tres cartas para adiante. Pero se observar, nos obter algo diferente. Polo tanto, neste caso aquí enriba, el pegou Lo, e así que esta liña executada, que modificou a nosa B. Pero, neste caso aquí, temos que simplemente ignorados, e fun para o [? L Siff. ?] Entón, algo está a suceder alí. O que está dicindo é que, sabemos que debe incorporarse aquí, pero non é. Calquera pode ver que o noso problema é nesta liña? É unha cousa moi minuto. E tamén se pode ollar para o seu código. Tamén linha-- esquecer que liña é en há-- pero é no [inaudível]. Si? COLUMNA 4: É o máis grande que páxina, se lelo no libro. COLUMNA 1: Exactamente. Así, o depurador non podería dicir iso, pero o depurador podería facelo para abaixo a unha liña que sabe que non funciona. E ás veces, cando todo ao final do semestre, cando está lidando con un centenar, unha cen algunhas liñas de código, e Non sei onde está fallando, esta é unha boa forma de facelo. Así, atopamos o noso erro. Pode resolve-lo no seu arquivo, e logo, pode executa-lo de novo, e todo funcionaría perfectamente. E o máis importante é isto pode parecer, Aceptar. Si. Legal. Sabía que está a procurar. Entón, vostede sabía o que facer. GDB pode ser super útil porque Pode imprimir todas esas cousas que non o faría. É moito máis útil do que printf. Cantos de vostedes usan como declaracións printf para descubrir onde un erro foi, non? Entón, con iso, non ten que manter a volver, e gústalle comentar en Printf, ou comentar, e descubrir o que ten que ser a impresión. Este, de feito, só permite que percorrer, imprimir cousas como está pasando, por iso, pode observar como cambian en tempo real, como o programa está a ser executado. E iso leva un pouco pouco de tempo para se acostumar. Recomendo só unha especie de ser un pouco frustrado con iso para agora. Se pasar unha hora sobre o semana aprendendo a usar o GDB, vai gardar tanto tempo despois. E literalmente. dicimos iso para a xente cada ano, e eu recordo cando eu tirei o clase, eu era como, eu vou estar ben. Non. Pset 6 chegou e eu estaba como, eu vou aprender como usar o GDB porque eu non saber o que está pasando aquí. Entón, se tomar o tempo para usalo en programas menores que está indo a ser traballando, como traballar por algo así como Visionare, como este. Ou se quere práctica adicional, estou seguro Podería vir enriba con programas de buggy, para que poida depurar se desexa. Pero se só levar moito tempo para chegar acostumar con iso, só xogar con el, el realmente vai atender-lo ben. E é realmente unha das aquelas cousas que só ten que tentar, e ensuciar as mans con, antes de que realmente entende-la. Realmente só entendín xa Eu tiña de depuración cousas con el, e é moito máis agradable para ter unha idea do como depurar, máis cedo ou máis tarde. Está ben. Legal. Sei que é tipo como un curso intensivo de GDB, e seguramente vou traballar para ter estes para parecer maior a próxima vez. Legal. Así, se volvemos ao noso PowerPoint. Será que isto vai funcionar? AWH. Si. Está ben. Entón, se precisa de calquera dos aqueles de novo, hai a lista. Busca Entón binario, que todos recorda o gran espectáculo de David rasgando teléfono libros pola metade. Realmente non entendo o libros de teléfono máis, porque, como onde obter libros de teléfono nos días de hoxe? Realmente non sei. A procura binaria. Alguén se lembra Como Binary traballos de investigación? Calquera en todo? Si? COLUMNA 5: Vostede sabe cando ollar para que a metade sería en, Con base niso, e librar-se da outra metade. COLUMNA 1 Exactamente. Entón, Busca binaria, é unha especie de a-- --nós gusta de chamalo de dividir e conquistar. Entón, o que vai facer é vai mirar no medio, e vai ver se corresponde o que está a procurar. E se iso non acontecer, entón tenta descubrir, é que será deixado metade ou a metade dereita. Entón, iso se pode se está a buscar en algo que está en orde alfabética, mira ti, oh. Será que Allison vir antes M? Si. Entón, nós estamos indo a mirar para o primeiro semestre. Ou pode ser como cos números. O que se poida comparar, pode ser resolto. Podes utilizar a busca binaria en. Entón, alguén se lembra deste gráfico ou o que é iso? É Complexidade asintótica. Así, este gráfico só describe o tempo que leva a resolver un problema como aumenta o número de cousas que está a usar. Entón, nós temos N, que é o tempo lineal. Se N ao longo de dous, o que é lixeiramente mellor, aínda medra super rápido. E entón debemos sesión, que é o que consideramos Binary Search. Se se decata que o seu problema queda moito máis e moito máis grande, o tempo que leva para resolver-lo non vai aumentar moito. É como comparable aquí no inicio. Vostede é como, Aceptar. Calquera cousa aquí realmente non importa que usamos, pero saír dun millón, mil millóns. Está intentando atopar some-- --you're intentando atopar unha agulla nun palheiro. Creo que quere este problema. Quere que esta complexidade, non lineal porque para todo o que coñecer o seu vai estar buscando por cada agulla individuo, cousa de feno, tentando ollar para a agulla. E iso non é moi divertido, na miña opinión. Gústame rápido. Gústame eficiente. E estudantes, traballadoras ti caras son, saben traballar de forma máis intelixente, non máis difícil tipo de cousas, como pode chegar a ser estes algoritmos. Entón, nós estamos indo a pé a través de só un exemplo rápido. Creo que vostedes deben ter unha man en Investigación binaria, pero no caso de alguén é algo difusa, quere reforzalo lo, imos só ir a través dun exemplo aquí. Entón, a xente está a buscar se a matriz contén sete. Entón, o primeiro que facemos é mirar no medio, non? E tamén vai ser a codificación Busca binaria en só un segundo. Entón, iso vai ser divertido. Entón, nós miramos no matrices pequenas medianas 3. Fai tres igualar 7? Non. É seis. Entón, é menor que ou maior que sete? Menor que. Si. Caras bo traballo. Eu sinto que como eu debería temos doces porque eu quere xoga-lo fóra para os estaleiros. É o que eu vou facer a próxima semana. El vai manter vostedes afiada. Entón, nós xogamos fóra que primeiro semestre, non? foi menor que. sabemos que todo en que parte esquerda será menos que o que estamos realmente a procurar. Así, non hai necesidade de prestar atención a ela. Só esqueza sobre iso. Entón, agora miramos para o noso lado dereito, e miramos para o medio alí, e agora son nove. Entón, 9 é-- --Everyone? Maior que o que somos buscar, non? Entón, nós estamos indo xogar fóra todo para a dereita. Como aquel. Agora, todos nós é deixar con un. Entón, imos comprobar, é este o que que estamos a buscar? el é. Atopamos o que queriamos. Por iso, está feito. Bilinear Search. E se observar, nos tiña sete entradas de alí. Levou só nós como tres veces, pero se está facendo como un billón, vostedes saben cantos pasos que faría ter se tivésemos catro millóns de cousas? Algún palpite? É 32. 32 pasos para atopar algo en catro millóns elemento da matriz por mor potencias de dous. Entón, dous é o 32, é de catro millóns. Así como moi tolo aínda está dentro como un relativamente pequeno número de pasos para atopar algo en catro millóns de elementos. Entón, nesa nota, estamos vai codificar iso para que vostedes poidan realmente tipo de ver como funciona isto. Todo ben, entón vostedes poden codificar. Vou deixar vós falar un pouco. Coñeza xente ao seu redor, o que é o que alguén quería da última sección. Entón, para coñecer a xente ao seu redor. Contacte un pouco. E todo o que quero de ti caras agora é só intentar crear un esbozo de pseudocódigo. Ok? Whoa. Todo o que quero de vostedes é que está só vai cubrir neste caso agora. Entón, eu teño definir esas superior e límites inferiores que representan o inicio e ao final da nosa matriz. E vai, en realidade, loop través de e descubrir o que estamos facendo dentro deste loop while. Entón, se pode descubrir out-- teño unha información há-- cales son os casos que temos aquí? Entón, se quere descubrir a casos, imos pseudocódigo aqueles e despois imos realmente codifica-las. E será, eu creo, espero que vai ser un pouco máis fácil do que espera. ¿Por que non é que moito código, en realidade, o que é moi legal. Mm-hm? Estudante: [inaudível]? Instrutor: Si. Había algo para atopar no medio. ALUMNO: Así, podemos usar isto. Está ben. Instrutor: Perfecto. Entón esta é o primeiro que necesitamos facer. Entón, atopar o medio. Grande. Entón tes unha idea de como poderíamos realmente atopar o medio con código? Estudante: Si. n máis de 2? Instrutor: Entón n máis de 2. Entón, unha cousa a lembrar que seus límites superiores e inferiores cambiar. Seguimos a constrição da parte da matriz nós estamos mirando para. Entón n máis de 2 só funcionará para o primeiro que facemos. Así, tendo superior e inferior en conta, como podemos obter ese elemento do medio? Porque queremos que a media entre superior e inferior, non? Mm-hm? Estudante: [inaudível]. Instrutor: Entón temos algún medio. E será superior máis baixa superior a 2. Impresionante. Alí imos nós. Un abaixo da liña. Vostedes están no seu camiño. Polo tanto, agora que temos o noso medio, o que queremos facer? Só en xeral. Non ten que codifica-lo. Si. Estudante: [inaudível]? Instrutor: Entón é máis porque é pensando a media entre os dous deles. Entón, se pensar neles como tipo de aumentar a partir dos lados, pensar sobre iso cando se achega no medio, quere así. Entón, se está en ambos os dous lados da medio, e temos como 5 e 7. Cando engade-los xuntos ti obter 12, ten divide por 2, é 6. Ás veces é difícil explicar por que funciona, pero se traballa con un exemplo, ás veces, vai axudar a descubrir se debe ser máis ou menos. Si. Estudante: [inaudível] exactamente no medio se tivesen un caso onde hai unha morea de números menores e como un número grande? Instrutor: Entón, todo o que precisa é o medio da matriz. Entón, se tiña unha morea de números pequenos e logo, un número moi grande ao final, non importa. Todo o que importa é que están clasificadas, só quero ollar para o medio do a matriz, porque aínda está fatiado o problema á metade. Legal. Polo tanto, agora que temos a medio, o que imos facer a continuación? ALUMNO: Compare. Instrutor: The comparar. Entón, comparar a media value_wanted. Legal. Entón ve aquí, temos este valor que queremos aquí. Teña en conta que esta é unha matriz. Así, refírese a media do índice. Por iso, queremos facer valores de media. Non esqueza, se quere comparar, de dous iguais. Fai única igual a ti só vai trasladar-lo, e despois, por suposto, é será o valor que quere. Polo tanto, non fagas iso. Entón imos ver se os valores no medio é igual ao valor que queremos. Non esqueza as súas claves. Dropbox debe ir. Entón, o que imos facer neste caso? Se é o que queremos para volver? Estamos tentando dicir. ALUMNO: imprimir. Instrutor: Ben, nós Non quere imprimir. Polo tanto, este é un bool aquí, polo tanto, quere voltar verdadeiro ou falso. Estamos dicindo, é este número un [? RRA? ?] Entón, se é, nós simplemente devolve-lo verdadeiro. Se podo soletrar verdade. ALUMNO: Por que non voltar cero? Instrutor: Entón vostede podería voltar cero se quixese. Pero neste caso, porque nosa función devolve un bool, necesitamos volver verdadeira ou falsa. ALUMNO: Cando está dicindo expresión booleana, pode configurar-lo igual a teito? Como se eu quero dicir, se esta condición non se cumpre, como é superior é igual a falso. Será que vai entender se só poñer teito do outro lado? Instrutor: Yeah. Entón, en realidade, se está sempre facendo algo como é superior ou é menor, que retorna verdadeiro ou falso e é realmente un estilo malo para digamos igual a igual a true ou iguais é igual a falso. Quere usar este resultado como o propio como o seu cheque. Non é o que eu quería. Iso é o que eu quería. Así, no caso de que vostede está pedindo sobre algo como gardar isto en c. Entón, se temos int main (void) e algo como isto. E ten, se é superior dalgunha entrada e está pregunta se pode facer algo coma isto? Non? ESTUDANTE: Eu estaba tentando para facelo [inaudível]. Porque se it's-- Instrutor: Certo. Entón quere que isto sexa falso, non? Estudante: Si. Instrutor: Entón, nese caso quero que realice, se iso non é verdade. Entón, a cousa legal facer alí é esta. Entón lembre de exclamación punto nega cousas? Di que [inaudível] non significa. Polo tanto, se miramos só esta parte aquí, din que avalía a falso como quere que el. Non falsa é certo que significa que este sería executado. Será que isto ten sentido? Estudante: Si. Instrutor: Awesome. Está ben. Entón, poderíamos só volver verdade neste caso. Polo tanto, agora temos dous outros casos neste caso. Cales son os nosos outros dous casos? Nós só facelo deste xeito. Entón imos comezar con outra cousa se os valores no medio é menor que o valor que queremos. Así, o noso valor no medio é menos que o valor que estamos a procurar. Así que conectado ti creo que quere actualizar? Superior ou inferior? Superior? Así que lado da matriz imos estar mirando? ALUMNO: A máis baixa. Instrutor: Estamos indo estar mirando cara á esquerda. Entón, algo pouco valor é menor. Polo tanto, o seu valor medio aquí é menor que o que queremos. Por iso, queremos levar o lado dereito da nosa matriz. Entón, nós estamos indo a actualizar o noso límite inferior. Entón, imos transferir nosa inferior. E o que pensas que debe ser menor? ESTUDANTE: O valor medio? Instrutor: Entón o value-- medio ALUMNO: Plus 1. Instrutor: --plus 1. Alguén me pode dicir por que temos que unha? Estudante: [? Ningún valor?] é máis igual a el. Instrutor: Certo. Porque xa sabemos que noso valor medio non é igual a iso e queremos borrar-lo desde todas as investigacións posteriores. Se esquece de que máis 1, esta vai gusta de loop indefinidamente. E só vai ser pego nunha loop infinito e entón vai segfault e as cousas van mal. Entón, asegúrese de sempre que non está incluíndo o valor que acaba de mirou. Entón, nós coidamos que cun plus 1. Polo tanto, agora temos a nosa última condición que sempre por razóns de seguridade podes consultar aquí, máis se o valor en o medio é maior que o valor queremos. Isto significa que queremos a metade do lado esquerdo. Entón, cal deles é que imos actualizar? Superior. E o que é este será igual? Medio menos 1 porque, claro, que queremos para asegurarse de que non estamos mirando para o valor medio de novo. E entón temos iso. É iso aí. Isto é todo de procura binaria é. Non é tan malo, non? É coma se 10 liñas de código con espazo en branco. Entón, moi poderoso, moi útil, vai estar a usalo nun dos seus Serie de exercicios posteriores. Quizais non este, pero máis tarde. Así, aprendela. Adoro. El vai te tratar ben. Entón, alguén ten algunha preguntas sobre procura binaria? Si. ALUMNO: Será que isto importa se o n é par ou impar? Instrutor: Non. Porque nós lanzalo ao medio como un int, ela só vai truncar-lo. Entón, que vai estar un enteiro e el vai finalmente clasificar a través de todo. Así que non se preocupe con iso. Todo o mundo bo? Impresionante. Legal. Entón, vós ten iso. Presentación. Así como estabamos falando, sei David mencionou tempos de execución de complexidade. Así, no mellor dos casos, é só un, o que chamamos tempo constante. Alguén me pode dicir por que isto pode ser? Que tipo de escenario que iso implica? Mm-hm. Estudante: [inaudível] first-- Instrutor: Entón no medio sendo o primeiro elemento que vén, non? Así, é un conxunto dun ou todo o que está a buscar só pasa a ser ben no medio. Entón, esa é a nosa mellor caso. Comeza en problemas reais, probablemente non chegará [inaudível] que moitas veces. E o noso peor caso? O noso peor caso é log n. E isto ten que ver co todo potencias de dous cousa que eu falei. Así, no peor caso, iso significaría que tivemos de cortar a matriz abaixo ata que era un elemento dun. Entón tivemos que corte-la pola metade tantas veces como nós podía. É por iso que é log n porque vostede segue dividindo por dous. Así presupostos, cousas que Necesito saber se está sempre vai usar unha busca binaria. Os seus elementos deben ser ordenados. Eles teñen que ser resoltas, porque esta é a única forma que pode saber se é capaz para xogar fóra metade. Se tivese esta bolsa confusa de números e está dicindo, OK, eu vou comprobar o medio número eo número que eu estou buscando é menos que iso, eu só vou para lanzar arbitrariamente fóra metade. Non sabe se o os números en que a outra metade. A súa lista debe ser resolta. Así, este pode ser indo adiante un pouco, pero ten que ter acceso aleatorio. Debe ser capaz de só ir aquel elemento do medio. Se ten que atravesar por algo ou leva etapas extra para chegar a ese elemento do medio, non se log n máis porque está engadindo máis traballo para el. E iso vai facer un pouco de máis sentido en dúas semanas, pero eu medio que quería prefacio, dar a vostedes unha idea do que é para vir. Pero estes son os dous premisas importantes que precisa para unha lista de binario. Asegúrese de que está clasificado. Ese é o gran problema para vostedes agora mesmo. E no que podemos entrar en o resto das nosas sortes. Entón, catro burbulla sorts--, inserción, selección e merge. Están todos ben legal. Se vostedes deciden tomar CS 124, vai aprender sobre todo tipo de tipos. E se é un fan xkcd, non é un sobre cómics moi legal como tipo realmente ineficaces, o que eu recomendo que vai mirar. Un deles é como especie de pánico, que é como, oh non, regresar disposición aleatoria. Sistema de apagado. Deixar. Entón, humor geeky é sempre bo. Entón, alguén recorda tipo de como só unha idea xeral de como bubble sort funciona. Vostede recorda? Estudante: Si. Instrutor: Dalle. Estudante: Entón está pasando e se é o máis grande, entón cambiar os dous. Instrutor: Mm-hm. Exactamente. Entón só iterado. Vostede verifica dous números. Se o anterior é maior despois do que aquel, só trocalos de forma que en Deste xeito, todos os números máis altos burbulla-se a fin da lista e todos os números máis baixos burbulla abaixo. Será que amosar a vostedes o frío efecto sonoro selección vídeo? É ben legal. Así como Robert dixo, o algoritmo que acaba de percorrer a lista, cambiando os valores adxacentes se eles non están en orde. E despois é só ir repetindo ata que non faga ningunha swaps. Entón, non é malo, non? Entón, só temos un exemplo rápido aquí. Entón, iso vai clasificar los en orde crecente. Entón, cando nós pasamos a primeira tempo, miramos a oito e seis non son, obviamente, en orde, nós trocalos. Entón mire para a próxima. Oito e catro non en orde. Trocalos. E despois de oito e dous, trocalos. Alí imos nós. Entón, despois de súa primeira pasaxe, vostede sabe que o seu maior número será todo o camiño na parte superior, porque é só será constantemente maior que o resto e el só vai para burbulla ata todo o camiño ata a final alí. Será que isto ten sentido para todos? Legal. Entón miramos para a nosa segunda pasaxe. Seis e catro, interruptor. Seis e dous, switch. E agora temos algunhas cousas en orde. Así, para cada paso que facer a través da nosa lista enteira, sabemos que como que moitos números ao final foi clasificados. Entón nós facemos unha terceira paso, que é un intercambio. E, a continuación, na nosa cuarta pasar, temos cero slots. E así sabemos que a nosa matriz ten sido resolto. E esa é a gran cousa con bubble sort. Sabemos que cando nós ter cero swaps, que significa que todo está en orde completa. É unha especie de como podemos comprobar. Entón, nós tamén estamos indo a codificar burbulla tipo o que tampouco é tan malo así. Ningún destes son tan malas. Sei que pode parecer un pouco asustado. Sei que cando eu tirei a clase, mesmo cando estaba ensinando a clase para Por primeira vez o ano pasado, Estaba tipo, como fago isto? Ten sentido na teoría, pero como é que imos realmente facer iso? É por iso que eu tamén quero andar por medio de código convosco aquí. Entón, eu teño un pseudocódigo para vós neste momento. Entón, só tes que manter isto presente como estamos a piques de facer a transición máis. Polo tanto, temos algúns contador que mantén o control dos nosos swaps, porque necesitamos ter seguro de que estamos comprobando iso. E iteramos toda a matriz como acabamos de facer con este exemplo. Se o elemento é maior que antes o elemento despois de onde estamos, nós trocalos e incrementamos a nosa contador, porque así que cambiar, queremos deixar o noso contador de saber diso. Calquera dúbida alí? Algo parece divertido aquí. ALUMNO: Vostede poñer o contador a cero cada vez que pasar polo loop? Non vai manter de volta a cero cada vez? Instrutor: Non necesariamente. Entón, o que pasa é que pasamos aquí. Entón faga agora, lembre, este executarase unha vez, sen falla. Entón vai establecer o contador igual a cero, logo vai para percorrer. Como se repite a través de, ha actualizar balcón. Como el actualiza balcón cando está feito, cando é acadar o final da matriz, se a nosa lista non fose resolto, contador foron actualizados. El verifica o estado de conservación e di, OK, é contador maior que cero. De ser isto, facelo de novo. Desexa reiniciar para que cando percorrer, contador é igual a cero. Se pasar por unha ordenada array, nada cambia, isto falla, e volver á lista ordenada. Será que isto ten sentido? Estudante: Podería un pouco. Instrutor: Aceptar. Se hai calquera outra cuestión que vén á tona. Si. Estudante: Cal sería a función ser para cambiar os elementos? Instrutor: Entón podemos realmente escribir que, se nós estamos indo agora. Legal. Entón, nesa nota, Alison vai para volver para o aparello. Vai ser divertido. E nós temos o noso bo burbulla cousa tipo aquí. Entón, eu xa fixen ciclismo a través da matriz. Temos os nosos swaps que son iguais a cero. Por iso, queremos cambiar adxacente elementos se eles están fóra de orde. Entón, o primeiro que necesitamos non é iterado nosa matriz. Entón, como pensas que pode iterado nosa matriz? Temos para e i é igual a 0. Queremos i a ser menos que n menos 1 menos k. E eu vou explicar isto nun segundo. Polo tanto, esta é unha optimización aquí, onde, recordo como dixen despois de cada paso a través da matriz de nós sei que todo o que é on-- Entón, despois dun pase de nós sabemos que este é clasificado. Tras dous pases sabemos que todo isto está clasificada. Despois de tres pasaxes de nós sei que é clasificada. Así, a forma que eu estou interactuar a través da matriz aquí, se está asegurarse de ir só a través do que se sabe é indiferenciado. Ok? Isto é só unha optimización. Pode escribir-lo só inxenuamente iteración través de todo, sería só levar máis tempo. Con este ciclo de catro é só unha boa optimización porque sabemos que despois de cada chea iteración través da matriz aquí, como cada ciclo completo aquí, sabemos que un máis destes elementos serán clasificados ao final. Polo tanto, non se preocupe con aqueles. Será que isto ten sentido para todos? Ese truco pouco fría? Entón, nese caso, se estamos interactuar a través, sabemos que queremos comprobar se matriz n e n + 1 están en orde. Está ben. Entón aquí está o pseudocódigo. Queremos comprobar se a matriz n e n máis 1 están en orde. Entón, o que podemos ter aí? Vai ser unha condicional. Será un caso. ALUMNO: Se array n é inferior a matriz n máis 1. Instrutor: Mm-hm. Ben, máis ou menos. ALUMNO: Maior que. Entón eu quero trocalos. Exactamente. Polo tanto, agora entramos en cal é a mecanismo de intercambio-los? Entón nós pasamos por iso brevemente, un tipo de función de intercambio a semana pasada. Alguén recorda como funcionaba? Polo tanto, non podemos só reenvía-los, non? Porque un deles vai perder. Se dixésemos A é igual a B e despois B é igual a A, toda unha súbita tanto son só igual a B. Entón o que temos que facer é que ten unha variable temporal que é vai realizar un dos nosos mentres estamos no proceso de cambio. Entón, o que temos é que imos ter algúns int temperatura é igual a-- pode atribuílo lo para calquera que quere, simplemente asegúrese de manter o control de ele-- polo tanto, neste caso, eu vou atribuílo la a matriz n + 1. Entón, iso vai soster o que quere valor é ese segundo bloque que estamos mirando. E entón o que podemos facer é que podemos ir adiante e variedade Reassign n + 1, porque sabemos que que teñen valor almacenado. Este é tamén un dos grandes coisas- Non sei se algún de vós tivemos problemas onde se alternan dous liñas de código, de súpeto as cousas funcionaban. Orde é moi importante no CS. Entón, asegúrese de diagrama cousas, se é posible sobre o que está realmente a suceder. Entón agora nós imos reatribuído array n + 1, porque sabemos que que teñen valor almacenado. E podemos asignar iso a matriz n ou neste caso variedade i. Moitas variables. Está ben. Matriz Entón agora temos trasladado i máis un para igualar o que está na matriz i. E agora podemos volver e asignar gama i co que? Calquera? Estudante: 10. Instrutor: 10. Exactamente. E unha última cousa. Se temos trocado agora, o que necesitamos facer? Que é o único que vai dicir se algunha vez rematar este programa? O que nos di que ten unha lista ordenada? Se non executar calquera swaps, non? Se permutas é igual de cero ao final desta. Así, sempre que realizar un intercambio, como nós só fixen aquí, queremos actualizar swaps. E sei que houbo unha pregunta anterior sobre se poida usar cero ou un, en vez de verdadeiro ou falso. E iso é o que iso fai aquí. Polo tanto, este di que se non swaps. Polo tanto, se permutas é cero, o que eu é-- sempre chegar en miñas verdades e os meus falsos mesturados. Queremos nos avaliar a verdade e non é. Entón, se é cero, entón é falsa. Negarse o con un [? bater?] convértese en verdade. Entón esta liña executa. Verdades e falsas e ceros e uns estar tolo. Así, se andar a modo por iso que vai ter sentido. Pero iso é o que este pequeno pouco de código aquí fai. Polo tanto, este verifica fixemos os swaps. Entón, se é somente cero, que será falsa e toda a cousa é indo para executar de novo. Legal? Estudante: Que fai pausa facer? Instrutor: Rompe só rompe-lo fóra do loop. Polo tanto, neste caso, sería así como acabar co programa e que tería só ten a súa lista clasificada. ESTUDANTE: Amazing. Instrutor: Eu sinto moito? ESTUDANTE: Como previamente usado por escrito sobre un escrito de cero presentar que si que vai funcionar ou non. Instrutor: Yeah. Así, pode voltar cero ou un. Neste caso, por que non estamos realmente facer algo coa función, nós só queremos que rompe. Nós realmente non se preocupan con iso. Brake tamén é bo se se usa para saír de catro lacetes ou condicións que non quere manter a execución. El só leva a fóra deles. É un pouco dunha cousa matices. Eu sinto que hai unha gran cantidade de man de ondas, como vai aprender sobre iso en breve. Pero vai aprender sobre iso en breve. Eu prometer. Está ben. Así que todos obter bubble sort? Non é tan malo. Iterado, cousas de intercambio, utilizando unha variable temp, e que está todo listo alí? Legal. Impresionante. Está ben. Volver ao PowerPoint. Calquera dúbida en xeral sobre estes ata agora? Legal. Mm-hm. Estudante: [inaudível] int main normalmente. Ten que ter que para iso? Instrutor: Entón, nós só buscar só no algoritmo de ordenación real. Se tivese que dentro como un programa máis grande, que tería un lugar principal int. Dependendo de onde vostede usar este algoritmo, sería determinar o que é sendo devolto por ela. Pero, para o noso caso, estamos estrictamente mirando como fai iso, en realidade, iterado través dun array. Polo tanto, non se preocupe con iso. Entón, nós estabamos falando sobre mellor caso e os peores escenarios de busca binaria. Por iso, é tamén importante facer que, para cada un dos nosos tipos. Entón, o que pensas que é o peor caso de execución de bubble sort? Vostedes lembran-se? ALUMNO: N menos 1. Instrutor: N menos 1. Entón isto significa que hai n menos 1 comparacións. Entón, unha cousa a entender é que na primeira iteración, que pasamos, nós comparamos estes dois-- de xeito que é un. Estes dous, tres, catro. Entón, despois de unha iteración nós xa ten catro comparacións. Cando eu estou falando de tempo de execución e n. N representa o número de comparacións como unha función de cantos elementos temos. Ok? Así que pasamos, temos catro. A próxima vez que vostede sabe que non facer ten que coidar do presente. Nós comparamos os dous, estes dous, estes dous, e se non tivésemos que a optimización co ciclo de catro que escribín, estaría comparando aquí de calquera maneira. Entón tería que executado a través da matriz e facer comparacións n n veces, porque cada vez que realizar, a través del, tipo unha cousa. E cada vez que percorren a matriz, facemos n comparacións. Así, o noso tempo de execución para iso é en realidade, n ao cadrado, que é moito peor na nosa rexistro final, porque iso significa se tivésemos catro mil millóns de elementos, é vai levar de catro millóns cadrados no canto de 32. Entón, non é o mellor tempo de execución, pero para algunhas cousas, vostede sabe, se está dentro un certo rango de elementos bubble sort pode ser bo para usar. Está ben. Entón agora o que é o mellor caso de tempo de execución? ALUMNO: Cero? Ou 1? Instrutor: Entón un faría ser unha comparación. Right. ALUMNO: N menos 1? Instrutor: Entón, si. Entón n menos un. Sempre que ten un concepto como n menos 1, temos a tendencia de simplemente deixar a e nós só dicir n porque ten comparar cada un dos these-- cada par. Polo tanto, sería n menos 1, que nos que acabara de dicir é aproximadamente n. Cando está lidando con tempo de execución, todo está achega. Sempre que é o expoñente correcto, é moi bo. Esa é a forma como lidamos con el. Así que o mellor caso é n, que significa que a lista xa está clasificado, e todo o que facemos é executado a través de e comproba que está clasificada. Legal. Todo correcto. Entón, como ve aquí, nós só ten algúns gráficos. Entón n ao cadrado. Fun. Moito peor que n, como vemos, e moi, moito peor que 2n rexistro. E entón comeza tamén en rexistro rexistros. E colle 124, entrar como a estrela de rexistro, que é como un tolo. Entón, se vostede está interesado, estrela rexistro de busca. É unha especie de diversión. Polo tanto, temos este gran gráfico. Só un heads-up, este un gráfico marabilloso ter para a súa termo medio, porque nós tempo para preguntar-lle estas diluír. Así, só a cabeza cara arriba, ten este no seu intercalar sobre a súa folla de fraude bo alí. Entón, nós só mirou para bubble sort. No peor dos casos, n ao cadrado, mellor caso, n. E nós imos ollar para os outros. E como se pode ver, a única un que realmente fai ben é merge sort, que nós imos entrar por que. Entón, nós estamos indo a ir ao xunto un tipo de selección aqui--. Alguén recorda como selección especie traballou? Dalle. ALUMNO: Basicamente pasar por unha orde e crear unha nova lista. E así como está poñendo elementos en, poñelos no lugar seguro na nova lista. Instrutor: Así que os sons máis como ordenación por inserción. Pero está realmente preto. Son moi semellantes. Mesmo eu pegalos mesturados ás veces. Antes desta sección eu era como, esperar. Está ben. Entón, o que quere facer é a selección de clasificación, o xeito que pode pensar sobre o tema ea forma Eu me asegurarse de que non tentar obter los mesturados, é que atravesa e selecciona o menor número e el pon que no inicio da súa lista. El cambio lo coa primeira posición. Eles realmente teñen un exemplo para min. Impresionante. Así, só unha forma de pensar en selección ele-- tipo, seleccione o menor valor. E nós estamos indo executado mediante un exemplo que eu creo que vai axudar, porque Creo visuais sempre axudar. Entón, imos comezar con algo que é totalmente normais. Rede será indiferenciados, verde serán clasificados. Todo fará sentido en un segundo. Entón nós pasamos por e iteramos desde o principio ata o final. E nós dicimos: OK, 2 é noso menor número. Entón, nós imos tomar dous e imos para mover para a fronte da nosa matriz porque é a menor número que temos. Entón, iso é o que este está facendo aquí. El só vai cambiar os dous. Entón agora temos un clasificado parte e unha parte non clasificado. E o que é bo lembrar sobre a selección de tipo é que estamos seleccionando só da parte non clasificado. A parte ordenada acaba de saír só. Mm-hm? ESTUDANTE: Como el sabe o que é menor sen comparalos lo para todos os demais valores na matriz. Instrutor: El fai comparalos-lo. Nós gústanos de ignorados. Este é só xeral global. Si. Cando escribimos o código que eu son seguro que vai estar máis satisfeito. Pero garde este primeiro elemento como a menor. Vostede compara e dicir, OK, é menor? Si. Mantelo. Aquí é menor? Non? Esta é a súa pequena, descargar-lo para o seu valor. E será moito máis feliz cando imos a través do código. Entón nós pasamos, nos troca-lo, polo que, a continuación, miramos para esta parcela non clasificado. Entón, nós estamos indo a seleccionar tres. Estamos indo para poñelas polo o fin da nosa parte ordenada. E nós só estamos indo para continuar facendo que, facendo iso, e facendo iso. Polo tanto, este é o noso tipo de pseudocódigo aquí. Imos codificar-lo aquí en un segundo. Pero só unha cousa de andar a través dun alto nivel. Está indo a ir de i é igual a 0 para n menos 2. Esa é outra optimización. Non te preocupes moito con iso. Entón, como estaba dicindo. Como Jacob estaba dicindo, coma nós seguir o que o noso mínimo é? Como sabemos? Temos que comparar todo na nosa lista. Entón mínimo é igual a i. É só dicir, neste caso, o índice do noso valor mínimo. Entón vai para percorrer e que vai de j é igual a i + 1. Entón xa sabemos que este é o noso primeiro elemento. Non necesitamos comparalos-lo a si mesmo. Entón nós comezamos a comparalo con o seguinte o que é por iso que é i + 1 para n menos 1, que é a final da matriz alí. E nós dixemos, se da matriz en j sexa inferior a matriz min, entón nós recolocar onde nosos índices mínimos é. E se non min é igual a i, como en que estabamos de volta para aquí. Así como cando fixemos primeiro un regalo. Neste caso, iria comezar a cero, el acabaría sendo dous. Así, non sería igual min i na final. Isto nos permite saber que necesitamos trocalos. Eu me sinto como un exemplo concreto axudará moito máis que iso. Entón, eu vou codificar iso convosco agora e eu creo que vai ser mellor. Tipos adoitan traballar desa forma en que moitas veces é mellor só para velos. Entón, o que queremos facer é queremos primeiro en menor elemento na súa posición na matriz. O que Jacob estaba dicindo. Debe almacenar que dalgunha forma. Entón, imos comezar iteración sobre a matriz. Nós imos dicir que é noso primeiro só para comezar. Entón, nós imos ter int menor é igual ao da matriz en i. Entón, unha cousa a notar, cada tempo este bucle execútase, estamos comezando un paso máis adiante. Cando comezamos miramos para este. A próxima vez que iterado, estamos comezando nun presente e atribuíndolle o noso menor valor. Polo tanto, é moi semellante ao bubble sort onde sabemos que despois dunha pasaxe, este último elemento é clasificado. Coa selección de clasificación, que é todo o contrario. En cada paso, sabemos que o primeiro é clasificada. Tras a segunda pasaxe, o segunda será clasificada. E como viu cos exemplos de diapositivas, nosa porción ordenados non para de crecer. Así, definindo o noso menor un para matrices i, todo o que está facendo constrição é o que nós estamos mirando de forma para minimizar o número de comparacións que facemos. Isto ten sentido para todos? Debe de min para ser executado a través de que de novo máis lenta ou con palabras diferentes? Estou feliz por. Está ben. Entón, nós estamos almacenando o valor neste punto, pero tamén queremos almacenar o índice. Entón, nós estamos indo para almacenar o posición da menor un, que só vai ser eu. Entón agora Jacob está satisfeito. Temos cousas gardadas. E agora temos que mirar a través de a parte non separados da matriz. Polo tanto, neste caso esta sería o noso indiferenciados. Este é i. Está ben. Entón o que nós imos facer será para un loop. Sempre que precisa iterado través dun array, a súa mente podería ir a un loop. Así, para algúns int k equals-- o que pensamos k será igual a comezar con? Isto é o que definimos como o noso menor valor e queremos comparalo lo. O que queremos comparar? Será este próximo, non? Entón, nós queremos k ser inicializar para i + 1 para comezar. E queremos k neste caso, Xa tamaño almacenados aquí, para que poidamos usar só tamaño. Tamaño sendo o tamaño da matriz. E nós só queremos actualizar k por un de cada vez. Legal. Entón, agora necesitamos atopar o elemento máis pequeno aquí. Entón, se nós iterado, nós quere dicir, se a matriz en k é menor que a menor value-- este é o lugar onde estamos, en realidade, manter o control do que é a menor aquí- entón queremos trasladar o noso menor valor é. Isto significa que, oh, somos iteración por aquí. Calquera valor que está aquí é non a nosa máis pequena cousa. Non queremos iso. Queremos trasladar-lo. Entón, se estamos a reatribuição-lo, o que facer pensas que pode ser neste código aquí? Queremos trasladar menor e posición. Entón, o que é menor agora? ESTUDANTE: Array k. Instrutor: Array k. E cal é a posición agora? O que hai de os índices de noso menor valor? É só k. Entón matriz k, k, eles combinan. Entón, nós queriamos que recolocar. E entón, despois que atopamos o menor, Así, a finais deste loop aquí atopamos o noso menor valor é, polo tanto, só troca-lo. Neste caso, como dicir que a nosa menor valor é aquí fóra. Este é o noso menor valor. Nós só queremos troca-lo aquí, o que é o que este función intercambio na parte inferior fixo, que acabamos escribiu-se xunto a algúns minutos. Por iso, debe parecer familiar. E entón el só vai iterado por medio ata acadar todo o camiño ao final, o que significa que ten cero elementos que son indiferenciados e todo o máis foi resolto. Ten sentido? Un pouco máis concretamente? O código axuda? ALUMNO: Para un tamaño, nunca realmente define-la ou cambia-la, como el sabe? Instrutor: Entón unha cousa a notarse aquí é o tamaño int. Entón, nós estamos dicindo neste tipo sort-- é unha función neste case-- é selección especie, é pasado na coa función. Entón, se non foi aprobada en, faría algo como coa lonxitude da matriz ou iterado para atopar a lonxitude. Pero porque é pasado en, podemos usalo só. Simplemente asumir que o usuario deulle un tamaño válido que en realidade representa un tamaño da súa matriz. Legal? Se vostedes teñen algún problema con estes ou quere máis práctica de codificación tipo no seu propio país, ten que ir study.cs50. É unha ferramenta. Teñen un verificador que realmente pode escribir. Eles fan pseudocódigo. Teñen máis vídeos e diapositivas incluíndo os que eu uso aquí. Entón, se aínda está sentindo un pouco confuso, proba iso. Como sempre, veña falar comigo, tamén. Pregunta? Estudante: Vostede está dicindo que o tamaño é previamente definido? Instrutor: Si. Tamaño é previamente definido se aquí na declaración da función. Entón asume que el fose aprobada en polo usuario, e para simplificar, imos supor que o usuario nos deu o tamaño correcto. Legal. Entón, iso é a selección de clasificación. Xente, sei que estamos aprendendo moito hoxe. É unha densa datos para sección. Entón, con iso, imos ir a ordenación por inserción. Está ben. Entón, antes de que temos que facer nosa análise runtime aquí. Así, no mellor dos casos, concedida sempre que eu mostre a mesa que eu xa tipo de xogou fóra. Pero o mellor caso de execución, o que pensamos? Todo resolto. N ao cadrado. Alguén ten unha explicación por que pensas? Estudante: Está comparando through-- Instrutor: Certo. Está comparando a través. En cada iteración, a pesar de estamos diminuíndo este por un, aínda está a buscar todo para atopar o menor. Así, aínda que o seu menor valor É aquí, en principio, aínda está comparando-a contra o resto para que seguro que é a máis pequena cousa. Entón vai acabar correndo por aproximadamente n veces ao cadrado. Todo correcto. E o que é o peor caso? Tamén n ao cadrado, porque está indo estar facendo este mesmo procedemento. Polo tanto, neste caso, a selección tipo ten algo que tamén chamamos tempo de execución esperado. Así, nos outros, só sei os límites superior e inferior. Dependendo de como o noso tolo lista é ou como indiferenciados é, que varían entre n ou n ao cadrado. Non sabemos. Pero por que a selección especie ten o mesmo peor eo mellor caso, que nos di que non importa o tipo de entrada que ter, se é completamente clasificadas ou totalmente inversa clasificadas, é vai levar a mesma cantidade de tempo. Entón, nese caso, se Teña en conta que da nosa mesa, realmente tiña un valor que estes dous tipos non teñen, tempo de execución que é esperado. Entón, nós sabemos que sempre que corremos selección especie, se pode garantir que executar un tempo n ao cadrado. Non hai variabilidade alí. É só esperar. E, de novo, se quere aprender máis, tomar CS 124 na primavera. Todo correcto. Xa vimos este. Legal. Así, tipo de inserción. E eu estou indo probablemente para brillar por iso. Non vou ter vostedes codifica-lo. Nós imos só pasar por ela. Entón ordenación por inserción é unha especie de semellante á selección especie en que temos tanto un indiferenciados e ordenados parte da matriz. Pero o que é diferente é que como pasar por un por un, nós só tomar calquera número é o seguinte na nosa indiferenciados, e clasificalos lo correctamente na nosa matriz clasificada. Vai facer máis sentido cun exemplo. Entón, todo comeza como indiferenciados, Así como coa selección tipo. E nós imos resolver iso en orde ascendente como fomos. Entón, na nosa primeira pasaxe tomamos o primeiro valor e dicimos: OK, está agora nunha lista por si mesmo. Porque está nunha lista por si mesmo, está clasificado. Parabéns por ser o primeiro elemento desta matriz. Xa está resolto todo no seu propio país. Entón agora temos un clasificado e un conxunto indiferenciado. Entón, agora imos dar o primeiro. Que pasa entre aquí e aquí está o que nós dicimos, OK, imos ollar para o primeiro valor da nosa matriz indiferenciados e nós estamos indo a introducir-lo no seu correcto lugar na matriz de clasificación. Entón, o que facemos é tomar 5 e podemos dicir, OK, 5 é maior que 3, por iso, só inserir-lo dereito á dereita do que iso. Somos bos. Entón imos ao noso próximo. E tomamos dous. Dicimos, OK, 2 é menos de 3, polo que sabemos que Debe de estar no cabeza da nosa lista agora. Entón, o que facemos é empurrar 3 e 5 para abaixo e pasamos 2 no que o primeiro slot. Entón, nós estamos só inseríndoas o o lugar correcto que debería ser. Entón, miramos para o noso seguinte, e nós dicimos seis. OK, é maior que 6 todo na nosa matriz clasificada, por iso, só marcalo ata o final. E entón miramos para catro. 4 é inferior a 6, é menos que 5, pero é maior que 3. Por iso, só tes que inserir-lo á dereita en a medio entre 3 e 5. Que algo para facer pouco máis concreto, aquí é o tipo de idea do que pasou. Así, para cada elemento non clasificado, que determinar onde na parcela clasificada el é. Así, tendo en conta a clasificado e non clasificado, temos que atravesar e figura para onde el encaixa na matriz de clasificación. E nós inserir-lo, desprazando o elementos á dereita do que abaixo. E entón nós só manter iterado ata que ten unha lista completamente resolto onde indiferenciados agora é cero e ordenada recolle o totalidade da nosa lista. Entón, de novo, para facer as cousas aínda máis concreto, temos pseudocódigo. Entón, basicamente, para i é igual a 0 a n menos 1, iso é só a lonxitude da nosa matriz. Temos algún elemento que é igual a a primeira matriz ou os primeiros índices. Montar j igual a iso. Así, mentres j é maior que cero e matriz, j menos 1 é maior que o elemento, polo que todo o que está facendo é estar seguro de que seu j representa realmente a porción non triados da matriz. Así, mentres aínda hai cousas para clasificar e j menos un é-- que é o elemento a ela? J nunca foi definido aquí. É unha especie de irritante. Está ben. De calquera forma. Entón j menos 1, está comprobando o elemento antes. Está dicindo, OK, é o elemento antes de onde queira que eu am-- imos realmente aproveitar iso. Entón, digamos que se trata como na nosa segunda pasaxe. Entón eu vai ser igual a 1, que é aquí. Entón i será igual a 1. Isto sería de 2, 4, 5, 6, 7. Todo correcto. Así, o noso elemento, neste caso, será igual a 4. E nós temos algúns j que é será igual a 1. Oh, j está diminuíndo. Isto é o que é. Entón, j é igual a i, entón o que é iso dicindo é que a medida que avanzamos, estamos só asegurarse de que non estamos máis indexación dese xeito cando estamos intentando para introducir as cousas na nosa lista clasificada. Polo tanto, cando j é igual a 1 e, neste caso matriz j menos um-- tan matriz j menos 1 é 2 neste case-- se é iso maior que o elemento, entón todo isto está facendo está cambiando as cousas. Polo tanto, neste caso, unha matriz j menos Sería matriz de cero, o que é 2. 2 non é maior que 4, de xeito que este non é executado. Así, o cambio non se move cara abaixo. O que isto fai aquí é só movendo o array ordenado baixo. Neste caso, de feito, nos podería fazer-- imos facelo tres. Entón, se estamos a camiñar a través de Neste exemplo, agora estamos aquí. Esta é clasificada. Este é indiferenciado. Legal? Entón, i é igual a 2, así noso elemento é igual a 3. E o noso j é igual a 2. Entón miramos a través e nós dicir, OK, é matriz j menos un maior que o elemento que nós estamos mirando? E a resposta é si, non? 4 é maior que 3 e j é 2, polo tanto, este código é executado. Entón, agora o que nós facemos unha serie de 2, polo que aquí, nós trocalos. Entón, nós só dicir, OK, array en 2 agora será 3. E j será igual j menos 1, que é 1. Isto é horrible, pero vostedes a idea. J é agora igual a 1. E matriz j é só vai ser igual ao noso elemento, que foi de 4. Eu apaguei algo que non debía ten ou algo miswrote, pero vós comeza a idea. É moverse en n. E entón, se iso fose, sería lazo de novo e el dicía: OK, j é un momento. E matriz j menos 1 é agora 2. É de 2 a menos de noso elemento? Non? Isto significa que temos este elemento inserido no punto correcto na nosa matriz clasificada. Entón podemos levar isto e dicimos: OK, a nosa matriz clasificada está aquí. E levaría ese número 6 e ser como, OK, é de 6 inferior a ese número? Non? Legal. Estamos ben. Facelo de novo. Dicimos 7. É menos que 7 finais da nosa matriz clasificada? Non. Entón, nós estamos ben. Entón, iso sería resolto. Basicamente todo isto fai se está dicindo take o primeiro elemento súa matriz non clasificado, descubrir a onde vai na súa matriz de clasificación. E iso só se encarga de swaps de facelo. Está basicamente só cambiando ata que estea no punto seguro. A imaxe visual é que é movendo todo para abaixo, facendo iso. Entón, é como a metade bubble sort-esquí. Consulte estudo 50. Recomendo probar codificar iso no seu propio país. Se ten calquera problema ou se quere ver código de exemplo para un tipo de inserción, por favor, me aviso. Estou sempre por preto. Entón, o peor caso de tempo de execución e mellor caso de execución. Como viu cara da mesa eu xa mostre, é tanto n ao cadrado e n. Así, tipo de ir fóra do que falamos sobre os nosos tipos anteriores, peor caso de tempo de execución é que, se é totalmente non separados, temos que comparar todos estes n veces. Nós facemos unha morea de comparacións porque se está en orde inversa, imos dicir, OK, este é o mesmo, isto é boa, e este terá que ser comparados contra o primeiro en ser movido cara atrás. E a medida que dirección o fin da cola, temos comparar, comparar e comparar contra todo. Entón, el acaba sendo preto de n ao cadrado. Se é correcto, entón dicir, OK, 2, vostede é bo. 3, está en relación a dous. Vostede é bo. 4, basta comparar coa cola. Vostede é bo. 6, comparar coa cola, está ben. Así, para cada punto, se xa está clasificadas, está facendo unha comparación. Entón é só n. E porque temos un mellor caso de execución de n e un caso peor tempo de execución de n cadrado, non temos tempo de execución esperado. E só depende do caos da nosa lista alí. E, de novo, outra gráfico e outra táboa. Así, as diferenzas entre os tipos. Eu estou indo só para brisa a través, eu sentir como falamos extensivamente sobre como todo tipo de variar e enlace xuntos. Entón, merge sort é o último Vou che aborrecer con caras. Temos un cadro moi colorido. Entón, merge sort é un algoritmo recursivo. Entón, vostedes saben o que unha función recursiva é? Alguén quere dicir? Quere tentar? Así, unha función recursiva é só unha función que chama a si mesmo. Entón, se vostedes están familiarizados coa secuencia de Fibonacci, que se considera recursivo porque levar os dous anteriores e engadila los xuntos para conseguir o seu próximo. Entón recursiva, sempre penso de recursividade como como unha espiral entón é como a espiral para abaixo para el. Pero é só unha función que chama a si mesmo. E, de feito, moi rapidamente eu pode amosar-lle o que parece. Entón recursiva aquí, se miramos, este é a recursivamente para resumir nunha matriz. Entón, todo o que facemos é temos a función suma suma que leva un tamaño e unha matriz. E se observar, o tamaño descensos dun nun. E todo o que fai é se x é igual a zero-- tanto, se o tamaño da matriz é igual a zero-- el retorna a cero. Se non, el resume este último elemento da matriz, e, a continuación, leva unha suma de resto da matriz. Entón, é só rompe-lo para abaixo en problemas cada vez menores. Longa historia curta, recursão, función que chama a si mesmo. Se iso é todo o que ten fóra deste, iso é o que unha función recursiva é. Se tomar 51, vai estar moi, moi cómodo con recursividade. É moi legal. Tiña sentido en como 03:00 unha noite fóra. E eu era como, por que eu non uso iso? Así, para merge sort, basicamente o que vai facer é que é vai rompe-lo e rompe-lo abaixo ata que é só elementos individuais. Os elementos individuais son fáciles de clasificar. Vemos isto. Se tes un elemento, é xa considerada clasificada. Entón, nunha entrada de n elementos, se n é inferior a 2, basta volver porque iso significa é 0 ou 1, como vimos. Aqueles son considerados elementos ordenados. Se non, rompe-lo ao medio. Ordenar a primeira parte, clasificar a segunda metade, logo fundín-las. Por que se chama merge sort. Polo tanto, temos aquí nós imos resolver estes. Así, temos telos ata que o tamaño da matriz é 1. Entón, cando é un, nós só volver porque este é un array ordenado, e este é un array ordenado, e iso é un array ordenado, todos estamos clasificadas. Entón, o que facemos é comezar a fundirse los xuntos. Así, o xeito que poida pensar en fusión é acaba de eliminar a menor número de cada unha das sub-matrices e só anexo-lo á matriz emerxeu. Entón, se ollar aquí, cando temos estes conxuntos temos 4, 6 e 1. Cando queremos mesturar estes, miramos para estes dous primeiros e dicimos: OK, un é menor, vai para adiante. 4 e 6, non hai nada para comparar que el, só marcalo ata o final. Cando quedamos estas dúas, nós só levar a unha menor destes dous, polo que é un. E agora nós tomamos a menor destes dous, entón 2. Menor destes dous, tres. Menor destes dous, 4, 5, 6. Entón, está só tirando estes. E porque teñen foron clasificadas anteriormente, só ten unha Comparación de cada vez que hai. Entón, máis código aquí, só representación. Entón comeza no medio e clasificar esquerda e á dereita e entón só mesturar aqueles. E non temos código para fundir aquí. Pero, de novo, se vai en estudar 50, que vai estar alí. Se non, vir falar comigo Se aínda está confuso. Entón cousa legal aquí é que mellor caso, peor caso, e tempo de execución espera son todos no rexistro n, que é moito mellor que temos visto para o resto das nosas sortes. Vimos n ao cadrado eo que realmente chegar aquí é n log n, o que é óptimo. Mira como moito mellor que é. Tal curva agradable. Polo tanto, moito máis eficiente. Se xa se poida, uso merge sort. Ela lle vai aforrar tempo. Entón, de novo, como dixemos, se está abaixo nesta rexión máis baixa, non que facer moita diferenza. Vostede levántase a miles e miles de entradas, definitivamente quere un algoritmo máis eficiente. E, unha vez máis, a nosa mesa fermoso de todos tipo que vostedes aprenderon hoxe. Entón, sei que foi un día denso. Iso non vai necesariamente para axudar co seu pset. Pero eu só quero facer un disclaimer esta sección non é só sobre Serie de exercicios. Todo este material é xusto xogo para os seus exames semestrais. E tamén se continúa con CS, estes son os fundamentos realmente importantes que precisa saber. Así, uns días serán un pouco máis pset axuda, pero algunhas semanas será contido moito máis efectiva que pode non parecer super útil para ti agora, pero eu prometer que se continúa no vai ser moi, moi útil. Entón é iso por sección. Down to the wire. Eu fixen iso nun minuto. Pero alí vai. E eu vou ter Donuts ou doces. Ten alguén alerxias a nada, polo camiño? Ovos e leite. Entón, Donuts son un non? Está ben. Todo correcto. Sen chocolate? Starburst. Starbursts son boas. Está ben. Nós imos ter Starburst semana seguida. Iso é o que eu vou chegar. Vostedes teñen unha excelente semana. Ler o spec. Deixe-me saber se tes algunha preguntas. PSet dúas clases deben ser para ti ata xoves. Se ten algunha dúbida sobre como eu graduada algo ou por que eu graduada algo do xeito que eu fixo, por favor me escriba, veña falar comigo. Estou un pouco ese tolo semana, pero prometo Eu aínda vou responder no prazo de 24 horas. Entón, ten unha excelente semana a todos. Boa sorte na súa pset.