ENCEINTE 1: Salut tout le monde! Bienvenue à la section. Je suis tellement content de voir que beaucoup d'entre vous, ici, et tout le monde qui regarde en ligne. Donc, comme d'habitude dos de bienvenue. Je espère que vous avez tous eu une belle week-end, plein de repos, de détente. Il faisait beau hier. Donc, je l'espère que vous avez apprécié l'extérieur. 

Alors d'abord quelques annonces. Classement. Ainsi, la plupart d'entre vous devriez avoir obtenu un Email de moi au sujet de votre Scratch Pset, ainsi que le classement de Pset 1. Donc, juste une couple de choses. Veillez à utiliser check50 dans style50. Ceux-ci sont destinés à être ressources pour vous les gars, pour vous assurer que vous obtenez autant de points que vous le pouvez sans les perdre inutilement. Donc, des choses comme le style sont très importants. Nous allons décoller pour elle. Certains d'entre vous peuvent avoir déjà remarqué que de votre Pset. Et check50 est juste un façon très simple de faire en sorte que nous sommes en train de retourner ce qui doit être retourné à l'utilisateur, et que tout fonctionne correctement. 

Sur la seconde note, assurez-vous Télécharger les choses dans le bon dossier. Il rend ma vie juste un peu plus difficile si vous téléchargez Pset 2 en 1 Pset parce que quand je télécharge des choses, ils ne sont pas téléchargés correctement. Et je sais qu'il est un peu bancal dans un système à s'y habituer, mais juste être super Attention, si seulement pour moi, de sorte que lorsque vous obtenez des e-mails à 2 heures comme et je suis classement. Si pas causer je dois regarder tout autour de votre Pset. Laisser refroidir. 

Je sais qu'il est tôt, mais je totalement pris au dépourvu fit par un essai qui est dû ce vendredi, que mes professeurs étaient comme, oh oui. Rappelez-vous, vous avez un essai en raison vendredi. Donc, je ne connais personne aime de penser à mi-mandat, mais votre premier quiz est le 15 Octobre, Octobre qui commence cette semaine. Ainsi, il pourrait être plus tôt que vous attendiez est tout. Alors que vous n'êtes pas jeté au dépourvu quand Je mentionne la section de la semaine prochaine que oh, votre quiz semaine prochaine, je pensais Je vous donne un peu plus d'une tête maintenant. 

Donc, votre problème réglé, le numéro trois. Comment les gens ont lu le spec par curiosité? Dáccord. Nous avons eu un couple. Type de bas de la dernière semaine mais qui est OK. Je sais qu'il était beau dehors. Donc Break Out. Certainement après on s'y fait lu aujourd'hui votre spec au moins essayer comme le téléchargement Code de la distribution et la gestion comme la première initiale chose qu'ils vous demandent de. Parce que nous utilisons le code de répartition et d'une bibliothèque que nous avons seulement été using-- --Il ya seulement la deuxième fois que nous avons fait cette Pset, des choses folles peuvent arriver avec votre appareil, et vous voulez trouver que les maintenant par rapport à plus tard. 

Parce que si il est jeudi soir ou il est Mercredi soir et pour une raison quelconque votre appareil ne se contente pas vouloir courir avec la bibliothèque ou à la distribution code, que des moyens vous ne pouvez même pas commencer à faire le codage. Parce que vous ne pouvez pas vérifier pour voir si cela fonctionne. Votre ne va pas être en mesure pour voir si il compile. Vous voulez prendre soin de ceux au début de la semaine, vous pouvez toujours envoyer un courriel me ou l'un des autres facteurs de transcription, et nous pouvons obtenir ceux fixés. Parce que ce sont des questions qui vont vous arrêter de faire de réels progrès. Il est pas comme un bug, que vous pouvez juste genre de sauter par-dessus. Si vous rencontrez des problèmes avec votre appareil ou un code de distribution, vous voulez vraiment obtenir que prendre soins de plutôt tôt que tard. Donc, même si tu ne vas pas en fait commencer à coder, téléchargez la distribution code, lire la spécification, assurez-vous tout est d'y travailler. D'accord? Si vous ne pouvez faire cela, je promettre votre vie sera plus facile. Et si vous allez probablement à le faire dès maintenant droit? Dáccord. Ainsi, des questions là-bas? Les choses logistiques? Tout le monde est bon? Dáccord. 

Avertissement pour ceux de vous dans la salle et en ligne. Je vais essayer de passer Powerpoint entre dans l'appareil parce que nous allons être faire un peu de codage aujourd'hui par la demande populaire de la anonyme suggestion sondage ai envoyé la semaine dernière. Donc, nous allons faire quelques codage. Donc, si vous voulez les gars aussi à feu à vos appareils, et vous devriez avoir reçu un e-mail de moi, avec un fichier d'exemple. Se il vous plaît sentir libre de le faire. 

Donc, nous allons parler GDB, qui est un débogueur. Il va vous aider sorte de savoir où les choses vont mal dans votre code. Il est vraiment juste une façon pour vous de faire un pas dans votre code comme ça se passe, et être en mesure d'imprimer des variables ou voir ce qui se passe réellement sous le capot versets votre programme juste la course, il est comme les failles, et vous êtes comme, aucune idée ce qui vient de se passer ici. Je ne sais pas quelle ligne il a échoué à. Je ne sais pas où il est allé mal. Ainsi, GDB va vous aider avec ça. Aussi, si vous décidez de continuer oui, et prendre 61, il va vraiment, vraiment être votre meilleur ami, parce que je peux vous dire parce que je vais à travers cette classe. 

Nous allons regarder binaire recherche, qui, si vous les gars me souviens le grand exemple de l'annuaire téléphonique spectacle de la classe. Nous allons mettre en œuvre cette, et marche à travers un petit peu plus, et puis nous allons à travers quatre différentes sortes, qui sont Bubble, Sélection, Insertion, et fusionner. Laisser refroidir. Ainsi, GDB comme je l'ai mentionné, est un débogueur. Et ce sont des sortes de gros choses, les grandes fonctions ou commandes que vous utilisez dans GDB, et je marcherai vous grâce à une démo de ce en une seconde. 

Donc, ce ne sont pas seulement va rester abstrait. Je vais essayer de faire ce que le béton que possible pour vous les gars. Donc, briser. Ça va être soit pause comme, un nombre, qui représente une ligne dans votre programme, ou vous pouvez nommer une fonction. Donc, si vous dites briser principal, il arrêtera au principal, et laissez vous marchez à travers cette fonction. 

De même, si vous avez un peu externe fonctionner comme Swap ou Cube, que nous avons examiné la semaine dernière. Si vous dites supprimera l'un de ceux-ci, chaque fois que votre programme frappe qui, il attendra pour vous lui dire quoi faire. Avant il suffit d'exécuter pour vous pourrait effectivement intervenir à l'intérieur de la fonction et voir ce qui se passe. Alors, la prochaine, saute un peu plus de la ligne suivante, va sur les fonctions. Étape. Ce sont tous peu abstrait. Alors, je vais juste courir à travers eux, mais vous les verrez en usage dans une seconde. 

Entrez dans une fonction. Donc, comme je le disais, comme avec Swap, il serait vous permettent de réellement que si vous êtes comme entrer physiquement à l'intérieur, vous pouvez jouer avec ces variables, impression ce qu'ils sont, voir ce qui se passe. Liste littéralement juste imprimer le code environnant. Donc, si vous oubliez de genre où vous êtes dans votre programme, ou vous vous demandez ce qui se passe autour d'elle, ce sera juste imprimer un segment de comme cinq ou six lignes autour d'elle. Ainsi, vous pouvez vous orienter sur l'endroit où vous êtes. 

Imprimer une variable. Donc, si vous avez la clé comme en César, que nous allons examiner. Vous pouvez dire Touche impression à tout moment. Il va vous dire ce que la valeur est si que, peut-être quelque part le long du chemin, vous avez écrasé votre clé. Vous pouvez effectivement dire que parce que vous pouvez réellement observer cette valeur. 

Dans les locaux, seulement des impressions vos variables locales. Donc, quand vous êtes dans une boucle, et vous voulez juste voir comme, oh. Quel est mon je? Quelle est cette valeur de clé que je l'initialise ici? Quel est le message à ce point? Il suffit d'imprimer tous de ceux-ci, de sorte que vous ne doivent pas individuellement dire, Imprimer I. Imprimer le message. Touche d'impression. Et puis sur Affichage. Qu'est-ce que cela fait est que vous déplacer dans le programme, il va juste assurez-vous qu'il est l'affichage de certaines certaine variable à chaque point. Alors que vous also-- --Il est une sorte de raccourci où vous ne devez pas continuer comme, oh. Touche d'impression ou Imprimer I. Il vient fera automatiquement pour vous. 

Donc, avec cela, nous allons de voir comment cela va. Je vais essayer de commutateur à mon appareil. Voir si je peux le faire. Tous. Nous allons simplement refléter le. Il ya rien de fou sur mon ordinateur portable de toute façon. Dáccord. Ce doit être celui-ci. Il est si petit. Voyons voir si nous pouvons le faire. 

Dáccord. Alice est évidemment mal ici un peu, Mais nous y reviendrons dans un momento. Dáccord. Nous allons nous contenter d'augmenter ce. Dáccord. Tout le monde peut voir que sorte de? Peut-être un petit peu? Je sais qu'il est un peu petite. Vous ne pouvez pas tout comprendre comment faire cette plus grande. Si quelqu'un sait. Est-ce que quelqu'un sait comment faire plus? Dáccord. Nous allons rouler avec lui. N'a pas d'importance de toute façon car il est juste qui est le code que vous les gars devraient avoir. 

Quoi de plus important est la borne ici. Et nous avons ici Pourquoi est-il si petit? Réglages. Oh. Vrai Ike. Comment agit-il? Sortir de là. Est-ce mieux pour tout le monde? Dáccord ,. Laisser refroidir. 

Vous savez quand vous êtes dans un CS des difficultés techniques de classe sont sorte de partie de the-- Donc, nous allons effacer ce. Dáccord. Donc, ici dans la section, que nous avons eu ici. César est un fichier exécutable. Donc je l'ai fait. Donc, une chose à réaliser avec GDB est que cela fonctionne uniquement sur les fichiers exécutables. Donc, vous ne pouvez pas l'exécuter sur un dotsy. Vous devez réellement faire vous que votre code compile, et qu'il peut effectivement être exécuté. 

