[Jouer de la musique] 

ANDI PENG: Bienvenue à la semaine 3 de l'article. Merci, vous les gars, pour tous à venir à cette heure de début plus tôt aujourd'hui. Nous avons un beau petit groupe intime d'aujourd'hui. Donc, nous espérons que nous arriverons à finition, peut-être, au début, un peu plus tôt aujourd'hui. Alors vite, quelques-uns annonces pour l'ordre du jour aujourd'hui. Avant de commencer, nous sommes va aller un peu plus certains problèmes logistiques brèves, pset questions, débriefing, des choses comme ça. Et puis nous allons plonger en plein. Nous allons utiliser un débogueur GDB appelé à commencer à démystifier notre code, que David expliqué dans la leçon l'autre jour. Nous allons passer en revue les quatre types de sortes. Nous allons passer en revue les assez rapidement car ils sont assez intensive. Mais sachez que toutes les diapositives et code source sont toujours en ligne. Donc, se sentir libre, à votre lecture, à revenir en arrière et prendre un coup d'oeil. 

Nous allons passer par notation asymptotique, qui est juste une façon de fantaisie de dire «runtimes» où nous avons le grand O, qui David a expliqué dans la leçon. Et nous avons aussi Omega, qui est le runtime limite inférieure. Et nous allons parler un peu plus en profondeur sur la façon dont ces travaux. Et enfin, nous allons passer en revue la recherche binaire, parce que beaucoup d'entre vous qui ont déjà regarda vos psets savez probablement que qui est une question qui est dans votre pset. Donc, vous serez tous heureux que nous couvrons aujourd'hui. 

Et enfin, pour votre la section des commentaires, je fait de gauche à environ 15 minutes la fin pour aller un peu plus logistique de pset3, des questions, peut-être un peu d'orientation, si vous voulez, avant de commencer la programmation. Essayons donc de passer à travers le matériau assez rapidement. Et alors nous pouvons passer du temps prendre plus de questions pour le jeu de processeurs. D'ACCORD. 

Rapidement, de sorte que quelques-uns annonces avant de commencer aujourd'hui. Tout d'abord, bienvenue à faire à travers deux de vos psets. Je pris un coup d'oeil à your-- oui, nous allons obtenir une salve d'applaudissements pour celui-là. En fait, je suis vraiment, vraiment impressionné. Je graduée le premier pset pour vous les gars semaine et vous dernières gars ont fait incroyable. 

Style était sur le point à part quelques commentaires. Assurez-vous que vous êtes toujours commenter votre code. Mais vos psets étaient sur le point. Et garder. Et il est bon pour la niveleuse voir que vous les gars mettent autant d'efforts dans votre style et votre conception dans votre code que nous aimerions pour vous de voir. Donc, je suis de passage le long de ma gratitude pour le reste de l'AT. 

Cependant, il ya un quelques questions de débriefing Je veux juste revenir là-dessus rendrait ma vie à la fois et beaucoup de l'autre AT 'vit un peu plus facile. Tout d'abord, je l'ai remarqué week-- passé combien d'entre vous ont été en cours d'exécution sur check50 votre code avant de vous présenter? D'ACCORD. Donc tout le monde devrait faire check50, because-- un secret-- nous fait check50 exécuter dans le cadre de notre rectitude scripts pour tester votre code. Donc, si votre code est un échec check50, selon toute vraisemblance, il va probablement l'échec de notre vérification ainsi. Parfois, vous les gars avoir les bonnes réponses. Comme, dans gourmand, certains vous avez les bons numéros, vous venez d'imprimer quelques trucs supplémentaires. Et ce truc supplémentaire ne parvient pas fait le chèque, parce que l'ordinateur ne fonctionne pas vraiment savoir ce qu'il cherche. Et il suffit d'exécuter à travers, voir que votre sortie ne comparons ce que nous attendons la réponse être, et marquer il est faux. 

Et je sais ce qui est arrivé dans certains de vos cas cette semaine. Je suis donc retourné et manuellement reclassé le code de tout le monde. Dans l'avenir, cependant, s'il vous plaît, s'il vous plaît assurez- que vous êtes en cours d'exécution 50 vérifier sur votre code. Parce qu'il est une sorte de douleur pour la TA d'avoir à revenir en arrière et reclasser manuellement chaque pset pour chaque unique, par exemple peu raté. Donc, je ne prenais pas hors des points. Je pense que je suis parti peut-être un ou deux pour la conception. À l'avenir cependant, si vous ne check50, points seront prises off pour l'exactitude. 

En outre, psets sont en raison vendredi à midi. Je pense qu'il ya un sept minutes période de grâce tard que nous vous donnons. Par temps de Harvard, ils sont autorisés à sept minutes de retard à tout. Donc, ici, à Yale, nous allons adhérer à cela aussi. Mais à peu près, à 12:07, si votre pset est pas, ça va être marqué comme fin. Et alors qu'il est marqué plus tard, je suis l'TA-- toujours en cours pour être titrant vos psets. Donc, vous verrez toujours une note apparaît. Cependant, à savoir que la fin du semestre, tous les psets fin sera juste automatiquement mis à zéro par l'ordinateur. 

Nous faisons cela pour deux raisons. Un, parfois nous sommes excusé, comme les excuses de Dean, plus tard que je ne sais pas encore. Donc, nous nous plaisons à nous assurer que nous classement tout juste au cas où, comme, je suis manquant l'excuse d'un doyen. Et d'autre part, garder à l'esprit, vous pouvez toujours déposer un pset que a des points d'intégrales. Et si nous aimons au grade tous vos psets juste pour vous assurer que votre champ de là et vous les essayer. Donc, même si il est tard, vous aurez toujours obtenir un crédit pour les points de portée, je pense. 

Donc morale de l'histoire est, assurez- vous que vos psets sont en sur-temps. Et si elles ne sont pas dans le temps, sachez qu'il est pas très grande. Ouais, avant de passer, quelqu'un at- Pour toute question concernant les commentaires des pset? Ouais. 

Public: Avez-vous dit que nous peut déposer l'un des psets? 

ANDI PENG: Ouais. Donc, il ya neuf psets globale au cours du semestre. Et si vous avez portée points-- donc portée est juste, assez bien, essayez-vous le problème, faites-vous mettre dans le temps, montrez-vous que vous avez démontré que vous avez lu la spec. Voilà à peu près la portée. Et si vous accomplissez points de périmètre, nous peut déposer le plus bas un sur la pleine portée. Voilà donc à votre avantage de compléter et essayer chaque jeu de processeurs. 

Même si aucun des upload-- les travailler, de les télécharger tous. Et puis nous espérons être en mesure de vous donner certains de ces points derrière. Frais. D'autres questions? Génial. 

Deuxièmement, bureau heures-- quelques-uns notes rapides sur les heures de bureau. Alors d'abord, venir plus tôt dans la semaine. Personne est jamais à les heures de bureau le lundi. Christabel est venu à les heures de bureau la nuit dernière. Ouais, Christabel. Et qu'est-ce que nous avons au bureau heures la nuit dernière, Christabel? 

PUBLIC: Nous avons eu de la crème glacée. 

ANDI PENG: Donc, ce qui est juste, nous avions crème glacée à des heures de bureau la nuit dernière. Bien que je ne peux pas vous promettre que nous aurons de la crème glacée aux heures de bureau chaque semaine, ce que je peux vous promettre est qu'il y aura un significativement mieux ratio élève TA. Comme légitime, il est comme trois à un. Considérant que, qui contraste avec Jeudi, vous avez environ 150 vraiment insisté sur les enfants et pas de crème glacée. Et il est tout simplement pas productif pour tout le monde. Donc morale de l'histoire est, venir tôt pour les heures de bureau et de bonnes choses qui va se passer. 

Aussi, être prêts à poser des questions. Tu sais? Indépendamment de ce que PS, je penser, ont été dit, nous avons reçu quelques étudiants qui viennent de jeudi à, comme 10:50 ne pas avoir lu la spec être comme aide-moi, aidez-moi. Malheureusement, à ce moment-là, il ya pas beaucoup que nous pouvons faire pour vous aider. Donc, s'il vous plaît venez tôt dans la semaine. Venez tôt pour les heures de bureau. Soyez prêts à poser des questions. Assurez-vous que vous, en tant un étudiant, où sont vous devez être de sorte que la AT peut vous guider le long, qui est ce que les heures de bureau doit être attribuée à. 

Deuxièmement, donc je sais professeurs tenons à nous surprendre avec des tests. Je devais un professeur ceux comme, yo, par la manière, rappeler que mi-parcours vous avez lundi prochain. Ouais, je ne savais pas à ce sujet mi-parcours. Donc, je vais être que TA qui vous rappelle tout ce quizz 0-- parce que, vous savez, nous sommes CS. Maintenant que nous avons des tableaux fait, vous obtenez pourquoi il est quizz 0, pas interroger 1, hein? D'ACCORD. Oh, je suis arrivé quelques rires sur celui-là. D'ACCORD. 

Donc quizz 0 sera le 14 Octobre si vous êtes dans la section du lundi au mercredi et 15 Octobre si vous êtes dans la section du mardi au jeudi. Cela ne vaut pas pour les ceux d'entre vous à Harvard who-- Je pense que vous serez tous prendre vos quiz sur la 14e. 

Donc oui, la semaine prochaine, si David, en cours, va, Ouais, donc à ce sujet Quiz semaine prochaine, vous tous ne sera pas choqué parce vous êtes venu à l'article et vous savez que votre Quiz 0 est dans deux semaines. Et nous aurons avis sessions et tout. Donc pas de soucis au sujet avoir peur pour ça. Toutes les questions before-- des questions à toutes les questions logistiques relatives, classement, les heures de bureau, les articles? Ouais. 

Auditoire: Alors, le quiz est va être durant conférence? 

ANDI PENG: Ouais. Donc, le quiz, je pense, est de 60 minutes allouées dans cet intervalle de temps que vous venez de prendre dans la salle de conférence. Donc, vous ne devez pas venir sur, comme un hasard 19h00. C'est parfait. Ouais. Frais. 

Bien. Nous allons donc introduire un concept de vous cette semaine que David a déjà genre de touché dans cette conférence la semaine dernière. Il a appelé GDB. Et combien d'entre vous, tandis que dans au cours de la rédaction de vos psets, ont remarqué un gros bouton qui dit "Debug" sur le haut de votre IDE? D'ACCORD. Alors maintenant, nous allons réellement obtenir pour déterrer le mystère de ce qui touche effectivement Est-ce que. Et je vous garantis, il est un belle, belle chose. 

