ALTAVOZ 1: Hola a todos! Bienvenido de nuevo a la sección. Así que me alegro de ver a muchos de ustedes, tanto aquí, y todo el mundo que está viendo en línea. Así que, como de costumbre atrás bienvenida. Espero que todos hayan tenido un precioso fin de semana, lleno de descanso, la relajación. Era hermoso el día de ayer. Así que, espero que hayan disfrutado del aire libre. 

Así que por primera vez un par de anuncios. Clasificación. Así, la mayoría de ustedes deben haber recibido una un correo electrónico de mí acerca de su juego de parámetros Scratch, así como la clasificación de juego de parámetros 1. Así, sólo un par de cosas. Asegúrese de utilizar check50 en style50. Estos están destinados a ser recursos para ustedes, para asegurarse de que usted está recibiendo tantos puntos como puedas sin innecesariamente perderlos. Por lo tanto, cosas como el estilo son muy importantes. Vamos a despegar para ello. Algunos de ustedes ya tienen notado que a partir de su juego de parámetros. Y check50 es sólo un manera muy fácil de asegurarse que en realidad estamos volviendo lo tiene que ser devuelto al usuario, y que todo está funcionando correctamente. 

En la segunda nota, asegúrese de que su subir cosas a la carpeta correcta. Se me hace la vida un poco más difícil si subes juego de parámetros 2 en juego de parámetros 1 porque al descargar cosas, no descarga correctamente. Y sé que es un poco wonky en un sistema que acostumbrarse a, pero simplemente ser súper cuidado, aunque sólo sea para mí, de modo que cuando usted está recibiendo mensajes de correo electrónico al igual que 02 a.m. y estoy de calificaciones. Si no causar tengo que mirar todo para su juego de parámetros. Enfriar. 

Sé que es temprano, pero me totalmente fue tomado con la guardia baja por un ensayo que es debido este viernes, que mis profesores eran como, oh sí. Recuerde, usted tiene un ensayo debido el viernes. Por lo tanto, no conozco a nadie le gusta pensar en los exámenes parciales, pero su primer concurso es el 15 de octubre, que octubre está comenzando esta semana. Por lo tanto, puede ser que sea más pronto de lo que esperaba es todo. Así que usted no está tirado con la guardia baja cuando Menciono sección de la próxima semana que oh, su concurso la próxima semana, pensé Te daría un poco más de las cabezas para arriba ahora. 

Así que, pon tu problema, número tres. ¿Cómo la gente ha leído la spec por curiosidad? Okay. Nos dieron un par. Tipo de abajo de la última semana, pero eso está bien. Sé que era hermoso a cabo. Así Break Out. Definitivamente después de que se hacen leer hoy su especificación por lo menos tratar como descargar código de distribución y el funcionamiento como la primera inicial Lo que te preguntan a. Debido a que estamos utilizando código de distribución y una biblioteca que sólo hemos estado using-- --Es sólo la segunda vez que hemos hecho este juego de parámetros, cosas locas pueden suceder con su aparato, y usted quiere encontrar que cabo ahora frente más tarde. 

Porque si es la noche del jueves o es Miércoles por la noche y por alguna razón su aparato simplemente no que desee ejecutar con la biblioteca o con la distribución código, que los medios ni siquiera se puede empezar a hacer la codificación. Porque no se puede comprobar para ver si funciona. Tu no vas a poder para ver si se compila. Usted quiere cuidar de los principios de la semana, cuando todavía me puede enviar por correo electrónico o uno de los otros TFS, y que podamos conseguir los fijados. Porque esas son cuestiones que van a dejar de usted de hacer ningún progreso real. No es como un bicho, que usted puede tipo de saltar sobre. Si usted está teniendo problemas con su aparato o código de distribución, usted realmente desea conseguir que toman cuidar de más temprano que tarde. Así que incluso si no vas a realidad empezar a programar, descargar la distribución código, lea la especificación, asegúrese todo lo que está trabajando allí. ¿De acuerdo? Si sólo se puede hacer eso, yo prometer su vida será más fácil. Y así, usted está probablemente va para hacerlo ahora mismo ¿no? Okay. Por lo tanto, cualquier pregunta allí? Cualquier cosas de logística? Todo el mundo es bueno? Okay. 

Exención de responsabilidad para los de que en la habitación y en línea. Yo voy a estar tratando de cambiar entre PowerPoint en el aparato porque vamos estar haciendo algo de código hoy por la demanda popular del anónimo encuesta sugerencia que envió la semana pasada. Por lo tanto, vamos a hacer algo de código. Así que, si ustedes también quieren para encender sus aparatos, y que debería haber conseguido un correo electrónico de mí, con un archivo de ejemplo. Por favor, siéntase libre de hacerlo. 

Por lo tanto, vamos a hablar de BGF, que es un depurador. Esto va a ayudar a usted tipo de averiguar dónde las cosas van mal en el código. Es sólo una manera para que den un paso a través de su código como está sucediendo, y ser capaz de imprimir las variables o ver lo que está sucediendo realmente bajo el capó versos su programa sólo correr, es como las fallas, y usted es como, ni idea lo que acaba de suceder aquí. No sé cuál es la línea que falló en. Yo no sé de dónde salió mal. Así, el BGF le va a ayudar con eso. Además, si usted decide continuar, sí, y tomar 61, lo que realmente, realmente ser su mejor amigo, porque yo puedo decir porque yo estoy pasando por esa clase. 

Vamos a mirar a binario búsqueda, que si ustedes recuerden el gran ejemplo de libro de teléfono espectáculo de clase. Estaremos implementando eso, y caminando a través de que un poco más, y luego vamos a través de cuatro diferentes tipos, que son de la burbuja, La selección, inserción, y Merge. Enfriar. Así, el BGF como he mencionado, es un depurador. Y estos son una especie de la gran cosas, las grandes funciones o comandos que se utiliza dentro de BGF, y voy a caminar que a través de una demostración de que en un segundo. 

Por lo tanto, esto no es sólo va a quedar abstracto. Voy a tratar de hacerlo lo más concreto como sea posible para ustedes. Por lo tanto, romper. Será ya sea descanso como, algún número, el cual representa una línea en su programa, o puede nombrar a una función. Así que, si usted dice romper principal, se detendrá en principal, y le permiten caminar a través de esa función. 

Del mismo modo, si usted tiene algunos externos funcionar como Intercambiar o Cubo, que vimos la semana pasada. Si usted dice que quebrante uno de estos, cada vez que el programa que realiza, que va a esperar para que usted pueda decirle lo que debe hacer. Antes de que se acaba de ejecutar lo que en realidad podría intervenir dentro de la función y ver lo que está pasando. Así, A continuación, simplemente salta sobre la siguiente línea, va más funciones. Paso. Todos estos son poco abstracto. Así que, yo sólo voy a correr a través de ellos, pero los verás en uso en un segundo. 

Entra en una función. Así como iba diciendo, como con Swap, lo haría le permiten realmente como si estuvieras como entrar físicamente en el interior, usted puede meterse con esas variables, impresión lo que son, ver lo que está pasando. Lista literalmente sólo imprimir el código circundante. Así que, si usted se olvida de tipo dónde usted está en su programa, o usted se está preguntando lo que está pasando a su alrededor, esto sólo se imprimirá un segmento de como cinco o seis líneas a su alrededor. Por lo tanto, usted puede conseguir orientado acerca de dónde se encuentre. 

Imprimir alguna variable. Por lo tanto, si usted tiene la llave como en César, que vamos a ver. Se puede decir Clave Imprimir en cualquier punto. Se te dirá lo que el valor es tan que, tal vez en algún lugar a lo largo del camino, ha sobrescrito su clave. En realidad se puede decir que debido a que en realidad se puede observar que el valor. 

En los locales, sólo impresiones cabo sus variables locales. Así, en cualquier momento que estás dentro de un bucle, y lo que desea es ver como, oh. ¿Qué es mi yo? ¿Qué es este valor de clave que inicializar aquí? ¿Cuál es el mensaje en este momento? Se acaba de imprimir todos de ellos, de modo que usted no tienen que individualmente decir, I. Imprimir Imprimir Mensaje. Clave de impresión. Y luego mostrar. Lo que hace es como usted paso a través del programa, que va sólo asegúrese de que es mostrar alguna variable determinada en cada punto. Así que usted También-- --es una especie de atajo donde usted no tiene que seguir así, oh. Clave Imprimir o I. Sólo automáticamente lo hará por usted. 

Así que, con eso, vamos para ver cómo va esto. Voy a tratar de interruptor a mi aparato. A ver si puedo hacer esto. Todos. Sólo vamos a reflejarla. No hay nada loco en mi computadora portátil de todos modos. Okay. Esto tiene que ser éste. Es tan pequeña. Vamos a ver si podemos hacer esto. 

Okay. Alice está obviamente luchando aquí sólo un poco, pero vamos a llegar en un recuerdo. Okay. Nosotros sólo vamos a aumentar este. Okay. ¿Todo mundo puede ver que tipo de? Tal vez un poco? Sé que es un poco pequeña. No se puede averiguar por cómo hacer esto más grande. Si alguien sabe. ¿Alguien sabe cómo hacer que sea más grande? Okay. Vamos a rodar con él. No importa de todos modos porque es sólo ese es el código que ustedes deberían tener. 

Lo que es más importante es el terminal de aquí. Y tenemos aquí ¿Por qué es tan pequeño? Ajustes. Oh. Verdadero Ike. ¿Cómo es esto? Fuera de allí. ¿Eso es mejor para todo el mundo? Okay ,. Enfriar. 

Ya sabes, cuando estás en un CS dificultades técnicas de clase son una especie de parte de el-- Por lo tanto, vamos a aclarar esto. Okay. Así que, aquí en la sección, que hemos tenido aquí. César es un archivo ejecutable. Así que lo hice. Así, una cosa es darse cuenta con GDB es que sólo funciona en archivos ejecutables. Por lo tanto, no se puede ejecutar en un dotsy. Usted tiene que hacer realidad Asegúrese de que su código se compila, y que lo que realmente se puede ejecutar. 