Donc, assurez-vous que, si elle ne le fait pas compiler, le compiler, de sorte que vous pouvez genre de courir à travers elle. Donc, pour commencer GDB, tout ce que vous faites, Gloria Type GDB, et ensuite seulement la fichier que vous voulez. Je Misspell toujours César. Mais vous voulez vous assurer que car il est un exécutable, point le flash de ti sorte que signifie que vous allez pour exécuter CSI vous allez exécuter Ces fichiers soit avec le débogueur. Dáccord. Donc, vous faites cela, vous obtenez ce genre de charabia. Il est juste tout ce qui concerne le débogueur. Vous ne devez pas vraiment inquiéter en ce moment. Et comme vous le voyez, nous avons cette parens ouvertes, le PIB, proches parens, et juste ressemble un peu notre ligne de commande, pas vrai? 

Donc, ce que nous voulons do-- -SO, La première chose est que nous voulons choisir un endroit pour casser. Donc, il ya un bug dans ce programme César que je présente, que nous allons le découvrir. Il ce qu'il fait est qu'il faut l'entrée Barfoo en majuscules, et pour une raison quelconque il ne change pas A. Il laisse juste seul, tout le reste est correct, mais la seconde lettre Un reste inchangé. Donc, nous allons essayer de comprendre pourquoi. Donc, la première chose que vous avez l'habitude vouloir faire chaque fois que vous démarrez sur GDB est de savoir où le casser. 

Alors César est un joli programme court. Nous avons juste une fonction, non? Quelle était notre fonction dans César? Il ya seulement une fonction, droit principal? Principal est une fonction pour tous vos programmes. Si vous ne disposez pas d'accueil, je pourrais être un peu inquiet en ce moment, mais je vous souhaite à tous aviez principal là-dedans. Donc, ce que nous pouvons faire est que nous pouvons juste briser Main, juste comme ça. Ainsi, il est dit, OK. Nous mettons notre point d'arrêt une il. 

Donc, maintenant la chose à retenir est à César prend un argument de ligne de commande à droite et nous avons pas encore fait n'importe où. Donc, ce que vous faites est quand vous allez réellement à fonctionner le programme, tout programme que vous êtes courir dans GDB qui doit ligne de commande arguments, vous allez à l'entrée lorsque vous commencez à exécuter. Donc, dans ce cas, nous faisons Exécuter avec une clé de trois. Et il va vraiment commencer. 

Donc, si vous voyez ici, nous avons Si RC est pas égal à 2. Donc, si vous les gars ont tout ce fichier que je envoyé jusqu'à vous verrez que cela ressemble le première ligne de notre fonction principale, à droite? Il est de vérifier pour voir si nous avons le bon nombre d'arguments. Donc, si vous vous demandez si RC est correct, vous pouvez faire quelque chose comme impression RC. RC est égal à deux, qui est ce que nous attendions, non? 

Ainsi, nous pouvons aller Ensuite, et continuer à travers. Donc, nous avons une certaine touche là. Et nous pouvons imprimer notre touche à veiller à ce que est correct. Intéressant. Pas tout à fait ce que nous attendions. Donc, une chose à réaliser avec GDB aussi, est qu'il est pas jusqu'à ce que vous frappez Ensuite, que la ligne que vous venez de voir est réellement exécuté. Donc, dans cette clé de cas n'a pas encore été attribué. Donc, la clé est une valeur d'ordures que vous voyez sur le fond il. Négatif 120-- $ --Il de un milliard et quelque chose des choses bizarres droit? Il est pas la clé que nous nous attendions. Mais si nous avons touché sur Suivant, puis nous essayer et touche d'impression, il est trois. 

Tout le monde voit que? Donc, si vous obtenez quelque chose que vous êtes comme, attendez. Ceci est complètement mal, et je ne sais pas comment cela pourrait se produire parce que tout ce que je veux à faire est de céder un certain nombre, une variable, essayez de frapper Ensuite, essayez d'imprimer encore une fois, et voir si cela fonctionne. Parce que ça ne va exécuter et effectivement affecter quelque chose après vous cliquez sur suivant. Donner un sens à tout le monde? Uh huh? 

SPEAKER 2: Lorsque vous aléatoire numéros qu'est-ce que cela signifie? 

ENCEINTE 1: Il est juste aléatoire. Il est juste ordures. Il est juste quelque chose que votre ordinateur attribue au hasard. Laisser refroidir. Donc, maintenant nous pouvons passer à travers, et si nous avons maintenant ce texte brut GetString. Alors, permettez-moi de présenter ce qui va se passer quand nous avons frappé Suivant ici. Notre GDB genre de disparition, non? En effet, GetString est maintenant d'exécution, droit? Donc, quand nous avons vu texte brut est égal à GetString, parens ouverts et parens, et nous avons atteint suivante, qui a effectivement exécutées maintenant. Donc, il attend Nous entrée de quelque chose. 

Donc, nous allons à l'entrée de notre nourriture qui est ce que ça ne vous dis-je et qui dit simplement qu'il est fin de l'exécution, que la fermeture des moyens de support, il est la sortie de cette boucle. Ainsi, nous pouvons frapper suivante, et maintenant, comme je suis que vous êtes tous au courant de César, cela est, ce qui est de cette ligne va faire. Il est pour Int I est égale à 0, N est égal à Strlen, texte brut, puis I est inférieur à N, I, plus, plus. Qu'est-ce que cette boucle va faire? Ouvrez votre message. Laisser refroidir. Donc, nous allons commencer à le faire. 

Donc, si cette condition correspondre, pour notre premier? Si il est un B, il est texte brut I. Nous peut obtenir des informations sur nos sections locales. Ainsi, i est nul, et si six, qui nous nous attendons, et notre clé est de trois. Tout ce qui fait sens, non? Ces chiffres sont tout exactement ce qu'ils devraient être. Donc, hum? Intervenant 3: je dois nombres aléatoires pour le mien. ENCEINTE 1: Eh bien, nous pouvons --Nous check-- peut discuter à ce sujet dans un second. Mais vous devriez obtenir ceci. Donc, si nous avons un capital B pour notre première, cette condition doit l'attraper, non? Donc, si nous avons atteint Ensuite, nous voyons Si ce qui exécute effectivement. Parce que si vous suivez le long de votre code, cette ligne ici, où je texte brut est remplacé par ce calcul, seulement exécute si le Si condition est correcte droit? 

GDB ne va vous montrer choses qui sont réellement d'exécution. Donc, si cette condition n'a pas été respectée Si, il est aller juste pour passer à la ligne suivante. D'accord? Donc, nous l'avons. Ce moyen de support il est fermé hors de la boucle maintenant. Donc, il va recommencer. Juste comme ça. Alors, que nous pouvons obtenir des informations sur nos habitants ici, et nous voyons que notre première lettre a changé, non? Il est maintenant un E, comme il se doit. Ainsi, nous pouvons continuer. 

Et nous avons cette vérification. Et ce contrôle devrait fonctionner, non? Il est A. Il doit être changé trois lettres à terme. Mais si vous remarquez, nous obtenir quelque chose de différent. Donc dans ce cas ici, il a attiré , et si cette ligne exécutée, qui a modifié notre B. Mais, dans ce cas-ci, nous avons juste qu'il sauté, cela, et est allé à la [? L SIFF. ?] Donc, quelque chose qui se passe là-bas. Qu'est-ce que vous dit est que, nous savons qu'il doit attraper ici, mais il est pas. Quelqu'un peut-il voir ce que notre problème est dans cette ligne? Il est une chose très minute. Et vous pouvez aussi regarder votre code. Il est également line-- oublier quelle ligne il est dans there-- mais il est dans la [inaudible]. Oui? 

Haut-parleur 4: Il est sur la supérieure page si vous le lisez dans le livre. ENCEINTE 1: Exactement. Ainsi, le débogueur ne pouvait pas dire vous, mais le débogueur Pourriez-vous vers une ligne que vous savez ne fonctionne pas. Et parfois, quand surtout plus tard dans le semestre, lorsque vous avez affaire à un cent, cent quelques lignes de code, et vous Je ne sais pas où il est défaillant, ceci est une excellente façon de le faire. Donc, nous avons trouvé notre bug. Vous pouvez le fixer dans votre fichier, et puis vous pouvez l'exécuter à nouveau, et tout devrait fonctionner parfaitement. Et la chose la plus importante est cela peut sembler, OK. Ouais. Laisser refroidir. Vous saviez ce que vous cherchez. Donc, vous saviez quoi faire. 

GDB peut être super utile parce que vous peut imprimer toutes ces choses que vous ne serait pas. Il est beaucoup plus utile que printf. Combien d'entre vous utilisez comme printf de savoir où un bug a été, non? Donc, avec cela, vous ne le faites pas avoir toujours revenir, et comme en commentant Printf, ou en commentant, et comprendre ce qui vous devez imprimer. Cela vous permet en fait juste à parcourir, imprimer des choses que vous allez à travers, donc, vous pouvez observer comment ils changent en temps réel, que votre programme est en cours d'exécution. 

Et il prend un peu peu de temps pour s'y habituer. Je recommande fortement tout genre d'être un peu frustré avec elle pour le moment. Si vous passez une heure sur la la semaine prochaine apprendre à utiliser GDB, vous vous épargnerez beaucoup de temps plus tard. Et littéralement. nous disons cela aux gens chaque année, et je me souviens quand je pris la classe, je me suis dit, je vais bien. Non. Pset 6 est venu sur et je suis comme, je vais apprendre comment utiliser GDB parce que je ne sais pas savoir ce qui se passe ici. 

Donc, si vous prenez le temps de manière utiliser sur les petits programmes que vous allez être travailler, comme le travail par quelque chose comme Visionäre, comme ça. Ou si vous voulez plus de pratique, je suis sûr Je pouvais venir avec des programmes en buggy, pour vous de déboguer si vous le souhaitez. 