Donc, jusqu'à présent, je pense il ya eu deux choses les étudiants ont été généralement faire lors du débogage psets. Un, ils ajoutent soit dans printf () - donc, tous les quelques lignes, ajoutent-ils dans un printf () - Oh, quelle est cette variable? Oh, quelle est cette variable maintenant-- et vous sorte de voir la progression de votre code tel qu'il fonctionne. Ou la deuxième méthode enfants font est qu'ils suffit d'écrire le tout puis aller comme ça à la fin. Espérons que cela fonctionne. Je vous garantis, GDB est mieux que ces deux méthodes. Ouais. Donc, ce sera votre nouveau meilleur ami. Parce qu'il est une belle chose que, visuellement, affiche à la fois ce qui fait votre code à un point spécifique ainsi que ce que l'ensemble de votre les variables sont porteurs, comme ce que leurs valeurs sont, à ce point précis. Et de cette façon, vous pouvez vraiment définir des points d'arrêt dans votre code. Vous pouvez exécuter ligne par ligne. Et GDB devra simplement pour vous, affiché pour vous, ce que toutes vos variables sont, que font-ils, ce qui se passe dans le code. Et de telle manière, il est tellement plus facile de voir ce qui se passe à la place de printf-ing ou l'écriture de vos déclarations. 

Donc, nous allons faire un exemple de cela plus tard. Donc, cela semble un peu abstrait. Pas de soucis, nous ferons des exemples. Et si essentiellement, les trois plus grands, fonctions les plus utilisées dont vous aurez besoin dans GDB sont l'étape suivante, au cours, et l'étape en boutons. Je vais diriger là, en fait, à l'heure actuelle. 

Ainsi, vous pouvez voir que tous les gars ou devrais-je agrandir un peu? À l'arrière, pouvez-vous le voir? Devrais-je agrandir? Juste un petit peu? OK cool. Nous y voilà. D'ACCORD. 

Je dois donc, ici, mon mise en œuvre pour les gourmands. Et tandis que beaucoup d'entre vous les gars écrit gourmand en boucle while que form-- est une manière parfaitement acceptable de le faire it-- une autre façon de le faire est de simplement diviser dans le modulo. Parce que vous pouvez avoir votre valeur, puis ont votre reste. Et puis vous pouvez juste ajouter tous ensemble. Est-ce que la logique de ce que je fais ici donner un sens à tout le monde, avant de commencer? Genre de? Frais. Génial. Il est un morceau sexy de code, je dirais. Comme je le disais, David, dans sermonner, après un certain temps, vous commencez à voir tout le code comme quelque chose qui est beau. Et parfois, quand vous voyez belle code, il est un tel sentiment merveilleux. 

Donc, cependant, alors que ce code est très beau, il ne fonctionne pas correctement. Donc, nous allons courir sur cette check50. Vérifiez 50 20-- oop. 2? Est-ce que pset2? Ouais. Oh, pset1. D'ACCORD. Donc, nous courons check50. 

Et comme vous pouvez le voir ici les gars, il est à défaut d'un couple de cas. Et pour certains d'entre vous, dans la Bien sûr de faire vos ensembles de problèmes, vous êtes comme, ah, pourquoi ça ne marche pas. Pourquoi est-il travaille depuis un certain valeurs, mais pas pour d'autres? Eh bien, GDB va vous aider à comprendre pourquoi ces entrées ne fonctionnaient pas. 

D'ACCORD. Voyons donc, l'un des Je contrôles échouait dans check50 est la valeur d'entrée de 0,41. Alors que la réponse correcte vous devriez obtenir est un 4. Mais au lieu de quoi je imprimer est le 3-n, ce qui est incorrect. Alors disons simplement exécuter manuellement, juste assurez-vous que check50 travaille. Faisons ./greedy. Oups, je dois faire gourmand. Nous y voilà. Maintenant ./greedy. 

Combien est dû? Faisons 0,41. Et oui, nous voyons ici qu'il est en sortie 3 quand la bonne réponse, en fait, devrait être de 4. Donc, nous allons entrer GDB et voir comment nous peut aller sur la fixation de ce problème. 

Donc, la première étape débogage toujours votre code est de mettre un point d'arrêt, ou un point à laquelle vous vouloir l'ordinateur ou le débogueur pour commencer à regarder. Donc, si vous ne faites pas vraiment savoir ce que votre problème est, généralement, la chose typique que nous voulons faire est de régler notre point d'arrêt à principal. Donc, si vous les gars pouvez voir cette bouton rouge juste là, yep, qui me fixant un point d'arrêt pour la fonction principale. Je clique sur cela. 

Et puis je peux aller jusqu'à mon bouton de débogage. Je frappe ce bouton. Permettez-moi de faire un zoom arrière si je peux. Nous y voilà. Donc, nous avons, ici, un panneau sur la droite. Je suis désolé, les gars dans le dos, vous ne peut pas vraiment voir vraiment bien. Mais essentiellement, tous les ce panneau de droite est en train de faire est de garder une trace de l'évidence à la fois ligne, qui est la ligne de code que l'ordinateur est en cours d'exécution, ainsi que tous vos variables ici. 

Donc, vous avez cents, pièces de monnaie, n, tous déclaré à des choses différentes à ce point. Pas de soucis, parce que nous avons pas réellement les initialisée à toutes les variables encore. Donc, dans votre ordinateur, votre ordinateur est juste de voir, oh, 32767 était la dernière fonction utilisée de cet espace de mémoire dans mon ordinateur. Et donc voilà où cents est actuellement. Mais pas une fois que vous exécutez le code, il devrait devenir initialisé. 

Donc, nous allons passer par ligne par ligne, ce qui se passe ici. D'ACCORD. Donc ici sont les trois boutons que je viens expliqué. Vous avez le jeu, ou la fonction Exécuter, bouton, vous avez la Étape sur le bouton, et vous avez également l'étape en touche. Et essentiellement, tous les trois leur suffit d'aller dans votre code et faire des choses différentes. 

Donc, généralement, quand vous êtes le débogage, nous ne voulons pas simplement sur Lecture, Parce que le jeu sera juste courir votre code à la fin de celui-ci. Et puis vous ne sera pas réellement savoir ce que votre problème est sauf si vous définissez plusieurs points d'arrêt. Si vous définissez plusieurs points d'arrêt, Il va juste automatiquement courir d'un point d'arrêt, à l'autre, à l'autre. Mais dans ce cas, nous avons juste celui-là, parce que nous vouloir travailler notre chemin de haut en bas en bas. Donc, nous allons ignorer ce bouton en ce moment aux fins de ce programme. 

Donc l'étape sur la fonction juste étapes sur chaque ligne et vous dit ce l'ordinateur est en train de faire. L'étape en fonction va dans la fonction réelle qui est sur votre ligne de code. Ainsi, par exemple, comme printf (), qui est fonction, non? Si je voulais physiquement étape dans la fonction printf (), Je voudrais aller effectivement dans le morceau de code où printf () a été écrit et voir que se passe-t-il ici. 

Mais généralement, nous supposons que le code que nous vous donnons fonctionne. Nous supposons que le printf () fonctionne. Nous supposons que getint () fonctionne. Il n'y a donc pas besoin de entrer dans ces fonctions. Mais si il ya des fonctions que vous vous écrivez que vous souhaitez vérifier sur ce qui se passe, vous voulez à l'étape dans cette fonction. 

Donc maintenant, nous allons juste enjamber ce morceau de code. Voyons donc. Oh, impression, "Oh hai, comment beaucoup de changement est dû? " Nous ne nous soucions pas. Nous savons que ce travail, donc nous intervenons sur elle. 

Alors n, qui est notre flotteur Nous avons initialized-- ou declared-- au sommet, nous sommes maintenant égale à celle de GetFloat (). Donc, nous allons passer par-dessus cela. Et nous voyons à la en bas ici, le programme me demandant de saisir une valeur. Donc, nous allons saisir la valeur que nous voulons pour tester ici, qui est de 0,41. Génial. 

Alors maintenant n-- Avez-vous les gars voir ici, au bottom-- il est stored-- parce que nous ne sont pas encore arrondi, il est stockée dans ce géant comme flotteur qui est 0,4099999996, qui est assez proche de notre fins, dès maintenant, à 0,41. Et puis, nous le verrons plus tard, comme nous continuer d'intensifier sur le programme, après ici, n est devenu arrondie et est devenu 41 cents. Génial. Donc, nous savons que le travail de notre arrondissement. Nous savons que nous avons la bon nombre de cents, de sorte que nous savons que cela est pas vraiment le problème. 

Donc nous continuons pas à pas dans ce programme. Nous allons ici. Et donc après cette ligne de code, nous devrait savoir combien de trimestres que nous avons. Nous intervenons plus. Et vous voyez que nous faisons, en fait, avons une trimestre parce que nous avons soustrait 25 de notre valeur initiale de 41. Et nous avons 16 gauche pour nos cents. 

Tout le monde comprend comment le programme multiplie par et pourquoi cents est maintenant devenu 16 et pourquoi, aujourd'hui, des pièces de monnaie est devenue 1? Tout le monde est cette logique? Frais. Donc à partir de ce point, le le travail de programme, non? Nous savons qu'il fait exactement ce que nous voulons. Et nous avons fait pas réellement avoir à imprimer, oh, ce est cents à ce point, ce qui est des pièces à ce stade. 

Nous continuons à passer par le programme. Enjamber. Frais. Nous passons en revue dimes. Génial. Nous voyons que cela a pris off 0,10 $ pour un sou. Et maintenant nous avons deux pièces. C'est correct. 

Nous passons en revue quelques centimes et nous voyons qui nous reste plus cents. Hmm, qui est étrange. Jusqu'à ici, au programme, je devais avoir soustrait mes sous. Peut-être tout simplement je ne suis pas faire ce droit en ligne. Et hélas, vous pouvez voir ici, parce que nous savons que nous intensifions à travers les lignes 32 et 33, qui est là notre programme avait indûment les variables courent. Donc, nous pouvons regarder et voir, oh, Je soustrayant cents ici, mais je ne suis pas fait ajouter à ma valeur de la pièce. Je ajoutant cents. Et je ne veux pas ajouter à cents, je tiens à ajouter aux pièces. Donc, si nous changeons cela à pièces de monnaie, nous avons un programme de travail. Je peux courir check50. Vous pouvez juste sortir sur GDB droit ici et puis exécutez à nouveau check50. Je ne pouvais le faire. Je dois faire gourmand. 0,41. Et ici, il est l'impression la bonne réponse. 