Por lo tanto, asegúrese de que si no lo hace compilar, que se compile, para que pueda especie de ejecutar a través de él. Así que, para empezar a GDB, todo lo que hacen, Gloria tipo BGF, y luego simplemente la archivo que desea. Yo siempre escribir mal César. Pero usted quiere asegurarse de que ya que es un archivo ejecutable, flash de punto de ti de manera que significa que vas para ejecutar CSI vas a ejecutar este presenta, ya sea con el depurador. Okay. Así que, de hacerlo, se obtiene este tipo de galimatías. Es sólo todas las cosas acerca de depurador. Usted realmente no tiene que preocuparse de eso ahora. Y como puedes ver, tenemos este parens abiertas, PIB, cerca parens, y sólo un poco se parece a nuestra línea de comandos, ¿verdad? 

Por lo tanto, lo que queremos hacer-- --así, La primera cosa es que queremos elegir un lugar para romperlo. Por lo tanto, hay un bug en este programa de César que presento, que vamos a averiguar. Es lo que hace es que se necesita la entrada Barfoo en todas las tapas, y por alguna razón no cambia A. Simplemente deja solo, es todo lo demás correcto, pero la segunda letra A permanece sin cambios. Por lo tanto, vamos a tratar de averiguar por qué es así. Por lo tanto, lo primero que suelen querer hacer cada vez que inicie el BGF es averiguar dónde romperlo. 

Así que César es un programa bastante corto. Sólo tenemos una función, ¿no? ¿Cuál era nuestra función en César? Sólo hay una función, derecho principal? Principal es una función para todos sus programas. Si usted no tuvo Principal, podría ser un poco preocupado en este momento, pero espero que todos hayan tenido Principal allí. Por lo tanto, lo que podemos hacer es que puede simplemente romper principal, así como así. Así que, se dice, en Aceptar. Fijamos nuestro único punto de interrupción allí. 

Así pues, ahora lo que hay que recordar que es del César toma un argumento de línea de comando de la derecha y nosotros no hemos hecho eso en cualquier lugar aún. Por lo tanto, lo que haces es cuando en realidad se va a ejecutar el programa, cualquier programa que usted está que se ejecuta en el BGF que necesita la línea de comandos argumentos, que van a la entrada cuando empiece a ejecutarlo. Así que, en este caso, lo hacemos Ejecutar con una llave de tres. Y será realmente empezar. 

Por lo tanto, si usted ve aquí, tenemos Si RC no es igual a 2. Así que si ustedes todos tenemos ese archivo que envié hasta verás que eso es como la primera línea de nuestra función principal, ¿no? Es la comprobación para ver si tenemos el número correcto de argumentos. Así que, si usted se está preguntando RC si es correcta, usted puede hacer algo al igual Imprimir RC. RC es de dos, que es lo que esperábamos, ¿verdad? 

Por lo tanto, podemos ir a continuación, y continuar a través de. Por lo tanto, tenemos alguna clave allí. Y podemos imprimir nuestra clave para asegurarse de que es correcto. Interesante. No es exactamente lo que esperábamos. Así, una cosa es darse cuenta con el BGF también, es que no es hasta que realmente golpea A continuación, que la línea que acaba de ver es en realidad ejecuta. Así que, en este caso clave no ha sido asignado todavía. Por lo tanto, es un valor clave de basura que se ve en la parte inferior hay. Negativo $ 120-- --Es de mil millones y algo que cosas extrañas ¿verdad? No es la llave que nos esperábamos. Pero si llegamos a continuación, y luego tratar de tecla Print, es tres. 

Todo el mundo ve eso? Así que, si te dan algo que usted es como, espera. Esto es completamente mal, y yo no lo sé cómo esto iba a pasar, porque todo lo que quiero que hacer es asignar un número, una variable, intentar golpear A continuación, intente imprimir de nuevo, y ver si funciona. Debido a que sólo se va a ejecutar y en realidad asignar algo después golpear en Siguiente. Tener sentido para todo el mundo? Uh huh? 

ALTAVOZ 2: Al azar números ¿qué significa eso? 

ALTAVOZ 1: Es sólo al azar. Es sólo basura. Es sólo algo que su computadora le asignará al azar. Enfriar. Así, ahora podemos pasar a través, y así ahora tenemos esta llanura GetString texto. Por lo tanto, permítanme presentarles lo que va a pasar cuando golpeamos Siguiente aquí. Nuestra BGF tipo de desaparece, ¿no? Esto se debe a GetString ahora está ejecutando, ¿verdad? Así que, cuando vimos texto plano es igual a GetString, parens abiertos y parens, y llegamos a continuación, que tiene realmente ejecutada ahora. Por lo tanto, está esperando nosotros a la entrada de algo. 

Por lo tanto, vamos a la entrada de nuestra comida que es lo que está fallando como te dije y que sólo dice que es terminado de ejecutarse, que la cierra significa soporte es salir de ese bucle. Así, podemos golpear Siguiente, y ahora, como estoy Seguro que todos conocemos de César, esto es, ¿cuál es esta línea va a hacer. Es para Int I es igual a 0, N es igual Strlen, texto plano, y luego I es menor que n, que, además, más. ¿Qué es este lazo va a hacer? Abra su mensaje. Enfriar. Por lo tanto, vamos a empezar a hacer eso. 

Así que, si esta condición coincidir, para nuestra primera? Si se trata de un B, que es texto plano I. puede obtener información acerca de nuestros locales. Por lo tanto, I es cero, y si seis, que esperamos, y nuestra clave es tres. Todo lo que tiene sentido, ¿verdad? Esos números son todos exactamente lo que deberían ser. Así, tararear? ALTAVOZ 3: Tengo números aleatorios para la mía. ALTAVOZ 1: Bueno, podemos check-- --nos puede charlar sobre eso en un segundo. Pero usted debe ser conseguir esto. Por lo tanto, si tenemos un capital de B para nuestra primera, esta condición debe cogerlo, ¿verdad? Así que, si llegamos a continuación, vemos que este caso en realidad ejecuta. Porque si usted está siguiendo a lo largo de su código, esta línea aquí, donde el texto sin formato que se sustituye con esta aritmética, sólo se ejecuta si el Si condición es correcta ¿verdad? 

BGF sólo se va a mostrar las cosas que son realmente de ejecución. Así que si no se cumple esta condición si, es sólo va a pasar a la siguiente línea. ¿De acuerdo? Por lo tanto, tenemos que. Este soporte significa que es cerrado fuera de ese bucle ahora. Por lo tanto, va a empezar de nuevo. Al igual que. Así, que podemos obtener información sobre nuestros lugareños aquí, y vemos que nuestra primera carta ha cambiado, ¿verdad? Ahora es una E, como debe ser. Así, podemos continuar. 

Y tenemos esta comprobación. Y este control debería funcionar, ¿no? Es A. Se debe cambiarse tres cartas hacia adelante. Pero si te fijas, nos conseguir algo diferente. Así que en este caso hasta aquí, me llamó que, por lo que esta línea ejecutado, que modificó nuestra B. Pero, en este caso aquí, tenemos que acaba de saltar que, y se fue a la [? L Siff. ?] Así que algo está pasando allí. Lo que usted está diciendo es que, sabemos que se debe coger aquí, pero no lo es. ¿Alguien puede ver lo que nuestro problema está en esa línea? Es una cosa muy minuto. Y también se puede mirar el código. También se line-- olvidar qué línea es en allí-- pero es en el [inaudible]. ¿Sí? 

ALTAVOZ 4: Está en la mayor de página si lo lee en el libro. ALTAVOZ 1: Exactamente. Por lo tanto, el depurador no podía decir que eso, pero el depurador podría conseguirle a una línea que sabe que no está funcionando. Y a veces, cuando todo más adelante en el semestre, cuando usted está tratando con un centenar, un cien pocas líneas de código, y que no sé donde está fallando, esta es una gran manera de hacerlo. Así, encontramos nuestro error. Usted puede fijarlo en su archivo, y entonces usted podría correr de nuevo, y todo funcionaría perfectamente. Y lo más importante es esto puede parecer, en Aceptar. Sí. Enfriar. Tú sabías lo que estás buscando. Por lo tanto, usted sabía qué hacer. 

GDB puede ser super útil porque usted puede imprimir todas estas cosas que usted no lo haría. Es mucho más útil que printf. ¿Cuántos de ustedes utiliza como declaraciones printf averiguar dónde era un error, ¿no? Así que, con esto, no lo hace tienen que seguir yendo, y les gusta comentar en Printf, o comentando, y averiguar lo que usted debe estar imprimiendo. En realidad, esto sólo le permite paso a paso, imprimir cosas como que estás pasando, así, usted puede observar cómo cambian en tiempo real, como su programa se está ejecutando. 

Y lo hace tomar un poco poco de tiempo para acostumbrarse. Yo recomendaría sólo tipo de ser un poco frustrado con él por ahora. Si usted pasa una hora sobre la la próxima semana para aprender a utilizar el BGF, usted se ahorrará tanto tiempo más adelante. Y literalmente. le decimos esto a la gente todos los años, y recuerdo cuando tomé la clase, yo estaba como, voy a estar bien. No. Juego de parámetros 6 se ha encendido y que era como, yo voy a aprender cómo utilizar GDB porque yo no lo hago saber lo que está pasando aquí. 

Así que si se toma el tiempo para usarlo en programas más pequeños que usted va a ser trabajando, como trabajar por algo así Visionäre, como este. O si quieres practicar más, estoy seguro Yo podría llegar a los programas con errores, para depurar si desea. 