Mais si vous venez de prendre un peu de temps pour obtenir habituer, jouer juste avec elle, il va vraiment bien vous servir. Et il est vraiment l'un des ces choses que vous venez de avoir à essayer, et vous salir les mains avec, avant de comprendre vraiment. Je ne comprenais vraiment une fois Je devais choses de débogage avec elle, et il est beaucoup plus agréable d'avoir une idée de comment déboguer plus tôt plutôt que plus tard. Dáccord. Laisser refroidir. Je sais que ce genre de comme un cours intensif de GDB, et je vais certainement travailler sur l'obtention ces pour paraître plus gros la prochaine fois. Laisser refroidir. 

Donc, si nous revenons à notre PowerPoint. Est-ce que cela va fonctionner? Awh. Oui. Dáccord. Donc, si jamais vous avez besoin de tout ceux de plus, il ya la liste. Recherche Donc binaire, où tout le monde se souvient le grand spectacle de David déchirant annuaires téléphoniques de moitié. Je ne suis pas vraiment le annuaires téléphoniques Plus, parce que, comme l'endroit où vous faire obtenir des livres de téléphone de nos jours? Je ne sais pas vraiment. La recherche binaire. Quelqu'un se souvient comment binaires de recherche œuvres? Tout le monde à tous? Ouais? SPEAKER 5: Vous savez, quand vous regardez à laquelle la moitié il serait, Sur cette base, et se débarrasser de l'autre moitié. 

ENCEINTE 1 Exactement. Ainsi, la recherche binaire, il est une sorte de A- -Nous aiment à l'appeler diviser et conquérir. Donc, ce que vous allez faire est vous aurez l'air dans le milieu, et vous verrez si elle correspond ce que vous cherchez. Et si elle ne le fait pas, alors vous essayez de comprendre, est ce que ça va être à gauche la moitié ou la moitié droite. Donc, ce serait peut-être si vous êtes à la recherche à quelque chose qui est classée par ordre alphabétique, voyez-vous, oh. Allison ne viennent avant M? Oui. Donc, nous allons regarder la première moitié. 

Ou peut-être comme des numéros. Tout ce que vous pouvez comparer, il peut être triée. Vous pouvez utiliser la recherche binaire sur. Donc, quelqu'un se souvient de cette graphique ou ce qu'il en est? Sa complexité asymptotique. Donc, ce graphique seulement décrit combien de temps il vous emmène à résoudre un problème vous augmentez le nombre de choses que vous utilisez. 

Donc, nous avons N, qui est le temps linéaire. Si N sur deux, ce qui est légèrement mieux, se développe toujours super rapide. Et puis nous avons Connectez-vous, ce qui est ce que nous considérons recherche binaire. Si nous remarquons, comme votre problème devient beaucoup et beaucoup plus, le temps qu'il vous faut pour le résoudre ne vraiment pas beaucoup augmenter. Il est comme comparable ici au début. Vous êtes comme, OK. Tout fait ici pas vraiment Quel que soit celui que nous utilisons, mais vous sortez d'un million, un milliard. Vous essayez de trouver some-- --you're essayer de trouver une aiguille dans une botte de foin. 

Je pense que vous voulez ce problème. Vous souhaitez que cette complexité, pas linéaire, car pour tout ce que vous sais tu vas être à la recherche à travers chaque aiguille individuelle, chose de foin, essayer de regarder pour votre aiguille. Et pas trop de plaisir dans mon opinion. Je voudrais rapidement. Je l'aime efficace. Et les étudiants qui travaillent dur vous les gars sont, vous savez travailler plus intelligemment, pas plus difficile ce genre de chose, comment vous peut compenser ces algorithmes. 

Donc, nous allons marcher par juste un petit exemple. Je pense que vous devriez avoir une main sur la recherche binaire, mais au cas où quelqu'un est un peu floue, veulent renforcer, nous allons simplement aller à travers un exemple ici. Donc, nous sommes à la recherche si le tableau contient sept. 

Donc, la première chose que nous faisons est regarder dans le milieu, à droite? Et aussi, vous allez être codage Recherche binaire dans une seconde. Donc, ça va être amusant. Donc nous regardons dans le petits tableaux intermédiaires 3. Est-ce que 3 égaux 7? Ne fonctionne pas. Il est six. Alors, est-il moins de ou supérieur à sept? Moins que. Oui. Travail les gars de Nice. Je sens que je que je devrais avoir des bonbons parce que je vouloir jeter dans les cours. Il est ce que je vais faire la semaine prochaine. Il vous gardera gars pointu. 

Donc, nous jetons que premier semestre, non? elle était inférieure à. nous savons que tout sur le côté gauche va être inférieur à ce que nous sommes actuellement à la recherche pour. Donc, il n'y a pas besoin de faire attention à elle. Il suffit de l'oublier. Donc, maintenant nous regardons notre droite, et nous sommes au milieu là-bas, et maintenant il est neuf. Ainsi, 9 est-- --Everyone? Supérieure à ce que nous sommes cherchez, non? Donc, nous allons jeter tout de suite à droite. Comme ça. Maintenant, tout ce que nous sommes laissés avec est un. Donc, nous vérifions, est celui que nous recherchons? il est. Nous avons trouvé ce que nous voulions. Nous avons donc fait. Recherche bilinéaire. 

Et si vous remarquez, nous eu sept entrées là-bas. Il ne nous a fallu que trois fois, mais si vous faites comme d'un milliard, vous savez les gars combien d'étapes il serait prendre si nous avions quatre milliards d'choses? Les suppositions? Il est 32. 32 étapes pour trouver quelque chose dans un quatre milliards rangée d'éléments en raison de puissances de deux. Donc deux est à 32, est à quatre milliards. 

Comment donc assez fou que vous êtes encore dans comme un assez petit nombre d'étapes de trouver quelque chose dans quatre milliards d'éléments. Donc, sur cette note, nous sommes va coder cette si vous les gars peuvent réellement sorte de voir comment cela fonctionne. Très bien, alors vous avez peut coder. Je vais vous laisser les gars parler un peu. Apprenez à connaître les gens autour de vous, qui est ce que quelqu'un voulait de la dernière section. 

Donc, apprendre à connaître les gens autour de vous. Parlez à un peu. Et tout ce que je veux de toi gars est juste en ce moment essayer de créer un plan de pseudo-code. D'accord? Whoa. Tout ce que je veux de vous les gars vous êtes est aller juste à remplir dans ce cas de tout. Donc, je l'ai mis ces supérieure et des bornes inférieures qui représenter le début et à la fin de notre tableau. Et vous allez réellement boucle et comprendre ce que nous faisons dans cette boucle while. 

Donc, si vous pouvez comprendre out-- je dois un soupçon there-- quels sont les cas que nous avons ici? Donc, si vous voulez comprendre la cas, nous Pseudocode ceux et puis nous allons effectivement les code. Et ça va être, je penser, je l'espère ça va être un peu plus facile que prévu. Parce qu'il est pas que beaucoup de code, en fait, ce qui est vraiment cool. 

Mm-hm? 

L'ÉLÈVE: [inaudible]? ENSEIGNANT: Oui. Il y avait quelque chose à trouver dans le milieu. 

L'ÉLÈVE: nous pouvons donc l'utiliser. Dáccord. 

ENSEIGNANT: Parfait. Voilà donc la première chose que nous devons faire. Donc, trouver le milieu. Grand. Donc, avez-vous une idée de la façon dont nous pourrions en fait trouver au milieu avec le code? 

L'ÉLÈVE: Oui. n plus de 2? ENSEIGNANT: Donc, plus de 2 n. Donc, une chose à retenir est que vos limites supérieures et inférieures changent. Nous continuons la constriction de la partie du tableau nous cherchons à. Alors n plus de 2 fonctionne uniquement pour la première chose que nous faisons. Donc, en prenant supérieure et inférieure en compte, comment pourrions-nous obtenir cet élément milieu? Parce que nous voulons que le milieu entre supérieur et inférieur, non? Mm-hm? 

L'ÉLÈVE: [inaudible]. 

ENSEIGNANT: Nous avons donc un certain milieu. Et ce sera supérieure, plus bas sur 2. Impressionnant. Nous y voilà. Un bas de ligne. Les gars, vous êtes sur votre chemin. Alors, maintenant que nous avons notre milieu, que voulons-nous faire? Juste en général. Vous n'êtes pas obligé de le coder. Oui. L'ÉLÈVE: [inaudible]? ENSEIGNANT: Donc, il est ainsi parce que vous êtes trouver la moyenne entre les deux d'entre eux. Donc, si vous pensez à eux comme une sorte de plus en plus sur les côtés, penser que vous vous approchez au milieu, vous voulez comme ça. Donc, si vous étiez sur chaque côté de la milieu, et nous avons comme 5 et 7. Lorsque vous ajoutez ensemble vous obtenir 12, vous divisez par 2, est de 6. 

Parfois, il est difficile de expliquer pourquoi cela fonctionne, mais si vous travaillez à travers Par exemple, parfois, ça va vous aider à déterminer si il devrait être plus ou moins. Oui. 

L'ÉLÈVE: [Inaudible] exactement au milieu si elles avaient un cas où il ya beaucoup de petits nombres et comme un grand nombre? 

ENSEIGNANT: Donc, tout ce que vous avez besoin est le milieu de la matrice. Donc, si vous aviez un tas de petits nombres et puis un vraiment grand nombre à la fin, il n'a pas d'importance. Tout ce qui importe est que ils sont triés, vous venez de vouloir regarder le milieu de le tableau parce que vous êtes encore tranchage votre problème en deux. Laisser refroidir. Alors, maintenant que nous avons le milieu, que faisons-nous maintenant? 

L'ÉLÈVE: Comparer. Animateur: Le comparer. Donc comparer milieu de value_wanted. Laisser refroidir. Donc, vous voyez ici, nous avons cette valeur que nous voulons ici. Rappelez-vous ceci est un tableau. Donc milieu se réfère à l'indice. Donc, nous voulons faire de valeurs moyennes. Ne pas oublier si vous voulez à comparer, égaux doubles. Vous faites equals unique que vous êtes aller juste à les rétrocéder, et puis, bien sûr, il est va être la valeur que vous souhaitez. Donc, ne pas le faire. 