Donc, comme vous les gars pouvez le voir, GDB est un outil vraiment puissant quand nous avons tellement de code passe et tellement de variables qu'il est difficile pour nous, comme un être humain, à garder la trace. L'ordinateur, dans la BDG débogueur, a la capacité de garder une trace de tout. Je sais que, dans Visionaire, vous les gars probablement aurait pu frapper quelques erreurs de segmentation parce que vous dirigiez en dehors des limites de votre tableau. Dans l'exemple de César, qui est exactement ce que je l'ai mis en œuvre ici. 

Donc je oublié de vérifier ce qui se passerait si je ne pas avoir deux arguments de ligne de commande. Je ne ai pas mis dans ce chèque. Et si je cours je me mis Debug-- mon point d'arrêt pour y droite. Je cours de débogage. 

D'ACCORD. Ouais. Donc en fait, GDB était censé pour moi ont dit qu'il y était une erreur de segmentation il. Je ne sais pas ce qui se passait là, mais quand je l'ai couru, il travaillait. Lorsque vous exécutez lignes de code et à travers GDB pourrait juste soudainement cesser de fumer sur vous, monter et regarder ce que l'erreur est rouge. Il vous dira, hey, vous eu une erreur de segmentation, ce qui signifie que vous avez essayé de l'accès espace dans un tableau qui n'a pas existé. Ouais. 

Ainsi, dans le prochain problème prévues cette semaine, les gars va probablement avoir beaucoup de les variables flottant autour. Tu ne vas pas être sûr de ce que ils signifient tous à un certain point. Donc GDB va vraiment vous aider à déterminer ce qu'ils sont tous égalant et être en mesure de voir que visuellement. Quelqu'un est confus sur la façon tout cela a été de travailler? Frais. Bien. Donc, après cela, nous sommes aller à plonger en sont quatre différents types de tri pour cette semaine. Combien d'entre vous, d'abord de tous, avant de commencer, avoir lu l'ensemble de spécifications pour pset3? D'ACCORD. Je suis fier de vous les gars. Voilà comme la moitié de la classe, qui est beaucoup plus que la dernière fois. 

Voilà donc grande, parce que quand nous parlons du contenu dans lecture-- ou désolé, dans section-- Je aime de rapporter beaucoup de cela revenir à ce que le pset est et comment vous voulez mettre en œuvre que dans votre pset. Donc, si vous venez d'avoir lire la spec, il va être beaucoup plus facile pour vous de comprendre de quoi je parle quand je dis, Oh hey, cela pourrait être une très bon endroit pour mettre en œuvre ce genre. Donc ceux d'entre vous qui ont lu le spec savoir que, dans le cadre de votre pset, vous allez avoir à écrire un type de tri. Donc, cela peut être très utile pour beaucoup d'entre vous aujourd'hui. 

Donc, nous allons commencer avec, essentiellement, le type le plus simple, de tri, le tri de sélection. L'algorithme typique pour comment nous allions à ce sujet est-- David a traversé ces tout en conférence, donc je vais rapidement passer le long ici-- est essentiellement, vous avoir un tableau de valeurs. Et puis, vous trouvez la plus petite valeur non triés et vous changez cette valeur avec la première valeur non triés. Et puis vous continuez à répéter avec le reste de votre liste. 

Et voici une explication visuelle de la façon dont cela pourrait fonctionner. Ainsi, par exemple, si nous devions commencer avec un tableau de cinq éléments, l'index 0 à 4, avec 3, 5, 2, 6, 4 et valeurs placé dans le array-- tellement en ce moment, nous allons juste à assumer qu'ils sont tous non triés parce que nous avons pas testé autrement. 

Alors, comment une sorte de sélection serait le travail est qu'il serait premier courir à travers la totalité de la matrice non triés. Il serait choisir la plus petite valeur. Dans ce cas, 3, droit maintenant, est la plus petite. Il obtient à 5. Nope, 5 ne soit pas supérieure than-- ou désolé, est pas inférieure: 3. Ainsi, la valeur minimale est toujours 3. Et puis vous arrivez à 2. L'ordinateur voit, oh, 2 est inférieure à 3. 2 doit désormais être la valeur minimale. Et ainsi de 2 swaps avec cette première valeur. 

Donc, après un passage, nous ne voyons en effet que le 2 et le 3 sont inversés. Et nous allons tout simplement continuer à faire cette fois avec le reste de la matrice. Nous allons donc à courir seulement à travers les quatre derniers index de la matrice. Nous verrons que 3 est la valeur minimale suivante. Donc, nous allons échanger qu'avec 4. Et puis nous allons juste garder qui traverse jusqu'à ce que, finalement, vous arriver à un tableau trié dans laquelle 2, 3, 4, 5, et 6 sont tous classés. Tout le monde comprend la logique de la façon dont une sorte de sélection fonctionne? 

Vous avez juste une sorte d'une valeur minimale. Vous gardez une trace de ce qui est. Et chaque fois que vous le trouvez, vous échangez avec la première valeur de la array-- ou, pas la première value-- la valeur suivante dans le tableau. Frais. 

Donc, comme vous les gars genre de vu d'un bref aperçu, nous allons Pseudocode cela. Donc, si vous les gars dans le dos voulez former un groupe, tout le monde à une table peut former un petit partenaire, je vais pour vous donner des gars comme trois minutes de parler seulement à travers la logique, en anglais, de la façon dont nous pourrions être en mesure de mettre en œuvre pseudo pour écrire une sorte de sélection. Et il ya des bonbons. S'il vous plaît venir et obtenir des bonbons. Si vous êtes dans le dos et que vous voulez Candy, je peut jeter des bonbons à vous. En fait, le faire refroidir vous--. Oh pardon. D'ACCORD. 

Donc, si nous aimerions, en tant une classe, écriture pseudo- pour savoir comment on pourrait approcher ce problème, se sentent juste libre. Je vais faire un tour et, dans l'ordre, demander aux groupes pour la ligne suivante de ce que nous devrions faire. Donc, si vous voulez les gars pour commencer off, quelle est la première chose à faire lorsque vous essayez de mettre en œuvre un moyen de résoudre ce programme pour trier sélectivement une liste? Disons simplement supposer que nous avoir un tableau, d'accord? 

AUDIENCE: Vous voulez créer une certaine sorte de [inaudible] que vous êtes qui traverse l'ensemble de votre réseau. 

ANDI PENG: Droit. Donc, vous allez vouloir pour itérer dans chacun des espaces, non? Tellement bon. Si vous voulez les gars de me donner le line-- prochaine ouais, dans le dos. 

AUDIENCE: Vérifiez-les tout pour la plus petite. 

PENG ANDI: Il nous allons. Donc, nous voulons passer et vérifiez voir ce que la valeur minimale est, non? Je vais abréger que pour "min." Qu'est-ce que vous voulez les gars à faire après vous avez trouvé la valeur minimum? 

AUDIENCE: [inaudible] ANDI PENG: Donc, vous allez vouloir changer avec le premier de ce tableau, droit? Voilà le début, je vais dire. Bien. Alors, maintenant que vous avez troqué la première l'un, que voulez-vous faire après? Alors maintenant, nous savons que celui-là doit être la plus petite valeur, non? Ensuite, vous avez un repos supplémentaire de la matrice qui est non triés. Donc ce que vous voulez faire ici, si vous gars veulent me donner la ligne suivante? AUDIENCE: Alors vous voulez parcourir pendant le reste de la matrice. ANDI PENG: Ouais. Et ce qui ne itérer sorte de impliquons nous aurons probablement besoin? Quel genre de-- 

AUDIENCE: Oh, une variable supplémentaire? ANDI PENG: Probablement une autre boucle, non? Donc, nous allons probablement vouloir pour itérer through-- grande. Et puis vous allez revenir en arrière et vérifier probablement le minimum à nouveau, droit? Et vous allez continuer à répéter ce, parce que les boucles juste aller pour continuer à fonctionner, non? 

Donc, comme vous les gars pouvez le voir, nous avons juste avoir un pseudo générale de la façon dont nous voulons que ce programme à regarder. Cette itération ici, ce que nous faisons généralement besoin d'écrire dans notre code si nous voulons pour parcourir une tableau, ce type de structure? Je pense que Christabel déjà dit cela avant. 

PUBLIC: Une boucle for. 

ANDI PENG: Une boucle for? Exactement. Donc, ce qui est probablement va être une boucle for. Qu'est-ce qu'un chèque ici va impliquer? Typiquement, si vous souhaitez vérifier si quelque chose est quelque chose else-- 

Audience: Si. 

ANDI PENG: Un si, à droite? Et puis le swap Ici, nous allons aller plus tard, parce que David a traversé qu'en conférence ainsi. Et puis la deuxième itération implies-- 

PUBLIC: Une autre boucle. 

ANDI PENG: --another boucle for, exactement. Donc, si nous sommes à la recherche à cela correctement, nous peut voir que nous sommes probablement allez avoir besoin d'un imbriquée boucle avec une instruction conditionnelle là puis une pièce réelle de code qui est aller à échanger les valeurs. Donc, je viens généralement écrits un code de pseudo ici. Et puis nous allons en fait physiquement, en tant que classe, essayer de mettre en œuvre aujourd'hui. Revenons dans cet IDE. 

Uh-oh. Pourquoi est-ce que pas-- il est là. D'ACCORD. Désolé, je vais essayer de zoomer un peu plus. Nous y voilà. Tout ce que je fais ici est que je avez créé un programme appelé «sélection / sort.c." Je ai créé un tableau de neuf valeurs, 4, 8, 2, 1, 6, 9, 7, 5, 3. Actuellement, que vous le pouvez voient, ils ne sont pas ordonnés. n va être le numéro vous indique la quantité de valeurs vous avez dans votre tableau. Dans ce cas, nous avons neuf valeurs. Et je viens de recevoir une boucle ici qui imprime le tableau non trié. 

Et à la fin, je dois aussi pour un boucle qui imprime simplement à nouveau. Donc, théoriquement, si ce programme fonctionne correctement, à la fin, vous devriez voir un imprimé pour la boucle dans lequel 1, 2, 3, 4, 5, 6, 7, 8, 9 sont tous correctement dans l'ordre. 

Donc, nous avons notre pseudo ici. Quelqu'un veut to-- Je suis juste va aller demander volunteers-- me dire exactement ce à taper si nous voulons, d'abord, simplement itérer à travers le début de ce tableau? Quelle est la ligne de code Je suis probablement avoir besoin ici? 