Pero si usted acaba de tomar un poco de tiempo para llegar acostumbrarse a él, simplemente jugar un rato con él, lo que realmente le servirá bien. Y es realmente una de esas cosas que usted acaba de que tenga que probar, y ensuciarse las manos con, antes de que realmente lo entiende. Realmente sólo entendí una vez Tuve que depurar las cosas con ella, y es mucho más agradable para tener una idea de cómo depurar más temprano que tarde. Okay. Enfriar. Sé que es algo así como un curso intensivo en el BGF, y sin duda trabajar en conseguir éstos se vean más grandes para la próxima vez. Enfriar. 

Así que, si nos remontamos a nuestra PowerPoint. ¿Esto va a trabajar? Awh. Sí. Okay. Así que, si alguna vez necesitas cualquiera de los que una vez más, está la lista. Buscar Así binario, que todo el mundo recuerda el gran espectáculo de David rasga los libros de teléfono a la mitad. Yo realmente no entiendo la guías telefónicas más, porque al igual que ¿por dónde conseguir los libros de teléfono en estos días? Realmente no lo sé. La búsqueda binaria. ¿Alguien recuerda cómo binario trabajos de búsqueda? Cualquier persona en absoluto? ¿Sí? ALTAVOZ 5: ¿Sabes cuando nos fijamos en los cuales la mitad sería en, Sobre la base de que, y deshacerse de la otra mitad. 

ALTAVOZ 1 Exactamente. Así, búsqueda binaria, es una especie de A-- --nos gusta llamarlo dividir y conquistar. Por lo tanto, lo que harás es usted se verá en el medio, y verás si coincide lo que estás buscando. Y si no lo hace, a continuación, intenta averiguar, es que va a quedar la mitad o la mitad derecha. Por lo tanto, esto podría ser si usted está buscando en algo que está en orden alfabético, ves, oh. ¿Viene Allison antes de M? Sí. Por lo tanto, vamos a mirar a la primera mitad. 

O podría ser que con los números. Cualquier cosa que pueda comparar, puede ser ordenada. Puedes utilizar la búsqueda binaria sobre. Por lo tanto, alguien se acuerda de este gráfico o lo que es esto? Es la complejidad asintótica. Por lo tanto, este gráfico sólo describe el tiempo que te lleva a resolver un problema como se aumenta el número de las cosas que está utilizando. 

Por lo tanto, tenemos N, que es el tiempo lineal. Si N más de dos, que es ligeramente mejor, todavía crece muy rápido. Y entonces hemos Login, la cual es lo que consideramos búsqueda binaria. Si nos damos cuenta, como su problema consigue mucho y mucho más grande, el tiempo que le lleva a resolverlo en realidad no aumentar mucho. Es como comparables aquí en el principio. Eres como, OK. Cualquier cosa que aquí no hace realmente importa que uno que utilizamos, pero usted consigue a un millón, un billón. Usted está tratando de encontrar some-- --you're tratando de encontrar una aguja en un pajar. 

Creo que quieres este problema. Usted quiere que esta complejidad, no lineal, porque por todo lo que sé que tu vas a estar buscando a través de cada aguja individual, cosa de heno, tratando de buscar la aguja. Y eso no es demasiado divertido en mi opinión. Me gusta rápido. Me gusta eficiente. Y como esforzados estudiantes le chicos son, ya sabes trabajar más inteligentemente, no más difícil que el tipo, la forma en que puede compensar estos algoritmos. 

Por lo tanto, vamos a caminar sólo a través de un ejemplo rápido. Creo que ustedes deben tener una mano en la búsqueda binaria, pero en caso de que alguien es un poco borroso, quieren reforzarlo, vamos a ir a través de un ejemplo aquí. Por lo tanto, estamos buscando si la matriz contiene siete. 

Por lo tanto, lo primero que hacemos es buscar en el medio, ¿no? Y también va a ser la codificación Binary Buscar en tan sólo un segundo. Por lo tanto, va a ser divertido. Así que nos fijamos en la pequeñas matrices medias 3. ¿Tiene 3 equivalen a 7? No lo hace. Son las seis. Así que, ¿es menos de o superior a siete? Menos que. Sí. Trabajo chicos Niza. Siento que como que debería tener dulces porque querer tirarlo en los patios. Es lo que voy a hacer la próxima semana. Se le mantendrá chicos agudo. 

Así, nos tiramos de que primera mitad, ¿no? fue menor que. sabemos que todo en ese lado de la izquierda va a ser menos de lo que en realidad estamos buscando. Por lo tanto, no hay necesidad de prestar atención a ella. Simplemente olvidarse de él. Así pues, ahora nos fijamos en nuestro lado derecho, y nos fijamos en el medio de allí, y ahora es de nueve. Así, 9 es-- --Todos? Más de lo que somos buscando, ¿verdad? Por lo tanto, vamos a lanzar lejos de todo a la derecha. Al igual que. Ahora, todo lo que nos queda es una. Así, comprobamos, es éste lo que estamos buscando? es. Hemos encontrado lo que queríamos. Así que hemos terminado. Bilineal Buscar. 

Y si te fijas, nos tenía siete entradas allí. Sólo nos llevó como tres veces, pero si usted está haciendo como un mil millones, ustedes saben la cantidad de pasos que lo haría tomar si tuviéramos cuatro mil millones de cosas? Cualquier conjeturas? Es 32. 32 pasos para encontrar algo en una de cuatro mil millones elemento de la matriz debido a potencias de dos. Así que dos es a 32, es de cuatro mil millones. 

¿Cómo es eso una locura todavía estás dentro de como un número bastante reducido de pasos para encontrar algo en cuatro mil millones de elementos. Así que en ese sentido, estamos va a codificar este así que ustedes pueden en realidad tipo de ver cómo funciona esto. Muy bien, así que ustedes pueden codificar. Voy a dejar que ustedes hablar un poco. Conozca a la gente que te rodea, que es lo que alguien quería de última sección. 

Así que llegar a conocer a las personas que te rodean. Hable por un rato. Y todo lo que quiero de ti chicos en este momento es sólo tratar de crear un esquema de pseudocódigo. ¿De acuerdo? Whoa. Todo lo que quiero de ustedes es que eres sólo va a llenar en este caso, mientras que. Así que me he puesto estos superior y límites inferiores que representar el comienzo y al final de nuestra matriz. Y usted va a realidad recorrer y descubrir lo que estamos haciendo dentro de este bucle while. 

Así que si usted puede calcular fuera-- tengo una pizca allí-- ¿cuáles son los casos que tenemos aquí? Así que si quieres averiguar la casos, vamos a los Pseudocódigo y luego vamos a realmente codificarlos. Y va a ser, pensar, es de esperar que va a ser un poco más fácil de lo esperado. Porque no es que mucho código, en realidad, lo que es realmente genial. 

Mm-hm? 

ESTUDIANTE: [inaudible]? INSTRUCTOR: Sí. Había algo para encontrar en el medio. 

ESTUDIANTE: Así que podemos usar eso. Okay. 

INSTRUCTOR: Perfecto. Así que eso es lo primero que tenemos que hacer. Así que encontrar el medio. Gran. Así que tienes una idea de cómo podríamos en realidad encontrar el centro con código? 

ESTUDIANTE: Sí. n más de 2? PROFESOR: Entonces n sobre 2. Así que una cosa a recordar es que sus límites superior e inferior cambian. Seguimos la constricción de la parte de la matriz que estamos buscando para. Así que n más de 2 sólo funcionará para la primera cosa que hacemos. Así que teniendo superiores e inferiores en cuenta, ¿cómo podemos conseguir que el elemento medio? Porque queremos que el medio entre superior e inferior, a la derecha? Mm-hm? 

ESTUDIANTE: [inaudible]. 

INSTRUCTOR: Así que tenemos algún medio. Y que va a ser superior, más bajo en 2. Impresionante. Hay que ir. Una línea hacia abajo. Ustedes están en su camino. Así que ahora que tenemos nuestro medio, ¿qué es lo que queremos hacer? Justo en general. Usted no tiene que codificarlo. Sí. ESTUDIANTE: [inaudible]? INSTRUCTOR: Así que es más porque eres encontrar la media entre los dos de ellos. Así que si usted piensa en ellos como especie de aumentar desde los lados, pensar en ello cuando se aproxima el medio, que desea así. Así que si usted fuera a cada lado de la medio, y tenemos como 5 y 7. Cuando se agregan juntos obtener 12, se divide por 2, es de 6. 

A veces es difícil explicar por qué funciona, pero si usted trabaja a través de un ejemplo a veces, que va a ayudar a determinar si debería ser más o menos. Sí. 

ESTUDIANTE: [inaudible] exactamente en el centro si tenían un caso en el que hay una gran cantidad de números más pequeños y al igual que un número grande? 

INSTRUCTOR: Así que todo lo que necesita es el centro de la matriz. Así que si usted tenía un montón de números pequeños y entonces uno realmente gran número al final, no importa. Todo lo que importa es que que están ordenados, sólo que desee ver en el centro de la matriz porque eres todavía cortando su problema a la mitad. Enfriar. Así que ahora que tenemos la medio, ¿qué hacemos después? 

ESTUDIANTE: Comparar. INSTRUCTOR: El comparar. Así que comparar a medio value_wanted. Enfriar. Así que ya ves aquí arriba tenemos este valor que queremos aquí. Recuerde que este es un array. Así medio se refiere al índice. Así que queremos hacer valores de media. No te olvides que si quieres para comparar, dobles iguales. Usted lo único es igual que estés sólo va a reasignar, y luego, por supuesto, es va a ser el valor que desee. Así que no hagas eso. 

Así que vamos a ver si los valores en el medio es igual al valor que queremos. No olvide sus llaves. Dropbox debe desaparecer. Así que, ¿qué hacemos en este caso? Si se trata de lo que queremos para volver? Estamos tratando de decir. 

ESTUDIANTE: Imprima. 