Nous allons donc voir si les valeurs de la moyenne est égale à la valeur que nous voulons. Ne pas oublier vos accolades. Dropbox devrait disparaître. Alors, que faisons-nous dans ce cas? Si elle est ce que voulons-nous revenir? Nous essayons de dire. 

L'ÉLÈVE: Imprimez. 

ENSEIGNANT: Eh bien, nous ne veulent pas imprimer. Donc ceci est un booléen ici, donc nous vouloir retourner true ou false. Nous disons, est ce numéro un [? RRA? ?] Donc, si elle est, nous revenons juste vrai. Si je peux épeler vrai. 

ÉTUDIANT: Pourquoi ne pas revenir à zéro? ENSEIGNANT: Donc, vous pourriez retourner zéro si vous voulez. Mais dans ce cas parce que notre fonction retourne un booléen, nous devons retourner true ou false. L'ÉLÈVE: Lorsque vous êtes disant expression booléenne, vous pouvez régler égale à faux? Comme si je veux dire, si cette condition ne sont pas remplies, comme est supérieure vaut Faux. Est-il comprendre si vous venez mettre faux de l'autre côté? ENSEIGNANT: Ouais. Donc en fait, si vous êtes jamais faire quelque chose comme est supérieur ou inférieur est, qui renvoie vrai ou faux et il est en fait un mauvais style de par exemple égal à égal vrai ou égaux vaut Faux. Vous souhaitez utiliser ce résultat comme lui-même en tant que votre chèque. Pas ce que je voulais. Voilà ce que je voulais. Ainsi, dans le cas de que vous demandez quelque chose comme sauvegarde dans c. 

Donc, si nous avons int main (void) et quelque chose comme ça. Et si vous avez est supérieure de certaines entrées et vous êtes vous demandant si vous pouvez faire quelque chose comme ça? Droit? Etudiant: Je tentais de le faire [inaudible]. Parce que si it's-- ENSEIGNANT: Droit. Donc, vous voulez que ce soit faux, non? L'ÉLÈVE: Oui. ENSEIGNANT: Donc, dans ce cas vous il veut à exécuter si il est pas vrai. Donc, la chose cool que vous faites là est la suivante. Alors rappelez-vous exclamation Point nie choses? Il dit [inaudible] ne signifie pas. Donc, si nous regardons seulement cette partie ici, vous seriez dire qui sera évalué à faux comme vous le souhaitez. Pas faux est vrai que signifie que ce serait exécuter. Est-ce logique? L'ÉLÈVE: Oui. INSTRUCTEUR: Awesome. Dáccord. Donc, nous pourrions revenir vrai dans ce cas. Alors maintenant, nous avons deux autres cas dans cette affaire. Quels sont nos deux autres cas? Disons simplement faire de cette façon. Commençons donc avec d'autre si les valeurs au milieu est inférieure à la valeur que nous voulons. Donc, notre valeur dans le milieu est moins que la valeur que nous recherchons. 

Alors, qui limite vous faire pensons que nous voulons mettre à jour? Supérieure ou inférieure? Supérieure? Ainsi, le côté de la matrice allons-nous envisager? 

ÉTUDIANTS: La plus faible. 

ENSEIGNANT: Nous allons nous à se pencher sur la gauche. Donc, d'autre si peu de valeur est moindre. Donc, votre valeur moyenne ici est moins que ce que nous voulons. Donc, nous voulons prendre le droite de notre tableau. Nous allons donc mettre à jour notre borne inférieure. Donc, nous allons réassigner notre faible. Et que pensez-vous devrait être inférieur? ÉTUDIANTS: La valeur moyenne? ENSEIGNANT: Donc, le milieu value-- L'ÉLÈVE: Plus 1. ENSEIGNANT: --plus 1. Quelqu'un peut-il me dire pourquoi nous avons que plus 1? 

L'ÉLÈVE: [? Aucune valeur?] est plus égale. 

ENSEIGNANT: Droit. Parce que nous savons déjà que notre valeur centrale est pas égal à et nous voulons exclure de toutes les recherches ultérieures. Si vous oubliez que plus 1, ce aimeront boucle indéfiniment. Et vous aurez juste être pris dans une boucle infinie et alors vous aurez une erreur de segmentation et les choses vont mal. Donc, assurez-vous toujours que vous n'êtes pas y compris la valeur que vous venez de regardé. Donc, nous nous occupons de cela avec un plus 1. 

Nous avons donc maintenant notre dernière condition qui je toujours pour des raisons de sécurité vous pouvez vérifier ici, si d'autre valeur à le milieu est supérieure à la valeur nous voulons. Cela signifie que nous voulons la moitié de gauche. Alors, qui que nous allons mettre à jour? Supérieure. Et quel est celui d'aller à égal? Moyen moins 1 parce que, bien sûr, nous voulons à faire en sorte que nous ne sommes pas en regardant cette valeur moyenne à nouveau. Et puis nous l'avons. Ce est tout. Voilà tout est recherche binaire. Il est pas si mal, non? Il est comme 10 lignes de Code avec un espace blanc. Donc, très puissant, très utile, vous voulez être utiliser dans un de vos psets plus tard. Peut-être pas celui-ci, mais plus tard. Donc apprendre. Aimer. Il vous traiter ainsi. Donc, quelqu'un at-il des questions sur la recherche binaire? Oui. 

L'ÉLÈVE: Est-ce important si votre n est pair ou impair? 

INSTRUCTEUR: Non Parce que nous jetons à la moyenne comme un int, il sera simplement tronquer. Donc, il restera un nombre entier et il sera finalement trier tout. Donc, vous ne devez pas vous inquiéter à ce sujet. Tout le monde bien? Impressionnant. Laisser refroidir. Donc, vous avez obtenu ce gars. Diaporama. Alors que nous parlions, je sais David mentionné runtimes de complexité. 

Donc, dans le meilleur des cas, il est juste un, que nous appelons la constante de temps. Quelqu'un peut-il me dire pourquoi cela pourrait être? Quel type de scénario qui entraînerait? Mm-hm. 

L'ÉLÈVE: [Inaudible] first-- ENSEIGNANT: Donc, le milieu étant le premier élément que nous arrivons à, non? Donc, soit un tableau d'un ou tout ce que nous cherchons juste se trouve être smack dab dans le milieu. Voilà donc notre meilleur des cas. Vous obtenez de véritables problèmes, probablement pas va atteindre [inaudible] qui souvent. Qu'en est-il notre pire des cas? Notre pire des cas est log n. Et cela a à voir avec l'ensemble des puissances de deux chose que je parlais. 

Ainsi, dans le pire des cas, cela signifierait que nous avons dû couper le tableau en bas jusqu'à ce qu'il soit un élément d'un seul. Nous avons donc dû l'abattre dans la moitié autant de fois que nous le pouvions. Voilà pourquoi il est log n parce que vous continuez à diviser par deux. Donc, les hypothèses, les choses que vous besoin de savoir si vous êtes jamais va utiliser une recherche binaire. Vos éléments doivent être triés. Ils doivent être triés car qui est la seule façon vous peut savoir si vous êtes en mesure à jeter la moitié. 

Si vous aviez ce sac pêle-mêle des numéros et que vous dites, OK, je vais vérifier le milieu nombre et le nombre que je cherche est moins que cela, je vais juste à jeter arbitrairement moitié. Vous ne voudriez pas savoir si votre nombres dans cette autre moitié. Votre liste doit être triée. De plus, cela peut être aller de l'avant un peu, mais vous devez avoir accès aléatoire. Vous devez être capable de tout aller à cet élément du milieu. Si vous avez à parcourir par quelque chose ou cela vous prend des mesures supplémentaires pour se rendre à cet élément du milieu, il est pas plus parce que log n vous ajoutez plus de travail en elle. Et cela fera un peu plus de sens dans deux semaines, mais je ne voulais genre de préface, vous les gars donner une idée de ce qui est à venir. Mais ce sont les deux hypothèses importantes que vous avez besoin pour une liste binaire. Assurez-vous qu'il est triée. Voilà le grand pour vous les gars en ce moment. Et que nous pouvons aller en le reste de nos sortes. Donc quatre bulle sorts--, insertion, la sélection et la fusion. Ils sont tous plutôt cool. Si vous les gars décident de prendre CS 124, prenez connaissance de toutes sortes de sortes. Et si vous êtes un fan XKCD, il est une bande dessinée sur vraiment cool comme sortes vraiment inefficaces, que je vous recommande fortement d'aller à regarder. L'un d'eux est comme panique sorte, qui est comme, oh non, retourner réseau aléatoire. système d'arrêt. Laissez. Donc humour geek est toujours bon. 

Donc ne Quelqu'un se souvient genre de comme juste une idée générale de la façon dont fonctionne tri à bulles. Vous vous souvenez? 

L'ÉLÈVE: Oui. 

ENSEIGNANT: Allez-y. 

Etudiant: Ainsi vous allez à travers et si elle est plus grande, alors vous échanger les deux. 

ENSEIGNANT: Mm-hm. Exactement. Alors que vous venez itérer. Vous vérifiez deux chiffres. Si l'un est plus grand avant que l'une après, vous les échangez juste pour que dans de cette façon tous les numéros plus élevés propager vers le haut vers la fin de la liste et tous les nombres inférieurs bulle vers le bas. 

At-il vous montrer les gars cool des effets sonores tri vidéo? Il est plutôt cool. Alors que Robert vient d'être dit, l'algorithme que vous entrez simplement dans la liste, permuter les valeurs adjacentes si ils ne sont pas dans l'ordre. Et puis juste continuer à répéter jusqu'à ce que vous ne faites pas de swaps. Donc, pas mal, non? Donc nous avons juste un petit exemple ici. Donc, cela va trier les dans l'ordre croissant. Ainsi, lorsque nous passons par le premier temps, nous regardons à travers huit et six ne sont évidemment pas dans l'ordre, nous les échanger. 

Alors regardez la suivante. Huit et quatre pas dans l'ordre. Les échanger. Et puis huit et deux, les permuter. Nous y voilà. Ainsi, après votre premier passage, vous savoir que votre plus grand nombre va être tout le chemin en haut, car il est juste va être constamment plus que tout le reste et il va juste bulle tout le chemin à la fin il. Est-ce que cela a un sens pour tout le monde? Laisser refroidir. 