AUDIENCE: [inaudible] 

ANDI PENG: Ouais, sentir to-- désolé gratuitement, vous ne pas avoir à tenir up-- sensation sans élever la voix un peu. 

Public: Pour int i vaut 0-- 

ANDI PENG: Ouais, bon. 

AUDIENCE: i est inférieur à la longueur du tableau. 

ANDI PENG: Donc, gardez à l'esprit ici, parce que nous ne pas avoir une fonction que nous dit la longueur d'un tableau, nous avons déjà un valeur qui stocke cela. Droit? Une autre chose à garder dans mind-- dans un tableau des neuf valeurs, ce sont les indices? Disons simplement que ce tableau était de 0 à 3. Vous voyez que le dernier l'indice est en fait 3. Il est pas 4, même si il ya quatre valeurs dans le tableau. 

Donc, ici, nous devons être très prudents de ce que notre condition pour la longueur CA va etre. 

Public: Ce ne serait pas n moins 1? ANDI PENG: Ça va n moins 1, exactement. Est-ce logique, pourquoi il est n moins 1, tout le monde? Il est parce que les tableaux sont indexés zéro. Ils commencent à 0 et vont jusqu'à n moins 1. Ouais, il est un peu délicat. D'ACCORD. Et alors-- AUDIENCE: Isnt'1 que déjà pris soin de bien, par tout simplement pas dire "inférieur ou égal à "et juste en disant" moins? " 

ANDI PENG: Voilà une très bonne question. Donc oui. Mais aussi, la façon dont nous sommes la mise en œuvre le droit de vérifier, vous devez comparer deux valeurs. Donc, vous voulez réellement quitter le »à« vide. Parce que si vous comparez celui-ci, tu ne vas pas rien avoir après à comparer, à droite? Ouais. Donc i ++. Ajoutons nos crochets dans. Oups. Génial. Donc, nous avons le début de notre boucle externe. Alors maintenant, nous voulons probablement créer une variable pour garder la trace de la plus petite valeur, non? Quelqu'un veut-il me donner le ligne de code qui ferait cela? Que devons-nous si nous allons à vouloir stocker quelque chose? 

Droit. Peut-être un meilleur nom pour que serait être-- "temp" totalement works-- peut-être un plus bien nommé serait, si nous voulons le plus petit value-- 

AUDIENCE: Min. ANDI PENG: min, là nous allons. min serait bon. Et là, qu'est-ce que nous vouloir initialiser à? Ceci est un peu délicat. Parce que maintenant à la à compter de ce tableau, vous avez rien regardé, non? Alors quoi, automatiquement, si nous sommes juste sur i est égal à 0, Que voulons-nous pour initialiser notre première valeur minimale à? AUDIENCE: i. ANDI PENG: i, exactement. Christabel, pourquoi voulons-nous pour l'initialiser à i? 

AUDIENCE: Parce que, eh bien, nous commençons à 0. Donc, parce que nous avons rien à comparer à, au minimum finira par être 0. 

ANDI PENG: Exactement. Alors, elle est tout à fait exact. Parce que nous avons pas réellement regardé encore rien, nous ne savons pas ce que notre valeur minimale est. Nous voulons simplement l'initialiser à i, qui, actuellement, se trouve ici. Et comme nous continuons à déplacer vers le bas de ce tableau, nous verrons que, à chaque passe supplémentaire, i incréments. Et à ce moment, i va probablement à vouloir être le minimum, parce que ça va être tout ce que est le début de la matrice non triés. Frais. 

Alors maintenant, nous voulons ajouter une boucle qui est ici va parcourir la non triés, ou dans le reste de ce tableau. Quelqu'un veut-il me donner un ligne de code qui ferait cela? Hint-- Que devons-nous ici? Qu'est-ce qui va se passer dans cette boucle? Ouais. PUBLIC: Nous aimerions donc voulons avoir un nombre entier différent, parce que nous sommes en cours d'exécution à travers le reste du tableau au lieu de la i, alors peut-être j. 

ANDI PENG: Ouais, j sonne bien pour moi. Égal? 

Auditoire: Alors, serait i + 1, parce vous commencez à la valeur suivante. Ensuite, à la end-- à nouveau, j est moins de n moins 1, et ensuite j ++. ANDI PENG: Grande. 

Et puis ici, nous allons vouloir de vérifier pour voir si notre condition est remplie, droit? Parce que vous voulez changer la valeur minimale si elle est effectivement plus petit que ce que vous êtes en le comparant, non? Alors qu'est-ce qu'on va vouloir ici? Vérifiez. Quel type de déclaration sans doute allons-nous ti veulent utiliser si nous vouloir vérifier quelque chose? 

PUBLIC: Une instruction if. 

ANDI PENG: Une instruction if. Donc si-- et ce qui va être la condition que nous voulons l'intérieur de notre if? 

Audience: Si la valeur de j est inférieure à la valeur de i-- 

ANDI PENG: Exactement. Donc si-- donc ce tableau est appelé «tableau». Génial. Donc, si ce array-- était-ce? Répète ça. 

Audience: Si array-j est inférieure à array-i, alors nous changerais min. Ainsi, le min serait j. 

ANDI PENG: Est-ce logique? D'ACCORD. Et maintenant, ici-bas, nous avons fait vouloir mettre en œuvre l'échange, non? Donc, rappeler, en conférence, que David, quand il essayait de the-- ce qui était échanger jus d'orange et milk-- it-- 

Public: Ce fut brut. 

ANDI PENG: Ouais, ça était une sorte de brute. Mais ce fut une assez bonne notion de temps démontrer. Alors, pensez à vos valeurs ici. Vous avez un tableau de min, un tableau de i, ou ce que nous avons essayé de permuter ici. Et vous avez probablement ne pouvez pas les verser dans l'autre dans le même temps, non? Alors qu'allons-nous au besoin de créer ici afin d'échanger les valeurs correctement? 

PUBLIC: Une variable temporaire. 

ANDI PENG: Une variable temporaire. Alors, faisons int température. Voir, ce serait une meilleure temps to-- whoa, ce qui était-ce? D'ACCORD. Donc, cela aurait été une meilleure le temps de nommer le "temp." variable Alors, faisons int température. Qu'allons-nous à la température de consigne égale à ici? AUDIENCE: Min? PENG ANDI: Il est un peu délicat. Il ne fait pas d'importance à la fin. Il n'a pas d'importance ce que Pour vous choisissez d'échanger en aussi longtemps que vous vous assurez que vous êtes garder une trace de ce que vous échanger. 

PUBLIC: Il pourrait être array-i. 

ANDI PENG: Ouais, faisons ensemble-i. Et puis, ce qui est la ligne suivante de code que nous voulons avoir ici? AUDIENCE: array-i est égal tableau-j. ANDI PENG: Et enfin? AUDIENCE: array-j est égal tableau-i. Audience: ou un tableau-j égaux array-temp-- ou, temp. 

ANDI PENG: OK. Donc, nous allons courir et de voir ce si elle va travailler. Où en est-il? Oh, cela pose un problème. Voir, sur la ligne 40, nous sommes essayer d'utiliser array-j? Mais d'où vient j exister que dans? 

AUDIENCE: Dans la boucle. ANDI PENG: Droit. Alors qu'est-ce qu'on va avoir besoin de faire? 

AUDIENCE: Définir l'extérieur the-- AUDIENCE: Ouais, je suppose que vous avez à utiliser une autre instruction if, non? Donc, comme, si le minimum-- tout droit, laissez-moi réfléchir. 

ANDI Peng: Les gars, essayez de prendre un coup d'oeil de Let Voir, ce qui est quelque chose que nous pouvons faire ici? 

AUDIENCE: OK. Donc, si le minimum ne correspond pas à j-- si la peine minimale est encore i-- alors nous aurions pas à échanger. 

ANDI PENG: Est-ce que l'égalité de i? Que voulez-vous dire ici? 

AUDIENCE: Ou oui, si le minimum ne correspond pas à i, ouais. ANDI PENG: OK. Eh bien cela résout, en quelque sorte, nos problèmes. Mais cela ne résout toujours pas le problème de ce qui se passe si j-- depuis j ne pas exister en dehors d'elle, ce qui pensez-vous que nous voulons faire avec elle? Déclarer à l'extérieur? Essayons d'exécuter ce. Uh-oh. Notre tri ne fonctionne pas. 

Comme vous pouvez le constater, notre première tableau avait ces valeurs. Et après, il devrait avoir été dans une, deux, trois, quatre, cinq, six, sept, huit, neuf. Ça ne fonctionne pas. Ahh. Qu'est-ce qu'on fait? AUDIENCE: Debug. ANDI PENG: Très bien, nous pouvons essayer. Nous pouvons déboguer. Rétrécir un peu. Fixons notre point d'arrêt. Allons OK like--. 

Donc, parce que nous savons déjà que ces lignes 15 à 22, sont working-- parce que tout que je fais est simplement itérer et printing-- Je peux aller de l'avant et sauter cela. Commençons à la ligne 25. Oop, permettez-moi de vous débarrasser de cette. 

Auditoire: Alors, le point d'arrêt de où commence la mise au point? ANDI PENG: Ou arrêts. AUDIENCE: Ou arrêts. ANDI PENG: Ouais. Vous pouvez définir plusieurs points d'arrêt et il peut juste passer de l'un à l'autre. Mais dans ce cas, nous ne savons pas où l'erreur se produit. Donc, nous voulons juste commencer par le haut vers le bas. Yep. D'ACCORD. 

Donc, cette ligne ici, on peut intervenir. Vous pouvez voir ici-bas, nous avons un tableau. Ce sont les valeurs qui se trouvent dans le tableau. Voyez-vous, comment l'index 0, il correspond à la value-- oh, Je vais essayer d'agrandir. Désolé, il est vraiment difficile à see-- indice de tableau 0, nous avons une valeur de 4 et puis ainsi de suite et ainsi de suite. Nous avons nos variables locales. En ce moment, i est égal à 0, que nous voulons qu'il soit. 

Et gardons pas à pas à travers. Notre minimum est égal à 0, que nous voulons également qu'il soit. Et puis nous entrons dans notre deuxième pour boucle, si le tableau est-j moins de tableau-i, qui il n'a pas été. Donc, vous avez vu comment que sauté sur cela? 