INSTRUCTOR: Bueno, no quieren imprimir. Así que este es un bool aquí, así que quieren volver verdadero o falso. Estamos diciendo, es este número un [? RRA? ?] Así que si lo es, simplemente devolvemos verdad. Si puedo deletrear cierto. 

ESTUDIANTE: ¿Por qué no le volverá a cero? INSTRUCTOR: por lo que podría volver a cero si querías. Pero en este caso porque nuestra función devuelve un bool, tenemos que volver, ya sea verdadera o falsa. ESTUDIANTE: Cuando estás diciendo expresión booleana, puedes configurarlo igual a falsa? Al igual que si quiero decir, si esta condición no se cumple, al igual que es superior es igual a falsa. ¿Va a entender si sólo poner falsa en el otro lado? INSTRUCTOR: Sí. Así que en realidad si estás siempre haciendo algo como es superior o es menor, que devuelve verdadero o falso y en realidad es un mal estilo de por ejemplo igual a igual a verdadero o iguales es igual a falsa. Usted desea utilizar ese resultado como a sí mismo como su cheque. No era lo que yo quería. Eso es lo que yo quería. Así que en el caso de que usted está pidiendo acerca de algo así como guardar esto en c. 

Así que si tenemos int main (void) y algo como esto. Y usted tiene si es superior de alguna entrada y ya está preguntando si se puede hacer algo como esto? Derecha? ESTUDIANTE: Yo estaba tratando para hacerlo [inaudible]. Porque si es-- INSTRUCTOR: Derecho. ¿Así que quieres que esto es falso, ¿no? ESTUDIANTE: Sí. INSTRUCTOR: Así que en este caso quiere que se ejecuta si no es verdad. Así que la cosa fresca que haces no es esto. Así que recuerde de exclamación punto niega cosas? Dice [inaudible] no significa. Así que si nos fijamos en sólo esta parte aquí, estarías dicen que evalúa a falso como usted desea. No es falso es cierto que significa esto sería ejecutar. ¿Eso tiene sentido? ESTUDIANTE: Sí. INSTRUCTOR: Awesome. Okay. Así que pudiéramos volver cierto en este caso. Así que ahora tenemos otros dos casos en este caso. ¿Cuáles son los otros dos casos? Vamos a hacerlo de esta manera. Así que vamos a empezar con otra cosa si los valores de la media es menor que el valor que queremos. Así que nuestro valor en el medio es menos que el valor que estamos buscando. 

Así que unido hacer pensamos que queremos poner al día? Alto o bajo? Alta? Así qué lado de la matriz vamos a estar mirando? 

ESTUDIANTE: La más baja. 

INSTRUCTOR: Nos vamos a estar mirando a la izquierda. Así lo demás si poco valor es menor. Por lo que su valor medio aquí es menos de lo que queremos. Por eso queremos tomar la lado derecho de nuestra matriz. Así que vamos a actualizar nuestra cota inferior. Así que vamos a reasignar nuestro inferior. ¿Y qué cree usted que debería ser más baja? ESTUDIANTE: El valor medio? INSTRUCTOR: Así que la value-- medio ESTUDIANTE: Plus 1. INSTRUCTOR: --plus 1. ¿Puede alguien decirme por qué tenemos que, más 1? 

ESTUDIANTE: [? Ningún valor?] es más igual a ella. 

INSTRUCTOR: Derecho. Porque ya sabemos que nuestro valor medio no es igual a y queremos excluirla de todas las búsquedas posteriores. Si se le olvida que más 1, este le gustaría bucle indefinidamente. Y sólo le atrapados en un bucle infinito y luego podrás segfault y las cosas van mal. Así que asegúrese siempre de que usted no está incluyendo el valor que acaba de mirado. Así que nosotros nos encargamos de que con un más 1. 

Así que ahora tenemos nuestra última condición Siempre que por razones de seguridad usted puede comprobar aquí, de lo contrario si el valor en el medio es mayor que el valor queremos. Eso significa que queremos la mitad de la mano izquierda. Así que uno vamos a actualizar? Superior. ¿Y cuál es éste va a ser igual? Medio menos 1, ya que, por supuesto, queremos para asegurarse de que no estamos mirando a ese valor medio nuevo. Y entonces lo tenemos. Eso es todo. Eso es todo de búsqueda binaria es. No es tan malo, ¿verdad? Es como 10 líneas de código con el espacio en blanco. Así que es muy potente, muy útil, se quiere a utilizar en uno de sus conjuntos de procesadores posteriores. Tal vez no éste, pero más tarde. Así que aprenderlo. Quiéralo. Se tratará bien. Así que ¿alguien tiene alguna preguntas sobre la búsqueda binaria? Sí. 

ESTUDIANTE: ¿Importa si el n es par o impar? 

INSTRUCTOR: No. Porque nos echamos a la media como un int, se acaba de truncar la misma. Por lo tanto, se mantendrá un número entero y lo hará eventualmente ordenar a través de todo. Así que usted no tiene que preocuparse por eso. Todo el mundo bien? Impresionante. Enfriar. Así que, ustedes me encargo. Presentación de diapositivas. Así como que estábamos hablando, lo sé David mencionó tiempos de ejecución de complejidad. 

Así que en el mejor de los casos, es sólo uno, que llamamos constante de tiempo. ¿Puede alguien decirme por qué podría ser? ¿Qué tipo de escenario habría que implicar? Mm-hm. 

ESTUDIANTE: [inaudible] primero-- INSTRUCTOR: Así que el medio es el primer elemento que llegamos a, ¿verdad? Así que, o una matriz de uno o lo que estamos buscando sólo pasa a ser justo en el medio. Así que esa es nuestra mejor de los casos. Te metes en problemas reales, probablemente no va a llegar a [inaudible] que a menudo. ¿Qué pasa con nuestra peor de los casos? Nuestro peor de los casos es log n. Y eso tiene que ver con el todo potencias de dos cosa que hablé. 

Así que en el peor de los casos que significaría que teníamos que cortar la matriz hacia abajo hasta que había un elemento de uno. Así que tuvimos que cortar hacia abajo en la mitad tantas veces como nos sea posible. Es por eso que es log n porque que acaba de seguir dividiendo por dos. Así suposiciones, cosas que vosotros necesita saber si alguna vez va a utilizar una búsqueda binaria. Sus elementos deben ser ordenados. Tienen que ser resuelto porque esa es la única manera en que puede saber si usted es capaz de que tirar la mitad de ella. 

Si tuvieras esta bolsa confusa de los números y que estás diciendo, Bien, voy a revisar el medio número y el número que estoy buscando es menos que eso, yo sólo voy tirar arbitrariamente la mitad. Usted no sabe si su números en ese otro medio. Su lista tiene que ser resuelto. Además, esto puede ser seguir adelante un poco, pero es necesario tener acceso aleatorio. ¡Tienes que ser capaz de simplemente ir a ese elemento medio. Si usted tiene que atravesar a través de algo o le toma medidas adicionales para llegar a ese elemento medio, no es log n más porque va a añadir más trabajo en él. Y esto hará un poco más sentido en dos semanas, pero yo como que quería escribir el prólogo, ustedes dar una idea de lo que es por venir. Pero esos son los dos supuestos importantes que usted necesita para obtener una lista binario. Asegúrese de que está ordenada. Esa es la gran uno para ustedes ahora mismo. Y en que podemos entrar en el resto de nuestras clases. Así que cuatro burbuja sorts--, inserción, selección y combinación. Son todos una especie de fresco. Si ustedes deciden tomar CS 124, usted aprenderá acerca de todo tipo de géneros. Y si eres un fan de XKCD, hay es un cómico genial sobre como tipo realmente ineficaces, que me altamente recomendable ir a mirar. Uno de ellos es como una especie de pánico, que es como, ¡oh no, volver disposición aleatoria. Sistema apagado. Deja. Así humor geek es siempre bueno. 

Así que ¿alguien recuerda tipo de como simplemente una idea general de cómo funciona la burbuja especie. ¿Te acuerdas? 

ESTUDIANTE: Sí. 

INSTRUCTOR: A por ello. 

ESTUDIANTE: ¿Así que estás pasando y si es más grande, entonces usted intercambia los dos. 

INSTRUCTOR: Mm-hm. Exactamente. Así que sólo iterar a través. Usted comprueba dos números. Si el anterior es más grande que el que después, usted acaba de intercambiar de manera que en de esta manera todos los números más altos la burbuja hacia el final de la lista y todos los números más bajos de la burbuja abajo. 

¿Él te muestre chicos el fresco efecto de sonido de clasificación de video? Es una especie de fresco. Así como sólo dijo Robert, el algoritmo que acaba de paso a través de la lista, el intercambio de los valores adyacentes si no están en orden. Y a continuación, sólo seguir repitiendo hasta que no se realicen canjes. Así que no está mal, ¿verdad? Así que sólo tenemos un ejemplo rápido aquí. Así que esto va a clasificar en orden ascendente. Así que cuando vamos a través de la primera tiempo, vemos a través de ocho y seis, obviamente, no son en fin, les cambiamos. 

Así que busque en la siguiente. Ocho y no cuatro en orden. Intercambiarlas. Y después de ocho y dos, ellos swap. Hay que ir. Así que después de su primera pasada, puede saber que su número más grande va a ser todo el camino en la parte superior, ya que es sólo va a estar constantemente más grande que todo lo demás y que sólo va a la burbuja todo el camino hasta el final allí. ¿Eso tiene sentido para todo el mundo? Enfriar. 

Entonces nos fijamos en nuestro segundo pase. Seis y cuatro, interruptor. Seis y dos, interruptor. Y ahora que tenemos algunas cosas en orden. Así, por cada paso que nos hacer a través de toda nuestra lista, sabemos que al igual que muchos números al final le han sido ordenados. Así que hacemos un tercer pase, que es uno de intercambio. Y luego en el cuarto pasar, tenemos cero ranuras. Y por lo que sabemos que nuestro matriz se ha clasificado. 