Alors nous regardons notre deuxième passage. Six et quatre, interrupteur. Six et deux, interrupteur. Et maintenant nous avons quelques choses dans l'ordre. Ainsi, pour chaque passe que nous faire à travers l'ensemble de notre liste, nous savons que comme que de nombreux numéros à la fin auront été triés. Nous faisons donc un troisième passage, qui est un swap. Et puis sur notre quatrième passer, nous avons cases à zéro. Et si nous savons que notre tableau a été trié. 

Et qui est le grand chose avec tri à bulles. Nous savons que lorsque nous avoir zéro swaps, qui signifie que tout est en ordre complète. Il est un peu de la façon dont nous vérifions. Donc, nous allons également coder bulle sorte qui est aussi pas mal. Aucun d'entre eux sont si mal que ça. Je sais qu'ils peuvent sembler un peu effrayant. Je sais que quand je prenais la classe, même quand je a été l'enseignement de la classe pour la première fois l'année dernière, Je suis comme, comment dois-je faire? Il est logique en théorie, mais comment pouvons-nous réellement faire cela? Qui est la raison pour laquelle je tiens aussi à marcher dans le code avec vous les gars ici. Je dois donc un pseudo pour vous les gars cette fois. Il suffit donc de garder cela à l'esprit nous sommes sur le point de passer sur. Nous avons donc une certaine compteur garde la trace de nos échanges, parce que nous devons faire en sorte que nous vérifions que. Et nous parcourons l'ensemble du réseau comme nous venons de le faire avec cet exemple. Si l'élément est plus grand que avant l'élément après où nous en sommes, nous les échangeons et on incrémente notre compteur parce que dès que nous échangeons, nous voulons que notre compteur sais. Vous avez des questions là-bas? Quelque chose semble drôle ici. L'ÉLÈVE: Avez-vous mis le compteur à zéro chaque fois que vous allez dans la boucle? Avez-vous pas continuer Retour à zéro chaque fois? ENSEIGNANT: Pas nécessairement. Donc ce qui arrive est que nous passons par ici. Donc faire tout, rappelez-vous, ce exécutera une fois à coup sûr. Donc, ça va régler le compteur égale à zéro, puis il va itérer. Comme il parcourt à travers, il mettra à jour compteur. Comme il met à jour contre, quand il est fait, quand il atteint la fin de la rangée, si notre liste n'a pas été triés, compteur ont été mis à jour. 

Alors il vérifie l'état et il dit, OK, va à l'encontre supérieur à zéro. Dans ce cas, le faire à nouveau. Vous souhaitez réinitialiser sorte que lorsque vous passer à travers, le compteur est égal à zéro. Si vous passez par un tri tableau, rien ne change, cela échoue, et vous retourner la liste triée. Est-ce que cela a un sens? L'ÉLÈVE: Peut-être dans un peu. ENSEIGNANT: OK. Si il ya un autre question qui se pose. Oui. 

L'ÉLÈVE: Que serait la fonction être pour échanger les éléments? 

ENSEIGNANT: Nous pouvons donc écrire que si nous allons en ce moment. Laisser refroidir. Donc, sur cette note, Alison va pour revenir à l'appareil. Ça va être amusant. Et nous avons notre belle tri à bulles chose ici. Donc je l'ai déjà fait du vélo à travers le réseau. Nous avons nos swaps sont égales à zéro. Donc, nous voulons échanger adjacent éléments si elles sont hors d'usage. Donc, la première chose que nous devons ne itérer sur notre tableau. 

Alors, comment pensez-vous que nous pourrions itérer sur notre tableau? Nous avons pour et i est égal à 0. Nous voulons i à être moins que n moins 1 moins k. Et je vais vous expliquer que dans un second. Donc, cela est une optimisation ici où, rappeler comment je l'ai dit après chaque passage à travers le tableau nous savoir que tout ce qui est on-- 

Donc, après un passage nous sachez que ce sont triés. Après deux passages nous savons que tout cela est triée. Après trois passages nous sais que cela triés. Donc, la façon dont je l'itération à travers le réseau ici, est il est fait sûr d'aller seulement à travers ce que nous savons est non triés. D'accord? Ceci est juste une optimisation. Vous pouvez écrire naïvement juste itérer tout, il serait juste prendre plus de temps. Avec cette boucle quatre il est juste une belle optimisation parce que nous savons que, après chaque plein itération à travers le tableau ici, comme chaque boucle complète ici, nous savons que l'un de plusieurs de ces éléments sont triés à la fin. 

Donc, nous ne devons pas nous inquiéter à propos de ceux-ci. Est-ce que cela a un sens pour tout le monde? Ce petit truc cool? Donc, dans ce cas, si nous nous parcourons, nous savons que nous voulons vérifier si tableau n et n + 1 sont dans l'ordre. Dáccord. Alors, voici le pseudo-code. Nous voulons vérifier si le tableau n et n + 1 sont dans l'ordre. Alors que peut-on y at-il? Il va y avoir une certaine condition. Ce sera une si. 

L'ÉLÈVE: si le tableau est n moins de rang n + 1. ENSEIGNANT: Mm-hm. Bien, inférieure ou supérieure. L'ÉLÈVE: Supérieur à. Ensuite, nous voulons les échanger. Exactement. Alors maintenant, nous entrons dans ce qui est la mécanisme pour les échanger? Alors nous sommes allés à travers ce brièvement, un type de la fonction de permutation de la semaine dernière. Quelqu'un se souvient comment il a travaillé? Donc, nous ne pouvons pas leur attribuer, non? Parce que l'un d'entre eux se perdre. Si nous disions A est égal à B, puis B est égal à un, tout d'un coup, deux d'entre eux sont juste égal à B. 

Donc, ce que nous avons à faire est de nous avoir une variable temporaire qui est va tenir une alors que la nôtre nous sommes en train d'échanger. Donc, ce que nous avons est que nous aurons un certain int température est égale to-- vous pouvez l'affecter à celui qu'on vous voulez, il suffit assurez-vous de garder une trace de it-- dans ce cas, je vais assigner à tableau n + 1. Donc, ça va pour contenir tous les valeur est dans ce deuxième bloc que nous cherchons à. 

Et puis nous pouvons faire est que nous pouvons aller avant et tableau Réaffecter n + 1, parce que nous savons que nous avoir que la valeur stockée. Ceci est également un des grands things-- Je ne sais pas si l'un de vous eu des problèmes où si vous passez deux lignes de code tout à coup les choses fonctionnaient. L'ordre est très important dans CS. Donc, assurez-vous diagramme choses si possible quant à ce qui se passe réellement. Alors maintenant, nous allons réaffecter tableau n + 1, parce que nous savons que nous avoir que la valeur stockée. 

Et nous pouvons attribuer à ce tableau n ou dans ce cas tableau i. Trop de variables. Dáccord. Tableau Alors maintenant, nous avons réaffecté i plus 1 à l'égalité de ce qui est dans le tableau i. Et maintenant, nous pouvons revenir en arrière et attribuer gamme i de quoi? Tout le monde? 

ÉTUDIANT: 10. 

ENSEIGNANT: 10. Exactement. Et une dernière chose. Si nous avons échangé maintenant, que devons-nous faire? Quelle est la seule chose que va nous dire si jamais nous mettons fin à ce programme? Que nous dit que nous avoir une liste triée? Si nous ne réalisons pas de swaps, non? Si swaps est égal à zéro à la fin de cette. Donc, chaque fois que vous effectuez un échange, comme nous vient de faire ici, nous voulons mettre à jour swaps. Et je sais qu'il y avait une question plus tôt au sujet pouvez-vous utiliser zéro ou un lieu de vrai ou faux. Et qui est ce que cela fait ici. Donc, cela dit, sinon des swaps. Donc, si swaps est zéro, qui est: Je me suis toujours obtenir mes vérités et mes faux mélangés. Nous voulons nous évaluons à vrai et il est pas. Donc, si il est nul, alors il est faux. Si vous niez avec un [? cogner?] il devient vrai. Alors cette ligne exécute. 

Vérités et faux et zéros et des uns deviennent fous. Juste si vous marchez lentement à travers elle, il prendra tout son sens. Mais qui est ce que ce petit peu de code ici fait. Donc ce vérifie nous avons fait des swaps. Donc, si elle est autre chose que zéro, ça va être faux et le tout est va exécuter à nouveau. Cool? 

ÉTUDIANT: Qu'est-ce que la rupture faire? 

ENSEIGNANT: Cassez juste vous éclate de la boucle. Donc, dans ce cas, il serait Comme à peu fin au programme et vous voulez bien avoir votre liste triée. L'ÉLÈVE: Amazing. ENSEIGNANT: Je suis désolé? L'ÉLÈVE: Parce que déjà nous utilisé 1 écrit sur écrit zéro présenter que si cela fonctionnera ou pas. 

ENSEIGNANT: Ouais. Ainsi, vous pouvez retourner zéro ou 1. Dans ce cas, parce que nous ne sommes pas réellement faire quelque chose avec la fonction, nous voulons juste casser. Nous ne nous soucions pas vraiment à ce sujet. Le frein est également bon, si il est utilisé pour sortir de quatre boucles ou des conditions qui vous ne voulez pas poursuivre l'exécution. Il vous suffit d'eux. Il est un peu une chose de nuance. Je me sens comme il ya beaucoup de ondulation de la main, comme vous allez apprendre à ce sujet prochainement. 

Mais vous allez apprendre à ce sujet prochainement. Je promets. Dáccord. Alors que tout le monde se tri à bulles? Pas trop mal. Itérer, des choses de swap en utilisant un variable temp, et nous sommes tous mis là? Laisser refroidir. Impressionnant. Dáccord. Retour à la PowerPoint. Toutes les questions en général sur ces jusqu'à présent? Laisser refroidir. Mm-hm. 

L'ÉLÈVE: [Inaudible] int main habituellement. Avez-vous d'avoir ce pour cela? 