Auditoire: Alors, si le cas minimum, tout that-- qui ne devrait pas être à l'intérieur de la première boucle? PENG ANDI: Non, parce que vous voulez continuer à tester. Vous voulez faire une comparaison tous les temps, même après que vous exécutez à travers elle. Vous ne voulez pas juste de le faire sur la première transmission. Vous voulez faire avec chaque passage supplémentaire à nouveau. Donc, vous voulez vérifier votre état intérieur. Donc, nous allons juste continuer à courir par ici. Je vais vous donner un indice gars. Il est à voir avec le fait que, lorsque vous vérifiez votre conditionnelle, vous n'êtes pas le contrôle pour l'indice correct. Donc maintenant vous vérifiez pour indice de tableau du j est inférieure à tableau Indice de i. Mais que faites-vous en place au le début de la boucle? Ne définissez pas vous j égal à i? 

Ouais, afin que nous puissions quitter le débogueur ici. Donc, nous allons jeter un oeil à notre pseudo. Pour-- nous allons commencer à i est égal à 0. Nous allons aller jusqu'à n moins 1. Voyons, ne nous avons ce droit? Yep, qui était juste. 

Alors l'intérieur ici, nous sommes va créer une valeur minimale et définir ce que égale à i. Avons-nous fait cela? Yep, l'a fait. Maintenant, dans notre intérieur pour la boucle, nous sommes va faire j est égal à i à n moins 1. Avons-nous fait cela? En effet, nous l'avons fait. 

Donc, cependant, ce que nous comparons ici? 

AUDIENCE: j + 1. ANDI PENG: Exactement. Et puis vous allez vouloir définir votre minimum égal à j + 1 ainsi. Alors je suis allé à travers ce très rapidement. Comprenez-vous les gars pourquoi il est j + 1? D'ACCORD. 

Donc, dans votre tableau, en votre premier passage, votre boucle, pour int i est égal à 0, disons simplement supposer cela n'a pas encore été modifié. Nous avons une gamme de, complètement, seulement quatre éléments non triés, non? Donc, nous voulons initialiser i égal à 0. Et je vais tout est courir à travers cette boucle. Et si dans le premier passage, nous allons à initialiser une variable appelée "min" Cela équivaut aussi je, parce nous ne disposons pas d'une valeur minimale. Alors qui est actuellement égal à 0 ainsi. Et puis nous allons passer. Et nous voulons réitérer à nouveau. Maintenant que nous avons trouvé ce que notre minimum est, nous voulons pour parcourir à nouveau pour voir si elle est de comparer, non? Donc j, ici, va à l'égalité de i, qui est 0. Et puis si le tableau J Plus i, qui est celui qui est à côté, comme moins que ce que votre minimum actuel valeur est, vous voulez échanger. 

Alors disons simplement que nous avons obtenu, comme, 2, 5, 1, 8. À l'heure actuelle, i est égal à 0 et j est égal à 0. Et voilà notre valeur minimale. Si array-J Plus i-- si une qui est après celui que nous étudions est supérieure à celle qui la précède, il va devenir le minimum. 

Donc, ici, nous voyons que 5 est pas moins que cela. Donc, ça va pas 5. Nous voyons que 1 est inférieur à 2, à droite? Alors maintenant, nous savons que notre minimum est va être la valeur de l'indice à 0, 1, 2. Ouais? Et puis quand vous arrivez ici, vous pouvez échanger les valeurs correctes. 

Alors, quand vous étiez juste avoir l'j avant, vous ne cherchiez pas à une après cela. Vous regardiez la même valeur, ce qui est pourquoi il juste ne faisait rien. Est-ce que de sens pour tout le monde, pourquoi nous avons besoin que plus 1 là-bas? D'ACCORD. Maintenant, nous allons courir juste à travers elle à faire que le reste du code est correct. Pourquoi en est-il? Ah, il est le min ici. Nous avons comparé la valeur erronée. Oh non. 

Oh oui, ici-bas, nous étions échangeant les mauvaises valeurs. Parce que nous cherchions à i et j. Ce sont ceux que nous partions. Nous voulons effectivement d'échanger le minimum, le minimum actuel, avec tout ce que l'on est à l'extérieur. Et comme vous les gars pouvez voir en bas ici, nous avons un tableau trié. Il a juste eu à voir avec le fait que lorsque nous devions le valeurs que nous comparions, nous ne cherchions pas à les bonnes valeurs. Nous étions à la recherche à la même ici, il ne fait l'échange. Vous devez regarder l'un à côté à elle et puis vous pouvez échanger. Voilà ce que était une sorte de bugger notre code avant. Et ce que je faisais ici est tout le débogueur aurait pu le faire pour vous Je l'ai fait sur le bord, car il est plus facile de voir plutôt que d'essayer de zoomer sur le débogueur. Est-ce que de sens pour tout le monde? Frais. 

Bien. Nous pouvons passer à parler notation asymptotique, qui est juste une façon élégante de dire la runtimes de toutes ces sortes. Donc, je sais David, en conférence, effleuré runtimes. Et il est passé par toute la formule la façon de calculer les temps d'exécution. Pas de soucis à ce sujet. Si vous êtes vraiment curieux sur la façon dont cela fonctionne, hésitez pas à me parler après l'article. Nous pouvons marcher à travers les formules ensemble. Mais tous les gars vous avez vraiment savoir est que n carré plus de 2 est la même chose que n carré. En raison du plus grand nombre, l'exposant, se développe le plus. Et donc pour nos fins, tous nous nous soucions est ce nombre géant qui est en pleine croissance. 

Alors, quel est le meilleur des cas l'exécution de la sélection sorte? Si vous allez avoir pour parcourir une liste puis itérer le reste de cette liste, combien de fois sont vous allez sans doute, dans le pire des case-- dans le meilleur des cas, sorry-- courir à travers? Peut-être que la meilleure question est à demander, ce qui est le pire des cas l'exécution de la sélection sorte. AUDIENCE: n carré. PENG ANDI: Il est n carré, droite. Donc un moyen facile de penser à cela ressemble, chaque fois que vous avez deux boucles for imbriquées, ça va être n carré. Parce que non seulement vous êtes qui traverse une fois de plus, vous devez revenir en arrière autour et courir à travers elle une fois de plus à l'intérieur pour chaque valeur. Donc, dans ce cas, vous n courir n fois au carré, qui est-- désolé, n fois n, ce qui équivaut n carré. 

Et Trier est aussi un peu unique en ce sens qu'il n'a pas d'importance si ceux-ci les valeurs sont déjà en commande. Il va toujours à courir à travers toute façon. Disons que ce fut 1, 2, 3, 4. Indépendamment du fait que oui ou non il est en ordre, il aurait quand même couru à travers et encore vérifié la valeur minimale. Il aurait fait la même nombre de contrôles à chaque fois, même si elle n'a pas réellement toucher à rien. 

Ainsi, dans un tel cas, le meilleur et le pire runtimes sont en fait équivalent. Donc l'exécution attendue de la sélection sorte, que l'on désigne par le symbole de thêta, thêta, dans ce cas, n serait également carré. Chacune de ces trois serait n carré. Tout le monde est clairement pourquoi l'exécution est n carré? 

Bien. Donc je vais juste courir vite à travers le reste des sortes. L'algorithme de bulle sort-- rappelez-vous, ce fut le premier David passa en conférence. Essentiellement, vous faites un pas toute la liste et vous vous swap-- juste comparer les deux à la fois. Et si l'on est plus grande, que vous venez de les échanger. Donc, si ceux-ci sont plus importants, vous souhaitez échanger. Je dois officielle ici. 

Alors disons simplement que vous aviez 8, 6, 4, 2. Vous souhaitez comparer le 8 et un 6. Vous aurez besoin de les échanger. Vous voulez comparer le 8 et un 4. Vous aurez besoin de les échanger. Si vous avez d'échanger le 8 et le 2, changer eux aussi. Ainsi, dans un tel sens, vous pouvez voir, joué sur une longue période de temps, comment les valeurs sorte de bulle à les extrémités, ce qui est pourquoi nous appellent tri à bulles. 

Nous voudrions simplement parcourir à nouveau sur notre deuxième passe, et notre troisième passage, et notre quatrième passe. Essentiellement, bulle pistes Tri juste jusqu'à ce que vous ne faites pas plus de swaps. Donc, dans ce sens, cela est juste le pseudo générale pour elle. Pas de soucis, ceux-ci seront en ligne. Nous ne disposons pas d'aller effectivement à ce sujet. 

On initialise juste un compteur variable qui commence à 0. Et nous parcourons l'ensemble du réseau. Et si une valeur est-- si cela valeur est supérieure à cette valeur, vous allez les échanger. Et puis vous êtes juste va continuer. Et vous allez compter. Et vous allez juste de continuer à faire ce tandis que le compteur est supérieur à 0, ce qui signifie que chaque fois que vous avez à échanger, vous savez que vous voulez aller arrière et vérifier à nouveau. Vous voulez garder le contrôle jusqu'à ce que vous savez que vous ne devez pas échanger plus. 

Alors quels sont les meilleurs et les pires cas pour les moteurs d'exécution tri à bulles? Et hint-- cela est réellement différente de la sélection sorte dans le sens que ces deux réponses ne sont pas les mêmes. Pensez à ce qui se passerait dans une affaire si elle a été déjà trié. Et penser à ce que qui se passerait si elle était dans le cas où il n'a pas été trié. Et vous pouvez sorte de courir travers pourquoi ce qui se passe. Je vais vous donner les gars, comme, 30 secondes pour réfléchir à cela. 

D'ACCORD. Quelqu'un at-il une conjecture à ce que le pire des cas, l'exécution du tri à bulles est? Ouais. 

AUDIENCE: Serait-il, comme, n fois n moins 1 ou quelque chose comme ça? Comme, à chaque fois qu'il est exécuté, il est juste, comme, un swap de moins que tout ce qu'il était. 

ANDI PENG: Ouais, donc vous avez tout à fait raison. Et ceci est un cas dans lequel votre réponse était en fait plus complexe que celui que nous devons donner. Donc ça va run-- je suis va effacer tout cela ici. Tout le monde est bon? Puis-je effacer cela? D'ACCORD. Vous allez courir à travers n fois la première fois, non? Et ils vont courir à travers n moins 1 pour la deuxième fois, non? Et puis vous allez garder aller, la mine n 2, et cetera. David a fait cela dans une conférence, où, si vous avez ajouté toutes ces valeurs, vous obtenez quelque chose qui est like-- Yeah plus de 2, ce qui réduit essentiellement juste vers le bas à n au carré. Vous allez obtenir une fraction bizarre là-dedans. Et si juste savoir que le carré n toujours a préséance sur la fraction. Et dans ce cas, le pire exécution serait n au carré. Si elle était en décroissant afin, pense, vous avoir à faire un échange à chaque fois unique. 