Y ese es el gran cosa con la burbuja de clase. Sabemos que cuando nos tener cero swaps, que significa que todo está en completo orden. Es una especie de cómo comprobamos. Así que también vamos a codificar burbuja qué tipo tampoco es tan malo. Ninguno de estos son tan malos. Sé que puede parecer un poco de miedo. Sé que cuando tomé la clase, incluso cuando yo fue la enseñanza de la clase de la primera vez el año pasado, Yo estaba como, ¿cómo puedo hacer esto? Tiene sentido en teoría, pero ¿cómo podemos realmente hacer esto? Es por eso que también quiero caminar a través de código con ustedes aquí. Así que tengo un pseudocódigo para ustedes en esta ocasión. Así que tener esto en mente a medida estamos a punto de hacer la transición más. Así que tenemos un poco de contador que realiza un seguimiento de nuestros swaps, porque tenemos que asegurarnos de que estamos comprobando que. Y iteramos toda la matriz como acabamos de hacer con este ejemplo. Si el elemento es más grande que antes el elemento después de donde estamos, nosotros los swap y incrementamos nuestra contador porque tan pronto como nos intercambiamos, queremos que nuestro contador sabe. Cualquier pregunta allí? Algo parece divertido por aquí. ESTUDIANTE: ¿Se ajusta el contador a cero cada vez que vaya a través del bucle? ¿No sigues adelante de vuelta a cero cada vez? INSTRUCTOR: No necesariamente. Así que lo que pasa es que vamos por aquí. Así que mientras que, recuerde, esto se ejecutará una vez sin falta. Así que va a establecer el contador igual a cero, a continuación, se va a recorrer. A medida que itera a través de, se actualizará mostrador. Como se actualiza mostrador, cuando se hace, cuando se alcanza el final de la matriz, si nuestra lista no ha sido ordenado, contador se habrá actualizado. 

Así entonces se comprueba la condición y dice, está bien, es contador mayor que cero. Si lo es, hacerlo de nuevo. Usted desea restablecer de modo que cuando usted ir a través de, el contador es igual a cero. Si usted va a través de una ordenada matriz, nada cambia, esto no funciona, y usted devolver la lista ordenada. ¿Eso tiene sentido? ESTUDIANTE: Se podría en un poco. INSTRUCTOR: OK. Si hay cualquier otro pregunta que surge. Sí. 

ESTUDIANTE: ¿Cuál sería la función será para el canje de los elementos? 

INSTRUCTOR: Así que en realidad podemos escribir que si vamos a la derecha ahora. Enfriar. Así que en esa nota, Alison va para cambiar de nuevo al aparato. Va a ser divertido. Y tenemos nuestro agradable burbuja especie cosa aquí. Así que ya lo hice en bicicleta a través de la matriz. Tenemos nuestros swaps que son iguales a cero. Así que queremos intercambiar adyacente elementos si están fuera de orden. Así que lo primero que tenemos que hacer es iterar a través de nuestra gama. 

Entonces, ¿cómo cree usted que podríamos iterar a través de nuestra gama? Tenemos para y i es igual a 0. Queremos i a ser menos de n menos 1 menos k. Y voy a explicar que en un segundo. Así que esta es una optimización aquí donde, recordar cómo he dicho después de cada pase a través de la que array saber que todo lo que es en-- 

Así que después de una pasada nos sé que esto está solucionado. Después de dos pases sabemos que todo esto está ordenada. Después de tres pases nos Sé que es ordenados. Así que la forma en que estoy iteración a través de la matriz aquí, se está asegurando de que ir solo a través de lo que sabemos que es clasificar. ¿De acuerdo? Eso es sólo una optimización. Se puede escribir que ingenuamente sólo iteración a través de todo, sería justo tomar más tiempo. Con este bucle es de cuatro sólo una buena optimización porque sabemos que después de cada pleno iteración a través de la matriz aquí, como cada bucle completo aquí, sabemos que uno más de estos elementos se ordenarán al final. 

Así que no tenemos que preocuparnos por aquellos. ¿Eso tiene sentido para todo el mundo? Ese pequeño truco genial? Así que en ese caso, si estamos iteración a través de, sabemos que queremos comprobar si matriz n y n + 1 están en orden. Okay. Así que aquí está el pseudocódigo. Queremos comprobar si matriz n y n + 1 están en orden. Entonces, ¿qué podríamos tener allí? Va a ser un poco de condicional. Será un si. 

ESTUDIANTE: Si matriz n es menos de matriz de n más 1. INSTRUCTOR: Mm-hm. Bueno, menor que o mayor que. ESTUDIANTE: Mayor que. Entonces queremos para intercambiarlas. Exactamente. Así que ahora nos metemos en lo que es la mecanismo para el intercambio de ellos? Así que nos fuimos a través de este breve, un tipo de función de intercambio de la semana pasada. ¿Alguien recuerda cómo funcionaba? Así que no podemos simplemente reasignar ellos, ¿verdad? Debido a que uno de ellos se pierda. Si hemos dicho que A es igual a B y B a continuación, es igual a A, todo repente ambos son sólo igual a B. 

Así que lo que tenemos que hacer es que tener una variable temporal que es va a celebrar uno de los nuestros, mientras que estamos en el proceso de intercambio. Así que lo que tenemos es que tendremos un poco de int temperatura es igual a-- puede asignarlo a lo que usted desea, apenas Asegúrese de mantener un registro de it-- por lo que en este caso, voy a asignarla a la matriz n + 1. Así que va a celebrar lo que sea valor está en ese segundo bloque que estamos viendo. 

Y entonces lo que podemos hacer es que podemos ir adelante y variedad Reasignar n + 1, porque sabemos que que tienen valor almacenado. Este es también uno de los grandes cosas-- No sé si alguno de ustedes tenido problemas donde si interruptor de dos líneas de código de repente las cosas funcionaron. El orden es muy importante en CS. Así que asegúrese de diagramar las cosas, si es posible en cuanto a lo que está sucediendo realmente. Así que ahora vamos a reasignar matriz n + 1, porque sabemos que que tienen valor almacenado. 

Y podemos asignar que a la matriz n o en este caso array i. Demasiadas variables. Okay. Array Así que ahora que hemos reasignado i más 1 para igualar lo que está en serie i. Y ahora podemos volver atrás y asignar serie i para qué? Cualquier persona? 

ESTUDIANTE: 10. 

INSTRUCTOR: 10. Exactamente. Y una última cosa. Si hemos cambiado ahora, ¿qué es lo que tenemos que hacer? ¿Qué es lo único eso va a decirnos si alguna vez terminar este programa? Lo que nos dice que tenemos tener una lista ordenada? Si no realizamos ningún swaps, ¿verdad? Si swaps es igual a cero al final de este. Así que cada vez que se realiza un intercambio, ya que acaba de hacer aquí, queremos actualizar los swaps. Y yo sabía que había un pregunta anterior sobre ¿verdad utilizar cero o uno en su lugar de verdadero o falso. Y eso es lo que hace esto aquí. Así que esto dice que si no los swaps. Así que si los swaps es cero, lo que es-- Siempre conseguir mis verdades y mis falses mezclados. Queremos que evaluemos true y no lo es. Así que si es cero, entonces es falso. Si niegas con un [? Bang?] se convierte en verdadera. Así que esta línea se ejecuta. 

Verdades y falsa y ceros y unos consiguen loco. Sólo si usted camina lentamente a través de ella tendrá sentido. Pero eso es lo que este pequeño poco de código aquí hace. Así que esto comprueba hemos hecho ningún swaps. Así que si es algo además de cero, que va a ser falso y toda la cosa es va a ejecutar de nuevo. Fresco? 

ESTUDIANTE: ¿Qué hace el descanso? 

INSTRUCTOR: Romper sólo que rompe fuera del circuito. Así que en este caso sería al igual que terminar el programa y lo haría sólo tener su lista ordenada. ESTUDIANTE: Amazing. INSTRUCTOR: Lo siento? ESTUDIANTE: Debido a que anteriormente utilizado escrito 1 sobre escrito cero para presentar que si que va a funcionar o no. 

INSTRUCTOR: Sí. Así que usted puede devolver cero o 1. En este caso, porque no estamos en realidad hacer cualquier cosa con la función, sólo queremos que se rompa. En realidad no se preocupan por él. Freno también es bueno si se utiliza para romper de cuatro bucles o condiciones que usted no desea mantener la ejecución. Simplemente te lleva fuera de ellos. Es un poco de una cosa matiz. Me siento como si hubiera una gran cantidad de mano que agita, como usted aprenderá acerca de esto pronto. 

Pero usted aprenderá acerca de esto pronto. Prometo. Okay. Así que no todo el mundo consigue burbuja especie? No está mal. Recorrer, cosas swaps utilizando un variable TEMP, y todos estamos establece allí? Enfriar. Impresionante. Okay. Volver al principio PowerPoint. Cualquier pregunta en general sobre éstos hasta el momento? Enfriar. Mm-hm. 

ESTUDIANTE: [inaudible] int main normalmente. No tienes que tener que para esto? 

INSTRUCTOR: Así que estábamos buscando justo en el algoritmo de ordenación real. Si tuvieras que dentro como un programa más amplio, usted tendría un algún lugar principal int. Dependiendo de donde usted utilizar este algoritmo, sería determinar cuál es siendo devuelto por él. Sin embargo, para nuestro caso, estamos estrictamente mirando cómo funciona esto en realidad recorrer una matriz. Así que no te preocupes por eso. 

Así que estábamos hablando mejor de los casos y peor de los casos para la búsqueda binaria. Así también es importante hacer que para cada una de nuestras clases. Entonces, ¿qué cree usted que es el peor de los casos caso el tiempo de ejecución de la burbuja especie? Ustedes recuerdan? 