ENSEIGNANT: Donc, nous voulions juste juste à l'algorithme de tri réelle. Si vous l'aviez dans comme un programme plus vaste, vous auriez une part principale int. Selon l'endroit où vous utiliser cet algorithme, il déterminer ce qui est être renvoyé par elle. Mais pour notre cas, nous sommes strictement regarder comment ce fait itération sur un tableau. Donc, nous ne nous inquiétons pas. 

Alors que nous parlions meilleur des cas et pires scénarios pour la recherche binaire. Donc, il est également important de faire que pour chacune de nos sortes. Alors, que pensez-vous est le pire cas de l'exécution de tri à bulles? Les gars, vous vous souvenez? 

ETUDIANT: N moins 1. ENSEIGNANT: N moins 1. Donc, cela signifie qu'il ya n moins une des comparaisons. Donc, une chose à réaliser est que sur la première itération, nous passons par, nous comparons ces two-- de sorte que est 1. Ces deux, trois, quatre. Ainsi, après une itération nous ont déjà quatre comparaisons. Quand je parle de l'exécution et n. N représente le nombre de comparaisons en fonction de la manière dont de nombreux éléments nous avons. D'accord? 

Donc, nous allons à travers, nous avons quatre. La prochaine fois que vous savez que nous ne le faisons pas à prendre soin de cela. Nous comparons ces deux, ces deux, ces deux, et si nous ne disposons que d'optimisation avec les quatre boucle que je l'ai écrit, vous seriez comparez ici de toute façon. Donc, vous auriez à courir à travers le réseau et faire des comparaisons n n fois, parce que chaque fois que nous en courir à travers elle nous trions une chose. 

Et chaque fois que nous courons à travers le tableau, nous faisons n comparaisons. Donc, notre exécution en est n fait carré, qui est bien pire dans notre connectez-vous fin parce que signifie que si nous avions quatre milliard éléments, il est va nous prendre quatre milliards carré au lieu de 32. Donc, pas la meilleure exécution, mais pour certaines choses, vous savez, si vous êtes à l'intérieur un certain ensemble d'éléments tri à bulles peut être bon d'utiliser. 

Dáccord. Alors maintenant, quelle est la meilleure exécution de cas? L'ÉLÈVE: Zero? Ou 1? 

ENSEIGNANT: Donc 1 serait être une comparaison. Droite. 

ETUDIANT: N moins 1? 

ENSEIGNANT: Alors, oui. Alors n moins 1. Chaque fois que vous avez un concept comme n moins 1, nous avons tendance à tout simplement le déposer et nous venons de dire n parce que vous avez à comparer chacun des these-- chaque paire. Donc, il serait n moins 1, ce qui nous nous venions de dire est d'environ n. Lorsque vous avez affaire à l'exécution, tout est dans approximatives. Tant que l'exposant est correct, vous êtes assez bon. 

Voilà comment nous traitons avec elle. Alors que le meilleur des cas est n, qui signifie que la liste est déjà trié, et tout ce que nous faisons est dirigé par et vérifiez qu'il est bien triée. Laisser refroidir. Bien. Donc, comme vous le voyez ici, nous avoir juste un peu plus de graphiques. Alors n carré. Fun. Bien pire que n comme nous le voyons, et bien, bien pire que journal 2n. Et puis vous avez aussi dans les journaux de log. Et vous prenez 124, vous obtenez en comme star du journal, qui est comme un fou. Donc, si vous êtes intéressé, journal de recherche étoile. Il est assez amusant. Donc, nous avons ce grand tableau. Juste un heads-up, cette une merveilleux tableau d'avoir pour votre mi-parcours parce que nous longtemps pour vous poser ces amincit. Alors seulement un heads-up, ont ceci sur votre à mi-parcours sur votre feuille de triche agréable Là. Donc nous avons juste regardé au tri à bulles. Le pire des cas, n carré, meilleur des cas, n. Et nous allons regarder les autres. 

Et comme vous pouvez le voir, la seule celui qui fait vraiment bien est le tri par fusion, qui nous allons entrer dans pourquoi. Donc, nous allons aller à la prochaine sorte de sélection ici--. Quelqu'un se souvient comment sélection sorte travaillé? Allez-y. 

L'ÉLÈVE: aller essentiellement par un ordre et créer une nouvelle liste. Et comme vous êtes éléments mettant dans, les mettre dans le bon endroit dans la nouvelle liste. 

ENSEIGNANT: Alors que les sons plus comme le tri par insertion. Mais vous êtes vraiment proche. Ils sont très semblables. Même moi, je les confondre parfois. Avant cette section, je me suis dit, attendre. Dáccord. Donc, ce que vous voulez faire est la sélection sorte, la façon dont vous pouvez penser à ce sujet et la manière Je fais en sorte que je cherche pas à obtenir les mélanger, est elle passe par et on sélectionne le le plus petit nombre et met que au début de votre liste. Il permute avec cette première place. Ils ont fait un exemple pour moi. Impressionnant. Alors juste une façon de penser de la sélection it-- Trier, sélectionner la plus petite valeur. Et nous allons courir à travers un exemple qui je pense va aider parce que Je pense visuels aident toujours. Nous commençons donc avec quelque chose qui est complètement non triés. Rouge sera non triés, vert sera triée. Il va donner un sens à une seconde. 

Donc, nous allons à travers et nous réitérons du début à la fin. Et nous disons, OK, 2 est notre petit nombre. Nous allons donc prendre 2 et nous allons pour le déplacer vers l'avant de notre gamme parce qu'il est le plus petit nombre que nous avons. Voilà ce que cela est en train de faire ici. Il va juste pour échanger les deux. Alors maintenant, nous avons une triés partie et une partie non triés. Et ce qui est bon de se rappeler sur la sélection sorte est que nous sommes seulement en sélectionnant à partir de la partie non triés. 

La partie triée vous suffit de laisser seul. Mm-hm? 

L'ÉLÈVE: Comment sait-il ce qui est le plus petit sans comparant pour chaque autre valeur dans le tableau. ENSEIGNANT: Il fait comparer. Nous aimons laissé tomber. Ceci est juste général global. Ouais. Lorsque nous écrivons le code que je suis sûr que vous serez plus satisfait. Mais vous stockez cette première comme le plus petit élément. Vous comparez et vous dire, OK, est-il plus petit? Oui. Gardez-le. Voici le plus petit? Non? 

Ceci est votre plus petit, réaffecter à votre valeur. Et vous serez beaucoup plus heureux lorsque nous passons par le code. Donc, nous allons à travers, nous échangeons, alors puis nous regardons cette partie non triés. Donc, nous allons sélectionner trois sur. Nous allons mettre sur à la fin de notre partie triée. Et nous allons tout simplement continuer à faire que, ce faisant, et le faire. Voici donc notre genre de pseudo ici. Nous allons coder ici dans une seconde. Mais quelque chose de marcher à travers à un niveau élevé. Vous allez passer de i est égal à 0 à n moins 2. Voilà une autre optimisation. Ne vous inquiétez pas trop à ce sujet. Donc, comme vous le disiez. Comme Jacob a dit, comment pouvons-nous garder une trace de ce que notre minimum est? Comment savons-nous? Nous devons comparer tout dans notre liste. 

Donc, au moins égale à i. Il est juste de dire dans ce cas l'indice de notre valeur minimale. Alors ça va pour parcourir et il va de j est égal à i + 1. Donc, nous savons déjà que qui est notre premier élément. On n'a pas besoin de le comparer à lui-même. Donc, nous commençons à en le comparant à l'autre celui qui est pourquoi il est i + 1 à n moins 1, qui est la fin du tableau il. Et nous avons dit si le tableau à j est inférieure éventail min, puis nous réaffectons où nos indices minimum est. 

Et si min est pas égal à i, en tant que Où nous étions de retour ici. Donc, comme lorsque nous avons fait celui-ci. Dans ce cas, il commencerait à zéro, il finirait par être deux. Ainsi, ne serait pas égal min i à la fin. Ce nous laisse savoir que nous avons besoin de les échanger. Je me sens comme un exemple concret aidera beaucoup plus que cela. Alors je vais coder cette place avec vous les gars en ce moment et je pense que ce sera mieux. 

Sortes ont tendance à travailler de cette façon que dans il est souvent préférable juste pour les voir. Donc, ce que nous voulons faire est on veut d'abord la plus petite élément dans sa position dans le tableau. Exactement ce que Jacob a dit. Vous avez besoin de stocker que d'une certaine manière. Donc, nous allons commencer ici itération sur le tableau. Nous allons dire qu'il est notre premier juste pour commencer. Donc nous allons avoir int plus petit est égal à tableau à i. 

Donc, une chose à noter, tous les fois cette boucle est exécutée, nous commençons une étape plus loin. Quand nous commençons à nous regardons celui-ci. La prochaine fois que nous parcourons, nous commençons à celui-ci et en lui attribuant la plus petite valeur. Il est donc très similaire à tri à bulles où nous savons que, après une passe, Ce dernier élément est triée. Avec sélection sorte, il est tout le contraire. 

A chaque passage, nous savons que le premier est triée. Après le deuxième passage, le second sera triée. Et comme vous l'avez vu avec les exemples de diapositives, notre partie triés ne cesse de croître. Donc, en mettant notre plus petit aux tableaux I, tout ce qu'il ya à faire est ce que la constriction nous cherchons à façon pour réduire au minimum le nombre de comparaisons que nous faisons. Cela fait-il sens à tout le monde? Avez-vous besoin de moi pour parcourir que encore plus lente ou en d'autres termes? Je suis heureux de. Dáccord. 

Nous sommes donc stocker la valeur à ce point, mais nous voulons aussi pour stocker l'index. Donc, nous allons stocker le la position de la plus petite un, qui va tout simplement être i. Alors maintenant, Jacob est satisfait. Nous avons des choses stockées. Et maintenant nous avons besoin de regarder à travers la partie non triés du tableau. Donc dans ce cas ce serait notre non triés. Ceci est i. Dáccord. 

Donc, ce que nous allons faire va être pour une boucle. Chaque fois que vous devez itération sur un tableau, votre esprit peut aller pour une boucle. Donc, pour certains int k equals-- ce que nous pensons k va correspondre à commencer? Voici ce que nous avons mis notre petit valeur et nous voulons comparer. Que voulons-nous à le comparer? Ça va être la prochaine, non? Nous voulons donc k être initialisé i + 1 pour commencer. 