Quel serait, potentiellement, la meilleure exécution de cas? Disons que, si la liste était déjà dans l'ordre, ce qui serait le runtime être? 

AUDIENCE: n. PENG ANDI: Il est n, exactement. Et pourquoi est-il n? AUDIENCE: Parce que vous venez devoir vérifier chaque fois. ANDI PENG: Exactement. Donc, dans le meilleur exécution possible, si cette liste était déjà sorted-- disons 1, 2, 3, 4-- vous serait tout simplement passer, vous vérifiez, vous verriez, oh, ils ont tous pan out. Je ne dois échanger. J'ai fini. Donc, dans ce cas, il est juste n ou le nombre d'étapes que vous venez eu à vérifier dans la première liste. 

Et après, nous avons maintenant atteint tri par insertion, où l'algorithme est essentiellement de fracture dans une partie triés et non triés. Et puis, un par un, les valeurs non triés sont inséré dans leur appropriée positions dans le début de la liste. 

Ainsi, par exemple, nous avons une liste des 3, 5, 2, 6, 4 à nouveau. Nous savons qu'il est actuellement non triés parce que nous venons tout juste commencé à regarder il. Nous prenons un coup d'oeil et nous savons que la première valeur est trié, non? Si vous cherchez seulement à un éventail de taille un, vous savez qu'il est triée. 

Alors que nous savons que le quatre autres sont non triés. Nous allons à travers et nous voyons cette valeur. Allons en arrière. Voir cette valeur de 5? Nous prenons un coup d'oeil. Nous comparons à 3. Nous savons qu'il est plus grand que 3, de sorte que nous savons que que ça triés. Donc, nous savons maintenant que les deux premiers sont triés et les trois derniers ne sont pas. 

Nous prenons un oeil à 2. Nous vérifions d'abord avec 5. Est-il moins de 5? Ce n'est pas. Nous devons donc continuer à regarder vers le bas. Ensuite, vous vérifiez 2 sur 3. Est-il moins? Non. Donc, vous savez 2 doit être inséré dans la partie avant 3 et 5 et les deux doivent être poussé dehors. Pour ce faire, à nouveau avec 6 et 4. Et nous continuons à vérifier simplement l'essentiel, où nous vérifions juste, vérifier, vérifier. Et jusqu'à ce qu'il soit dans la bonne position, nous sorte de juste insérez-le dans la bonne position, qui est où le nom de celui-ci est venu. 

Voilà donc simplement l'algorithme, pseudo-soi, en quelque sorte, sur la façon dont nous pourrions mettre en œuvre un tri par insertion. Pseudocode est ici. Il est tout en ligne. Pas de soucis si vous les gars sont essayant de copier cette baisse. Donc encore une fois, même ce question-- serait la pire des runtimes meilleur et pour le tri par insertion? Il est très similaire à la dernière question. Je vais vous donner les gars, comme, 30 secondes pour réfléchir à cela aussi. 

OK Quelqu'un veut- me donner la pire de l'exécution? Ouais. 

AUDIENCE: n carré. 

PENG ANDI: Il est n carré. Et pourquoi est-il n carré? 

AUDIENCE: Parce que dans l'ordre inverse, vous avez de passer par n fois n, qui est-- ANDI PENG: Oui, exactement. Donc même chose que dans le tri à bulles. Si cette liste est en ordre décroissant, vous êtes allez avoir à vérifier une première fois. Et puis avec tous les valeur supplémentaire, vous êtes allez avoir à vérifier contre chaque valeur unique, non? Et donc tout à fait, vous allez faire une fois n de dépasser un autre n passent, qui n est au carré. Qu'en est-il le meilleur des cas? Ouais. 

AUDIENCE: n moins 1, parce que la premier est déjà au carré. 

ANDI PENG: Donc, à proximité. La réponse est en fait n. Parce que pendant que le premier est une triés, il peut ne pas lui actually-- nous avons juste eu de la chance, dans cet exemple, que deux qui est arrivé à être le plus petit nombre. Mais ce ne sera pas toujours le cas. Si 2 est déjà trié dans le début mais vous regardez et il ya un 1 ici, le 1 va le heurter. Et il va finir jusqu'à être heurté de toute façon. 

Donc, dans le meilleur des cas, il est en fait juste va être n. Si vous avez 1, 2, 3, 4, 5, 6, 7, 8, vous êtes aller à courir à travers toute cette liste une fois de vérifier pour voir si tout va bien. Tout le monde est clair sur la course temps de sélection ainsi? Je sais que je vais à travers ces vraiment rapide. Mais savez juste que si vous connaissez le concepts généraux, vous devriez être bon. D'ACCORD. Donc, je vais vous donner les gars peut-être, comme, une minute pour parler à vos voisins sur ce que sont quelques-unes des principales différences entre ces types de sortes. Nous allons passer en revue que bientôt. AUDIENCE: Oh, OK. ANDI PENG: Ouais. D'ACCORD. Cool, Reprenons en tant que classe. D'ACCORD. Donc, ce fut une sorte de question ouverte dans le sens qu'il ya beaucoup de réponses pour eux. Et nous allons passer en revue certains d'entre eux brièvement. Je voulais juste pour vous les gars penser à ce différenciée les trois types de sortes. Et je entendu, aussi, un grand question-- ce ne fusionne sorte faire? Grande question, parce que ce ce que nous sommes couvrant prochaine. 

Donc, le tri par fusion est le une sorte que les fonctions très différemment des autres sortes. Comme vous les gars peuvent see-- fait David cette démo où il avait toute la fraîcheur bruits de voir comment fusionner Trier couru, comme, à l'infini plus rapidement que les deux autres types? D'ACCORD. Voilà donc parce fusion implémente sorte que fracture et conquérir concept que nous avons parlé de beaucoup de choses en cours. En ce sens que nous aimons travailler plus intelligemment, pas plus difficile, quand on divise et conquérir des problèmes, et les briser vers le bas, puis les mettre ensemble, bonnes choses arrivent toujours. 

Ainsi, la manière qui fusionnent Trier travaille essentiellement est qu'il divise une tableau non trié dans la moitié. Et puis, il a obtenu deux moitiés de tableaux. Et il trie simplement les deux moitiés. Il ne cesse de diviser en deux, en la moitié, dans la moitié jusqu'à ce que tout est trié puis de façon récursive met tout cela ensemble. 

Voilà donc vraiment abstrait. Donc, ceci est juste un peu de pseudo-code. Cela fait-il sens la façon dont il fonctionne? Alors disons simplement que vous avez un tableau de n éléments, non? Si n est inférieur à 2, vous pouvez retourner. Parce que vous savez que si il ya une seule chose, il doit être triée. Sinon, vous triez la moitié gauche, puis vous triez la moitié droite, puis vous fusionnez. 

Ainsi, alors que l'air vraiment facile, en réalité, il est de penser à un peu difficile. Parce que vous êtes comme, Eh bien, voilà sorte de tournant sur lui-même. Droit? Il est en cours d'exécution sur elle-même. Donc, dans ce sens, David touché sur la récursivité en classe. Et voilà un concept nous parlerons plus. Il est ce qui, ces deux lignes ici, est en fait juste le programme lui disant d'exécuter lui-même avec entrée différente. Alors plutôt que de lui-même exécuté avec l'ensemble de n éléments, vous pouvez le décomposer dans la la moitié gauche et la moitié droite et puis exécutez-le à nouveau. 

Et puis nous allons examiner visuellement, parce que je suis un apprenant visuel. Il fonctionne mieux pour moi. Donc, nous allons regarder un exemple visuel ici. 

Disons que nous avons un tableau, six éléments, 3, 5, 2, 6, 4, 1, non trié. Très bien, il ya beaucoup sur cette page. Donc, si vous les gars pouvez consulter le première étape ici, 3, 5, 2, 6, 4, 1, vous pouvez diviser en deux. Vous avez 3, 5, 2, 6, 4, 1. Vous savez que ceux-ci vous aren't-- Je ne sais pas si elles sont triées ou non, si vous continuez à les briser, dans la moitié, dans la moitié, dans la moitié, jusqu'à ce que finalement, vous avez un seul élément. Et un élément est toujours triée, non? 

Nous savons donc que 3, 5, 2, 4, 6, 1, par eux-mêmes, sont triés. Et maintenant, nous pouvons les remettre ensemble. Donc, nous savons que le 3, 5. Nous mettons les ensemble. Nous savons que ce tri. Les 2 est toujours là. Nous pouvons mettre le 4 et le 6 ensemble. Nous savons que que ça triés, alors nous avons mis cela ensemble. Et la figure 1 est là. 

Et puis vous regardez juste ces deux moitiés ici. Vous avez le 3, 5, 2, 2, 3, 5. Vous pouvez les comparer commencement de tout. Parce que vous savez que ceci est trié et vous savez que que ça triés. Ainsi donc, vous ne devez pas même à comparer le 5, vous comparez juste le 3. Et la figure 2 est inférieur à 3, de sorte que vous savez 2 doit aller à la fin. 

Même chose là-bas. Le 1 doit aller ici. Et puis quand vous allez mettre ces deux valeurs, vous savez que ce sont triés et vous savez que ce sont triés. Alors le 1 et le 2, la figure 1 est inférieur à 2. Qui vous dit que le 1 devrait aller sur la fin de cette sans même regarder 3 ou 5. Et puis le 4, vous pouvez juste vérifier, il va droit ici. Vous ne devez pas regarder le 5. Même chose avec la 6. Vous savez que le 6-- juste n'a pas besoin d'être regardé. 

Et de cette façon, vous êtes juste vous sauver beaucoup d'étapes lorsque vous faites la comparaison. Vous ne disposez pas de comparer tous les élément contre d'autres éléments. Vous comparez seulement contre ceux que vous avez besoin de le comparer contre. Voilà donc genre d'un concept abstrait. Pas de soucis si elle est pas tout droit de vous frapper encore. Mais en général, cela est comment une sorte de fusion fonctionne. Questions, questions rapides, avant de passer? Ouais. 