ESTUDIANTE: N menos 1. INSTRUCTOR: N menos 1. Así que eso significa que hay n menos 1 comparaciones. Así que una cosa es darse cuenta de que en la primera iteración, vamos a través, comparamos estos dos-- así que eso es 1. Estos dos, tres, cuatro. Así que después de una iteración que ya tiene cuatro comparaciones. Cuando estoy hablando de tiempo de ejecución y n. N representa el número de comparaciones como una función de cuántos elementos tenemos. ¿De acuerdo? 

Así que vamos a través, tenemos cuatro. La próxima vez que usted sabe no lo hacemos tiene que hacerse cargo de esto. Comparamos estos dos, estos dos, estos dos, y si no tuviéramos que la optimización con los cuatro bucle que escribí, usted estaría comparando aquí de todos modos. Así que tendría que ejecutar a través de la matriz y hacer comparaciones n n veces, porque cada vez que correr a través de él clasificamos una cosa. 

Y cada vez que nos encontramos a través de la matriz, hacemos n comparaciones. Así que nuestro tiempo de ejecución de esto es en realidad n cuadrado, que es mucho peor en nuestra ingrese final porque eso significa que si teníamos cuatro miles de millones de elementos, es nos va a llevar cuatro mil millones cuadrado en lugar de 32. Así que no es el mejor tiempo de ejecución, pero para algunas cosas, ya sabes, si estás dentro de de un cierto rango de elementos burbuja especie puede estar bien para su uso. 

Okay. Así que ahora lo que es el mejor tiempo de ejecución de caso? ESTUDIANTE: Cero? O 1? 

INSTRUCTOR: 1 Así que lo haría ser una comparación. Derecha. 

ESTUDIANTE: N menos 1? 

INSTRUCTOR: Así que, sí. Así n menos 1. Siempre que tenga un concepto como n menos 1, tendemos a simplemente dejarlo y acabamos de decir n porque tienes comparar cada uno de these-- cada par. Así que sería n menos 1, que nos que acabábamos de decir es aproximadamente n. Cuando usted está tratando con el tiempo de ejecución, todo está en aproximados. Mientras el exponente es correcta, eres bastante bueno. 

Así es como nos ocupamos de ello. Así que el mejor de los casos es n, el cual significa que la lista ya está ordenado, y todo lo que hacemos es ejecutar a través de y compruebe que está ordenada. Enfriar. Bien. Así que como ves aquí, sólo hay algunas más gráficos. Así que n al cuadrado. Diversión. Mucho peor que n como vemos, y mucho, mucho peor que 2n registro. Y entonces usted también consigue en registro registros. Y usted toma 124, te metes en como estrella de registro, que es como una locura. Así que si usted está interesado, estrella de registro de búsqueda. Es un poco de diversión. Así que tenemos este gran cuadro. Sólo una cabeza, este un maravillosa carta tenga para su medio plazo, ya que tiempo para pedirle que estos se adelgaza. Así que sólo un cabezas, tienen esto en su a medio plazo en su hoja de trucos agradable Ya está. Así que acabamos de ver burbujas especie. Peor de los casos, n al cuadrado, mejor de los casos, n. Y vamos a mirar a los demás. 

Y como se puede ver, la única uno que realmente le va bien es una especie de combinación, que vamos a entrar en por qué. Así que vamos a ir a la siguiente aquí-- selección especie. ¿Alguien recuerda cómo selección trabajó especie? No te lo pienses. 

ESTUDIANTE: Básicamente pasar por un orden y crear una nueva lista. Y así como usted está poniendo elementos en, los puso en el lugar correcto en la nueva lista. 

INSTRUCTOR: ¿Así que los sonidos más como la ordenación por inserción. Pero estás muy cerca. Son muy similares. Incluso llego ellos confunden a veces. Antes de esta sección yo estaba como, espere. Okay. Así que lo que usted desea hacer es una especie de selección, la forma en que se pueda imaginar al respecto y la forma Me aseguro de no tratar de conseguir se confundan, es que pasa por y selecciona el menor número y pone que al principio de su lista. Se intercambia con ese primer lugar. De hecho, tienen un ejemplo para mí. Impresionante. Así que una manera de pensar en la selección it-- Ordena, seleccione el valor más pequeño. Y vamos a ejecutar a través de un ejemplo que creo que va a ayudar porque Creo visuales siempre ayudan. Así que empezamos con algo que es completamente sin clasificar. Rojo será sin clasificar, verde, serán ordenados. Todo tendrá sentido en un segundo. 

Así que vamos a través y iteramos desde el principio hasta el final. Y decimos, OK, 2 es nuestro número más pequeño. Así que vamos a tener 2 y vamos para moverlo a la parte delantera de nuestra gama porque es la número más pequeño que tenemos. Así que eso es lo que esto está haciendo aquí. Es sólo va a cambiar los dos. Así que ahora tenemos un clasificado parte y una parte sin clasificar. Y lo que es bueno recordar sobre la selección de especie es que sólo estamos seleccionando de la parte sin clasificar. 

La parte ordenada que acaba de dejar solos. Mm-hm? 

ESTUDIANTE: ¿Cómo sabe lo que es el más pequeño sin compararlo a cualquier otro valor en el array. INSTRUCTOR: Lo hace compararlo. Nos gusta lo saltamos. Esto es sólo en general en general. Sí. Cuando escribimos el código que estoy Seguro que estará más satisfecho. Pero usted guarda el primer elemento como el más pequeño. Se trata de comparar y usted decir, OK, ¿es más pequeño? Sí. Keep it. Aquí es más pequeño? ¿No? 

Este es su más pequeño, reasignar a su valor. Y serás mucho más feliz cuando vamos a través del código. Así que vamos a través, nos cambiamos, así que a continuación nos fijamos en esta porción sin clasificar. Así que vamos a seleccionar tres. Vamos a ponerlo en en Al final de nuestra parte ordenada. Y sólo vamos a seguir haciendo que, haciendo eso, y haciendo eso. Así que este es nuestro tipo de pseudocódigo aquí. Vamos a codificarlo hasta aquí en un segundo. Pero sólo algo para caminar a través de un alto nivel. Te vas a ir de i es igual a 0 a n menos 2. Esa es otra de optimización. No se preocupe demasiado acerca de él. Así como usted decía. Como Jacob estaba diciendo, ¿cómo podemos llevar un registro de lo que nuestro mínimo es? ¿Cómo lo sabemos? Tenemos que comparar todo en nuestra lista. 

Así mínimo es igual a i. Es simplemente diciendo en este caso el índice de nuestro valor mínimo. Así que se va a recorrer y va desde j es igual a i + 1. Así que ya sabemos que ese es nuestro primer elemento. No necesitamos para compararla con la propia. Así que empezar a comparar a la siguiente uno que es por eso que es i + 1 a n menos 1, que es el final de la matriz allí. Y nosotros dijimos si matriz en j es de menos de matriz min, entonces reasignar donde nuestros índices mínimos es. 

Y si min no es igual a i, como se en donde estábamos de vuelta por aquí. Así como cuando lo hicimos por primera vez este uno. En este caso, sería empezar a cero, sería llegar a ser dos. Así min no lo haría igual i en el final. Que nos permite saber que que necesitamos para intercambiarlas. Me siento como un ejemplo concreto ayudará mucho más que esto. Así que voy a codificar esta con ustedes en este momento y creo que va a ser mejor. 

Ordena tienden a trabajar de esa manera en que a menudo es mejor sólo para verlos. Así que lo que queremos hacer es lo primero que queremos la más pequeña elemento en su posición en el array. Exactamente lo que Jacob estaba diciendo. Necesita almacenar que de algún modo. Así que vamos a comenzar aquí iteración en la matriz. Vamos a decir que es nuestro primero sólo para empezar. Así que vamos a tener int más pequeño es igual a la matriz en i. 

Así que una cosa a notar, cada vez este bucle se ejecuta, estamos empezando un paso más allá a lo largo. Cuando empezamos nos fijamos en éste. La próxima vez que recorrer, estamos empezando a éste y asignándole nuestro valor más pequeño. Así que es muy similar a la burbuja de tipo donde sabemos que después de una sola pasada, este último elemento está ordenada. Con la selección de especie, que es todo lo contrario. 

En cada pase, sabemos que la primera de ellas está ordenada. Después de la segunda pasada, el segundo, serán ordenados. Y como se vio con los ejemplos de diapositivas, nuestra porción ordenados sigue creciendo. Así que mediante el establecimiento de nuestro uno más pequeño a matrices i, todo lo que está haciendo se constricción de lo que estamos viendo con el fin de para minimizar el número de las comparaciones que hacemos. ¿Eso tiene sentido para todo el mundo? ¿Me necesita para funcionar a través de ese otra vez más lento o con otras palabras? Estoy feliz. Okay. 

Así que estamos almacenando el valor en este punto, pero también queremos almacenar el índice. Así que vamos a almacenar el la posición de los más pequeños uno, que es sólo va a ser i. Así que ahora Jacob está satisfecho. Tenemos cosas almacenadas. Y ahora tenemos que mirar a través de la parte no seleccionada de la matriz. Así que en este caso esta sería nuestro sin clasificar. Esto es i. Okay. 

Así que lo que vamos a hacer va a ser de un bucle. Siempre que necesite iterar a través de una matriz, su mente podía ir a por un bucle. Así que para algunos int k equals-- ¿qué pensamos k va a ser igual para empezar? Esto es lo que nos propusimos como nuestro más pequeño valor y queremos compararlo. ¿Qué es lo que queremos compararlo? Va a ser el próximo uno, ¿verdad? Por lo que queremos k para ser inicializado a i + 1 para comenzar. 

Y queremos k en este caso ya han almacenado tamaño hasta aquí, por lo que sólo podemos usar tamaño. Tamaño ser el tamaño de la matriz. Y sólo queremos actualizar k en uno cada vez. Enfriar. Así que ahora tenemos que encontrar el elemento más pequeño aquí. Así que si nos recorrer, nos quiero decir, si en la matriz k es menor que nuestro value-- más pequeño aquí es donde estamos en realidad hacer el seguimiento de lo que es el más pequeño aquí-- entonces queremos reasignar cuál es nuestro valor más pequeño es. 