Et nous voulons k dans ce cas nous ont déjà stocké taille ici, si nous pouvons simplement utiliser la taille. Taille étant la taille de la matrice. Et nous voulons juste mettre à jour par une k à chaque fois. Laisser refroidir. Alors maintenant, nous devons trouver le plus petit élément ici. Donc, si nous parcourons, nous envie de dire, si le tableau à k est inférieure à la plus petite value-- voilà où nous en sommes réellement garder une trace de ce qui est le plus petit ici-- alors nous voulons réaffecter ce que notre plus petite valeur est. 

Cela signifie que, oh, nous sommes itérer ici. Quelle que soit la valeur est ici pas la plus petite chose. Nous ne voulons pas. Nous voulons réaffecter. Nous sommes donc si le réaffectant, qu'est-ce que vous pensez peut-être dans ce code ici? Nous voulons réaffecter plus petite et la position. Donc, ce qui est plus petit maintenant? L'ÉLÈVE: Array k. INSTRUCTEUR: Array k. Et quelle est la position maintenant? Ce qui est des indices de notre plus petite valeur? Il est juste k. Donc tableau k, k, ils correspondent. Nous avons donc voulu que réaffecter. Et puis après nous avons trouvé notre petit, si à la fin de cette boucle pour ici nous avons trouvé ce que notre petit valeur est, alors nous avons l'échanger. Dans ce cas, comme, disons, notre plus petite valeur est ici. Ceci est notre plus petite valeur. 

Nous voulons simplement l'échanger ici, qui est ce que la fonction de permutation en bas fait, que nous venons d'écrire jusqu'à ensemble il ya quelques minutes. Donc, il devrait vous être familier. Et puis il sera simplement itérer à travers jusqu'à ce qu'il atteigne tout le chemin à la fin, ce qui signifie que vous avoir des éléments zéro non trié et tout le reste a été réglé. Donner un sens? Un peu plus concrètement? L'aide de code? 

ÉTUDIANT: Pour une taille, vous ne vraiment définir ou modifier, comment sait-il? 

ENSEIGNANT: Donc, une chose à remarque ici est la taille de int. Nous disons donc dans ce genre sort-- est une fonction en ce qu'il est case-- sélection sorte, il est passé avec la fonction. Donc, si il n'a pas été adopté , vous feriez quelque chose comme avec la longueur de la matrice ou si vous souhaitez effectuer une itération dans pour trouver la longueur. Mais parce qu'il est passé en, nous pouvons simplement utiliser. Vous assumez juste que l'utilisateur vous a donné une taille valide représente réellement une taille de votre tableau. Cool? 

Si vous les gars avez des problèmes avec ces ou si vous voulez plus pratique de codage sortes sur votre propre, vous devriez aller à study.cs50. Il est un outil. Ils ont un correcteur qui vous pouvez réellement écrire. Ils font pseudo. Ils ont plus de vidéos et diapositives y compris ceux que je utilise ici. Donc, si vous vous sentez encore un peu floue, essayer cela. Comme toujours, venez me parler, trop. Question? 

L'ÉLÈVE: Voulez-vous dire la taille est préalablement défini? ENSEIGNANT: Oui. Taille est défini précédemment jusqu'à ici dans la déclaration de fonction. Alors vous supposez que cela a été adoptée en par l'utilisateur, et pour des raisons de simplicité, nous allons supposer que la utilisateur nous a donné la bonne taille. Laisser refroidir. Alors que la sélection sorte. Les gars, je sais que nous allons apprendre beaucoup de choses aujourd'hui. Il est un dense données pour la section. Donc, avec cela, nous allons aller à tri par insertion. 

Dáccord. Donc, avant que nous avons à faire notre analyse de l'exécution ici. Donc, dans le meilleur des cas, accordé depuis que je vous ai montré la table je l'ai déjà genre de celui-ci a donné loin. Mais le meilleur de l'exécution de cas, qu'est-ce que nous pensons? Tout triée. N carré. Quelqu'un at-il une explication pourquoi vous en pensez? 

ÉTUDIANTS: Vous faites la comparaison through-- ENSEIGNANT: Droit. Vous vous comparez à travers. À chaque itération, même si nous décrémenter ce par un, vous êtes toujours à la recherche à travers tout de trouver le plus petit. Donc, même si votre petite valeur est ici au début, vous êtes toujours comparer contre tout le reste pour vous assurer qu'il est la plus petite chose. Donc, vous vous retrouverez en cours d'exécution à travers n fois approximativement carré. Bien. Et ce qui est le pire des cas? Aussi n carré parce que vous allez à faire la même procédure. Donc dans ce cas, la sélection a en quelque sorte quelque chose que nous appelons aussi l'exécution prévue. Ainsi, dans les autres, nous savons juste les limites supérieures et inférieures. Selon la façon dont notre fou liste est non triés ou comment il est, ils varient entre n ou n carré. Nous ne savons pas. 

Mais parce que la sélection a le même genre pire et le meilleur des cas, qui nous dit que Peu importe le type de commentaires que nous avons ont, que ce soit complètement triés ou totalement triés inverse, il est va prendre la même quantité de temps. Donc, dans ce cas, si vous se souvenir de notre table, il y avait en fait une valeur qui ces deux types ne sont pas, qui est de l'exécution attendu. Donc, nous savons que chaque fois que nous courons sélection sorte, il est garanti à exécuter une durée de n carré. Il n'y a pas de variabilité. Il est juste prévu. Et, encore une fois, si vous voulez apprendre De plus, prendre CS 124 au printemps. Bien. Nous avons vu celui-ci. Laisser refroidir. Trier Alors insertion. Et je vais probablement à se frayer à travers cela. Je ne vais pas vous les gars ont coder. Nous allons marcher à travers elle. Donc, le tri par insertion est un peu de similaire à la sélection sorte dans ce que nous avons à la fois un non triés et triés partie du tableau. 

Mais ce qui est différent est que que nous traversons un par un, nous prenons simplement ce numéro est à côté de notre non triés, et trier correctement ce dans notre tableau trié. Il va faire plus de sens avec un exemple. Alors tout commence non triés, Tout comme avec la sélection sorte. Et nous allons régler ce problème en ordre croissant comme nous l'avons été. Donc, sur notre premier passage nous prenons la première valeur et nous disons, OK, vous êtes maintenant dans une liste par vous-même. 

Parce que vous êtes dans une liste par vous-même, vous sont triés. Félicitations pour être le premier élément de ce tableau. Vous êtes déjà triées sur votre propre. Alors maintenant, nous avons une triés et un tableau non trié. Alors maintenant, nous prenons la première. Qu'est-ce qui se passe entre ici et voici que nous disons, OK, nous allons regarder la première valeur de notre tableau non trié et nous allons à l'entrée dans son bonne place dans le tableau trié. 

Donc, ce que nous faisons est que nous prenons 5 et nous disons, OK, 5 est supérieur à 3, donc nous suffit d'insérer la droite à la droite de cette. Nous sommes bons. Alors que nous passons à notre prochain. Et nous prenons 2. Nous disons, OK, 2 est moins de 3, donc nous savons qu'il qui doit être à la devant notre liste maintenant. Donc, ce que nous faisons est que nous poussons 3 et 5 vers le bas et nous passons 2 dans le premier emplacement. Donc, nous ne faisons que de l'insérer dans au bon endroit, il devrait être. 

Ensuite, nous regardons notre prochain, et nous disons 6. OK, 6 est supérieure à tout dans notre tableau trié, si nous étiquetterons juste sur la fin. Et puis nous sommes à 4. La figure 4 est inférieur à 6, il est moins de 5, mais elle est supérieure à 3. Donc nous suffit d'insérer directement dans le milieu entre 3 et 5. Donc, pour en faire une petite peu plus concret, ici est le genre de idée de ce qui est arrivé. Ainsi, pour chaque élément non triés, nous déterminer où, dans la partie triée il est. 

Donc, en gardant à l'esprit la triés et non triés, nous avons à parcourir à travers la figure et où il inscrit dans le tableau trié. Et nous l'insérons en déplaçant le les éléments à droite de celui-ci vers le bas. Et puis nous gardons juste itérer jusqu'à ce que nous avoir une liste complètement trié où non triés est maintenant zéro et triée reprend la intégralité de notre liste. Donc, encore une fois, pour rendre les choses encore Plus concrètement, nous avons pseudo. 

Donc, fondamentalement, pour i est égale à 0 à n moins 1, qui est juste la longueur de notre tableau. Nous avons un élément qui est égal à la première matrice ou les premiers indices. Nous avons mis j égale à celle. Ainsi, alors que j est supérieur à zéro et le tableau, j moins 1 est supérieure à la élément, donc tout ce qui est à faire est faire en sorte que votre j représente vraiment la partie non triés du tableau. 

Ainsi, alors il est encore des choses pour trier et j moins un est-- ce est l'élément lui? J n'a jamais été défini ici. Il est un peu ennuyeux. Dáccord. Quoi qu'il en soit. Donc j moins 1, vous vérifiez l'élément avant. Vous dites, OK, est l'élément avant où je laisse de am-- effectivement tirer cela. Donc, disons que cela est comme sur notre deuxième passage. Donc je va être égal 1, ce qui est ici. 

Donc je va être égal à 1. Ce serait 2, 4, 5, 6, 7. Bien. Donc, notre élément dans ce cas va être égal à 4. Et nous avons quelques j qui est va être égal à 1. Oh, j est décrémentation. Voilà ce qu'il est. Donc j est égal à i, donc ce qu'il en est dit est que nous avançons, nous sommes en train de faire en sorte que nous ne sommes pas sur l'indexation de cette façon quand nous essayons à insérer choses dans notre liste triée. 