Auditoire: Alors, vous avez dit que vous prenez le 1, puis le 4, 6 et la et les mettre dans. Donc, ne sont pas those-- ne sont pas vous les regardant comme des éléments distincts, et non comme l'ensemble? ANDI PENG: Ouais. Donc ce qui se passe est que vous essentiellement sont la création d'un réseau de nouvelle marque. Donc, vous savez que, ici, je dois deux tableaux de taille 3, non? Donc, vous savez que mon tableau trié doit avoir six éléments. Alors que vous venez de créer un nouvelle quantité de mémoire. Donc, vous êtes un peu comme gaspiller de la mémoire, mais cela n'a pas d'importance parce qu'il est si petit. Alors vous regardez le 1 et vous regardez le 2. Et vous savez que le 1 est inférieur à 2. Donc, vous savez que 1 devrait aller dans le début de l'ensemble de ceux-ci. 

Vous ne même pas besoin de regarder le 3 et le 5. Donc, vous savez 1 y va. Ensuite, vous essentiellement couper le 1. Il est, comme, morts pour nous. Ensuite, nous avons seulement 2, 3, 5, puis 4 et 6. Et puis vous savez cela, vous comparer le 4 et le 2, oh, le 2 devrait aller là-bas. Donc, vous l'écrasez 2 vers le bas, vous hachez-le. Ainsi donc, vous avez juste le 3 et le 5 dans le 4 et le 6. Et vous continuez à hacher le tout jusqu'à ce que vous les mettez dans le tableau. 

Auditoire: Alors, vous êtes juste toujours comparant la [inaudible]? 

ANDI PENG: Exactement. Donc, dans ce sens, vous êtes simplement comparer, essentiellement, un numéro contre l'autre numéro. Et parce que vous savez qu'il est triée, vous ne pas avoir à regarder à travers tous les nombres. Vous avez juste à regarder le premier. Et puis vous pouvez juste plop les vers le bas, parce que vous savez ils appartiennent où ils doivent appartenir. Ouais. Bonne question. 

Et puis, si l'un de vous sont un peu ambitieux, hésitez pas à regarder ce code. Ceci est en fait la la mise en œuvre physique de la façon dont nous pourrions écrire tri par fusion. Et vous pouvez le voir, il est très courte. Mais les idées derrière il sont assez complexes. Donc, si vous vous sentez comme ce dessin sur dans vos devoirs ce soir, vous pouvez. 

D'ACCORD. David est également rendu au cours de cette conférence dans. Quels sont le meilleur des cas runtimes, pires cas, runtimes et les runtimes attendus de tri par fusion? A quelques secondes pour réfléchir. Ceci est assez difficile, mais un peu intuitive si vous pensez à ce sujet. Bien. 

Public: Est ce que le pire des cas n log n? ANDI PENG: Exactement. Et pourquoi est-il n log n. 

AUDIENCE: est-ce pas parce qu'il devient exponentiellement plus rapide, il est donc comme une fonction de cette lieu d'être juste tout simplement n carré ou quelque chose? ANDI PENG: Exactement. Donc la raison pour laquelle la runtime sur ce journal est n n est ce que vous êtes because-- faire dans toutes ces étapes? Vous êtes juste couper en deux, non? Et donc quand nous faisons la journal, tout ce qu'il fait est de diviser un problème en deux, dans la moitié, dans la moitié, en plus de moitiés. Et dans ce sens, vous pouvez genre d'éliminer le modèle linéaire que nous avons utilisé. Parce que quand vous hachez choses dans la moitié, il est un journal. Cela est juste la mathématique façon de le représenter. 

Et puis finalement, à la fin, vous êtes juste faire une dernière passe à travers de mettre tout en ordre, non? Et donc si vous avez juste à vérifier une chose, qui est n. Et si vous êtes du genre multipliant les deux ensemble. Donc, il est comme vous avez cette finale vérifier n ici avec un journal de n ici. Et si vous multipliez eux, qui est n log n. 

Et donc le meilleur et le pire affaire et attendu sont tout n log n. Il est aussi comme une autre sorte. Il est comme la sélection Trier dans le sens où il n'a pas d'importance ce que votre la liste est, il va juste à faire la même chose à chaque fois. D'ACCORD. Donc, comme vous les gars pouvez le voir, même si les sortes que nous sommes passés through-- n carré, il est pas très efficace. Et même ce n log n est pas la plus efficace. Si vous les gars sont curieux, il ya des mécanismes de tri qui sont si efficaces qu'ils sont presque essentiellement plat dans l'exécution. 

Vous avez un peu de log n. Vous avez un peu de log n log. Nous ne touchons pas sur eux dans cette classe en ce moment. Mais si vous les gars sont curieux, hésitez pas à Google, ce qui est les mécanismes de tri les plus efficaces. Je ne sais pas, il ya certains ceux qui sont vraiment drôles, like-- il ya certains vraiment les drôles que les gens font. Et vous vous demandez comment ils jamais pensé à cela. Donc Google, si vous avez un peu de secours temps, sur, quels sont les moyens drôles que personnes-- ainsi que personnes ways-- efficaces ont été en mesure de mettre en œuvre toutes sortes. D'ACCORD. Et voici juste un petit tableau à portée de main. Je sais tout de vous, avant que quizz 0, sera dans votre chambre sans doute essayer à mémoriser que. Voilà donc agréable là pour vous les gars. Il suffit de ne pas oublier que la logique prises en vue: pourquoi ces chiffres se produisaient. Si vous êtes toujours perdu, juste faire vous que vous savez ce que les sortes sont. Et vous pouvez courir à travers dans votre esprit de comprendre pourquoi ceux réponses sont ces réponses. 

Bien. Donc, nous allons déplacer sur, enfin, à la recherche. Parce que, comme ceux d'entre vous qui ont lu le pset, recherche fait également partie de Le problème de cette semaine fixe. Vous serez invité à mettre en œuvre deux types de recherches. L'un est une recherche linéaire et on est une recherche binaire. 

Ainsi, la recherche linéaire est assez facile. Vous voulez juste à l'élément recherche d'une liste pour voir si vous obtenez. Vous avez juste à itérer. Et si elle est égale à quelque chose, vous pouvez simplement revenir, non? Mais celui que nous sommes les plus intéressé à parler est binaire de recherche, à droite, qui est la diviser et conquérir mécanisme David a été la démonstration en cours. 

Rappelez-vous l'exemple du livre de téléphone qu'il continue à élever, celui qu'il sorte de luttait un peu sur cette dernière année, où vous divisez le problème dans la moitié, en deux, en deux, à plusieurs reprises, jusqu'à ce que vous trouverez ce que vous cherchez? Et vous avez le l'exécution de cette ainsi. Et vous pouvez le voir, il est significativement plus efficace que tout autre type de recherche. 

Ainsi, la manière que nous irions à propos la mise en œuvre d'une recherche binaire est, si nous avions un tableau, index 0 à 6, sept éléments, nous pouvons regarder au milieu, droite- désolé, si notre question first-- si nous voulons poser la question de, t- le tableau contient l'élément de 7, de toute évidence, être humain, et ayant tel un petit tableau, il est facile pour nous à dire oui. Mais la façon de mettre en œuvre un fichier binaire recherche serait de regarder dans le milieu. 

Nous savons que l'indice 3 est au milieu, parce que nous savent qu'il ya sept éléments. Qu'est-ce que 7 divisé par 2? Vous pouvez couper ce supplément 1. Vous avez 3 dans le milieu. Donc, est un tableau de 3 égale à 7? Il est pas, non? Mais nous pouvons faire quelques vérifications. Est un tableau de 3 à moins de 7 ou est un tableau de 3 supérieur à 7? 

Et nous savons qu'il est inférieur à 7. Donc, nous savons que, oh, elle doit ne pas être dans la moitié gauche. Nous savons qu'il doit être dans la moitié droite, non? Donc, nous ne pouvons tout simplement couper la moitié du tableau. Nous ne devons même pas regarder plus. Parce que nous savons que la moitié de notre problem-- nous savons que la réponse est dans la moitié droite de notre problème. Donc, nous attendons juste à ce moment. 

Alors maintenant, nous regardons le milieu de ce qui reste. Cet indice 5. Nous faisons la même vérification à nouveau et nous voyons qu'il est plus petit. Donc, nous nous tournons vers la gauche de cela. Et puis, nous voyons que l'enregistrement. Est la valeur du tableau au Indice 4 égale à 7? C'est. Donc, nous pouvons retourner vrai, parce que nous avons trouvé la valeur dans notre liste. Est-ce que la façon dont je suis passé par qui font sens pour tout le monde? D'ACCORD. Je vais vous donner les gars peut-être, comme, trois, quatre minutes pour comprendre cette façon de pseudocode dans. 

Alors, imaginez je vous ai demandé d'écrire une fonction recherche appelé () qui a renvoyé une valeur, une valeur booléenne, cela était vrai ou false-- comme, vrai si vous avez trouvé le valeur false si vous ne l'avez pas. Et puis, vous étiez passé dans la valeur que vous étaient à la recherche en valeurs, qui est l'array-- oh, je mets définitivement que, dans le mauvais endroit. D'ACCORD. Quoi qu'il en soit, cela devrait avoir été à la droite des valeurs. Et puis int n est le nombre d'éléments dans ce tableau. Comment feriez-vous pour essayer à Pseudocode ce problème dans? Je vais vous donner des gars comme trois minutes pour le faire. Non, je pense qu'il ya terre que: oui, il ya un juste ici. AUDIENCE: Puis-je? ANDI PENG: Ouais, je vous avez obtenu. Est-ce travail? OK cool. 

D'ACCORD. Tous les gars de droite, nous sommes va freiner dans. D'ACCORD. Donc, supposons que nous avons cette belle petit tableau avec n valeurs en elle. Je ne dessine les lignes. Mais comment pourrions-nous aller sur en essayant d'écrire cela? Quelqu'un veut- me donner la première ligne? Si vous voulez me donner le première ligne de ce pseudo. 

AUDIENCE: [inaudible] AUDIENCE: Vous voudriez pour itérer through-- AUDIENCE: Juste une autre pour la boucle? AUDIENCE: --pour. 

ANDI PENG: Donc, celui est un peu délicat. Pensez about-- vous voulez pour continuer à fonctionner de cette boucle encore et encore jusqu'à quand? 

AUDIENCE: Jusqu'à ce que le [inaudible] La valeur est égale à cette valeur. ANDI PENG: Exactement. Ainsi, vous pouvez en fait juste write-- nous pouvons même le simplifier plus encore. Nous pouvons juste faire une boucle while, à droite? Ainsi, vous pouvez juste avoir loop-- nous savons que cela est un tout. Mais pour l'instant, je vais à-dire «boucle» - par quoi? Boucle until-- ce qui est notre condition de fin? Je pense que je l'ai entendu. Je entendu quelqu'un dire. 