Esto significa que, oh, estamos iteración a través de aquí. Cualquiera que sea el valor es aquí es no la cosa más pequeña. Nosotros no queremos. Queremos volver a asignar la misma. Así que si estamos reasignando, qué hacer usted piensa que podría estar en el código aquí? Queremos volver a asignar más pequeño y la posición. Entonces, ¿qué es más pequeña ahora? ESTUDIANTE: Array k. INSTRUCTOR: Array k. ¿Y cuál es la posición ahora? ¿Qué hay de los índices de nuestro valor más pequeño? Es sólo k. Así matriz k, k, que coinciden. Así que queríamos que reasignar. Y a continuación, después de que nos encontramos nuestra más pequeña, así que al final de este bucle for aquí hemos encontrado lo que nuestro pequeño valor es, por lo que sólo se intercambie. En este caso, al igual que decir que nuestra valor más pequeño es aquí. Este es nuestro valor más pequeño. 

Sólo queremos cambiar desde aquí, que es lo que la función de intercambio en la parte inferior hicimos, que sólo escribimos arriba juntos hace un par de minutos. Por lo tanto, debería parecer familiar. Y entonces se acaba de repetir hasta que llega a través de todo el camino hasta el final, lo que significa que usted tener cero elementos que no clasificadas y todo lo demás se ha ordenado. Tiene sentido? Un poco más concreta? El código ayuda? 

ESTUDIANTE: Para un tamaño, nunca realmente definirlo o cambiarlo, ¿cómo sabe? 

INSTRUCTOR: Así que una cosa es cuenta aquí es el tamaño int. Así que estamos diciendo en este tipo sort-- es una función en este caso-- es selección especie, se aprobó con la función. Así que si no se aprobó en, usted haría algo como con la longitud de la matriz o usted recorrer para encontrar la longitud. Pero debido a que se aprobó en, sólo podemos usarlo. Usted acaba de asumir que el usuario le dio un tamaño válido que en realidad representa un tamaño de la matriz. Fresco? 

Si ustedes tienen algún problema con estos o desea más práctica de codificación tipo por su cuenta, usted debe ir a study.cs50. Es una herramienta. Tienen un corrector que en realidad se puede escribir. Lo hacen pseudocódigo. Tienen más vídeos y diapositivas incluyendo los que utilizo aquí. Así que si usted todavía está sintiendo un poco borroso, trate de eso. Como siempre, venir a hablar conmigo, también. Pregunta? 

ESTUDIANTE: ¿Está usted diciendo que el tamaño se define anteriormente? INSTRUCTOR: Sí. El tamaño se define previamente para arriba aquí en la declaración de la función. Así que usted asume que ha sido aprobada en por el usuario, y por el bien de la simplicidad, vamos a suponer que el usuario nos dio la talla correcta. Enfriar. Así que esa es la selección de clasificación. Chicos, saben que estamos aprendiendo mucho hoy. Es una densa datos para la sección. Así que con eso, vamos para ir a la ordenación por inserción. 

Okay. Así que antes de que nosotros tenemos que hacer nuestro análisis de tiempo de ejecución aquí. Así, en el mejor de los casos, concedido desde que te mostré la mesa que ya clase de lo delató. Pero mejor tiempo de ejecución caso, ¿qué pensamos? Todo ordenadas. N al cuadrado. ¿Alguien tiene una explicación para qué te parece? 

ESTUDIANTE: Usted está comparando through-- INSTRUCTOR: Derecho. Usted está comparando a través. En cada iteración, aunque estamos decrementar este por uno, usted todavía está buscando a través de todo para encontrar el más pequeño. Así que incluso si su valor más pequeño es aquí en el comienzo, usted todavía está comparándolo contra todo lo demás para asegurarse de que es la cosa más pequeña. Así que va a terminar corriendo a través de aproximadamente n veces al cuadrado. Bien. Y ¿cuál es el peor de los casos? También n al cuadrado porque vas a estar haciendo eso mismo procedimiento. Así, en este caso, la selección tipo tiene algo que también llamamos el tiempo de ejecución esperado. Así que en los otros, solo sabemos los límites superior e inferior. Dependiendo de qué tan loco nuestro lista es o cómo clasificar lo que sea, que varían entre n o n al cuadrado. No sabemos. 

Pero debido a que la selección tiene el mismo tipo peor y mejor de los casos, que nos dice que no importa qué tipo de entrada que tiene, ya sea por completo ordenados o completamente revertir ordenados, es va a tomar la misma cantidad de tiempo. Así que en ese caso, si recordar de nuestra mesa, que en realidad tenía un valor que estas dos clases no tienen, que es el tiempo de ejecución esperado. Así que sabemos que cada vez que corremos selección especie, está garantizado que ejecutar una n al cuadrado del tiempo. No hay variabilidad allí. Sólo espera. Y, de nuevo, si quieres aprender más, tomar CS 124 en la primavera. Bien. Hemos visto esta. Enfriar. Así que tipo de inserción. Y probablemente voy para arder a través de este. No voy a tener ustedes codificarlo. Tendremos caminamos a través de él. Así que la ordenación por inserción es una especie de tipo similar a la selección en que tenemos tanto una sin clasificar y ordenados parte de la matriz. 

Pero lo que es diferente es que a medida que avanzamos a través de uno a uno, que acabamos de tomar cualquier número está al lado de nuestro sin clasificar, y clasificarlo correctamente en nuestra matriz ordenada. Se va a hacer más sentido con un ejemplo. Así que todo empieza como sin clasificar, Al igual que con la selección de clasificación. Y vamos a resolver esto en orden ascendente como lo hemos sido. Así que en nuestro primer pase tomamos el primer valor y decimos, OK, usted es ahora en una lista por su cuenta. 

Debido a que usted está en una lista por sí mismo, que está ordenada. Felicidades por ser el primer elemento de esta matriz. Usted ya está la ordenó todo por su cuenta. Así que ahora tenemos un clasificado y un arsenal sin clasificar. Así que ahora tenemos la primera. ¿Qué pasa entre aquí y aquí es que nosotros decimos, Bien, vamos a mirar el primer valor de nuestra gama sin clasificar y vamos a la entrada en su lugar correcto en el arreglo ordenado. 

Así que lo que hacemos es que tomamos 5 y decimos, OK, 5 es mayor que 3, así que nos insertamos derecho a la derecha de eso. Somos buenos. Así que a continuación pasamos a nuestro siguiente. Y tomamos 2. Nosotros decimos, OK, 2 es menos de 3, por lo que sabemos que tiene que estar en el frente a nuestra lista ahora. Así que lo que hacemos es empujamos 3 y 5 hacia abajo y nos movemos 2 en la primera ranura. Así que estamos a sólo insertarlo en el lugar correcto que debería ser. 

Entonces nos fijamos en nuestra siguiente, y decimos 6. Aceptar, 6 es mayor que todo en nuestra matriz ordenada, así que simplemente etiquetarla hasta el final. Y luego nos fijamos en 4. 4 es menor que 6, es menos del 5 pero es mayor que 3. Así que sólo nos insertamos la derecha el medio entre 3 y 5. Así que para hacer que un poco poco más concreto, aquí es una especie de la idea de lo que pasó. Así que para cada elemento sin clasificar, que determinar dónde en la parte ordenada es. 

Así que teniendo en cuenta la clasificados y sin clasificar, tenemos que recorrer a través de la figura y dónde encaja en la matriz ordenada. Y lo insertamos desplazando la elementos a la derecha hacia abajo. Y entonces nos mantenemos iteración a través hasta que tener una lista totalmente ordenada donde no seleccionados es ahora cero y ordenada ocupa el totalidad de nuestra lista. Así que, de nuevo, para hacer las cosas aún más concreto, tenemos pseudocódigo. 

Así que, básicamente, para i es igual a 0 a n menos 1, eso es sólo la duración de nuestra matriz. Tenemos algún elemento que es igual a la primera matriz o los primeros índices. Establecemos j igual a eso. Así, mientras que j es mayor que cero y la matriz, j menos 1 es mayor que la elemento, por lo que todo lo que está haciendo es asegurarse de que el j realmente representa la parte no seleccionada de la matriz. 

Así, mientras que todavía hay cosas para ordenar y j menos uno lo es-- es el elemento ella? J nunca se definió aquí. Es un poco molesto. Okay. De todas formas. Así j menos 1, usted está comprobando el elemento antes de ella. ¿Estás diciendo, OK, es el elemento antes de donde quiera que vamos am-- realmente sacar esto hacia fuera. Así que digamos que este es como en nuestro segundo pase. Así que va a ser igual a 1, lo que es aquí. 

Así que va a ser igual a 1. Esto sería 2, 4, 5, 6, 7. Bien. Así que nuestro elemento, en este caso va a ser igual a 4. Y tenemos algunos j que es va a ser igual a 1. Oh, j se decremento. Eso es lo que es. Así que j es igual a i, por lo que es esto dicho es que a medida que avanzamos, sólo estamos asegurando de que no somos más la indexación de esta manera cuando estamos tratando para insertar cosas en nuestra lista ordenada. 

Así que cuando j es igual a 1 en este caso y matriz j menos uno-- tan gama j menos 1 es 2 en este caso-- si eso es mayor que el elemento, entonces todo esto está haciendo está cambiando las cosas. Así pues, en este caso, matriz j menos uno sería matriz cero, que es 2. 2 no es mayor que 4, por lo que este no se ejecuta. Así que el cambio no se mueve hacia abajo. Lo que esto hace aquí es sólo mover la matriz ordenada hacia abajo. En este caso, en realidad, nos podría hacer-- vamos a hacer este 3. Así que si vamos a caminar a través de este ejemplo, ahora estamos aquí. Esto se solucionó. Esto es sin clasificar. Fresco? Así que i es igual a 2, por lo nuestro elemento es igual a 3. Y nuestro j es igual a 2. Así que miramos a través y nos decir, OK, es matriz j menos uno mayor que el elemento que estamos viendo? Y la respuesta es sí, ¿verdad? 4 es mayor que 3 y j es 2, por lo que este código se ejecuta. 