Ainsi, lorsque j est égal à 1 dans ce cas et tableau j moins One-- afin gamme j moins 1 2 est dans ce case-- si cela est supérieure à l'élément, puis tout cela est fait est changeant les choses. Donc dans ce cas, un tableau J moins un serait gamme zéro, ce qui est 2. La figure 2 est inférieure ou égale à 4, si ce ne l'exécute pas. Ainsi, le changement ne se déplace pas vers le bas. Qu'est-ce que ce fait ici est juste déplacer votre tableau trié vers le bas. Dans ce cas, effectivement, nous pourrait do-- faisons ce 3. Donc, si nous sommes à traverser avec cet exemple, nous sommes maintenant ici. Ce sont triés. Ceci est non triés. Cool? Donc i est égal à 2, alors notre élément est égal à 3. Et notre j est égal à 2. Donc, nous regardons à travers et nous dire, OK, est un tableau J moins un l'élément supérieur que nous cherchons à? Et la réponse est oui, non? La figure 4 est supérieur à 3 et j est 2, si ce code est exécuté. 

Alors maintenant, ce que nous faisons un tableau à 2, donc ici, nous les échanger. Donc, nous disons juste, OK, array à 2 va maintenant être 3. Et j va égaler j moins 1, qui est une. Voilà horrible, mais vous les gars avez l'idée. J est maintenant égal à 1. Et j éventail va juste être égale à notre élément, qui était de 4. Je effacé quelque chose que je ne devrait pas avoir ou quelque chose miswrote, mais vous les gars avez l'idée. 

Il déplacer à n. Et puis si ce l'était, il boucle nouveau et il dit, OK, j est 1 maintenant. Et ensemble j moins 1 est maintenant 2. Est 2 de moins que notre élément? Non? Cela signifie que nous avons inséré cet élément au bon endroit dans notre tableau trié. Ensuite, nous pouvons prendre cela et nous dire, OK, notre tableau trié est ici. Et il faudrait ce nombre 6 et être comme, OK, est inférieur à 6 ce numéro? Non? Laisser refroidir. Nous sommes très bien. 

Faites-le à nouveau. Nous disons 7. 7 est inférieure à la fin de notre tableau trié? Non. Nous sommes donc bien. Donc, ce serait réglé. Fondamentalement tout cela ne est il est dit prendre le premier élément de votre tableau non trié, savoir où il va dans votre tableau trié. Et cela prend juste soin de swaps de le faire. Vous fondamentalement juste échange jusqu'à ce qu'il soit au bon endroit. L'image visuelle est que vous êtes déplaçant tout vers le bas en faisant cela. 

Donc, il est comme la moitié tri à bulles-esque. Découvrez étude 50. Je recommande vivement d'essayer à coder sur votre propre. Si vous avez des questions ou vous voulez voir exemple de code pour un tri par insertion, se il vous plaît, faites-moi savoir. Je suis toujours là. Donc le pire des cas d'exécution et la meilleure exécution de cas. Comme vous le gars vu de la table je l'ai déjà vous a montré, il est à la fois n et n carré. 

Donc genre d'aller hors de ce que nous avons parlé sur nos sortes précédentes, pire cas d'exécution est que si il est complètement non triés, nous devons comparer l'ensemble de ces n fois. Nous faisons beaucoup de comparaisons parce que si il est dans l'ordre inverse, nous allons dire, OK, ce est le même, ce qui est bon, et celle-ci devra être comparé contre le premier à être déplacé en arrière. Et comme nous obtenons vers l'extrémité de queue, nous avons à comparer, comparer, et comparer contre tout. 

Donc, il finit par être n approximativement carré. Si elle est correcte, alors vous dites, OK, 2, vous êtes bon. 3, vous êtes par rapport à 2. Vous êtes doué. 4, vous comparez juste à la queue. Vous êtes doué. 6, comparer à la queue, vous êtes très bien. Ainsi, pour chaque place si elle est déjà triés, vous faites une comparaison. Donc, il est juste n. Et parce que nous avons une meilleure exécution de cas de n et le pire des cas l'exécution de n carré, on n'a pas d'autonomie prévu. 

Cela dépend de la chaos de notre liste il. Et encore une fois, un autre graphique et une autre table. Donc, les différences entre les genres. Je vais passer à travers de, je l'impression que nous avons parlé longuement sur la façon dont ils ont tous genre de varier et de lier ensemble. Donc, le tri par fusion est le dernier Je vais vous ennuyer avec les gars. Nous avons une image assez coloré. Donc, le tri par fusion est un algorithme récursif. Donc, ne vous les gars savent ce que une fonction récursive est? 

Tout le monde veut dire? Vous voulez essayer? Ainsi, une fonction récursive est juste une fonction qui appelle lui-même. Donc, si vous les gars sont familiers avec la suite de Fibonacci, qui est réputé récursive car vous prenez les deux précédents et ajoutez-les ensemble pour obtenir votre prochain. Donc récursif, je pense toujours de la récursivité comme une spirale si vous êtes comme la spirale vers le bas en elle. Mais il est juste une fonction qui se dit. 

Et, en fait, très rapidement je peut vous montrer à quoi ça ressemble. Donc récursif ici, si l'on regarde, ce sont la façon récursive à somme sur un tableau. Donc, tout ce que nous faisons est nous avons fonction de somme somme qui prend une taille et un tableau. Et si vous remarquez, la taille décrémente de un à chaque fois. Et tout ce qu'il fait est si x est égal à zero-- donc si la taille de la matrice est égale à zero-- elle renvoie zéro. 

Sinon, il résume ce dernier élément du tableau, et prend alors une somme de le reste de la matrice. Donc, il est juste de le décomposer en problèmes plus petits et plus petits. Longue histoire courte, la récursivité, fonction que lui-même appelle. Si cela est tout ce que vous avez sur ce, qui est ce qui est une fonction récursive. Si vous prenez 51, vous obtiendrez très, très à l'aise avec la récursivité. Il est vraiment cool. Il avait un sens à comme 3 heures une nuit. Et je me suis dit, pourquoi ai-je jamais l'utiliser? 

Donc, pour le tri par fusion, essentiellement ce qu'il va faire est qu'il est aller à le décomposer et de le briser vers le bas jusqu'à ce qu'il soit seulement des éléments simples. Les éléments simples sont faciles à trier. Nous voyons que. Si vous avez un élément, il est déjà considéré triée. Donc, sur une entrée de n éléments, si n est inférieur à 2, il suffit de retourner parce que les moyens il est soit 0 ou 1 comme nous l'avons vu. Ceux-ci sont considérés comme des éléments triés. 

Sinon briser en deux. Trier la première moitié, trier la deuxième la moitié, puis de les fusionner. Pourquoi il est appelé tri par fusion. Nous avons donc ici nous allons régler ces. Donc, nous continuons à les avoir jusqu'à ce que la taille du tableau est 1. Alors, quand il est 1, nous revenons juste parce que cela est un tableau trié, et cela est un tableau trié, et qui est un tableau trié, nous sommes tous triée. Alors ce que nous faisons est que nous commencer à les fusionner ensemble. 

Donc, la façon dont vous pouvez penser à la fusion est vous suffit de retirer le plus petit nombre de chacun des sous-réseaux et juste ajouter à la gamme émergé. Donc, si vous regardez ici, lorsque nous avons ces jeux nous ont 4, 6, et 1. Quand nous voulons fusionner celles-ci, nous regardons ces deux premiers et nous disons, OK, 1 est plus petit, il va vers l'avant. 4 et 6, il n'y a rien à comparer à, juste marquer sur la fin. 

Lorsque nous combinons les deux, nous avons juste prendre la plus petite des deux, il est donc 1. Et maintenant, nous prenons la plus petit de ces deux, de sorte que deux. Plus petite de ces deux, trois. Plus petit de ces deux, quatre, cinq, six. Donc, vous êtes juste arracher ces. Et parce qu'ils ont été triés au préalable, vous avez juste un comparaison chaque fois. Donc, plus de code ici, juste représentation. Donc, vous commencez au milieu et vous triez gauche et la droite et puis vous venez de fusionner ces. 

Et nous ne disposons pas de code pour fusionner ici. Mais, encore une fois, si vous allez sur étudier 50, il sera là. Sinon venir me parler si vous êtes encore confus. Alors qui est cool ici est que meilleur des cas, pire des cas, et l'exécution prévu sont tous en log n, qui est beaucoup mieux que nous avons vu pour le reste de nos sortes. Nous avons vu n au carré et ce que nous en fait obtenir ici est n log n, ce qui est excellent. 

Regardez comment beaucoup mieux ce qui est. Cette une belle courbe. Donc beaucoup plus efficace. Si jamais vous pouvez, utilisez le tri par fusion. Elle vous fera économiser du temps. Là encore, comme nous l'avons dit, si vous êtes dans cette région inférieure, il ne fait pas que beaucoup de différence. Vous vous levez à des milliers et des milliers d'entrées, vous voulez absolument un algorithme plus efficace. Et, encore une fois, notre belle table de tous sortes que vous les gars ont appris aujourd'hui. 

Donc, je sais que ça fait une journée dense. Ce ne va pas nécessairement pour vous aider avec votre jeu de processeurs. Mais je veux juste faire une mise en garde cet article ne concerne pas seulement psets. Tout ce matériel est juste jeu pour vos examens trimestriels. Et aussi si vous continuer avec CS, Ce sont ces points réellement importants que vous devez savoir. Ainsi, certains jours seront un peu plus d'aide pset, mais quelques semaines seront beaucoup plus de contenu réel cela peut ne pas sembler super- utile pour vous maintenant, mais je vous promets si vous continuez sur sera très, très utile. 

Voilà donc pour la section. Sur le fil. Je l'ai fait en une minute. Mais là vous allez. Et je vais avoir des beignets ou des bonbons. Quelqu'un est-il allergique à rien, d'ailleurs? Les œufs et le lait. Donc beignets sont un non? Dáccord. Bien. Chocolat non? Starburst. Starbursts sont bonnes. Dáccord. Nous allons avoir Starburst la semaine prochaine alors. Voilà ce que je vais prendre. Les gars, vous avez une très bonne semaine. Lire vos spécifications. 

Faites-moi savoir si vous avez des questions. PSEt deux qualités doivent être à vous de jeudi. Si vous avez des questions comment je graduée quelque chose ou pourquoi je graduée quelque chose comme je ne, se il vous plaît écrivez-moi, venez me parler. Je suis un peu cette folle semaine, mais je vous promets Je vais quand même répondre dans les 24 heures. Donc, avoir une grande semaine, tout le monde. Bonne chance pour votre jeu de processeurs.