Audience: Valeurs égale milieu. ANDI PENG: Dites-le à nouveau. AUDIENCE: Ou, jusqu'à ce que le valeur que vous êtes à la recherche pour est égale à la valeur moyenne. 

ANDI PENG: Que faire si il est pas là? Que faire si la valeur que vous êtes à la recherche pour est pas réellement dans ce tableau? AUDIENCE: Vous revenez 1. 

ANDI PENG: Mais qu'est-ce que nous voulons boucle jusqu'à ce que si nous avons une condition? Ouais. 

AUDIENCE: Jusqu'à il ya une seule valeur? ANDI PENG: Vous pouvez faire une boucle until-- Donc, vous savez que vous êtes va avoir une valeur max, non? Et vous savez que vous allez pour avoir une valeur de minutes, non? Parce que aussi, que quelque chose Je oublié de dire avant, que quelque chose qui est critique sur la recherche binaire est que votre réseau est déjà trié. Parce qu'il n'y a aucun moyen de faire ce si elles sont juste des valeurs aléatoires. Vous ne savez pas si l'on est plus grand que l'autre, non? 

Donc, vous savez que votre max et vos minutes sont ici, non? Si vous allez à l'ajustement votre maximum dans vos minutes et les mid-- disons simplement assumer votre mi valeur est ici-- droit vous allez essentiellement boucle jusqu'à ce que votre minimum est environ le même que votre maximum, à droite, ou si votre max est pas le même que votre min. Droit? Parce que quand cela arrive, vous savez que vous avez finalement atteint la même valeur. Donc, vous voulez faire une boucle jusqu'à ce que votre min est inférieure ou égale to-- oops, pas moins de ou égal à, dans l'autre sens est around-- max. 

Est-ce que de sens? Je fis quelques essais pour obtenir ce droit. Mais boucle jusqu'à ce que la valeur de votre max est essentiellement presque moins ou égale à votre minimum, non? Voilà quand vous savez que vous avez convergé. PUBLIC: Quand serait votre maximum valeur soit inférieure au minimum? ANDI PENG: Si vous continuez à réglage, ce qui est ce que nous allons à faire dans ce domaine. Cela a-t-il du sens? Minimum et maximum sont juste entiers que nous sommes probablement allez vouloir créer de garder trace de où nous sommes à la recherche. Parce que le tableau existe indépendamment de ce que nous faisons. Comme, nous ne sommes pas réellement physiquement coupant le tableau, non? Nous sommes en train de réglage où nous sommes à la recherche. Cela a-t-il du sens? 

AUDIENCE: Ouais. 

ANDI PENG: OK. Donc, si cela est la condition de notre boucle, Que voulons-nous à l'intérieur de cette boucle? Qu'allons-nous à vouloir faire? Donc maintenant, nous avons un maximum et un minimum, à droite, probablement créé ici quelque part. Nous allons probablement envie de trouver un milieu, à droite? Comment allons-nous être en mesure de trouver le milieu? Quelle est la mathematical-- AUDIENCE: Max Plus min divisé par 2. ANDI PENG: Exactement. Cela a-t-il du sens? Et avez-vous les gars vous verrez pourquoi nous n'a pas seulement use-- pourquoi nous avons fait cette au lieu de faire simplement n divisé par 2? Il est parce que n est une valeur que cela va rester le même. Droit? Mais comme nous ajustons notre minimum et valeurs maximales, ils vont changer. Et en conséquence, notre milieu qui va changer aussi. Voilà pourquoi nous voulons pour ce faire ici. D'ACCORD. 

Et puis, maintenant que nous avons trouvé our-- ouais. 

AUDIENCE: Juste un question-- rapide quand vous dites min et max, supposons-nous que il est déjà triée? 

ANDI PENG: Ouais, qui est en fait un condition préalable à une recherche binaire, que vous devez savoir qu'il est triée. Ce qui explique pourquoi sorte, vous écrivez dans votre problème réglé avant votre recherche binaire. D'ACCORD. Alors, maintenant que nous savons où notre milieu est, que voulez-vous faire ici? 

PUBLIC: Nous voulons comparer que à l'autre. ANDI PENG: Exactement. Donc, vous allez comparer milieu à la valeur, à droite? Et qu'est-ce que dire nous lorsque nous comparons? Que voulons-nous faire ensuite? 

Audience: Si la valeur est plus grande que le milieu, nous voulons couper. ANDI PENG: Exactement. Donc, si la valeur est plus grande que le milieu, nous sommes allez vouloir modifier celles-ci minimum et Maxes, non? Que voulons-nous changer? Donc, si nous connaissons la valeur est quelque part ici, ce que vous faites, nous changer? Nous voulons changer notre minimales à mi, non? Et puis d'autre, si elle est dans ce la moitié, que voulons-nous changer? 

Public: Votre maximale. ANDI PENG: Ouais. Et puis vous allez juste de garder en boucle, non? Parce que maintenant, après une itération à travers, vous avez un max ici. Et puis vous pouvez recalculer un milieu. Et puis vous pouvez comparer. Et vous allez continuer jusqu'à ce que les minutes et les Maxes ont essentiellement convergé. Et qui est quand vous savez que vous avez atteint la fin de celui-ci. Et soit vous l'avez trouvé ou si vous avez pas à ce point. 

Cela fait-il sens pour tout le monde? D'ACCORD. Ceci est très important, parce que vous aurez à écrire ce soir dans votre code. Mais vous les gars avez une assez bonne sens de ce que vous devriez faire, ce qui est bon. D'ACCORD. Donc, nous avons environ sept minutes partie gauche. Donc, nous allons parler pset ce que nous allons faire. Ainsi, le jeu de processeurs est divisé en deux moitiés. Le premier semestre implique la mise en œuvre d'une découverte dans lequel vous écrivez une recherche linéaire, un recherche binaire, et un algorithme de tri. 

Donc ceci est la première temps dans un pset où nous serons en vous donnant les gars ce qu'on appelle code de distribution, qui est le code que nous avons pré-écrite, mais juste laissé quelques morceaux hors pour vous de terminer l'écriture. Alors vous les gars, quand vous regardez cette code, vous pourriez obtenir vraiment peur. Si vous êtes juste comme, ahh, je ne savent pas ce que cela fait, Je ne sais pas, comme, qui semble si compliqué, ahh, se détendre. C'est bon. Lire la spécification. La spécification va vous expliquer exactement ce que tous ces programmes font. 

Par exemple, un programme est generate.c cela viendra avec votre pset. Vous ne avez pas réellement besoin de le toucher, mais vous devez comprendre ce qu'il fait. Et generate.c, tout ce qu'il est fait est soit générer des nombres aléatoires ou vous pouvez lui donner une graine, comme un nombre préétabli qu'il faut, et elle génère d'autres numéros. Donc, il ya une façon spécifique à dans lequel la mise en œuvre generate.c vous pouvez juste faire un tas de chiffres pour vous de tester vos méthodes sur d'autres. 

Donc, si vous voulez, pour par exemple, tester votre trouvaille, vous voulez exécuter generate.c, générer un tas de chiffres, et puis exécutez votre fonction des aides. Votre fonction des aides est l'endroit où vous êtes effectivement écrit physiquement code. Et penser aides comme un fichier de bibliothèque vous écrivez que find appelle. Et au sein de helpers.c, vous aurez faire recherche et de tri. 

Et puis vous allez à l'essentiel juste les mettre tous ensemble. La spec vous dire comment mettre ça sur la ligne de commande. Et vous serez en mesure de tester si oui ou pas votre tris et de recherches travaillent. Frais. Quelqu'un at-il déjà commencé et problèmes ou des questions rencontrées ils ont en ce moment avec ce? D'ACCORD. 

AUDIENCE: Attendez. J'ai une question. 

ANDI PENG: Ouais. 

Auditoire: Alors, je commencé à faire la recherche linéaire dans helpers.c et il ne fonctionnait pas vraiment. Mais plus tard, je découvert que nous venons avoir à supprimer et faire une recherche binaire. Qu'importe donc si ça ne fonctionne pas? 

ANDI PENG: La réponse courte est non. Mais puisque nous sommes pas-- AUDIENCE: Mais pas son effectivement le contrôle. ANDI PENG: Nous ne sommes jamais aller voir ça. Mais vous voudrez probablement vous assurer votre recherche fonctionne. Parce que si votre linéaire recherche ne fonctionne pas, alors les chances sont de votre binaire la recherche ne va pas fonctionner aussi bien. Parce que vous avez similaires logique dans chacun d'eux. Et non, il n'a pas vraiment d'importance. Donc les seuls vous tournez en sont en quelque sorte et la recherche binaire. Ouais. 

Et aussi, beaucoup d'enfants étaient d'essayer de compiler helpers.c. Vous n'êtes pas effectivement autorisé pour ce faire, parce helpers.c ne possède pas une fonction principale. Et donc vous devriez seulement être effectivement compilation générer et trouver, parce que trouver des appels helpers.c et les fonctions en son sein. Alors que rend le débogage une douleur dans le cul. Mais voilà ce que nous avons à faire. AUDIENCE: Vous venez de faire tout, non? ANDI Peng: vous pouvez simplement faire toute aussi bien, ouais. D'ACCORD. Voilà donc en termes de ce que le pset vous demande tous de faire. Si vous avez des questions, ne libre pour me demander, après l'article. Je serai là pour, comme, 20 minutes. 

Et oui, les pset de vraiment pas si mal que ça. Vous devriez être OK. Ceux-ci, il suffit de suivre les lignes directrices. Type de avoir un sentiment de, logiquement, ce devrait se passer et vous serez amende. Ne soyez pas trop peur. Il ya beaucoup de code déjà écrit il. Ne soyez pas trop peur si vous ne le faites pas comprendre ce que tout cela signifie. Si elle est beaucoup, il est tout à fait bien. Et venir à des heures de bureau. Nous vous aiderons à vous jetez un oeil. 

Public: Avec le supplément fonctions, ne nous regardons ceux en place? 

ANDI PENG: Ouais, ceux qui sont dans le code. Dans le jeu de 15, la moitié des il est déjà écrit pour vous. Donc, ces fonctions sont déjà dans le code. Yep. Bien. Eh bien, bonne chance. Il est un jour dégoûtant. Donc, nous espérons que vous les gars ne se sentent pas trop mal à rester à l'intérieur et de codage.