Así que ahora lo que hacemos un arreglo en 2, por lo que aquí, les swap. Así que nos limitamos a decir, OK, matriz a las 2 de ahora va a ser de 3. Y j va a ser igual j menos 1, que es 1. Eso es horrible, pero ustedes chicos se ponen la idea. J es ahora igual a 1. Y gama j es sólo va a ser igual a nuestro elemento, que era 4. Borré algo que no debería tener o algo miswrote, pero ustedes chicos se ponen la idea. 

Se mueve en el n. Y luego, si esto fuera, lo haría bucle de nuevo y sería decir, OK, j es 1 ahora. Y gama j menos 1 es ahora 2. Es 2 menos que nuestro elemento? ¿No? Eso significa que hemos insertado este elemento en el lugar correcto en nuestra matriz ordenada. Entonces podemos tomar esto y digamos, Aceptar, nuestra matriz ordenada es aquí. Y sería tomar este número 6 y ser como, OK, es de 6 a menos de este número? ¿No? Enfriar. Estamos bien. 

Hazlo de nuevo. Decimos 7. Es 7 menos que el fin de nuestra matriz ordenada? No. Así que estamos bien. Así que este sería solucionado. Básicamente todo lo que esto hace se está diciendo toma el primer elemento de la matriz sin clasificar, averiguar a dónde va en su matriz ordenada. Y esto sólo se hace cargo de los swaps de hacer eso. Básicamente, se está simplemente intercambiando hasta que esté en el lugar correcto. La imagen visual es que eres moviendo todo por hacer eso. 

Así que es como la mitad de la burbuja especie-esque. Echa un vistazo a estudio 50. Recomiendo probar para codificar esto por su cuenta. Si usted tiene algún problema o si desea ver código de ejemplo para una ordenación por inserción, por favor hágamelo saber. Estoy siempre alrededor. Así que el peor tiempo de ejecución de caso y el mejor tiempo de ejecución caso. Al chico vio desde la mesa que ya que mostró, es tanto n al cuadrado y n. 

Así que tipo de ir fuera de lo que hablamos sobre las clases con nuestros anteriores, peor caso de tiempo de ejecución es que si que está completamente sin clasificar, tenemos que comparar todas estas veces n. Hacemos un montón de comparaciones porque si es en orden inverso, vamos a decir, OK, este es el mismo, esto es bueno, y éste tendrá que ser comparado contra el primero en ser trasladado de nuevo. Y a medida que nos hacia el extremo de la cola, tenemos para comparar, comparar y comparar contra todo. 

Por lo tanto, termina siendo aproximadamente n al cuadrado. Si es correcta, entonces dices, OK, 2, ya está bueno. 3, usted está frente a un 2. Estas bien. 4, que acaba de comparar a la cola. Estas bien. 6, compara a la cola, que estás bien. Así, por cada punto si ya está ordenados, usted está haciendo una comparación. Así que es sólo n. Y porque tenemos un mejor tiempo de ejecución de caso de n y un peor caso de tiempo de ejecución de n cuadrado, no tenemos tiempo de ejecución esperado. 

Sólo depende de la el caos de nuestra lista allí. Y de nuevo, otro gráfico y la otra tabla. Así diferencias entre clases. Yo sólo voy a brisa a través, yo sentir que hemos hablado extensamente sobre la forma en que toda la clase de variar y unir. Así Ordenamiento por mezcla es el último Yo te aburriré con los chicos. Tenemos un cuadro bonito colorido. Así fusionar especie es un algoritmo recursivo. Así que ¿sabe usted lo que chicos una función recursiva es? 

¿Alguien quiere decir? ¿Quieres probar? Así que una función recursiva es sólo una función que llama a sí mismo. Así que si ustedes están familiarizados con la secuencia de Fibonacci, eso es porque considera recursiva usted toma los dos anteriores y sumarlos para obtener su siguiente. Así recursiva, siempre pienso de la recursividad como como una espiral por lo que usted es como una espiral hacia abajo en él. Pero es sólo una función que llama a sí mismo. 

Y, en realidad, muy rápido me usted puede mostrar lo que parece. Así recursiva aquí, si nos fijamos, este es la manera recursiva para resumir a través de una matriz. Así que todo lo que hacemos es tenemos la función suma suma que toma un tamaño y una matriz. Y si te fijas, el tamaño decrementos en uno cada vez. Y todo lo que hace es si x es igual a zero-- así que si el tamaño de la matriz es igual a zero-- devuelve cero. 

De lo contrario, resume este último elemento de la matriz, y después toma una suma de el resto de la matriz. Así que es justo y lo descomponen en problemas más pequeños y más pequeños. Larga historia corta, la recursividad, función que llama a sí mismo. Si eso es todo lo que tienes fuera de esto, eso es lo que es una función recursiva. Si usted toma 51, obtendrá muy, muy cómodo con la recursividad. Es realmente genial. Tenía sentido al igual que 03 a.m. una noche fuera. Y yo estaba como, ¿por qué he nunca usarlo? 

Así que para la fusión especie, básicamente, lo que va a hacer es que es va a romper hacia abajo y romper hacia abajo hasta que sus elementos sólo individuales. Los elementos individuales son fáciles de clasificar. Vemos que. Si usted tiene uno de los elementos, es ya considerada ordenada. Así que en una entrada de n elementos, si n es menor que 2, simplemente volver porque eso significa es 0 o 1 como hemos visto. Los que se consideran elementos ordenados. 

De lo contrario, romper por la mitad. Ordene la primera mitad, ordenar la segunda la mitad, y luego unirlos. ¿Por qué se llama fusión especie. Así que tenemos aquí vamos a resolver estos. Así que seguimos teniéndolos hasta que el tamaño de la matriz es 1. Por eso, cuando es 1, apenas volvemos porque este es un arreglo ordenado, y esto es un arreglo ordenado, y eso es una matriz ordenada, todos estamos ordenados. Así que lo que hacemos es que iniciar la fusión de ellos juntos. 

Así que la forma en que puede pensar en la fusión es que acaba de extraer la más pequeña número de cada una de las matrices de sub y sólo añadir a la matriz surgido. Así que si usted mira aquí, cuando tenemos estos conjuntos que tienen 4, 6, y 1. Cuando queremos fusionar estos, nos fijamos en estos dos primeros y decimos, OK, 1 es más pequeña, que va a la parte delantera. 4 y 6, que no hay nada para comparar que, simplemente Etiquétalo hasta el final. 

Cuando combinamos estos dos, que acabamos de tomar el más pequeño de estos dos, por lo que es 1. Y ahora tenemos la más pequeño de los dos, así que 2. Más pequeño de estos dos, 3. Más pequeño de estos dos, 4, 5, 6. Así que usted está tirando de ellas. Y porque no tienen sido ordenados previamente, sólo hay uno comparación cada vez que hay. Así que más código aquí, la representación justa. Así se inicia en el centro y a ordenar a la izquierda y la derecha y entonces simplemente fusionar esos. 

Y no tenemos código para fusionar aquí. Pero, de nuevo, si usted va en estudiar 50, que va a estar allí. De lo contrario, venir a hablar conmigo si usted todavía está confundido. Así que lo bueno aquí es que mejor de los casos, peor de los casos, y el tiempo de ejecución esperado están todos en log n, que es mucho mejor que la que hemos visto por el resto de nuestras clases. Hemos visto n al cuadrado y lo que en realidad llegar aquí se n log n, lo cual es genial. 

Mira lo mucho mejor que es. Tal agradable curva. Así que mucho más eficiente. Si alguna vez se pueda, utilizar la combinación de clase. Esto le ahorrará tiempo. Por otra parte, como hemos dicho, si estás abajo en esta zona inferior, no tiene que gran parte de la diferencia. Te levantas a miles y miles de entradas, usted definitivamente quiere un algoritmo más eficiente. Y, de nuevo, nuestra hermosa mesa de todos tipo que ustedes aprendieron hoy. 

Así que sé que ha sido un día denso. Esto no es necesariamente va para ayudarle con su conjunto de procesadores. Pero yo sólo quiero hacer un descargo de responsabilidad esa sección no se trata sólo de conjuntos de procesadores. Todo este material es justo juego para sus exámenes parciales. Y también si lo hace seguir adelante con CS, estos son fundamentos muy importantes que usted necesita saber. Así que algunos días serán un poco más pset ayuda, pero algunas semanas serán contenido mucho más real que puede no parecer súper útil para usted en este momento, pero te prometo si continúa el va a ser muy, muy útil. 

Así que eso es todo por sección. Abajo al alambre. Lo hice en un minuto. Pero hay que ir. Y voy a tener donas o dulces. ¿Es alérgico a cualquier persona nada, por cierto? Los huevos y la leche. Así donas son un no? Okay. Bien. Hay chocolate? Starburst. Starbursts son buenas. Okay. Vamos a tener Starburst próxima semana entonces. Eso es lo que voy a conseguir. Ustedes tienen una gran semana. Lea su especificación. 

Déjeme saber si usted tiene alguna pregunta. PSET dos grados deben ser a usted para el jueves. Si usted tiene alguna pregunta acerca de cómo me califiqué algo o por qué yo califiqué algo la forma en que hizo, por favor envíeme un correo electrónico, venir a hablar conmigo. Estoy un poco esta locura semana, pero te prometo Todavía voy a responder dentro de 24 horas. Así que tener una gran semana, todo el mundo. Buena suerte en su conjunto de procesadores.