1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> ENCEINTE 1: Salut tout le monde! 3 00:00:12,300 --> 00:00:13,890 Bienvenue à la section. 4 00:00:13,890 --> 00:00:17,480 Je suis tellement content de voir que beaucoup d'entre vous, ici, et tout le monde qui regarde en ligne. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Donc, comme d'habitude dos de bienvenue. 7 00:00:20,920 --> 00:00:24,360 Je espère que vous avez tous eu une belle week-end, plein de repos, de détente. 8 00:00:24,360 --> 00:00:26,026 Il faisait beau hier. 9 00:00:26,026 --> 00:00:27,525 Donc, je l'espère que vous avez apprécié l'extérieur. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Alors d'abord quelques annonces. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Classement. 14 00:00:32,700 --> 00:00:37,350 Ainsi, la plupart d'entre vous devriez avoir obtenu un Email de moi au sujet de votre Scratch Pset, 15 00:00:37,350 --> 00:00:39,920 ainsi que le classement de Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Donc, juste une couple de choses. 18 00:00:42,220 --> 00:00:45,150 Veillez à utiliser check50 dans style50. 19 00:00:45,150 --> 00:00:47,250 Ceux-ci sont destinés à être ressources pour vous les gars, 20 00:00:47,250 --> 00:00:50,660 pour vous assurer que vous obtenez autant de points que vous le pouvez 21 00:00:50,660 --> 00:00:52,390 sans les perdre inutilement. 22 00:00:52,390 --> 00:00:54,407 Donc, des choses comme le style sont très importants. 23 00:00:54,407 --> 00:00:55,740 Nous allons décoller pour elle. 24 00:00:55,740 --> 00:00:58,115 Certains d'entre vous peuvent avoir déjà remarqué que de votre Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 Et check50 est juste un façon très simple de faire en sorte 27 00:01:01,450 --> 00:01:05,050 que nous sommes en train de retourner ce qui doit être retourné à l'utilisateur, 28 00:01:05,050 --> 00:01:06,690 et que tout fonctionne correctement. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Sur la seconde note, assurez-vous Télécharger les choses dans le bon dossier. 31 00:01:12,040 --> 00:01:14,470 Il rend ma vie juste un peu plus difficile 32 00:01:14,470 --> 00:01:18,836 si vous téléchargez Pset 2 en 1 Pset parce que quand je télécharge des choses, 33 00:01:18,836 --> 00:01:20,085 ils ne sont pas téléchargés correctement. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 Et je sais qu'il est un peu bancal dans un système à s'y habituer, 36 00:01:24,560 --> 00:01:26,950 mais juste être super Attention, si seulement pour moi, 37 00:01:26,950 --> 00:01:30,080 de sorte que lorsque vous obtenez des e-mails à 2 heures comme et je suis classement. 38 00:01:30,080 --> 00:01:33,710 Si pas causer je dois regarder tout autour de votre Pset. 39 00:01:33,710 --> 00:01:34,440 Laisser refroidir. 40 00:01:34,440 --> 00:01:37,270 >> Je sais qu'il est tôt, mais je totalement pris au dépourvu fit 41 00:01:37,270 --> 00:01:40,800 par un essai qui est dû ce vendredi, que mes professeurs étaient comme, oh oui. 42 00:01:40,800 --> 00:01:42,550 Rappelez-vous, vous avez un essai en raison vendredi. 43 00:01:42,550 --> 00:01:45,780 Donc, je ne connais personne aime de penser à mi-mandat, 44 00:01:45,780 --> 00:01:50,620 mais votre premier quiz est le 15 Octobre, Octobre qui commence cette semaine. 45 00:01:50,620 --> 00:01:53,290 Ainsi, il pourrait être plus tôt que vous attendiez est tout. 46 00:01:53,290 --> 00:01:57,510 Alors que vous n'êtes pas jeté au dépourvu quand Je mentionne la section de la semaine prochaine que oh, 47 00:01:57,510 --> 00:02:00,560 votre quiz semaine prochaine, je pensais Je vous donne un peu plus 48 00:02:00,560 --> 00:02:01,500 d'une tête maintenant. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Donc, votre problème réglé, le numéro trois. 51 00:02:04,660 --> 00:02:07,070 Comment les gens ont lu le spec par curiosité? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 Dáccord. 54 00:02:09,199 --> 00:02:10,229 Nous avons eu un couple. 55 00:02:10,229 --> 00:02:12,320 Type de bas de la dernière semaine mais qui est OK. 56 00:02:12,320 --> 00:02:13,650 Je sais qu'il était beau dehors. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Donc Break Out. 59 00:02:16,660 --> 00:02:21,010 Certainement après on s'y fait lu aujourd'hui votre spec au moins 60 00:02:21,010 --> 00:02:25,240 essayer comme le téléchargement Code de la distribution et la gestion 61 00:02:25,240 --> 00:02:27,430 comme la première initiale chose qu'ils vous demandent de. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Parce que nous utilisons le code de répartition et d'une bibliothèque 64 00:02:32,590 --> 00:02:36,790 que nous avons seulement été using-- --Il ya seulement la deuxième fois que nous avons fait cette Pset, 65 00:02:36,790 --> 00:02:38,650 des choses folles peuvent arriver avec votre appareil, 66 00:02:38,650 --> 00:02:41,370 et vous voulez trouver que les maintenant par rapport à plus tard. 67 00:02:41,370 --> 00:02:45,570 >> Parce que si il est jeudi soir ou il est Mercredi soir et pour une raison quelconque 68 00:02:45,570 --> 00:02:48,912 votre appareil ne se contente pas vouloir courir avec la bibliothèque 69 00:02:48,912 --> 00:02:50,620 ou à la distribution code, que des moyens 70 00:02:50,620 --> 00:02:52,309 vous ne pouvez même pas commencer à faire le codage. 71 00:02:52,309 --> 00:02:54,100 Parce que vous ne pouvez pas vérifier pour voir si cela fonctionne. 72 00:02:54,100 --> 00:02:55,975 Votre ne va pas être en mesure pour voir si il compile. 73 00:02:55,975 --> 00:03:00,500 Vous voulez prendre soin de ceux au début de la semaine, vous pouvez toujours envoyer un courriel me 74 00:03:00,500 --> 00:03:03,100 ou l'un des autres facteurs de transcription, et nous pouvons obtenir ceux fixés. 75 00:03:03,100 --> 00:03:05,410 Parce que ce sont des questions qui vont vous arrêter 76 00:03:05,410 --> 00:03:07,120 de faire de réels progrès. 77 00:03:07,120 --> 00:03:10,055 Il est pas comme un bug, que vous pouvez juste genre de sauter par-dessus. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Si vous rencontrez des problèmes avec votre appareil ou un code de distribution, 80 00:03:13,420 --> 00:03:16,211 vous voulez vraiment obtenir que prendre soins de plutôt tôt que tard. 81 00:03:16,211 --> 00:03:20,410 Donc, même si tu ne vas pas en fait commencer à coder, téléchargez la distribution 82 00:03:20,410 --> 00:03:24,040 code, lire la spécification, assurez-vous tout est d'y travailler. 83 00:03:24,040 --> 00:03:25,134 D'accord? 84 00:03:25,134 --> 00:03:27,675 Si vous ne pouvez faire cela, je promettre votre vie sera plus facile. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 Et si vous allez probablement à le faire dès maintenant droit? 87 00:03:31,410 --> 00:03:32,100 Dáccord. 88 00:03:32,100 --> 00:03:33,950 Ainsi, des questions là-bas? 89 00:03:33,950 --> 00:03:35,850 Les choses logistiques? 90 00:03:35,850 --> 00:03:36,910 Tout le monde est bon? 91 00:03:36,910 --> 00:03:38,270 Dáccord. 92 00:03:38,270 --> 00:03:41,700 >> Avertissement pour ceux de vous dans la salle et en ligne. 93 00:03:41,700 --> 00:03:45,437 Je vais essayer de passer Powerpoint entre dans l'appareil 94 00:03:45,437 --> 00:03:47,270 parce que nous allons être faire un peu de codage 95 00:03:47,270 --> 00:03:53,630 aujourd'hui par la demande populaire de la anonyme suggestion sondage ai envoyé la semaine dernière. 96 00:03:53,630 --> 00:03:55,480 Donc, nous allons faire quelques codage. 97 00:03:55,480 --> 00:03:57,800 Donc, si vous voulez les gars aussi à feu à vos appareils, 98 00:03:57,800 --> 00:04:02,910 et vous devriez avoir reçu un e-mail de moi, avec un fichier d'exemple. 99 00:04:02,910 --> 00:04:04,310 Se il vous plaît sentir libre de le faire. 100 00:04:04,310 --> 00:04:07,340 >> Donc, nous allons parler GDB, qui est un débogueur. 101 00:04:07,340 --> 00:04:09,970 Il va vous aider sorte de savoir où 102 00:04:09,970 --> 00:04:11,860 les choses vont mal dans votre code. 103 00:04:11,860 --> 00:04:15,370 Il est vraiment juste une façon pour vous de faire un pas dans votre code comme ça se passe, 104 00:04:15,370 --> 00:04:19,100 et être en mesure d'imprimer des variables ou voir ce qui se passe réellement 105 00:04:19,100 --> 00:04:22,980 sous le capot versets votre programme juste la course, il est comme les failles, 106 00:04:22,980 --> 00:04:25,030 et vous êtes comme, aucune idée ce qui vient de se passer ici. 107 00:04:25,030 --> 00:04:26,730 Je ne sais pas quelle ligne il a échoué à. 108 00:04:26,730 --> 00:04:29,040 Je ne sais pas où il est allé mal. 109 00:04:29,040 --> 00:04:31,280 Ainsi, GDB va vous aider avec ça. 110 00:04:31,280 --> 00:04:35,240 Aussi, si vous décidez de continuer oui, et prendre 61, 111 00:04:35,240 --> 00:04:38,430 il va vraiment, vraiment être votre meilleur ami, parce que je peux vous dire 112 00:04:38,430 --> 00:04:40,840 parce que je vais à travers cette classe. 113 00:04:40,840 --> 00:04:43,620 >> Nous allons regarder binaire recherche, qui, si vous les gars me souviens 114 00:04:43,620 --> 00:04:47,540 le grand exemple de l'annuaire téléphonique spectacle de la classe. 115 00:04:47,540 --> 00:04:50,620 Nous allons mettre en œuvre cette, et marche à travers un petit peu plus, 116 00:04:50,620 --> 00:04:54,650 et puis nous allons à travers quatre différentes sortes, qui sont Bubble, 117 00:04:54,650 --> 00:04:56,285 Sélection, Insertion, et fusionner. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Laisser refroidir. 120 00:04:58,330 --> 00:05:00,390 Ainsi, GDB comme je l'ai mentionné, est un débogueur. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 Et ce sont des sortes de gros choses, les grandes fonctions ou commandes 123 00:05:09,370 --> 00:05:13,240 que vous utilisez dans GDB, et je marcherai vous grâce à une démo de ce en une seconde. 124 00:05:13,240 --> 00:05:15,360 >> Donc, ce ne sont pas seulement va rester abstrait. 125 00:05:15,360 --> 00:05:18,000 Je vais essayer de faire ce que le béton que possible pour vous les gars. 126 00:05:18,000 --> 00:05:19,870 Donc, briser. 127 00:05:19,870 --> 00:05:22,200 Ça va être soit pause comme, un nombre, qui 128 00:05:22,200 --> 00:05:26,900 représente une ligne dans votre programme, ou vous pouvez nommer une fonction. 129 00:05:26,900 --> 00:05:30,150 Donc, si vous dites briser principal, il arrêtera au principal, 130 00:05:30,150 --> 00:05:32,400 et laissez vous marchez à travers cette fonction. 131 00:05:32,400 --> 00:05:36,350 >> De même, si vous avez un peu externe fonctionner comme Swap ou Cube, 132 00:05:36,350 --> 00:05:38,450 que nous avons examiné la semaine dernière. 133 00:05:38,450 --> 00:05:41,780 Si vous dites supprimera l'un de ceux-ci, chaque fois que votre programme frappe qui, 134 00:05:41,780 --> 00:05:44,290 il attendra pour vous lui dire quoi faire. 135 00:05:44,290 --> 00:05:47,860 Avant il suffit d'exécuter pour vous pourrait effectivement intervenir à l'intérieur de la fonction 136 00:05:47,860 --> 00:05:49,020 et voir ce qui se passe. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Alors, la prochaine, saute un peu plus de la ligne suivante, va sur les fonctions. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Étape. 141 00:05:55,560 --> 00:05:56,810 Ce sont tous peu abstrait. 142 00:05:56,810 --> 00:06:00,530 Alors, je vais juste courir à travers eux, mais vous les verrez en usage dans une seconde. 143 00:06:00,530 --> 00:06:01,810 >> Entrez dans une fonction. 144 00:06:01,810 --> 00:06:04,170 Donc, comme je le disais, comme avec Swap, il serait 145 00:06:04,170 --> 00:06:07,110 vous permettent de réellement que si vous êtes comme entrer physiquement à l'intérieur, 146 00:06:07,110 --> 00:06:10,990 vous pouvez jouer avec ces variables, impression ce qu'ils sont, voir ce qui se passe. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Liste littéralement juste imprimer le code environnant. 149 00:06:14,830 --> 00:06:17,570 Donc, si vous oubliez de genre où vous êtes dans votre programme, 150 00:06:17,570 --> 00:06:19,880 ou vous vous demandez ce qui se passe autour d'elle, 151 00:06:19,880 --> 00:06:23,790 ce sera juste imprimer un segment de comme cinq ou six lignes autour d'elle. 152 00:06:23,790 --> 00:06:26,080 Ainsi, vous pouvez vous orienter sur l'endroit où vous êtes. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Imprimer une variable. 155 00:06:28,650 --> 00:06:34,590 Donc, si vous avez la clé comme en César, que nous allons examiner. 156 00:06:34,590 --> 00:06:36,220 Vous pouvez dire Touche impression à tout moment. 157 00:06:36,220 --> 00:06:40,070 Il va vous dire ce que la valeur est si que, peut-être quelque part le long du chemin, 158 00:06:40,070 --> 00:06:42,070 vous avez écrasé votre clé. 159 00:06:42,070 --> 00:06:45,495 Vous pouvez effectivement dire que parce que vous pouvez réellement observer cette valeur. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> Dans les locaux, seulement des impressions vos variables locales. 162 00:06:48,780 --> 00:06:53,120 Donc, quand vous êtes dans une boucle, et vous voulez juste voir comme, oh. 163 00:06:53,120 --> 00:06:54,270 Quel est mon je? 164 00:06:54,270 --> 00:06:57,020 Quelle est cette valeur de clé que je l'initialise ici? 165 00:06:57,020 --> 00:06:58,537 Quel est le message à ce point? 166 00:06:58,537 --> 00:07:00,370 Il suffit d'imprimer tous de ceux-ci, de sorte que vous 167 00:07:00,370 --> 00:07:04,330 ne doivent pas individuellement dire, Imprimer I. Imprimer le message. 168 00:07:04,330 --> 00:07:04,970 Touche d'impression. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 Et puis sur Affichage. 171 00:07:07,700 --> 00:07:10,370 Qu'est-ce que cela fait est que vous déplacer dans le programme, 172 00:07:10,370 --> 00:07:13,980 il va juste assurez-vous qu'il est l'affichage de certaines certaine variable 173 00:07:13,980 --> 00:07:14,780 à chaque point. 174 00:07:14,780 --> 00:07:17,160 Alors que vous also-- --Il est une sorte de raccourci où 175 00:07:17,160 --> 00:07:19,530 vous ne devez pas continuer comme, oh. 176 00:07:19,530 --> 00:07:23,150 Touche d'impression ou Imprimer I. Il vient fera automatiquement pour vous. 177 00:07:23,150 --> 00:07:25,959 >> Donc, avec cela, nous allons de voir comment cela va. 178 00:07:25,959 --> 00:07:28,000 Je vais essayer de commutateur à mon appareil. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Voir si je peux le faire. 181 00:07:31,271 --> 00:07:31,770 Tous. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Nous allons simplement refléter le. 184 00:07:42,370 --> 00:07:44,530 Il ya rien de fou sur mon ordinateur portable de toute façon. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 Dáccord. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Ce doit être celui-ci. 189 00:08:01,054 --> 00:08:01,795 Il est si petit. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Voyons voir si nous pouvons le faire. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> Dáccord. 194 00:08:10,940 --> 00:08:15,305 Alice est évidemment mal ici un peu, 195 00:08:15,305 --> 00:08:17,995 Mais nous y reviendrons dans un momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 Dáccord. 198 00:08:22,020 --> 00:08:25,900 Nous allons nous contenter d'augmenter ce. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 Dáccord. 201 00:08:29,380 --> 00:08:31,679 Tout le monde peut voir que sorte de? 202 00:08:31,679 --> 00:08:32,470 Peut-être un petit peu? 203 00:08:32,470 --> 00:08:33,594 Je sais qu'il est un peu petite. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Vous ne pouvez pas tout comprendre comment faire cette plus grande. 206 00:08:37,530 --> 00:08:38,350 Si quelqu'un sait. 207 00:08:38,350 --> 00:08:40,309 Est-ce que quelqu'un sait comment faire plus? 208 00:08:40,309 --> 00:08:40,932 Dáccord. 209 00:08:40,932 --> 00:08:42,140 Nous allons rouler avec lui. 210 00:08:42,140 --> 00:08:45,801 N'a pas d'importance de toute façon car il est juste qui est le code que vous les gars devraient 211 00:08:45,801 --> 00:08:46,300 avoir. 212 00:08:46,300 --> 00:08:48,310 >> Quoi de plus important est la borne ici. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 Et nous avons ici Pourquoi est-il si petit? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Réglages. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Vrai Ike. 220 00:09:09,500 --> 00:09:10,880 Comment agit-il? 221 00:09:10,880 --> 00:09:11,770 Sortir de là. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Est-ce mieux pour tout le monde? 224 00:09:21,810 --> 00:09:22,525 Dáccord ,. 225 00:09:22,525 --> 00:09:23,025 Laisser refroidir. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Vous savez quand vous êtes dans un CS des difficultés techniques de classe 228 00:09:28,220 --> 00:09:32,971 sont sorte de partie de the-- Donc, nous allons effacer ce. 229 00:09:32,971 --> 00:09:33,470 Dáccord. 230 00:09:33,470 --> 00:09:38,060 Donc, ici dans la section, que nous avons eu ici. 231 00:09:38,060 --> 00:09:40,830 César est un fichier exécutable. 232 00:09:40,830 --> 00:09:41,800 Donc je l'ai fait. 233 00:09:41,800 --> 00:09:46,370 Donc, une chose à réaliser avec GDB est que cela fonctionne uniquement sur les fichiers exécutables. 234 00:09:46,370 --> 00:09:48,040 Donc, vous ne pouvez pas l'exécuter sur un dotsy. 235 00:09:48,040 --> 00:09:50,532 Vous devez réellement faire vous que votre code compile, 236 00:09:50,532 --> 00:09:51,865 et qu'il peut effectivement être exécuté. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Donc, assurez-vous que, si elle ne le fait pas compiler, le compiler, 239 00:09:56,186 --> 00:09:57,810 de sorte que vous pouvez genre de courir à travers elle. 240 00:09:57,810 --> 00:10:04,590 Donc, pour commencer GDB, tout ce que vous faites, Gloria Type GDB, et ensuite seulement la 241 00:10:04,590 --> 00:10:06,250 fichier que vous voulez. 242 00:10:06,250 --> 00:10:08,240 Je Misspell toujours César. 243 00:10:08,240 --> 00:10:11,730 Mais vous voulez vous assurer que car il est un exécutable, 244 00:10:11,730 --> 00:10:14,210 point le flash de ti sorte que signifie que vous allez 245 00:10:14,210 --> 00:10:19,240 pour exécuter CSI vous allez exécuter Ces fichiers soit avec le débogueur. 246 00:10:19,240 --> 00:10:19,910 Dáccord. 247 00:10:19,910 --> 00:10:22,885 Donc, vous faites cela, vous obtenez ce genre de charabia. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Il est juste tout ce qui concerne le débogueur. 250 00:10:25,750 --> 00:10:28,200 Vous ne devez pas vraiment inquiéter en ce moment. 251 00:10:28,200 --> 00:10:31,460 Et comme vous le voyez, nous avons cette parens ouvertes, le PIB, proches parens, 252 00:10:31,460 --> 00:10:34,690 et juste ressemble un peu notre ligne de commande, pas vrai? 253 00:10:34,690 --> 00:10:37,010 >> Donc, ce que nous voulons do-- -SO, La première chose 254 00:10:37,010 --> 00:10:39,570 est que nous voulons choisir un endroit pour casser. 255 00:10:39,570 --> 00:10:42,332 Donc, il ya un bug dans ce programme César 256 00:10:42,332 --> 00:10:44,290 que je présente, que nous allons le découvrir. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 Il ce qu'il fait est qu'il faut l'entrée Barfoo en majuscules, et pour une raison quelconque 259 00:10:56,350 --> 00:11:01,950 il ne change pas A. Il laisse juste seul, tout le reste est correct, 260 00:11:01,950 --> 00:11:03,980 mais la seconde lettre Un reste inchangé. 261 00:11:03,980 --> 00:11:07,120 Donc, nous allons essayer de comprendre pourquoi. 262 00:11:07,120 --> 00:11:10,440 Donc, la première chose que vous avez l'habitude vouloir faire chaque fois que vous démarrez sur GDB 263 00:11:10,440 --> 00:11:12,010 est de savoir où le casser. 264 00:11:12,010 --> 00:11:14,956 >> Alors César est un joli programme court. 265 00:11:14,956 --> 00:11:16,330 Nous avons juste une fonction, non? 266 00:11:16,330 --> 00:11:18,520 Quelle était notre fonction dans César? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Il ya seulement une fonction, droit principal? 269 00:11:24,350 --> 00:11:26,490 Principal est une fonction pour tous vos programmes. 270 00:11:26,490 --> 00:11:29,230 Si vous ne disposez pas d'accueil, je pourrais être un peu inquiet en ce moment, 271 00:11:29,230 --> 00:11:31,000 mais je vous souhaite à tous aviez principal là-dedans. 272 00:11:31,000 --> 00:11:34,150 Donc, ce que nous pouvons faire est que nous pouvons juste briser Main, juste comme ça. 273 00:11:34,150 --> 00:11:35,190 Ainsi, il est dit, OK. 274 00:11:35,190 --> 00:11:37,430 Nous mettons notre point d'arrêt une il. 275 00:11:37,430 --> 00:11:42,870 >> Donc, maintenant la chose à retenir est à César prend un argument de ligne de commande à droite 276 00:11:42,870 --> 00:11:45,150 et nous avons pas encore fait n'importe où. 277 00:11:45,150 --> 00:11:47,560 Donc, ce que vous faites est quand vous allez réellement à fonctionner 278 00:11:47,560 --> 00:11:51,540 le programme, tout programme que vous êtes courir dans GDB qui doit ligne de commande 279 00:11:51,540 --> 00:11:55,010 arguments, vous allez à l'entrée lorsque vous commencez à exécuter. 280 00:11:55,010 --> 00:11:59,280 Donc, dans ce cas, nous faisons Exécuter avec une clé de trois. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 Et il va vraiment commencer. 283 00:12:02,040 --> 00:12:08,480 >> Donc, si vous voyez ici, nous avons Si RC est pas égal à 2. 284 00:12:08,480 --> 00:12:12,210 Donc, si vous les gars ont tout ce fichier que je envoyé jusqu'à 285 00:12:12,210 --> 00:12:15,100 vous verrez que cela ressemble le première ligne de notre fonction principale, à droite? 286 00:12:15,100 --> 00:12:17,890 Il est de vérifier pour voir si nous avons le bon nombre d'arguments. 287 00:12:17,890 --> 00:12:20,620 Donc, si vous vous demandez si RC est correct, 288 00:12:20,620 --> 00:12:23,250 vous pouvez faire quelque chose comme impression RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC est égal à deux, qui est ce que nous attendions, non? 291 00:12:28,640 --> 00:12:32,010 >> Ainsi, nous pouvons aller Ensuite, et continuer à travers. 292 00:12:32,010 --> 00:12:33,200 Donc, nous avons une certaine touche là. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 Et nous pouvons imprimer notre touche à veiller à ce que est correct. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Intéressant. 297 00:12:39,500 --> 00:12:41,210 Pas tout à fait ce que nous attendions. 298 00:12:41,210 --> 00:12:44,810 Donc, une chose à réaliser avec GDB aussi, est 299 00:12:44,810 --> 00:12:49,000 qu'il est pas jusqu'à ce que vous frappez Ensuite, que la ligne que vous venez de voir 300 00:12:49,000 --> 00:12:50,720 est réellement exécuté. 301 00:12:50,720 --> 00:12:53,870 Donc, dans cette clé de cas n'a pas encore été attribué. 302 00:12:53,870 --> 00:12:57,050 Donc, la clé est une valeur d'ordures que vous voyez sur le fond il. 303 00:12:57,050 --> 00:13:03,680 Négatif 120-- $ --Il de un milliard et quelque chose des choses bizarres droit? 304 00:13:03,680 --> 00:13:05,340 Il est pas la clé que nous nous attendions. 305 00:13:05,340 --> 00:13:10,720 Mais si nous avons touché sur Suivant, puis nous essayer et touche d'impression, il est trois. 306 00:13:10,720 --> 00:13:11,710 >> Tout le monde voit que? 307 00:13:11,710 --> 00:13:13,780 Donc, si vous obtenez quelque chose que vous êtes comme, attendez. 308 00:13:13,780 --> 00:13:15,540 Ceci est complètement mal, et je ne sais pas 309 00:13:15,540 --> 00:13:20,150 comment cela pourrait se produire parce que tout ce que je veux à faire est de céder un certain nombre, une variable, 310 00:13:20,150 --> 00:13:22,900 essayez de frapper Ensuite, essayez d'imprimer encore une fois, et voir si cela fonctionne. 311 00:13:22,900 --> 00:13:27,830 Parce que ça ne va exécuter et effectivement affecter quelque chose après vous 312 00:13:27,830 --> 00:13:29,340 cliquez sur suivant. 313 00:13:29,340 --> 00:13:30,336 Donner un sens à tout le monde? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> SPEAKER 2: Lorsque vous aléatoire numéros qu'est-ce que cela signifie? 316 00:13:33,220 --> 00:13:34,790 >> ENCEINTE 1: Il est juste aléatoire. 317 00:13:34,790 --> 00:13:35,710 Il est juste ordures. 318 00:13:35,710 --> 00:13:38,320 Il est juste quelque chose que votre ordinateur attribue au hasard. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Laisser refroidir. 321 00:13:40,220 --> 00:13:45,760 Donc, maintenant nous pouvons passer à travers, et si nous avons maintenant ce texte brut GetString. 322 00:13:45,760 --> 00:13:48,600 Alors, permettez-moi de présenter ce qui va se passer quand nous avons frappé Suivant ici. 323 00:13:48,600 --> 00:13:51,320 Notre GDB genre de disparition, non? 324 00:13:51,320 --> 00:13:55,720 En effet, GetString est maintenant d'exécution, droit? 325 00:13:55,720 --> 00:14:01,460 Donc, quand nous avons vu texte brut est égal à GetString, parens ouverts et parens, 326 00:14:01,460 --> 00:14:04,380 et nous avons atteint suivante, qui a effectivement exécutées maintenant. 327 00:14:04,380 --> 00:14:06,580 Donc, il attend Nous entrée de quelque chose. 328 00:14:06,580 --> 00:14:13,560 >> Donc, nous allons à l'entrée de notre nourriture qui est ce que ça ne vous dis-je 329 00:14:13,560 --> 00:14:18,020 et qui dit simplement qu'il est fin de l'exécution, que la fermeture 330 00:14:18,020 --> 00:14:19,980 des moyens de support, il est la sortie de cette boucle. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Ainsi, nous pouvons frapper suivante, et maintenant, comme je suis que vous êtes tous au courant de César, 333 00:14:25,420 --> 00:14:27,260 cela est, ce qui est de cette ligne va faire. 334 00:14:27,260 --> 00:14:32,030 Il est pour Int I est égale à 0, N est égal à Strlen, texte brut, puis 335 00:14:32,030 --> 00:14:33,960 I est inférieur à N, I, plus, plus. 336 00:14:33,960 --> 00:14:35,210 Qu'est-ce que cette boucle va faire? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Ouvrez votre message. 339 00:14:39,160 --> 00:14:39,770 Laisser refroidir. 340 00:14:39,770 --> 00:14:41,330 Donc, nous allons commencer à le faire. 341 00:14:41,330 --> 00:14:47,210 >> Donc, si cette condition correspondre, pour notre premier? 342 00:14:47,210 --> 00:14:52,250 Si il est un B, il est texte brut I. Nous peut obtenir des informations sur nos sections locales. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Ainsi, i est nul, et si six, qui nous nous attendons, et notre clé est de trois. 345 00:14:57,970 --> 00:14:59,227 Tout ce qui fait sens, non? 346 00:14:59,227 --> 00:15:01,310 Ces chiffres sont tout exactement ce qu'ils devraient être. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Donc, hum? 349 00:15:03,870 --> 00:15:05,620 Intervenant 3: je dois nombres aléatoires pour le mien. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 ENCEINTE 1: Eh bien, nous pouvons --Nous check-- peut discuter à ce sujet dans un second. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Mais vous devriez obtenir ceci. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Donc, si nous avons un capital B pour notre première, 356 00:15:20,130 --> 00:15:22,080 cette condition doit l'attraper, non? 357 00:15:22,080 --> 00:15:27,120 Donc, si nous avons atteint Ensuite, nous voyons Si ce qui exécute effectivement. 358 00:15:27,120 --> 00:15:29,220 Parce que si vous suivez le long de votre code, 359 00:15:29,220 --> 00:15:33,460 cette ligne ici, où je texte brut est remplacé par ce calcul, 360 00:15:33,460 --> 00:15:35,720 seulement exécute si le Si condition est correcte droit? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB ne va vous montrer choses qui sont réellement d'exécution. 363 00:15:40,240 --> 00:15:45,140 Donc, si cette condition n'a pas été respectée Si, il est aller juste pour passer à la ligne suivante. 364 00:15:45,140 --> 00:15:46,540 D'accord? 365 00:15:46,540 --> 00:15:48,510 Donc, nous l'avons. 366 00:15:48,510 --> 00:15:51,171 Ce moyen de support il est fermé hors de la boucle maintenant. 367 00:15:51,171 --> 00:15:52,420 Donc, il va recommencer. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Juste comme ça. 370 00:15:56,280 --> 00:15:59,120 Alors, que nous pouvons obtenir des informations sur nos habitants ici, 371 00:15:59,120 --> 00:16:02,575 et nous voyons que notre première lettre a changé, non? 372 00:16:02,575 --> 00:16:05,150 Il est maintenant un E, comme il se doit. 373 00:16:05,150 --> 00:16:07,360 Ainsi, nous pouvons continuer. 374 00:16:07,360 --> 00:16:08,500 >> Et nous avons cette vérification. 375 00:16:08,500 --> 00:16:09,916 Et ce contrôle devrait fonctionner, non? 376 00:16:09,916 --> 00:16:12,570 Il est A. Il doit être changé trois lettres à terme. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Mais si vous remarquez, nous obtenir quelque chose de différent. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Donc dans ce cas ici, il a attiré , et si cette ligne exécutée, 381 00:16:22,860 --> 00:16:28,620 qui a modifié notre B. Mais, dans ce cas-ci, 382 00:16:28,620 --> 00:16:32,860 nous avons juste qu'il sauté, cela, et est allé à la [? L SIFF. ?] 383 00:16:32,860 --> 00:16:34,660 Donc, quelque chose qui se passe là-bas. 384 00:16:34,660 --> 00:16:37,780 Qu'est-ce que vous dit est que, nous savons qu'il doit attraper ici, 385 00:16:37,780 --> 00:16:39,200 mais il est pas. 386 00:16:39,200 --> 00:16:42,210 Quelqu'un peut-il voir ce que notre problème est dans cette ligne? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Il est une chose très minute. 389 00:16:46,969 --> 00:16:48,510 Et vous pouvez aussi regarder votre code. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Il est également line-- oublier quelle ligne il est dans there-- mais il est dans la [inaudible]. 392 00:16:54,940 --> 00:16:55,480 Oui? 393 00:16:55,480 --> 00:16:58,639 >> Haut-parleur 4: Il est sur la supérieure page si vous le lisez dans le livre. 394 00:16:58,639 --> 00:16:59,430 ENCEINTE 1: Exactement. 395 00:16:59,430 --> 00:17:02,620 Ainsi, le débogueur ne pouvait pas dire vous, mais le débogueur 396 00:17:02,620 --> 00:17:05,880 Pourriez-vous vers une ligne que vous savez ne fonctionne pas. 397 00:17:05,880 --> 00:17:09,319 Et parfois, quand surtout plus tard dans le semestre, lorsque 398 00:17:09,319 --> 00:17:12,910 vous avez affaire à un cent, cent quelques lignes de code, et vous 399 00:17:12,910 --> 00:17:16,190 Je ne sais pas où il est défaillant, ceci est une excellente façon de le faire. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Donc, nous avons trouvé notre bug. 402 00:17:18,989 --> 00:17:21,530 Vous pouvez le fixer dans votre fichier, et puis vous pouvez l'exécuter à nouveau, 403 00:17:21,530 --> 00:17:23,029 et tout devrait fonctionner parfaitement. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 Et la chose la plus importante est cela peut sembler, OK. 406 00:17:30,590 --> 00:17:31,090 Ouais. 407 00:17:31,090 --> 00:17:31,370 Laisser refroidir. 408 00:17:31,370 --> 00:17:32,744 Vous saviez ce que vous cherchez. 409 00:17:32,744 --> 00:17:34,910 Donc, vous saviez quoi faire. 410 00:17:34,910 --> 00:17:39,021 >> GDB peut être super utile parce que vous peut imprimer toutes ces choses que vous 411 00:17:39,021 --> 00:17:39,520 ne serait pas. 412 00:17:39,520 --> 00:17:41,160 Il est beaucoup plus utile que printf. 413 00:17:41,160 --> 00:17:43,440 Combien d'entre vous utilisez comme printf 414 00:17:43,440 --> 00:17:46,200 de savoir où un bug a été, non? 415 00:17:46,200 --> 00:17:48,450 Donc, avec cela, vous ne le faites pas avoir toujours revenir, 416 00:17:48,450 --> 00:17:51,139 et comme en commentant Printf, ou en commentant, 417 00:17:51,139 --> 00:17:52,930 et comprendre ce qui vous devez imprimer. 418 00:17:52,930 --> 00:17:55,670 Cela vous permet en fait juste à parcourir, imprimer des choses 419 00:17:55,670 --> 00:18:00,000 que vous allez à travers, donc, vous pouvez observer comment ils changent en temps réel, 420 00:18:00,000 --> 00:18:02,190 que votre programme est en cours d'exécution. 421 00:18:02,190 --> 00:18:04,390 >> Et il prend un peu peu de temps pour s'y habituer. 422 00:18:04,390 --> 00:18:07,850 Je recommande fortement tout genre d'être un peu frustré avec elle 423 00:18:07,850 --> 00:18:08,930 pour le moment. 424 00:18:08,930 --> 00:18:13,450 Si vous passez une heure sur la la semaine prochaine apprendre à utiliser GDB, 425 00:18:13,450 --> 00:18:16,140 vous vous épargnerez beaucoup de temps plus tard. 426 00:18:16,140 --> 00:18:18,750 Et littéralement. nous disons cela aux gens chaque année, 427 00:18:18,750 --> 00:18:23,890 et je me souviens quand je pris la classe, je me suis dit, je vais bien. 428 00:18:23,890 --> 00:18:24,700 Non. 429 00:18:24,700 --> 00:18:27,030 Pset 6 est venu sur et je suis comme, je vais apprendre 430 00:18:27,030 --> 00:18:29,500 comment utiliser GDB parce que je ne sais pas savoir ce qui se passe ici. 431 00:18:29,500 --> 00:18:32,940 >> Donc, si vous prenez le temps de manière utiliser sur les petits programmes 432 00:18:32,940 --> 00:18:35,697 que vous allez être travailler, comme le travail 433 00:18:35,697 --> 00:18:37,530 par quelque chose comme Visionäre, comme ça. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Ou si vous voulez plus de pratique, je suis sûr Je pouvais venir avec des programmes en buggy, 436 00:18:42,850 --> 00:18:45,300 pour vous de déboguer si vous le souhaitez. 437 00:18:45,300 --> 00:18:49,300 >> Mais si vous venez de prendre un peu de temps pour obtenir habituer, jouer juste avec elle, 438 00:18:49,300 --> 00:18:50,550 il va vraiment bien vous servir. 439 00:18:50,550 --> 00:18:52,591 Et il est vraiment l'un des ces choses que vous venez de 440 00:18:52,591 --> 00:18:57,340 avoir à essayer, et vous salir les mains avec, avant de comprendre vraiment. 441 00:18:57,340 --> 00:19:02,090 Je ne comprenais vraiment une fois Je devais choses de débogage avec elle, 442 00:19:02,090 --> 00:19:08,170 et il est beaucoup plus agréable d'avoir une idée de comment déboguer plus tôt plutôt que plus tard. 443 00:19:08,170 --> 00:19:08,850 Dáccord. 444 00:19:08,850 --> 00:19:09,625 Laisser refroidir. 445 00:19:09,625 --> 00:19:12,960 Je sais que ce genre de comme un cours intensif de GDB, 446 00:19:12,960 --> 00:19:16,400 et je vais certainement travailler sur l'obtention ces pour paraître plus gros la prochaine fois. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Laisser refroidir. 449 00:19:18,280 --> 00:19:20,390 >> Donc, si nous revenons à notre PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Est-ce que cela va fonctionner? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 Awh. 454 00:19:30,210 --> 00:19:31,101 Oui. 455 00:19:31,101 --> 00:19:31,600 Dáccord. 456 00:19:31,600 --> 00:19:35,480 Donc, si jamais vous avez besoin de tout ceux de plus, il ya la liste. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Recherche Donc binaire, où tout le monde se souvient le grand spectacle de David 459 00:19:40,830 --> 00:19:42,259 déchirant annuaires téléphoniques de moitié. 460 00:19:42,259 --> 00:19:44,050 Je ne suis pas vraiment le annuaires téléphoniques Plus, 461 00:19:44,050 --> 00:19:46,530 parce que, comme l'endroit où vous faire obtenir des livres de téléphone de nos jours? 462 00:19:46,530 --> 00:19:48,220 Je ne sais pas vraiment. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 La recherche binaire. 465 00:19:50,590 --> 00:19:52,464 Quelqu'un se souvient comment binaires de recherche œuvres? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Tout le monde à tous? 468 00:19:55,220 --> 00:19:56,325 Ouais? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: Vous savez, quand vous regardez à laquelle la moitié 470 00:19:58,283 --> 00:20:01,146 il serait, Sur cette base, et se débarrasser de l'autre moitié. 471 00:20:01,146 --> 00:20:01,896 >> ENCEINTE 1 Exactement. 472 00:20:01,896 --> 00:20:06,290 Ainsi, la recherche binaire, il est une sorte de A- -Nous aiment à l'appeler diviser et conquérir. 473 00:20:06,290 --> 00:20:09,170 Donc, ce que vous allez faire est vous aurez l'air dans le milieu, 474 00:20:09,170 --> 00:20:11,990 et vous verrez si elle correspond ce que vous cherchez. 475 00:20:11,990 --> 00:20:15,420 Et si elle ne le fait pas, alors vous essayez de comprendre, est ce que ça va être à gauche 476 00:20:15,420 --> 00:20:16,450 la moitié ou la moitié droite. 477 00:20:16,450 --> 00:20:19,325 Donc, ce serait peut-être si vous êtes à la recherche à quelque chose qui est classée par ordre alphabétique, 478 00:20:19,325 --> 00:20:20,720 voyez-vous, oh. 479 00:20:20,720 --> 00:20:22,750 Allison ne viennent avant M? 480 00:20:22,750 --> 00:20:23,250 Oui. 481 00:20:23,250 --> 00:20:25,030 Donc, nous allons regarder la première moitié. 482 00:20:25,030 --> 00:20:26,450 >> Ou peut-être comme des numéros. 483 00:20:26,450 --> 00:20:28,830 Tout ce que vous pouvez comparer, il peut être triée. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Vous pouvez utiliser la recherche binaire sur. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Donc, quelqu'un se souvient de cette graphique ou ce qu'il en est? 488 00:20:37,455 --> 00:20:39,520 Sa complexité asymptotique. 489 00:20:39,520 --> 00:20:42,830 Donc, ce graphique seulement décrit combien de temps il 490 00:20:42,830 --> 00:20:46,230 vous emmène à résoudre un problème vous augmentez le nombre de choses 491 00:20:46,230 --> 00:20:47,090 que vous utilisez. 492 00:20:47,090 --> 00:20:51,260 >> Donc, nous avons N, qui est le temps linéaire. 493 00:20:51,260 --> 00:20:54,560 Si N sur deux, ce qui est légèrement mieux, se développe toujours super rapide. 494 00:20:54,560 --> 00:20:58,360 Et puis nous avons Connectez-vous, ce qui est ce que nous considérons recherche binaire. 495 00:20:58,360 --> 00:21:03,630 Si nous remarquons, comme votre problème devient beaucoup et beaucoup plus, 496 00:21:03,630 --> 00:21:06,600 le temps qu'il vous faut pour le résoudre ne vraiment pas beaucoup augmenter. 497 00:21:06,600 --> 00:21:09,010 Il est comme comparable ici au début. 498 00:21:09,010 --> 00:21:10,060 Vous êtes comme, OK. 499 00:21:10,060 --> 00:21:13,000 Tout fait ici pas vraiment Quel que soit celui que nous utilisons, 500 00:21:13,000 --> 00:21:16,220 mais vous sortez d'un million, un milliard. 501 00:21:16,220 --> 00:21:20,010 Vous essayez de trouver some-- --you're essayer de trouver une aiguille dans une botte de foin. 502 00:21:20,010 --> 00:21:21,550 >> Je pense que vous voulez ce problème. 503 00:21:21,550 --> 00:21:25,850 Vous souhaitez que cette complexité, pas linéaire, car pour tout ce que vous 504 00:21:25,850 --> 00:21:30,049 sais tu vas être à la recherche à travers chaque aiguille individuelle, chose de foin, 505 00:21:30,049 --> 00:21:31,340 essayer de regarder pour votre aiguille. 506 00:21:31,340 --> 00:21:34,730 Et pas trop de plaisir dans mon opinion. 507 00:21:34,730 --> 00:21:35,500 Je voudrais rapidement. 508 00:21:35,500 --> 00:21:36,620 Je l'aime efficace. 509 00:21:36,620 --> 00:21:40,450 Et les étudiants qui travaillent dur vous les gars sont, vous savez travailler plus intelligemment, 510 00:21:40,450 --> 00:21:43,010 pas plus difficile ce genre de chose, comment vous peut compenser ces algorithmes. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Donc, nous allons marcher par juste un petit exemple. 513 00:21:47,910 --> 00:21:51,090 Je pense que vous devriez avoir une main sur la recherche binaire, 514 00:21:51,090 --> 00:21:54,352 mais au cas où quelqu'un est un peu floue, veulent renforcer, 515 00:21:54,352 --> 00:21:56,310 nous allons simplement aller à travers un exemple ici. 516 00:21:56,310 --> 00:21:59,490 Donc, nous sommes à la recherche si le tableau contient sept. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Donc, la première chose que nous faisons est regarder dans le milieu, à droite? 519 00:22:06,010 --> 00:22:09,340 Et aussi, vous allez être codage Recherche binaire dans une seconde. 520 00:22:09,340 --> 00:22:11,310 Donc, ça va être amusant. 521 00:22:11,310 --> 00:22:13,710 Donc nous regardons dans le petits tableaux intermédiaires 3. 522 00:22:13,710 --> 00:22:15,501 Est-ce que 3 égaux 7? 523 00:22:15,501 --> 00:22:16,000 Ne fonctionne pas. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Il est six. 526 00:22:19,550 --> 00:22:21,480 Alors, est-il moins de ou supérieur à sept? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Moins que. 529 00:22:23,960 --> 00:22:24,570 Oui. 530 00:22:24,570 --> 00:22:25,170 Travail les gars de Nice. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Je sens que je que je devrais avoir des bonbons parce que je 533 00:22:27,360 --> 00:22:29,460 vouloir jeter dans les cours. 534 00:22:29,460 --> 00:22:30,270 Il est ce que je vais faire la semaine prochaine. 535 00:22:30,270 --> 00:22:31,436 Il vous gardera gars pointu. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Donc, nous jetons que premier semestre, non? 538 00:22:34,690 --> 00:22:35,670 elle était inférieure à. 539 00:22:35,670 --> 00:22:39,325 nous savons que tout sur le côté gauche 540 00:22:39,325 --> 00:22:41,700 va être inférieur à ce que nous sommes actuellement à la recherche pour. 541 00:22:41,700 --> 00:22:43,491 Donc, il n'y a pas besoin de faire attention à elle. 542 00:22:43,491 --> 00:22:45,120 Il suffit de l'oublier. 543 00:22:45,120 --> 00:22:48,720 Donc, maintenant nous regardons notre droite, et nous sommes au milieu là-bas, 544 00:22:48,720 --> 00:22:50,510 et maintenant il est neuf. 545 00:22:50,510 --> 00:22:55,510 Ainsi, 9 est-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Supérieure à ce que nous sommes cherchez, non? 547 00:22:57,470 --> 00:22:59,860 Donc, nous allons jeter tout de suite à droite. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Comme ça. 550 00:23:01,940 --> 00:23:03,700 Maintenant, tout ce que nous sommes laissés avec est un. 551 00:23:03,700 --> 00:23:07,760 Donc, nous vérifions, est celui que nous recherchons? il est. 552 00:23:07,760 --> 00:23:08,970 Nous avons trouvé ce que nous voulions. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Nous avons donc fait. 555 00:23:11,690 --> 00:23:12,550 Recherche bilinéaire. 556 00:23:12,550 --> 00:23:15,740 >> Et si vous remarquez, nous eu sept entrées là-bas. 557 00:23:15,740 --> 00:23:24,320 Il ne nous a fallu que trois fois, mais si vous faites comme d'un milliard, 558 00:23:24,320 --> 00:23:28,190 vous savez les gars combien d'étapes il serait prendre si nous avions quatre milliards d'choses? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Les suppositions? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Il est 32. 563 00:23:33,960 --> 00:23:37,110 32 étapes pour trouver quelque chose dans un quatre milliards 564 00:23:37,110 --> 00:23:39,650 rangée d'éléments en raison de puissances de deux. 565 00:23:39,650 --> 00:23:43,550 Donc deux est à 32, est à quatre milliards. 566 00:23:43,550 --> 00:23:50,430 >> Comment donc assez fou que vous êtes encore dans comme un assez petit nombre d'étapes 567 00:23:50,430 --> 00:23:52,650 de trouver quelque chose dans quatre milliards d'éléments. 568 00:23:52,650 --> 00:23:55,730 Donc, sur cette note, nous sommes va coder cette 569 00:23:55,730 --> 00:23:58,950 si vous les gars peuvent réellement sorte de voir comment cela fonctionne. 570 00:23:58,950 --> 00:24:01,520 Très bien, alors vous avez peut coder. 571 00:24:01,520 --> 00:24:04,100 Je vais vous laisser les gars parler un peu. 572 00:24:04,100 --> 00:24:07,970 Apprenez à connaître les gens autour de vous, qui est ce que quelqu'un voulait de la dernière section. 573 00:24:07,970 --> 00:24:10,280 >> Donc, apprendre à connaître les gens autour de vous. 574 00:24:10,280 --> 00:24:11,305 Parlez à un peu. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 Et tout ce que je veux de toi gars est juste en ce moment 577 00:24:15,730 --> 00:24:17,575 essayer de créer un plan de pseudo-code. 578 00:24:17,575 --> 00:24:18,075 D'accord? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Tout ce que je veux de vous les gars vous êtes est aller juste à remplir dans ce cas de tout. 583 00:24:29,520 --> 00:24:32,170 Donc, je l'ai mis ces supérieure et des bornes inférieures qui 584 00:24:32,170 --> 00:24:35,250 représenter le début et à la fin de notre tableau. 585 00:24:35,250 --> 00:24:40,440 Et vous allez réellement boucle et comprendre 586 00:24:40,440 --> 00:24:42,470 ce que nous faisons dans cette boucle while. 587 00:24:42,470 --> 00:24:45,810 >> Donc, si vous pouvez comprendre out-- je dois un soupçon there-- quels sont les cas 588 00:24:45,810 --> 00:24:46,640 que nous avons ici? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Donc, si vous voulez comprendre la cas, nous Pseudocode ceux 591 00:24:51,560 --> 00:24:53,350 et puis nous allons effectivement les code. 592 00:24:53,350 --> 00:24:55,330 Et ça va être, je penser, je l'espère ça va 593 00:24:55,330 --> 00:24:56,788 être un peu plus facile que prévu. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Parce qu'il est pas que beaucoup de code, en fait, ce qui est vraiment cool. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> L'ÉLÈVE: [inaudible]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 ENSEIGNANT: Oui. 601 00:25:37,650 --> 00:25:38,595 Il y avait quelque chose à trouver dans le milieu. 602 00:25:38,595 --> 00:25:39,552 >> L'ÉLÈVE: nous pouvons donc l'utiliser. 603 00:25:39,552 --> 00:25:39,770 Dáccord. 604 00:25:39,770 --> 00:25:40,603 >> ENSEIGNANT: Parfait. 605 00:25:40,603 --> 00:25:42,950 Voilà donc la première chose que nous devons faire. 606 00:25:42,950 --> 00:25:44,330 Donc, trouver le milieu. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Grand. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Donc, avez-vous une idée de la façon dont nous pourrions en fait trouver au milieu avec le code? 611 00:25:55,010 --> 00:25:55,980 >> L'ÉLÈVE: Oui. 612 00:25:55,980 --> 00:25:57,000 n plus de 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 ENSEIGNANT: Donc, plus de 2 n. 615 00:25:59,500 --> 00:26:05,170 Donc, une chose à retenir est que vos limites supérieures et inférieures changent. 616 00:26:05,170 --> 00:26:08,110 Nous continuons la constriction de la partie du tableau nous cherchons à. 617 00:26:08,110 --> 00:26:11,970 Alors n plus de 2 fonctionne uniquement pour la première chose que nous faisons. 618 00:26:11,970 --> 00:26:17,810 Donc, en prenant supérieure et inférieure en compte, comment pourrions-nous obtenir cet élément milieu? 619 00:26:17,810 --> 00:26:20,640 Parce que nous voulons que le milieu entre supérieur et inférieur, non? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> L'ÉLÈVE: [inaudible]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> ENSEIGNANT: Nous avons donc un certain milieu. 625 00:26:28,080 --> 00:26:32,730 Et ce sera supérieure, plus bas sur 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Impressionnant. 628 00:26:35,690 --> 00:26:36,570 Nous y voilà. 629 00:26:36,570 --> 00:26:37,280 Un bas de ligne. 630 00:26:37,280 --> 00:26:38,560 Les gars, vous êtes sur votre chemin. 631 00:26:38,560 --> 00:26:41,400 Alors, maintenant que nous avons notre milieu, que voulons-nous faire? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Juste en général. 634 00:26:45,900 --> 00:26:47,734 Vous n'êtes pas obligé de le coder. 635 00:26:47,734 --> 00:26:48,335 Oui. 636 00:26:48,335 --> 00:26:49,210 L'ÉLÈVE: [inaudible]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 ENSEIGNANT: Donc, il est ainsi parce que vous êtes trouver la moyenne entre les deux 639 00:27:10,310 --> 00:27:10,810 d'entre eux. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Donc, si vous pensez à eux comme une sorte de plus en plus sur les côtés, 642 00:27:17,370 --> 00:27:21,640 penser que vous vous approchez au milieu, vous voulez comme ça. 643 00:27:21,640 --> 00:27:27,150 Donc, si vous étiez sur chaque côté de la milieu, et nous avons comme 5 et 7. 644 00:27:27,150 --> 00:27:31,440 Lorsque vous ajoutez ensemble vous obtenir 12, vous divisez par 2, est de 6. 645 00:27:31,440 --> 00:27:33,726 >> Parfois, il est difficile de expliquer pourquoi cela fonctionne, 646 00:27:33,726 --> 00:27:35,600 mais si vous travaillez à travers Par exemple, parfois, 647 00:27:35,600 --> 00:27:37,962 ça va vous aider à déterminer si il devrait être plus ou moins. 648 00:27:37,962 --> 00:27:38,846 Oui. 649 00:27:38,846 --> 00:27:40,830 >> L'ÉLÈVE: [Inaudible] exactement au milieu 650 00:27:40,830 --> 00:27:43,950 si elles avaient un cas où il ya beaucoup de petits nombres 651 00:27:43,950 --> 00:27:45,860 et comme un grand nombre? 652 00:27:45,860 --> 00:27:49,750 >> ENSEIGNANT: Donc, tout ce que vous avez besoin est le milieu de la matrice. 653 00:27:49,750 --> 00:27:53,010 Donc, si vous aviez un tas de petits nombres et puis un vraiment grand nombre 654 00:27:53,010 --> 00:27:54,799 à la fin, il n'a pas d'importance. 655 00:27:54,799 --> 00:27:56,840 Tout ce qui importe est que ils sont triés, vous venez de 656 00:27:56,840 --> 00:27:59,339 vouloir regarder le milieu de le tableau parce que vous êtes encore 657 00:27:59,339 --> 00:28:00,700 tranchage votre problème en deux. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Laisser refroidir. 660 00:28:03,680 --> 00:28:06,430 Alors, maintenant que nous avons le milieu, que faisons-nous maintenant? 661 00:28:06,430 --> 00:28:07,150 >> L'ÉLÈVE: Comparer. 662 00:28:07,150 --> 00:28:08,150 Animateur: Le comparer. 663 00:28:08,150 --> 00:28:11,670 Donc comparer milieu de value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Laisser refroidir. 666 00:28:15,160 --> 00:28:17,950 Donc, vous voyez ici, nous avons cette valeur que nous voulons ici. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Rappelez-vous ceci est un tableau. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Donc milieu se réfère à l'indice. 671 00:28:26,970 --> 00:28:29,785 Donc, nous voulons faire de valeurs moyennes. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Ne pas oublier si vous voulez à comparer, égaux doubles. 674 00:28:35,650 --> 00:28:38,250 Vous faites equals unique que vous êtes aller juste à les rétrocéder, 675 00:28:38,250 --> 00:28:41,090 et puis, bien sûr, il est va être la valeur que vous souhaitez. 676 00:28:41,090 --> 00:28:42,300 Donc, ne pas le faire. 677 00:28:42,300 --> 00:28:44,350 >> Nous allons donc voir si les valeurs de la moyenne 678 00:28:44,350 --> 00:28:46,460 est égale à la valeur que nous voulons. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Ne pas oublier vos accolades. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox devrait disparaître. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Alors, que faisons-nous dans ce cas? 685 00:28:56,200 --> 00:28:59,360 Si elle est ce que voulons-nous revenir? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Nous essayons de dire. 688 00:29:02,626 --> 00:29:03,440 >> L'ÉLÈVE: Imprimez. 689 00:29:03,440 --> 00:29:05,314 >> ENSEIGNANT: Eh bien, nous ne veulent pas imprimer. 690 00:29:05,314 --> 00:29:08,220 Donc ceci est un booléen ici, donc nous vouloir retourner true ou false. 691 00:29:08,220 --> 00:29:12,280 Nous disons, est ce numéro un [? RRA? ?] Donc, si elle est, 692 00:29:12,280 --> 00:29:13,788 nous revenons juste vrai. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Si je peux épeler vrai. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> ÉTUDIANT: Pourquoi ne pas revenir à zéro? 697 00:29:20,805 --> 00:29:22,930 ENSEIGNANT: Donc, vous pourriez retourner zéro si vous voulez. 698 00:29:22,930 --> 00:29:26,780 Mais dans ce cas parce que notre fonction retourne un booléen, 699 00:29:26,780 --> 00:29:28,962 nous devons retourner true ou false. 700 00:29:28,962 --> 00:29:30,920 L'ÉLÈVE: Lorsque vous êtes disant expression booléenne, 701 00:29:30,920 --> 00:29:33,450 vous pouvez régler égale à faux? 702 00:29:33,450 --> 00:29:39,860 Comme si je veux dire, si cette condition ne sont pas remplies, comme est supérieure vaut Faux. 703 00:29:39,860 --> 00:29:42,332 Est-il comprendre si vous venez mettre faux de l'autre côté? 704 00:29:42,332 --> 00:29:43,040 ENSEIGNANT: Ouais. 705 00:29:43,040 --> 00:29:44,820 Donc en fait, si vous êtes jamais faire quelque chose 706 00:29:44,820 --> 00:29:49,600 comme est supérieur ou inférieur est, qui renvoie vrai ou faux 707 00:29:49,600 --> 00:29:53,850 et il est en fait un mauvais style de par exemple égal à égal vrai ou égaux 708 00:29:53,850 --> 00:29:54,840 vaut Faux. 709 00:29:54,840 --> 00:30:00,210 Vous souhaitez utiliser ce résultat comme lui-même en tant que votre chèque. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Pas ce que je voulais. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Voilà ce que je voulais. 714 00:30:09,240 --> 00:30:13,205 Ainsi, dans le cas de que vous demandez quelque chose comme sauvegarde dans c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Donc, si nous avons int main (void) et quelque chose comme ça. 717 00:30:25,150 --> 00:30:31,922 Et si vous avez est supérieure de certaines entrées et vous êtes 718 00:30:31,922 --> 00:30:33,630 vous demandant si vous pouvez faire quelque chose comme ça? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Droit? 721 00:30:35,679 --> 00:30:37,470 Etudiant: Je tentais de le faire [inaudible]. 722 00:30:37,470 --> 00:30:38,450 Parce que si it's-- 723 00:30:38,450 --> 00:30:39,200 ENSEIGNANT: Droit. 724 00:30:39,200 --> 00:30:41,197 Donc, vous voulez que ce soit faux, non? 725 00:30:41,197 --> 00:30:41,780 L'ÉLÈVE: Oui. 726 00:30:41,780 --> 00:30:45,960 ENSEIGNANT: Donc, dans ce cas vous il veut à exécuter si il est pas vrai. 727 00:30:45,960 --> 00:30:50,510 Donc, la chose cool que vous faites là est la suivante. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Alors rappelez-vous exclamation Point nie choses? 730 00:30:55,650 --> 00:30:58,270 Il dit [inaudible] ne signifie pas. 731 00:30:58,270 --> 00:31:03,590 Donc, si nous regardons seulement cette partie ici, vous seriez 732 00:31:03,590 --> 00:31:05,740 dire qui sera évalué à faux comme vous le souhaitez. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Pas faux est vrai que signifie que ce serait exécuter. 735 00:31:09,880 --> 00:31:11,037 Est-ce logique? 736 00:31:11,037 --> 00:31:11,620 L'ÉLÈVE: Oui. 737 00:31:11,620 --> 00:31:12,453 INSTRUCTEUR: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 Dáccord. 740 00:31:14,300 --> 00:31:16,330 Donc, nous pourrions revenir vrai dans ce cas. 741 00:31:16,330 --> 00:31:20,357 Alors maintenant, nous avons deux autres cas dans cette affaire. 742 00:31:20,357 --> 00:31:21,565 Quels sont nos deux autres cas? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Disons simplement faire de cette façon. 745 00:31:32,900 --> 00:31:40,660 Commençons donc avec d'autre si les valeurs au milieu 746 00:31:40,660 --> 00:31:43,230 est inférieure à la valeur que nous voulons. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Donc, notre valeur dans le milieu est moins que la valeur que nous recherchons. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Alors, qui limite vous faire pensons que nous voulons mettre à jour? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Supérieure ou inférieure? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Supérieure? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Ainsi, le côté de la matrice allons-nous envisager? 757 00:32:06,470 --> 00:32:07,500 >> ÉTUDIANTS: La plus faible. 758 00:32:07,500 --> 00:32:09,750 >> ENSEIGNANT: Nous allons nous à se pencher sur la gauche. 759 00:32:09,750 --> 00:32:11,120 Donc, d'autre si peu de valeur est moindre. 760 00:32:11,120 --> 00:32:14,730 Donc, votre valeur moyenne ici est moins que ce que nous voulons. 761 00:32:14,730 --> 00:32:17,202 Donc, nous voulons prendre le droite de notre tableau. 762 00:32:17,202 --> 00:32:18,910 Nous allons donc mettre à jour notre borne inférieure. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Donc, nous allons réassigner notre faible. 765 00:32:23,020 --> 00:32:25,221 Et que pensez-vous devrait être inférieur? 766 00:32:25,221 --> 00:32:26,304 ÉTUDIANTS: La valeur moyenne? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 ENSEIGNANT: Donc, le milieu value-- 769 00:32:28,820 --> 00:32:30,136 L'ÉLÈVE: Plus 1. 770 00:32:30,136 --> 00:32:31,010 ENSEIGNANT: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Quelqu'un peut-il me dire pourquoi nous avons que plus 1? 773 00:32:34,380 --> 00:32:35,730 >> L'ÉLÈVE: [? Aucune valeur?] est plus égale. 774 00:32:35,730 --> 00:32:36,120 >> ENSEIGNANT: Droit. 775 00:32:36,120 --> 00:32:38,661 Parce que nous savons déjà que notre valeur centrale est pas égal à 776 00:32:38,661 --> 00:32:42,750 et nous voulons exclure de toutes les recherches ultérieures. 777 00:32:42,750 --> 00:32:46,360 Si vous oubliez que plus 1, ce aimeront boucle indéfiniment. 778 00:32:46,360 --> 00:32:49,620 Et vous aurez juste être pris dans une boucle infinie et alors vous aurez une erreur de segmentation 779 00:32:49,620 --> 00:32:50,370 et les choses vont mal. 780 00:32:50,370 --> 00:32:54,780 Donc, assurez-vous toujours que vous n'êtes pas y compris la valeur que vous venez de 781 00:32:54,780 --> 00:32:55,380 regardé. 782 00:32:55,380 --> 00:32:58,530 Donc, nous nous occupons de cela avec un plus 1. 783 00:32:58,530 --> 00:33:04,840 >> Nous avons donc maintenant notre dernière condition qui je toujours pour des raisons de sécurité 784 00:33:04,840 --> 00:33:12,664 vous pouvez vérifier ici, si d'autre valeur à le milieu est supérieure à la valeur 785 00:33:12,664 --> 00:33:13,163 nous voulons. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Cela signifie que nous voulons la moitié de gauche. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Alors, qui que nous allons mettre à jour? 790 00:33:23,260 --> 00:33:23,760 Supérieure. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 Et quel est celui d'aller à égal? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Moyen moins 1 parce que, bien sûr, nous voulons 795 00:33:33,690 --> 00:33:38,370 à faire en sorte que nous ne sommes pas en regardant cette valeur moyenne à nouveau. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 Et puis nous l'avons. 798 00:33:45,110 --> 00:33:45,610 Ce est tout. 799 00:33:45,610 --> 00:33:46,820 Voilà tout est recherche binaire. 800 00:33:46,820 --> 00:33:48,190 Il est pas si mal, non? 801 00:33:48,190 --> 00:33:51,590 Il est comme 10 lignes de Code avec un espace blanc. 802 00:33:51,590 --> 00:33:57,510 Donc, très puissant, très utile, vous voulez être utiliser dans un de vos psets plus tard. 803 00:33:57,510 --> 00:33:59,360 Peut-être pas celui-ci, mais plus tard. 804 00:33:59,360 --> 00:34:00,670 Donc apprendre. 805 00:34:00,670 --> 00:34:01,510 Aimer. 806 00:34:01,510 --> 00:34:02,980 Il vous traiter ainsi. 807 00:34:02,980 --> 00:34:05,370 Donc, quelqu'un at-il des questions sur la recherche binaire? 808 00:34:05,370 --> 00:34:06,196 Oui. 809 00:34:06,196 --> 00:34:09,840 >> L'ÉLÈVE: Est-ce important si votre n est pair ou impair? 810 00:34:09,840 --> 00:34:10,750 >> INSTRUCTEUR: Non 811 00:34:10,750 --> 00:34:18,150 Parce que nous jetons à la moyenne comme un int, il sera simplement tronquer. 812 00:34:18,150 --> 00:34:21,600 Donc, il restera un nombre entier et il sera finalement trier tout. 813 00:34:21,600 --> 00:34:23,909 Donc, vous ne devez pas vous inquiéter à ce sujet. 814 00:34:23,909 --> 00:34:24,580 Tout le monde bien? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Impressionnant. 817 00:34:26,850 --> 00:34:27,919 Laisser refroidir. 818 00:34:27,919 --> 00:34:30,836 Donc, vous avez obtenu ce gars. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Diaporama. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Alors que nous parlions, je sais David mentionné runtimes de complexité. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Donc, dans le meilleur des cas, il est juste un, que nous appelons la constante de temps. 825 00:34:50,340 --> 00:34:51,909 Quelqu'un peut-il me dire pourquoi cela pourrait être? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Quel type de scénario qui entraînerait? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> L'ÉLÈVE: [Inaudible] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 ENSEIGNANT: Donc, le milieu étant le premier élément que nous arrivons à, non? 833 00:35:03,830 --> 00:35:08,167 Donc, soit un tableau d'un ou tout ce que nous cherchons juste 834 00:35:08,167 --> 00:35:09,750 se trouve être smack dab dans le milieu. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Voilà donc notre meilleur des cas. 837 00:35:13,380 --> 00:35:17,540 Vous obtenez de véritables problèmes, probablement pas va atteindre [inaudible] qui souvent. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 Qu'en est-il notre pire des cas? 840 00:35:19,750 --> 00:35:21,270 Notre pire des cas est log n. 841 00:35:21,270 --> 00:35:25,360 Et cela a à voir avec l'ensemble des puissances de deux chose que je parlais. 842 00:35:25,360 --> 00:35:30,930 >> Ainsi, dans le pire des cas, cela signifierait que nous avons dû couper le tableau en bas 843 00:35:30,930 --> 00:35:33,270 jusqu'à ce qu'il soit un élément d'un seul. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Nous avons donc dû l'abattre dans la moitié autant de fois que nous le pouvions. 846 00:35:38,930 --> 00:35:41,430 Voilà pourquoi il est log n parce que vous continuez à diviser par deux. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Donc, les hypothèses, les choses que vous besoin de savoir si vous êtes jamais 849 00:35:45,830 --> 00:35:48,050 va utiliser une recherche binaire. 850 00:35:48,050 --> 00:35:50,680 Vos éléments doivent être triés. 851 00:35:50,680 --> 00:35:53,890 Ils doivent être triés car qui est la seule façon vous 852 00:35:53,890 --> 00:35:57,060 peut savoir si vous êtes en mesure à jeter la moitié. 853 00:35:57,060 --> 00:36:00,260 >> Si vous aviez ce sac pêle-mêle des numéros et que vous dites, 854 00:36:00,260 --> 00:36:05,380 OK, je vais vérifier le milieu nombre et le nombre que je cherche 855 00:36:05,380 --> 00:36:08,510 est moins que cela, je vais juste à jeter arbitrairement moitié. 856 00:36:08,510 --> 00:36:11,130 Vous ne voudriez pas savoir si votre nombres dans cette autre moitié. 857 00:36:11,130 --> 00:36:12,655 Votre liste doit être triée. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 De plus, cela peut être aller de l'avant un peu, 860 00:36:16,560 --> 00:36:18,360 mais vous devez avoir accès aléatoire. 861 00:36:18,360 --> 00:36:21,940 Vous devez être capable de tout aller à cet élément du milieu. 862 00:36:21,940 --> 00:36:25,110 Si vous avez à parcourir par quelque chose 863 00:36:25,110 --> 00:36:28,630 ou cela vous prend des mesures supplémentaires pour se rendre à cet élément du milieu, 864 00:36:28,630 --> 00:36:31,750 il est pas plus parce que log n vous ajoutez plus de travail en elle. 865 00:36:31,750 --> 00:36:34,800 Et cela fera un peu plus de sens dans deux semaines, 866 00:36:34,800 --> 00:36:37,950 mais je ne voulais genre de préface, vous les gars donner une idée de ce qui est 867 00:36:37,950 --> 00:36:38,999 à venir. 868 00:36:38,999 --> 00:36:40,790 Mais ce sont les deux hypothèses importantes 869 00:36:40,790 --> 00:36:44,804 que vous avez besoin pour une liste binaire. 870 00:36:44,804 --> 00:36:45,720 Assurez-vous qu'il est triée. 871 00:36:45,720 --> 00:36:47,920 Voilà le grand pour vous les gars en ce moment. 872 00:36:47,920 --> 00:36:52,170 Et que nous pouvons aller en le reste de nos sortes. 873 00:36:52,170 --> 00:36:56,444 Donc quatre bulle sorts--, insertion, la sélection et la fusion. 874 00:36:56,444 --> 00:36:57,485 Ils sont tous plutôt cool. 875 00:36:57,485 --> 00:37:02,860 Si vous les gars décident de prendre CS 124, prenez connaissance de toutes sortes de sortes. 876 00:37:02,860 --> 00:37:07,575 Et si vous êtes un fan XKCD, il est une bande dessinée sur vraiment cool 877 00:37:07,575 --> 00:37:11,530 comme sortes vraiment inefficaces, que je vous recommande fortement d'aller à regarder. 878 00:37:11,530 --> 00:37:16,170 L'un d'eux est comme panique sorte, qui est comme, oh non, retourner réseau aléatoire. 879 00:37:16,170 --> 00:37:16,991 système d'arrêt. 880 00:37:16,991 --> 00:37:17,490 Laissez. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Donc humour geek est toujours bon. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Donc ne Quelqu'un se souvient genre de comme juste une idée générale 885 00:37:25,750 --> 00:37:27,810 de la façon dont fonctionne tri à bulles. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Vous vous souvenez? 888 00:37:32,155 --> 00:37:32,755 >> L'ÉLÈVE: Oui. 889 00:37:32,755 --> 00:37:33,970 >> ENSEIGNANT: Allez-y. 890 00:37:33,970 --> 00:37:38,980 >> Etudiant: Ainsi vous allez à travers et si elle est plus grande, alors vous échanger les deux. 891 00:37:38,980 --> 00:37:39,820 >> ENSEIGNANT: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Exactement. 893 00:37:40,564 --> 00:37:41,730 Alors que vous venez itérer. 894 00:37:41,730 --> 00:37:43,050 Vous vérifiez deux chiffres. 895 00:37:43,050 --> 00:37:46,510 Si l'un est plus grand avant que l'une après, 896 00:37:46,510 --> 00:37:50,230 vous les échangez juste pour que dans de cette façon tous les numéros plus élevés 897 00:37:50,230 --> 00:37:54,990 propager vers le haut vers la fin de la liste et tous les nombres inférieurs bulle vers le bas. 898 00:37:54,990 --> 00:37:59,355 >> At-il vous montrer les gars cool des effets sonores tri vidéo? 899 00:37:59,355 --> 00:38:00,480 Il est plutôt cool. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Alors que Robert vient d'être dit, l'algorithme que vous entrez simplement dans la liste, 902 00:38:05,200 --> 00:38:07,930 permuter les valeurs adjacentes si ils ne sont pas dans l'ordre. 903 00:38:07,930 --> 00:38:10,975 Et puis juste continuer à répéter jusqu'à ce que vous ne faites pas de swaps. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Donc, pas mal, non? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Donc nous avons juste un petit exemple ici. 908 00:38:16,319 --> 00:38:18,360 Donc, cela va trier les dans l'ordre croissant. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Ainsi, lorsque nous passons par le premier temps, nous regardons à travers huit 911 00:38:23,470 --> 00:38:26,880 et six ne sont évidemment pas dans l'ordre, nous les échanger. 912 00:38:26,880 --> 00:38:27,985 >> Alors regardez la suivante. 913 00:38:27,985 --> 00:38:29,430 Huit et quatre pas dans l'ordre. 914 00:38:29,430 --> 00:38:30,450 Les échanger. 915 00:38:30,450 --> 00:38:32,530 Et puis huit et deux, les permuter. 916 00:38:32,530 --> 00:38:33,470 Nous y voilà. 917 00:38:33,470 --> 00:38:39,519 Ainsi, après votre premier passage, vous savoir que votre plus grand nombre 918 00:38:39,519 --> 00:38:41,810 va être tout le chemin en haut, car il est juste 919 00:38:41,810 --> 00:38:44,210 va être constamment plus que tout le reste 920 00:38:44,210 --> 00:38:46,810 et il va juste bulle tout le chemin à la fin il. 921 00:38:46,810 --> 00:38:48,226 Est-ce que cela a un sens pour tout le monde? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Laisser refroidir. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Alors nous regardons notre deuxième passage. 926 00:38:53,920 --> 00:38:54,980 Six et quatre, interrupteur. 927 00:38:54,980 --> 00:38:55,920 Six et deux, interrupteur. 928 00:38:55,920 --> 00:38:58,700 Et maintenant nous avons quelques choses dans l'ordre. 929 00:38:58,700 --> 00:39:02,240 Ainsi, pour chaque passe que nous faire à travers l'ensemble de notre liste, 930 00:39:02,240 --> 00:39:06,320 nous savons que comme que de nombreux numéros à la fin auront été triés. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Nous faisons donc un troisième passage, qui est un swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 Et puis sur notre quatrième passer, nous avons cases à zéro. 935 00:39:15,910 --> 00:39:18,570 Et si nous savons que notre tableau a été trié. 936 00:39:18,570 --> 00:39:20,900 >> Et qui est le grand chose avec tri à bulles. 937 00:39:20,900 --> 00:39:23,720 Nous savons que lorsque nous avoir zéro swaps, qui 938 00:39:23,720 --> 00:39:26,497 signifie que tout est en ordre complète. 939 00:39:26,497 --> 00:39:27,580 Il est un peu de la façon dont nous vérifions. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Donc, nous allons également coder bulle sorte qui est aussi pas mal. 942 00:39:36,480 --> 00:39:38,120 Aucun d'entre eux sont si mal que ça. 943 00:39:38,120 --> 00:39:40,210 Je sais qu'ils peuvent sembler un peu effrayant. 944 00:39:40,210 --> 00:39:42,124 Je sais que quand je prenais la classe, même quand je 945 00:39:42,124 --> 00:39:44,290 a été l'enseignement de la classe pour la première fois l'année dernière, 946 00:39:44,290 --> 00:39:46,165 Je suis comme, comment dois-je faire? 947 00:39:46,165 --> 00:39:48,540 Il est logique en théorie, mais comment pouvons-nous réellement faire cela? 948 00:39:48,540 --> 00:39:51,420 Qui est la raison pour laquelle je tiens aussi à marcher dans le code avec vous les gars ici. 949 00:39:51,420 --> 00:39:54,915 Je dois donc un pseudo pour vous les gars cette fois. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Il suffit donc de garder cela à l'esprit nous sommes sur le point de passer sur. 952 00:39:58,970 --> 00:40:04,210 Nous avons donc une certaine compteur garde la trace de nos échanges, 953 00:40:04,210 --> 00:40:08,370 parce que nous devons faire en sorte que nous vérifions que. 954 00:40:08,370 --> 00:40:11,830 Et nous parcourons l'ensemble du réseau comme nous venons de le faire avec cet exemple. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Si l'élément est plus grand que avant l'élément après où nous en sommes, 957 00:40:17,325 --> 00:40:20,760 nous les échangeons et on incrémente notre compteur parce que dès que nous échangeons, 958 00:40:20,760 --> 00:40:23,850 nous voulons que notre compteur sais. 959 00:40:23,850 --> 00:40:26,247 Vous avez des questions là-bas? 960 00:40:26,247 --> 00:40:27,580 Quelque chose semble drôle ici. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 L'ÉLÈVE: Avez-vous mis le compteur à zéro chaque fois que vous allez dans la boucle? 963 00:40:32,350 --> 00:40:34,339 Avez-vous pas continuer Retour à zéro chaque fois? 964 00:40:34,339 --> 00:40:35,505 ENSEIGNANT: Pas nécessairement. 965 00:40:35,505 --> 00:40:39,710 Donc ce qui arrive est que nous passons par ici. 966 00:40:39,710 --> 00:40:43,830 Donc faire tout, rappelez-vous, ce exécutera une fois à coup sûr. 967 00:40:43,830 --> 00:40:46,480 Donc, ça va régler le compteur égale à zéro, 968 00:40:46,480 --> 00:40:48,070 puis il va itérer. 969 00:40:48,070 --> 00:40:50,590 Comme il parcourt à travers, il mettra à jour compteur. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Comme il met à jour contre, quand il est fait, quand il atteint la fin de la rangée, 972 00:40:56,900 --> 00:41:00,830 si notre liste n'a pas été triés, compteur ont été mis à jour. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Alors il vérifie l'état et il dit, OK, va à l'encontre supérieur à zéro. 975 00:41:07,150 --> 00:41:09,290 Dans ce cas, le faire à nouveau. 976 00:41:09,290 --> 00:41:14,340 Vous souhaitez réinitialiser sorte que lorsque vous passer à travers, le compteur est égal à zéro. 977 00:41:14,340 --> 00:41:18,240 Si vous passez par un tri tableau, rien ne change, 978 00:41:18,240 --> 00:41:21,355 cela échoue, et vous retourner la liste triée. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Est-ce que cela a un sens? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 L'ÉLÈVE: Peut-être dans un peu. 983 00:41:26,356 --> 00:41:27,147 ENSEIGNANT: OK. 984 00:41:27,147 --> 00:41:28,980 Si il ya un autre question qui se pose. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Oui. 987 00:41:30,680 --> 00:41:33,760 >> L'ÉLÈVE: Que serait la fonction être pour échanger les éléments? 988 00:41:33,760 --> 00:41:36,900 >> ENSEIGNANT: Nous pouvons donc écrire que si nous allons en ce moment. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Laisser refroidir. 991 00:41:38,300 --> 00:41:42,155 Donc, sur cette note, Alison va pour revenir à l'appareil. 992 00:41:42,155 --> 00:41:43,080 Ça va être amusant. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 Et nous avons notre belle tri à bulles chose ici. 995 00:41:47,390 --> 00:41:50,800 Donc je l'ai déjà fait du vélo à travers le réseau. 996 00:41:50,800 --> 00:41:53,030 Nous avons nos swaps sont égales à zéro. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Donc, nous voulons échanger adjacent éléments si elles sont hors d'usage. 999 00:41:58,440 --> 00:42:03,020 Donc, la première chose que nous devons ne itérer sur notre tableau. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Alors, comment pensez-vous que nous pourrions itérer sur notre tableau? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Nous avons pour et i est égal à 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Nous voulons i à être moins que n moins 1 moins k. 1006 00:42:22,454 --> 00:42:23,870 Et je vais vous expliquer que dans un second. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Donc, cela est une optimisation ici où, rappeler comment je l'ai dit après chaque passage 1009 00:42:32,830 --> 00:42:36,655 à travers le tableau nous savoir que tout ce qui est on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Donc, après un passage nous sachez que ce sont triés. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Après deux passages nous savons que tout cela est triée. 1014 00:42:50,060 --> 00:42:52,750 Après trois passages nous sais que cela triés. 1015 00:42:52,750 --> 00:42:55,620 Donc, la façon dont je l'itération à travers le réseau ici, 1016 00:42:55,620 --> 00:43:01,090 est il est fait sûr d'aller seulement à travers ce que nous savons est non triés. 1017 00:43:01,090 --> 00:43:01,644 D'accord? 1018 00:43:01,644 --> 00:43:02,810 Ceci est juste une optimisation. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Vous pouvez écrire naïvement juste itérer tout, 1021 00:43:08,210 --> 00:43:09,970 il serait juste prendre plus de temps. 1022 00:43:09,970 --> 00:43:12,470 Avec cette boucle quatre il est juste une belle optimisation 1023 00:43:12,470 --> 00:43:18,460 parce que nous savons que, après chaque plein itération à travers le tableau ici, 1024 00:43:18,460 --> 00:43:24,050 comme chaque boucle complète ici, nous savons que l'un de plusieurs de ces éléments 1025 00:43:24,050 --> 00:43:25,760 sont triés à la fin. 1026 00:43:25,760 --> 00:43:28,294 >> Donc, nous ne devons pas nous inquiéter à propos de ceux-ci. 1027 00:43:28,294 --> 00:43:29,710 Est-ce que cela a un sens pour tout le monde? 1028 00:43:29,710 --> 00:43:30,950 Ce petit truc cool? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Donc, dans ce cas, si nous nous parcourons, 1031 00:43:37,270 --> 00:43:50,590 nous savons que nous voulons vérifier si tableau n et n + 1 sont dans l'ordre. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 Dáccord. 1034 00:43:53,559 --> 00:43:54,600 Alors, voici le pseudo-code. 1035 00:43:54,600 --> 00:43:57,540 Nous voulons vérifier si le tableau n et n + 1 sont dans l'ordre. 1036 00:43:57,540 --> 00:43:59,520 Alors que peut-on y at-il? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Il va y avoir une certaine condition. 1039 00:44:03,120 --> 00:44:04,220 Ce sera une si. 1040 00:44:04,220 --> 00:44:07,066 >> L'ÉLÈVE: si le tableau est n moins de rang n + 1. 1041 00:44:07,066 --> 00:44:07,816 ENSEIGNANT: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Bien, inférieure ou supérieure. 1044 00:44:10,699 --> 00:44:11,615 L'ÉLÈVE: Supérieur à. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Ensuite, nous voulons les échanger. 1047 00:44:17,620 --> 00:44:18,570 Exactement. 1048 00:44:18,570 --> 00:44:23,570 Alors maintenant, nous entrons dans ce qui est la mécanisme pour les échanger? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Alors nous sommes allés à travers ce brièvement, un type de la fonction de permutation de la semaine dernière. 1051 00:44:28,137 --> 00:44:29,595 Quelqu'un se souvient comment il a travaillé? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Donc, nous ne pouvons pas leur attribuer, non? 1054 00:44:34,950 --> 00:44:36,640 Parce que l'un d'entre eux se perdre. 1055 00:44:36,640 --> 00:44:41,696 Si nous disions A est égal à B, puis B est égal à un, tout d'un coup, deux d'entre eux 1056 00:44:41,696 --> 00:44:43,150 sont juste égal à B. 1057 00:44:43,150 --> 00:44:45,720 >> Donc, ce que nous avons à faire est de nous avoir une variable temporaire qui est 1058 00:44:45,720 --> 00:44:49,055 va tenir une alors que la nôtre nous sommes en train d'échanger. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Donc, ce que nous avons est que nous aurons un certain int température est égale to-- vous pouvez l'affecter 1061 00:44:56,464 --> 00:44:59,130 à celui qu'on vous voulez, il suffit assurez-vous de garder une trace de it-- 1062 00:44:59,130 --> 00:45:01,840 dans ce cas, je vais assigner à tableau n + 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Donc, ça va pour contenir tous les valeur est dans ce deuxième bloc 1065 00:45:07,674 --> 00:45:08,590 que nous cherchons à. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> Et puis nous pouvons faire est que nous pouvons aller avant et tableau Réaffecter n + 1, 1068 00:45:13,240 --> 00:45:14,990 parce que nous savons que nous avoir que la valeur stockée. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Ceci est également un des grands things-- Je ne sais pas si l'un de vous 1071 00:45:19,270 --> 00:45:23,780 eu des problèmes où si vous passez deux lignes de code tout à coup les choses fonctionnaient. 1072 00:45:23,780 --> 00:45:25,880 L'ordre est très important dans CS. 1073 00:45:25,880 --> 00:45:29,450 Donc, assurez-vous diagramme choses si possible 1074 00:45:29,450 --> 00:45:31,230 quant à ce qui se passe réellement. 1075 00:45:31,230 --> 00:45:34,256 Alors maintenant, nous allons réaffecter tableau n + 1, 1076 00:45:34,256 --> 00:45:36,005 parce que nous savons que nous avoir que la valeur stockée. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> Et nous pouvons attribuer à ce tableau n ou dans ce cas tableau i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Trop de variables. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 Dáccord. 1083 00:45:55,470 --> 00:46:01,500 Tableau Alors maintenant, nous avons réaffecté i plus 1 à l'égalité de ce qui est dans le tableau i. 1084 00:46:01,500 --> 00:46:08,240 Et maintenant, nous pouvons revenir en arrière et attribuer gamme i de quoi? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Tout le monde? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> ÉTUDIANT: 10. 1089 00:46:14,010 --> 00:46:14,680 >> ENSEIGNANT: 10. 1090 00:46:14,680 --> 00:46:15,180 Exactement. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 Et une dernière chose. 1093 00:46:18,640 --> 00:46:21,840 Si nous avons échangé maintenant, que devons-nous faire? 1094 00:46:21,840 --> 00:46:23,740 Quelle est la seule chose que va nous dire 1095 00:46:23,740 --> 00:46:27,542 si jamais nous mettons fin à ce programme? 1096 00:46:27,542 --> 00:46:29,250 Que nous dit que nous avoir une liste triée? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Si nous ne réalisons pas de swaps, non? 1099 00:46:33,750 --> 00:46:36,900 Si swaps est égal à zéro à la fin de cette. 1100 00:46:36,900 --> 00:46:42,975 Donc, chaque fois que vous effectuez un échange, comme nous vient de faire ici, nous voulons mettre à jour swaps. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 Et je sais qu'il y avait une question plus tôt au sujet pouvez-vous 1103 00:46:47,210 --> 00:46:49,689 utiliser zéro ou un lieu de vrai ou faux. 1104 00:46:49,689 --> 00:46:50,980 Et qui est ce que cela fait ici. 1105 00:46:50,980 --> 00:46:52,750 Donc, cela dit, sinon des swaps. 1106 00:46:52,750 --> 00:47:01,310 Donc, si swaps est zéro, qui est: Je me suis toujours obtenir mes vérités et mes faux mélangés. 1107 00:47:01,310 --> 00:47:03,960 Nous voulons nous évaluons à vrai et il est pas. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Donc, si il est nul, alors il est faux. 1110 00:47:09,630 --> 00:47:12,560 Si vous niez avec un [? cogner?] il devient vrai. 1111 00:47:12,560 --> 00:47:13,975 Alors cette ligne exécute. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Vérités et faux et zéros et des uns deviennent fous. 1114 00:47:17,370 --> 00:47:20,690 Juste si vous marchez lentement à travers elle, il prendra tout son sens. 1115 00:47:20,690 --> 00:47:23,320 Mais qui est ce que ce petit peu de code ici fait. 1116 00:47:23,320 --> 00:47:26,490 Donc ce vérifie nous avons fait des swaps. 1117 00:47:26,490 --> 00:47:30,054 Donc, si elle est autre chose que zéro, ça va être faux 1118 00:47:30,054 --> 00:47:31,970 et le tout est va exécuter à nouveau. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Cool? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> ÉTUDIANT: Qu'est-ce que la rupture faire? 1123 00:47:36,000 --> 00:47:38,990 >> ENSEIGNANT: Cassez juste vous éclate de la boucle. 1124 00:47:38,990 --> 00:47:41,570 Donc, dans ce cas, il serait Comme à peu fin au programme 1125 00:47:41,570 --> 00:47:43,828 et vous voulez bien avoir votre liste triée. 1126 00:47:43,828 --> 00:47:44,536 L'ÉLÈVE: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 ENSEIGNANT: Je suis désolé? 1129 00:47:49,010 --> 00:47:52,110 L'ÉLÈVE: Parce que déjà nous utilisé 1 écrit sur écrit zéro 1130 00:47:52,110 --> 00:47:54,170 présenter que si cela fonctionnera ou pas. 1131 00:47:54,170 --> 00:47:54,878 >> ENSEIGNANT: Ouais. 1132 00:47:54,878 --> 00:47:56,410 Ainsi, vous pouvez retourner zéro ou 1. 1133 00:47:56,410 --> 00:47:58,950 Dans ce cas, parce que nous ne sommes pas réellement faire quelque chose avec la fonction, 1134 00:47:58,950 --> 00:48:00,150 nous voulons juste casser. 1135 00:48:00,150 --> 00:48:02,680 Nous ne nous soucions pas vraiment à ce sujet. 1136 00:48:02,680 --> 00:48:06,960 Le frein est également bon, si il est utilisé pour sortir 1137 00:48:06,960 --> 00:48:10,710 de quatre boucles ou des conditions qui vous ne voulez pas poursuivre l'exécution. 1138 00:48:10,710 --> 00:48:12,110 Il vous suffit d'eux. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Il est un peu une chose de nuance. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Je me sens comme il ya beaucoup de ondulation de la main, 1143 00:48:18,445 --> 00:48:19,740 comme vous allez apprendre à ce sujet prochainement. 1144 00:48:19,740 --> 00:48:20,955 >> Mais vous allez apprendre à ce sujet prochainement. 1145 00:48:20,955 --> 00:48:21,500 Je promets. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 Dáccord. 1148 00:48:23,170 --> 00:48:24,840 Alors que tout le monde se tri à bulles? 1149 00:48:24,840 --> 00:48:25,550 Pas trop mal. 1150 00:48:25,550 --> 00:48:31,910 Itérer, des choses de swap en utilisant un variable temp, et nous sommes tous mis là? 1151 00:48:31,910 --> 00:48:32,960 Laisser refroidir. 1152 00:48:32,960 --> 00:48:34,080 Impressionnant. 1153 00:48:34,080 --> 00:48:34,807 Dáccord. 1154 00:48:34,807 --> 00:48:35,765 Retour à la PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Toutes les questions en général sur ces jusqu'à présent? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Laisser refroidir. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> L'ÉLÈVE: [Inaudible] int main habituellement. 1162 00:48:45,279 --> 00:48:46,695 Avez-vous d'avoir ce pour cela? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> ENSEIGNANT: Donc, nous voulions juste juste à l'algorithme de tri réelle. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Si vous l'aviez dans comme un programme plus vaste, 1167 00:48:56,350 --> 00:48:57,891 vous auriez une part principale int. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Selon l'endroit où vous utiliser cet algorithme, 1170 00:49:02,880 --> 00:49:05,860 il déterminer ce qui est être renvoyé par elle. 1171 00:49:05,860 --> 00:49:09,960 Mais pour notre cas, nous sommes strictement regarder comment ce fait 1172 00:49:09,960 --> 00:49:11,300 itération sur un tableau. 1173 00:49:11,300 --> 00:49:12,570 Donc, nous ne nous inquiétons pas. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Alors que nous parlions meilleur des cas et pires scénarios pour la recherche binaire. 1176 00:49:19,830 --> 00:49:22,470 Donc, il est également important de faire que pour chacune de nos sortes. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Alors, que pensez-vous est le pire cas de l'exécution de tri à bulles? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Les gars, vous vous souvenez? 1181 00:49:30,700 --> 00:49:31,784 >> ETUDIANT: N moins 1. 1182 00:49:31,784 --> 00:49:32,700 ENSEIGNANT: N moins 1. 1183 00:49:32,700 --> 00:49:35,070 Donc, cela signifie qu'il ya n moins une des comparaisons. 1184 00:49:35,070 --> 00:49:40,060 Donc, une chose à réaliser est que sur la première itération, 1185 00:49:40,060 --> 00:49:43,360 nous passons par, nous comparons ces two-- de sorte que est 1. 1186 00:49:43,360 --> 00:49:46,685 Ces deux, trois, quatre. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Ainsi, après une itération nous ont déjà quatre comparaisons. 1189 00:49:55,050 --> 00:49:58,230 Quand je parle de l'exécution et n. 1190 00:49:58,230 --> 00:50:04,680 N représente le nombre de comparaisons en fonction de la manière dont de nombreux éléments 1191 00:50:04,680 --> 00:50:05,570 nous avons. 1192 00:50:05,570 --> 00:50:06,430 D'accord? 1193 00:50:06,430 --> 00:50:08,860 >> Donc, nous allons à travers, nous avons quatre. 1194 00:50:08,860 --> 00:50:11,780 La prochaine fois que vous savez que nous ne le faisons pas à prendre soin de cela. 1195 00:50:11,780 --> 00:50:15,140 Nous comparons ces deux, ces deux, ces deux, 1196 00:50:15,140 --> 00:50:20,050 et si nous ne disposons que d'optimisation avec les quatre boucle que je l'ai écrit, 1197 00:50:20,050 --> 00:50:22,750 vous seriez comparez ici de toute façon. 1198 00:50:22,750 --> 00:50:26,170 Donc, vous auriez à courir à travers le réseau 1199 00:50:26,170 --> 00:50:34,380 et faire des comparaisons n n fois, parce que chaque fois que nous en 1200 00:50:34,380 --> 00:50:36,670 courir à travers elle nous trions une chose. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> Et chaque fois que nous courons à travers le tableau, nous faisons n comparaisons. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Donc, notre exécution en est n fait carré, qui 1205 00:50:46,330 --> 00:50:48,400 est bien pire dans notre connectez-vous fin parce que 1206 00:50:48,400 --> 00:50:51,965 signifie que si nous avions quatre milliard éléments, il est 1207 00:50:51,965 --> 00:50:55,260 va nous prendre quatre milliards carré au lieu de 32. 1208 00:50:55,260 --> 00:51:01,240 Donc, pas la meilleure exécution, mais pour certaines choses, 1209 00:51:01,240 --> 00:51:04,610 vous savez, si vous êtes à l'intérieur un certain ensemble d'éléments 1210 00:51:04,610 --> 00:51:06,540 tri à bulles peut être bon d'utiliser. 1211 00:51:06,540 --> 00:51:07,530 >> Dáccord. 1212 00:51:07,530 --> 00:51:12,290 Alors maintenant, quelle est la meilleure exécution de cas? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 L'ÉLÈVE: Zero? 1215 00:51:14,940 --> 00:51:16,420 Ou 1? 1216 00:51:16,420 --> 00:51:18,140 >> ENSEIGNANT: Donc 1 serait être une comparaison. 1217 00:51:18,140 --> 00:51:19,114 Droite. 1218 00:51:19,114 --> 00:51:20,002 >> ETUDIANT: N moins 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> ENSEIGNANT: Alors, oui. 1221 00:51:22,320 --> 00:51:22,990 Alors n moins 1. 1222 00:51:22,990 --> 00:51:26,510 Chaque fois que vous avez un concept comme n moins 1, nous avons tendance à tout simplement le déposer 1223 00:51:26,510 --> 00:51:31,680 et nous venons de dire n parce que vous avez à comparer chacun des these-- chaque paire. 1224 00:51:31,680 --> 00:51:36,470 Donc, il serait n moins 1, ce qui nous nous venions de dire est d'environ n. 1225 00:51:36,470 --> 00:51:39,280 Lorsque vous avez affaire à l'exécution, tout est dans approximatives. 1226 00:51:39,280 --> 00:51:43,860 Tant que l'exposant est correct, vous êtes assez bon. 1227 00:51:43,860 --> 00:51:45,700 >> Voilà comment nous traitons avec elle. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Alors que le meilleur des cas est n, qui signifie que la liste est déjà trié, 1230 00:51:51,780 --> 00:51:54,320 et tout ce que nous faisons est dirigé par et vérifiez qu'il est bien triée. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Laisser refroidir. 1233 00:51:56,855 --> 00:51:57,355 Bien. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Donc, comme vous le voyez ici, nous avoir juste un peu plus de graphiques. 1236 00:52:01,920 --> 00:52:02,660 Alors n carré. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Bien pire que n comme nous le voyons, et bien, bien pire que journal 2n. 1240 00:52:09,730 --> 00:52:12,060 Et puis vous avez aussi dans les journaux de log. 1241 00:52:12,060 --> 00:52:18,020 Et vous prenez 124, vous obtenez en comme star du journal, qui est comme un fou. 1242 00:52:18,020 --> 00:52:20,172 Donc, si vous êtes intéressé, journal de recherche étoile. 1243 00:52:20,172 --> 00:52:20,880 Il est assez amusant. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Donc, nous avons ce grand tableau. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Juste un heads-up, cette une merveilleux tableau d'avoir 1248 00:52:28,720 --> 00:52:31,350 pour votre mi-parcours parce que nous longtemps pour vous poser ces amincit. 1249 00:52:31,350 --> 00:52:36,090 Alors seulement un heads-up, ont ceci sur votre à mi-parcours sur votre feuille de triche agréable 1250 00:52:36,090 --> 00:52:36,616 Là. 1251 00:52:36,616 --> 00:52:37,990 Donc nous avons juste regardé au tri à bulles. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Le pire des cas, n carré, meilleur des cas, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 Et nous allons regarder les autres. 1256 00:52:44,950 --> 00:52:47,940 >> Et comme vous pouvez le voir, la seule celui qui fait vraiment bien 1257 00:52:47,940 --> 00:52:50,910 est le tri par fusion, qui nous allons entrer dans pourquoi. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Donc, nous allons aller à la prochaine sorte de sélection ici--. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Quelqu'un se souvient comment sélection sorte travaillé? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Allez-y. 1264 00:53:05,700 --> 00:53:08,210 >> L'ÉLÈVE: aller essentiellement par un ordre et créer une nouvelle liste. 1265 00:53:08,210 --> 00:53:11,001 Et comme vous êtes éléments mettant dans, les mettre dans le bon endroit 1266 00:53:11,001 --> 00:53:11,750 dans la nouvelle liste. 1267 00:53:11,750 --> 00:53:14,040 >> ENSEIGNANT: Alors que les sons plus comme le tri par insertion. 1268 00:53:14,040 --> 00:53:15,040 Mais vous êtes vraiment proche. 1269 00:53:15,040 --> 00:53:15,915 Ils sont très semblables. 1270 00:53:15,915 --> 00:53:17,440 Même moi, je les confondre parfois. 1271 00:53:17,440 --> 00:53:18,981 Avant cette section, je me suis dit, attendre. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 Dáccord. 1274 00:53:20,630 --> 00:53:24,141 Donc, ce que vous voulez faire est la sélection sorte, 1275 00:53:24,141 --> 00:53:25,890 la façon dont vous pouvez penser à ce sujet et la manière 1276 00:53:25,890 --> 00:53:30,140 Je fais en sorte que je cherche pas à obtenir les mélanger, est elle passe par 1277 00:53:30,140 --> 00:53:33,280 et on sélectionne le le plus petit nombre et 1278 00:53:33,280 --> 00:53:36,070 met que au début de votre liste. 1279 00:53:36,070 --> 00:53:37,730 Il permute avec cette première place. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Ils ont fait un exemple pour moi. 1282 00:53:45,370 --> 00:53:46,540 Impressionnant. 1283 00:53:46,540 --> 00:53:50,130 Alors juste une façon de penser de la sélection it-- Trier, sélectionner la plus petite valeur. 1284 00:53:50,130 --> 00:53:51,940 Et nous allons courir à travers un exemple 1285 00:53:51,940 --> 00:53:55,320 qui je pense va aider parce que Je pense visuels aident toujours. 1286 00:53:55,320 --> 00:53:58,510 Nous commençons donc avec quelque chose qui est complètement non triés. 1287 00:53:58,510 --> 00:54:00,730 Rouge sera non triés, vert sera triée. 1288 00:54:00,730 --> 00:54:02,190 Il va donner un sens à une seconde. 1289 00:54:02,190 --> 00:54:08,950 >> Donc, nous allons à travers et nous réitérons du début à la fin. 1290 00:54:08,950 --> 00:54:12,320 Et nous disons, OK, 2 est notre petit nombre. 1291 00:54:12,320 --> 00:54:15,680 Nous allons donc prendre 2 et nous allons pour le déplacer vers l'avant de notre gamme 1292 00:54:15,680 --> 00:54:17,734 parce qu'il est le plus petit nombre que nous avons. 1293 00:54:17,734 --> 00:54:19,150 Voilà ce que cela est en train de faire ici. 1294 00:54:19,150 --> 00:54:20,820 Il va juste pour échanger les deux. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Alors maintenant, nous avons une triés partie et une partie non triés. 1297 00:54:25,450 --> 00:54:27,810 Et ce qui est bon de se rappeler sur la sélection sorte 1298 00:54:27,810 --> 00:54:30,690 est que nous sommes seulement en sélectionnant à partir de la partie non triés. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> La partie triée vous suffit de laisser seul. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> L'ÉLÈVE: Comment sait-il ce qui est le plus petit sans comparant 1303 00:54:38,452 --> 00:54:39,868 pour chaque autre valeur dans le tableau. 1304 00:54:39,868 --> 00:54:41,250 ENSEIGNANT: Il fait comparer. 1305 00:54:41,250 --> 00:54:42,041 Nous aimons laissé tomber. 1306 00:54:42,041 --> 00:54:43,850 Ceci est juste général global. 1307 00:54:43,850 --> 00:54:44,831 Ouais. 1308 00:54:44,831 --> 00:54:47,205 Lorsque nous écrivons le code que je suis sûr que vous serez plus satisfait. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Mais vous stockez cette première comme le plus petit élément. 1311 00:54:53,030 --> 00:54:56,110 Vous comparez et vous dire, OK, est-il plus petit? 1312 00:54:56,110 --> 00:54:56,660 Oui. 1313 00:54:56,660 --> 00:54:57,460 Gardez-le. 1314 00:54:57,460 --> 00:54:58,640 Voici le plus petit? 1315 00:54:58,640 --> 00:54:59,660 Non? 1316 00:54:59,660 --> 00:55:02,510 >> Ceci est votre plus petit, réaffecter à votre valeur. 1317 00:55:02,510 --> 00:55:06,340 Et vous serez beaucoup plus heureux lorsque nous passons par le code. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Donc, nous allons à travers, nous échangeons, alors puis nous regardons cette partie non triés. 1320 00:55:13,970 --> 00:55:15,810 Donc, nous allons sélectionner trois sur. 1321 00:55:15,810 --> 00:55:18,890 Nous allons mettre sur à la fin de notre partie triée. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 Et nous allons tout simplement continuer à faire que, ce faisant, et le faire. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Voici donc notre genre de pseudo ici. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Nous allons coder ici dans une seconde. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Mais quelque chose de marcher à travers à un niveau élevé. 1330 00:55:37,270 --> 00:55:40,275 Vous allez passer de i est égal à 0 à n moins 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Voilà une autre optimisation. 1333 00:55:43,530 --> 00:55:45,020 Ne vous inquiétez pas trop à ce sujet. 1334 00:55:45,020 --> 00:55:46,620 Donc, comme vous le disiez. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Comme Jacob a dit, comment pouvons-nous garder une trace de ce que notre minimum est? 1337 00:55:54,406 --> 00:55:55,030 Comment savons-nous? 1338 00:55:55,030 --> 00:55:57,060 Nous devons comparer tout dans notre liste. 1339 00:55:57,060 --> 00:55:59,600 >> Donc, au moins égale à i. 1340 00:55:59,600 --> 00:56:03,870 Il est juste de dire dans ce cas l'indice de notre valeur minimale. 1341 00:56:03,870 --> 00:56:07,660 Alors ça va pour parcourir et il va de j est égal à i + 1. 1342 00:56:07,660 --> 00:56:11,420 Donc, nous savons déjà que qui est notre premier élément. 1343 00:56:11,420 --> 00:56:13,240 On n'a pas besoin de le comparer à lui-même. 1344 00:56:13,240 --> 00:56:16,970 Donc, nous commençons à en le comparant à l'autre celui qui est pourquoi il est i + 1 à n 1345 00:56:16,970 --> 00:56:20,110 moins 1, qui est la fin du tableau il. 1346 00:56:20,110 --> 00:56:25,090 Et nous avons dit si le tableau à j est inférieure éventail min, 1347 00:56:25,090 --> 00:56:29,200 puis nous réaffectons où nos indices minimum est. 1348 00:56:29,200 --> 00:56:37,470 >> Et si min est pas égal à i, en tant que Où nous étions de retour ici. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Donc, comme lorsque nous avons fait celui-ci. 1351 00:56:41,790 --> 00:56:49,310 Dans ce cas, il commencerait à zéro, il finirait par être deux. 1352 00:56:49,310 --> 00:56:53,010 Ainsi, ne serait pas égal min i à la fin. 1353 00:56:53,010 --> 00:56:55,720 Ce nous laisse savoir que nous avons besoin de les échanger. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Je me sens comme un exemple concret aidera beaucoup plus que cela. 1356 00:57:00,470 --> 00:57:04,970 Alors je vais coder cette place avec vous les gars en ce moment et je pense que ce sera mieux. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Sortes ont tendance à travailler de cette façon que dans il est souvent préférable juste pour les voir. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Donc, ce que nous voulons faire est on veut d'abord la plus petite 1361 00:57:17,280 --> 00:57:19,890 élément dans sa position dans le tableau. 1362 00:57:19,890 --> 00:57:21,280 Exactement ce que Jacob a dit. 1363 00:57:21,280 --> 00:57:23,090 Vous avez besoin de stocker que d'une certaine manière. 1364 00:57:23,090 --> 00:57:25,900 Donc, nous allons commencer ici itération sur le tableau. 1365 00:57:25,900 --> 00:57:28,970 Nous allons dire qu'il est notre premier juste pour commencer. 1366 00:57:28,970 --> 00:57:38,308 Donc nous allons avoir int plus petit est égal à tableau à i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Donc, une chose à noter, tous les fois cette boucle est exécutée, 1369 00:57:45,050 --> 00:57:48,550 nous commençons une étape plus loin. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Quand nous commençons à nous regardons celui-ci. 1372 00:57:57,440 --> 00:58:00,840 La prochaine fois que nous parcourons, nous commençons à celui-ci 1373 00:58:00,840 --> 00:58:02,680 et en lui attribuant la plus petite valeur. 1374 00:58:02,680 --> 00:58:10,450 Il est donc très similaire à tri à bulles où nous savons que, après une passe, 1375 00:58:10,450 --> 00:58:11,700 Ce dernier élément est triée. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Avec sélection sorte, il est tout le contraire. 1378 00:58:15,120 --> 00:58:18,950 >> A chaque passage, nous savons que le premier est triée. 1379 00:58:18,950 --> 00:58:21,360 Après le deuxième passage, le second sera triée. 1380 00:58:21,360 --> 00:58:26,470 Et comme vous l'avez vu avec les exemples de diapositives, notre partie triés ne cesse de croître. 1381 00:58:26,470 --> 00:58:34,020 Donc, en mettant notre plus petit aux tableaux I, tout ce qu'il ya à faire 1382 00:58:34,020 --> 00:58:37,340 est ce que la constriction nous cherchons à façon 1383 00:58:37,340 --> 00:58:40,164 pour réduire au minimum le nombre de comparaisons que nous faisons. 1384 00:58:40,164 --> 00:58:41,770 Cela fait-il sens à tout le monde? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Avez-vous besoin de moi pour parcourir que encore plus lente ou en d'autres termes? 1387 00:58:46,380 --> 00:58:47,180 Je suis heureux de. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 Dáccord. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Nous sommes donc stocker la valeur à ce point, 1392 00:58:55,540 --> 00:58:57,840 mais nous voulons aussi pour stocker l'index. 1393 00:58:57,840 --> 00:59:01,010 Donc, nous allons stocker le la position de la plus petite 1394 00:59:01,010 --> 00:59:02,770 un, qui va tout simplement être i. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Alors maintenant, Jacob est satisfait. 1397 00:59:05,440 --> 00:59:06,870 Nous avons des choses stockées. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 Et maintenant nous avons besoin de regarder à travers la partie non triés du tableau. 1400 00:59:11,870 --> 00:59:18,170 Donc dans ce cas ce serait notre non triés. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Ceci est i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 Dáccord. 1405 00:59:26,210 --> 00:59:30,040 >> Donc, ce que nous allons faire va être pour une boucle. 1406 00:59:30,040 --> 00:59:32,066 Chaque fois que vous devez itération sur un tableau, 1407 00:59:32,066 --> 00:59:33,440 votre esprit peut aller pour une boucle. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Donc, pour certains int k equals-- ce que nous pensons 1410 00:59:38,090 --> 00:59:39,700 k va correspondre à commencer? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Voici ce que nous avons mis notre petit valeur et nous voulons comparer. 1413 00:59:44,766 --> 00:59:47,090 Que voulons-nous à le comparer? 1414 00:59:47,090 --> 00:59:48,730 Ça va être la prochaine, non? 1415 00:59:48,730 --> 00:59:53,200 Nous voulons donc k être initialisé i + 1 pour commencer. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> Et nous voulons k dans ce cas nous ont déjà stocké taille ici, 1418 01:00:02,800 --> 01:00:03,930 si nous pouvons simplement utiliser la taille. 1419 01:00:03,930 --> 01:00:06,240 Taille étant la taille de la matrice. 1420 01:00:06,240 --> 01:00:09,620 Et nous voulons juste mettre à jour par une k à chaque fois. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Laisser refroidir. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Alors maintenant, nous devons trouver le plus petit élément ici. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Donc, si nous parcourons, nous envie de dire, si le tableau à k 1427 01:00:31,380 --> 01:00:37,080 est inférieure à la plus petite value-- voilà où nous en sommes réellement 1428 01:00:37,080 --> 01:00:42,950 garder une trace de ce qui est le plus petit ici-- 1429 01:00:42,950 --> 01:00:47,740 alors nous voulons réaffecter ce que notre plus petite valeur est. 1430 01:00:47,740 --> 01:00:50,645 >> Cela signifie que, oh, nous sommes itérer ici. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Quelle que soit la valeur est ici pas la plus petite chose. 1433 01:00:53,740 --> 01:00:54,448 Nous ne voulons pas. 1434 01:00:54,448 --> 01:00:56,100 Nous voulons réaffecter. 1435 01:00:56,100 --> 01:01:02,050 Nous sommes donc si le réaffectant, qu'est-ce que vous pensez peut-être dans ce code ici? 1436 01:01:02,050 --> 01:01:04,160 Nous voulons réaffecter plus petite et la position. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Donc, ce qui est plus petit maintenant? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 L'ÉLÈVE: Array k. 1441 01:01:09,130 --> 01:01:09,963 INSTRUCTEUR: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 Et quelle est la position maintenant? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Ce qui est des indices de notre plus petite valeur? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Il est juste k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Donc tableau k, k, ils correspondent. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Nous avons donc voulu que réaffecter. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 Et puis après nous avons trouvé notre petit, si à la fin de cette boucle pour 1454 01:01:39,950 --> 01:01:45,100 ici nous avons trouvé ce que notre petit valeur est, alors nous avons l'échanger. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 Dans ce cas, comme, disons, notre plus petite valeur est ici. 1457 01:01:50,816 --> 01:01:51,940 Ceci est notre plus petite valeur. 1458 01:01:51,940 --> 01:01:57,690 >> Nous voulons simplement l'échanger ici, qui est ce que la fonction de permutation en bas 1459 01:01:57,690 --> 01:02:01,270 fait, que nous venons d'écrire jusqu'à ensemble il ya quelques minutes. 1460 01:02:01,270 --> 01:02:02,775 Donc, il devrait vous être familier. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 Et puis il sera simplement itérer à travers jusqu'à ce qu'il atteigne tout le chemin 1463 01:02:08,030 --> 01:02:13,100 à la fin, ce qui signifie que vous avoir des éléments zéro non trié 1464 01:02:13,100 --> 01:02:14,800 et tout le reste a été réglé. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Donner un sens? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Un peu plus concrètement? 1469 01:02:19,280 --> 01:02:19,990 L'aide de code? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> ÉTUDIANT: Pour une taille, vous ne vraiment définir ou modifier, 1472 01:02:26,410 --> 01:02:27,340 comment sait-il? 1473 01:02:27,340 --> 01:02:32,380 >> ENSEIGNANT: Donc, une chose à remarque ici est la taille de int. 1474 01:02:32,380 --> 01:02:35,680 Nous disons donc dans ce genre sort-- est une fonction en ce qu'il est case-- 1475 01:02:35,680 --> 01:02:40,770 sélection sorte, il est passé avec la fonction. 1476 01:02:40,770 --> 01:02:43,460 Donc, si il n'a pas été adopté , vous feriez quelque chose 1477 01:02:43,460 --> 01:02:47,840 comme avec la longueur de la matrice ou si vous souhaitez effectuer une itération dans 1478 01:02:47,840 --> 01:02:49,390 pour trouver la longueur. 1479 01:02:49,390 --> 01:02:52,680 Mais parce qu'il est passé en, nous pouvons simplement utiliser. 1480 01:02:52,680 --> 01:02:55,720 Vous assumez juste que l'utilisateur vous a donné une taille valide 1481 01:02:55,720 --> 01:02:57,698 représente réellement une taille de votre tableau. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Cool? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Si vous les gars avez des problèmes avec ces ou si vous voulez plus pratique de codage sortes 1486 01:03:05,870 --> 01:03:08,050 sur votre propre, vous devriez aller à study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Il est un outil. 1489 01:03:12,670 --> 01:03:15,040 Ils ont un correcteur qui vous pouvez réellement écrire. 1490 01:03:15,040 --> 01:03:16,180 Ils font pseudo. 1491 01:03:16,180 --> 01:03:19,310 Ils ont plus de vidéos et diapositives y compris ceux que je utilise ici. 1492 01:03:19,310 --> 01:03:23,150 Donc, si vous vous sentez encore un peu floue, essayer cela. 1493 01:03:23,150 --> 01:03:25,670 Comme toujours, venez me parler, trop. 1494 01:03:25,670 --> 01:03:26,320 Question? 1495 01:03:26,320 --> 01:03:28,611 >> L'ÉLÈVE: Voulez-vous dire la taille est préalablement défini? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 ENSEIGNANT: Oui. 1498 01:03:29,900 --> 01:03:35,570 Taille est défini précédemment jusqu'à ici dans la déclaration de fonction. 1499 01:03:35,570 --> 01:03:39,060 Alors vous supposez que cela a été adoptée en par l'utilisateur, et pour des raisons de simplicité, 1500 01:03:39,060 --> 01:03:41,896 nous allons supposer que la utilisateur nous a donné la bonne taille. 1501 01:03:41,896 --> 01:03:43,240 Laisser refroidir. 1502 01:03:43,240 --> 01:03:44,390 Alors que la sélection sorte. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Les gars, je sais que nous allons apprendre beaucoup de choses aujourd'hui. 1505 01:03:47,640 --> 01:03:49,710 Il est un dense données pour la section. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Donc, avec cela, nous allons aller à tri par insertion. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> Dáccord. 1510 01:04:02,510 --> 01:04:06,100 Donc, avant que nous avons à faire notre analyse de l'exécution ici. 1511 01:04:06,100 --> 01:04:10,190 Donc, dans le meilleur des cas, accordé depuis que je vous ai montré 1512 01:04:10,190 --> 01:04:11,960 la table je l'ai déjà genre de celui-ci a donné loin. 1513 01:04:11,960 --> 01:04:15,430 Mais le meilleur de l'exécution de cas, qu'est-ce que nous pensons? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Tout triée. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N carré. 1518 01:04:22,070 --> 01:04:24,780 Quelqu'un at-il une explication pourquoi vous en pensez? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> ÉTUDIANTS: Vous faites la comparaison through-- 1521 01:04:30,519 --> 01:04:31,268 ENSEIGNANT: Droit. 1522 01:04:31,268 --> 01:04:32,540 Vous vous comparez à travers. 1523 01:04:32,540 --> 01:04:35,630 À chaque itération, même si nous décrémenter ce par un, 1524 01:04:35,630 --> 01:04:38,950 vous êtes toujours à la recherche à travers tout de trouver le plus petit. 1525 01:04:38,950 --> 01:04:42,390 Donc, même si votre petite valeur est ici au début, 1526 01:04:42,390 --> 01:04:44,710 vous êtes toujours comparer contre tout le reste 1527 01:04:44,710 --> 01:04:46,550 pour vous assurer qu'il est la plus petite chose. 1528 01:04:46,550 --> 01:04:49,820 Donc, vous vous retrouverez en cours d'exécution à travers n fois approximativement carré. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Bien. 1531 01:04:51,590 --> 01:04:52,785 Et ce qui est le pire des cas? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Aussi n carré parce que vous allez à faire la même procédure. 1534 01:04:57,980 --> 01:05:01,670 Donc dans ce cas, la sélection a en quelque sorte quelque chose 1535 01:05:01,670 --> 01:05:04,010 que nous appelons aussi l'exécution prévue. 1536 01:05:04,010 --> 01:05:07,400 Ainsi, dans les autres, nous savons juste les limites supérieures et inférieures. 1537 01:05:07,400 --> 01:05:11,180 Selon la façon dont notre fou liste est non triés ou comment il est, 1538 01:05:11,180 --> 01:05:15,350 ils varient entre n ou n carré. 1539 01:05:15,350 --> 01:05:16,550 Nous ne savons pas. 1540 01:05:16,550 --> 01:05:22,820 >> Mais parce que la sélection a le même genre pire et le meilleur des cas, qui nous dit que 1541 01:05:22,820 --> 01:05:25,880 Peu importe le type de commentaires que nous avons ont, que ce soit complètement 1542 01:05:25,880 --> 01:05:29,130 triés ou totalement triés inverse, il est 1543 01:05:29,130 --> 01:05:30,740 va prendre la même quantité de temps. 1544 01:05:30,740 --> 01:05:33,760 Donc, dans ce cas, si vous se souvenir de notre table, 1545 01:05:33,760 --> 01:05:38,610 il y avait en fait une valeur qui ces deux types ne sont pas, 1546 01:05:38,610 --> 01:05:40,390 qui est de l'exécution attendu. 1547 01:05:40,390 --> 01:05:43,350 Donc, nous savons que chaque fois que nous courons sélection sorte, 1548 01:05:43,350 --> 01:05:45,380 il est garanti à exécuter une durée de n carré. 1549 01:05:45,380 --> 01:05:46,630 Il n'y a pas de variabilité. 1550 01:05:46,630 --> 01:05:47,630 Il est juste prévu. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 Et, encore une fois, si vous voulez apprendre De plus, prendre CS 124 au printemps. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Bien. 1555 01:05:56,712 --> 01:05:57,545 Nous avons vu celui-ci. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Laisser refroidir. 1558 01:05:59,030 --> 01:06:00,930 Trier Alors insertion. 1559 01:06:00,930 --> 01:06:03,330 Et je vais probablement à se frayer à travers cela. 1560 01:06:03,330 --> 01:06:05,440 Je ne vais pas vous les gars ont coder. 1561 01:06:05,440 --> 01:06:06,580 Nous allons marcher à travers elle. 1562 01:06:06,580 --> 01:06:10,500 Donc, le tri par insertion est un peu de similaire à la sélection sorte 1563 01:06:10,500 --> 01:06:14,460 dans ce que nous avons à la fois un non triés et triés partie du tableau. 1564 01:06:14,460 --> 01:06:20,260 >> Mais ce qui est différent est que que nous traversons un par un, 1565 01:06:20,260 --> 01:06:24,210 nous prenons simplement ce numéro est à côté de notre non triés, 1566 01:06:24,210 --> 01:06:28,507 et trier correctement ce dans notre tableau trié. 1567 01:06:28,507 --> 01:06:30,090 Il va faire plus de sens avec un exemple. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Alors tout commence non triés, Tout comme avec la sélection sorte. 1570 01:06:35,430 --> 01:06:38,740 Et nous allons régler ce problème en ordre croissant comme nous l'avons été. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Donc, sur notre premier passage nous prenons la première valeur 1573 01:06:43,340 --> 01:06:46,700 et nous disons, OK, vous êtes maintenant dans une liste par vous-même. 1574 01:06:46,700 --> 01:06:49,150 >> Parce que vous êtes dans une liste par vous-même, vous sont triés. 1575 01:06:49,150 --> 01:06:52,460 Félicitations pour être le premier élément de ce tableau. 1576 01:06:52,460 --> 01:06:54,800 Vous êtes déjà triées sur votre propre. 1577 01:06:54,800 --> 01:06:58,900 Alors maintenant, nous avons une triés et un tableau non trié. 1578 01:06:58,900 --> 01:07:01,760 Alors maintenant, nous prenons la première. 1579 01:07:01,760 --> 01:07:05,600 Qu'est-ce qui se passe entre ici et voici que nous disons, 1580 01:07:05,600 --> 01:07:08,890 OK, nous allons regarder la première valeur de notre tableau non trié 1581 01:07:08,890 --> 01:07:13,270 et nous allons à l'entrée dans son bonne place dans le tableau trié. 1582 01:07:13,270 --> 01:07:21,460 >> Donc, ce que nous faisons est que nous prenons 5 et nous disons, OK, 5 est supérieur à 3, 1583 01:07:21,460 --> 01:07:24,630 donc nous suffit d'insérer la droite à la droite de cette. 1584 01:07:24,630 --> 01:07:25,130 Nous sommes bons. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Alors que nous passons à notre prochain. 1587 01:07:28,420 --> 01:07:29,720 Et nous prenons 2. 1588 01:07:29,720 --> 01:07:34,330 Nous disons, OK, 2 est moins de 3, donc nous savons qu'il 1589 01:07:34,330 --> 01:07:36,220 qui doit être à la devant notre liste maintenant. 1590 01:07:36,220 --> 01:07:41,800 Donc, ce que nous faisons est que nous poussons 3 et 5 vers le bas et nous passons 2 dans le premier emplacement. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Donc, nous ne faisons que de l'insérer dans au bon endroit, il devrait être. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Ensuite, nous regardons notre prochain, et nous disons 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 est supérieure à tout dans notre tableau trié, 1596 01:07:53,620 --> 01:07:56,000 si nous étiquetterons juste sur la fin. 1597 01:07:56,000 --> 01:07:56,960 Et puis nous sommes à 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 La figure 4 est inférieur à 6, il est moins de 5, mais elle est supérieure à 3. 1600 01:08:03,020 --> 01:08:06,270 Donc nous suffit d'insérer directement dans le milieu entre 3 et 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Donc, pour en faire une petite peu plus concret, 1603 01:08:10,530 --> 01:08:12,280 ici est le genre de idée de ce qui est arrivé. 1604 01:08:12,280 --> 01:08:16,430 Ainsi, pour chaque élément non triés, nous déterminer où, dans la partie triée 1605 01:08:16,430 --> 01:08:17,090 il est. 1606 01:08:17,090 --> 01:08:20,680 >> Donc, en gardant à l'esprit la triés et non triés, 1607 01:08:20,680 --> 01:08:26,080 nous avons à parcourir à travers la figure et où il inscrit dans le tableau trié. 1608 01:08:26,080 --> 01:08:31,460 Et nous l'insérons en déplaçant le les éléments à droite de celui-ci vers le bas. 1609 01:08:31,460 --> 01:08:34,910 Et puis nous gardons juste itérer jusqu'à ce que nous 1610 01:08:34,910 --> 01:08:39,270 avoir une liste complètement trié où non triés est maintenant zéro 1611 01:08:39,270 --> 01:08:41,720 et triée reprend la intégralité de notre liste. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Donc, encore une fois, pour rendre les choses encore Plus concrètement, nous avons pseudo. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Donc, fondamentalement, pour i est égale à 0 à n moins 1, 1616 01:08:52,410 --> 01:08:54,790 qui est juste la longueur de notre tableau. 1617 01:08:54,790 --> 01:09:00,979 Nous avons un élément qui est égal à la première matrice ou les premiers indices. 1618 01:09:00,979 --> 01:09:03,200 Nous avons mis j égale à celle. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Ainsi, alors que j est supérieur à zéro et le tableau, j moins 1 1621 01:09:09,210 --> 01:09:11,660 est supérieure à la élément, donc tout ce qui est à faire 1622 01:09:11,660 --> 01:09:17,479 est faire en sorte que votre j représente vraiment 1623 01:09:17,479 --> 01:09:20,010 la partie non triés du tableau. 1624 01:09:20,010 --> 01:09:30,745 >> Ainsi, alors il est encore des choses pour trier et j moins un est-- ce 1625 01:09:30,745 --> 01:09:31,840 est l'élément lui? 1626 01:09:31,840 --> 01:09:34,760 J n'a jamais été défini ici. 1627 01:09:34,760 --> 01:09:35,677 Il est un peu ennuyeux. 1628 01:09:35,677 --> 01:09:36,176 Dáccord. 1629 01:09:36,176 --> 01:09:36,689 Quoi qu'il en soit. 1630 01:09:36,689 --> 01:09:39,899 Donc j moins 1, vous vérifiez l'élément avant. 1631 01:09:39,899 --> 01:09:46,460 Vous dites, OK, est l'élément avant où je laisse de am-- 1632 01:09:46,460 --> 01:09:47,540 effectivement tirer cela. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Donc, disons que cela est comme sur notre deuxième passage. 1635 01:09:56,830 --> 01:09:59,525 Donc je va être égal 1, ce qui est ici. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Donc je va être égal à 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Ce serait 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Bien. 1642 01:10:16,750 --> 01:10:20,945 Donc, notre élément dans ce cas va être égal à 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 Et nous avons quelques j qui est va être égal à 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Oh, j est décrémentation. 1647 01:10:30,971 --> 01:10:31,720 Voilà ce qu'il est. 1648 01:10:31,720 --> 01:10:35,680 Donc j est égal à i, donc ce qu'il en est dit est que nous avançons, 1649 01:10:35,680 --> 01:10:37,530 nous sommes en train de faire en sorte que nous ne sommes pas sur 1650 01:10:37,530 --> 01:10:43,520 l'indexation de cette façon quand nous essayons à insérer choses dans notre liste triée. 1651 01:10:43,520 --> 01:10:49,850 >> Ainsi, lorsque j est égal à 1 dans ce cas et tableau j moins One-- afin gamme j moins 1 1652 01:10:49,850 --> 01:10:54,610 2 est dans ce case-- si cela est supérieure à l'élément, 1653 01:10:54,610 --> 01:10:57,700 puis tout cela est fait est changeant les choses. 1654 01:10:57,700 --> 01:11:04,790 Donc dans ce cas, un tableau J moins un serait gamme zéro, ce qui est 2. 1655 01:11:04,790 --> 01:11:08,430 La figure 2 est inférieure ou égale à 4, si ce ne l'exécute pas. 1656 01:11:08,430 --> 01:11:11,460 Ainsi, le changement ne se déplace pas vers le bas. 1657 01:11:11,460 --> 01:11:18,790 Qu'est-ce que ce fait ici est juste déplacer votre tableau trié vers le bas. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 Dans ce cas, effectivement, nous pourrait do-- faisons ce 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Donc, si nous sommes à traverser avec cet exemple, nous sommes maintenant ici. 1662 01:11:31,970 --> 01:11:32,740 Ce sont triés. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Ceci est non triés. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Cool? 1667 01:11:39,860 --> 01:11:46,620 Donc i est égal à 2, alors notre élément est égal à 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 Et notre j est égal à 2. 1670 01:11:52,270 --> 01:12:00,620 Donc, nous regardons à travers et nous dire, OK, est un tableau J moins un 1671 01:12:00,620 --> 01:12:03,470 l'élément supérieur que nous cherchons à? 1672 01:12:03,470 --> 01:12:05,540 Et la réponse est oui, non? 1673 01:12:05,540 --> 01:12:11,275 La figure 4 est supérieur à 3 et j est 2, si ce code est exécuté. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Alors maintenant, ce que nous faisons un tableau à 2, donc ici, nous les échanger. 1676 01:12:18,550 --> 01:12:25,620 Donc, nous disons juste, OK, array à 2 va maintenant être 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 Et j va égaler j moins 1, qui est une. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Voilà horrible, mais vous les gars avez l'idée. 1681 01:12:37,200 --> 01:12:38,360 J est maintenant égal à 1. 1682 01:12:38,360 --> 01:12:44,360 Et j éventail va juste être égale à notre élément, qui était de 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Je effacé quelque chose que je ne devrait pas avoir ou quelque chose miswrote, 1685 01:12:48,570 --> 01:12:49,910 mais vous les gars avez l'idée. 1686 01:12:49,910 --> 01:12:50,640 >> Il déplacer à n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 Et puis si ce l'était, il boucle nouveau et il dit, OK, j est 1 maintenant. 1689 01:12:57,960 --> 01:13:00,665 Et ensemble j moins 1 est maintenant 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Est 2 de moins que notre élément? 1692 01:13:03,760 --> 01:13:04,540 Non? 1693 01:13:04,540 --> 01:13:07,970 Cela signifie que nous avons inséré cet élément 1694 01:13:07,970 --> 01:13:10,110 au bon endroit dans notre tableau trié. 1695 01:13:10,110 --> 01:13:14,400 Ensuite, nous pouvons prendre cela et nous dire, OK, notre tableau trié est ici. 1696 01:13:14,400 --> 01:13:19,940 Et il faudrait ce nombre 6 et être comme, OK, est inférieur à 6 ce numéro? 1697 01:13:19,940 --> 01:13:20,480 Non? 1698 01:13:20,480 --> 01:13:21,080 Laisser refroidir. 1699 01:13:21,080 --> 01:13:22,680 Nous sommes très bien. 1700 01:13:22,680 --> 01:13:23,530 >> Faites-le à nouveau. 1701 01:13:23,530 --> 01:13:24,740 Nous disons 7. 1702 01:13:24,740 --> 01:13:29,010 7 est inférieure à la fin de notre tableau trié? 1703 01:13:29,010 --> 01:13:29,520 Non. 1704 01:13:29,520 --> 01:13:30,430 Nous sommes donc bien. 1705 01:13:30,430 --> 01:13:32,760 Donc, ce serait réglé. 1706 01:13:32,760 --> 01:13:38,610 Fondamentalement tout cela ne est il est dit prendre 1707 01:13:38,610 --> 01:13:42,060 le premier élément de votre tableau non trié, 1708 01:13:42,060 --> 01:13:46,010 savoir où il va dans votre tableau trié. 1709 01:13:46,010 --> 01:13:48,780 Et cela prend juste soin de swaps de le faire. 1710 01:13:48,780 --> 01:13:51,300 Vous fondamentalement juste échange jusqu'à ce qu'il soit au bon endroit. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 L'image visuelle est que vous êtes déplaçant tout vers le bas en faisant cela. 1713 01:13:56,990 --> 01:13:59,420 >> Donc, il est comme la moitié tri à bulles-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Découvrez étude 50. 1716 01:14:03,420 --> 01:14:06,000 Je recommande vivement d'essayer à coder sur votre propre. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Si vous avez des questions ou vous voulez voir exemple de code pour un tri par insertion, 1719 01:14:12,450 --> 01:14:13,750 se il vous plaît, faites-moi savoir. 1720 01:14:13,750 --> 01:14:14,500 Je suis toujours là. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Donc le pire des cas d'exécution et la meilleure exécution de cas. 1723 01:14:20,200 --> 01:14:30,700 Comme vous le gars vu de la table je l'ai déjà vous a montré, il est à la fois n et n carré. 1724 01:14:30,700 --> 01:14:35,590 >> Donc genre d'aller hors de ce que nous avons parlé sur nos sortes précédentes, pire 1725 01:14:35,590 --> 01:14:38,760 cas d'exécution est que si il est complètement non triés, 1726 01:14:38,760 --> 01:14:42,530 nous devons comparer l'ensemble de ces n fois. 1727 01:14:42,530 --> 01:14:47,020 Nous faisons beaucoup de comparaisons parce que si il est dans l'ordre inverse, 1728 01:14:47,020 --> 01:14:50,360 nous allons dire, OK, ce est le même, ce qui est bon, 1729 01:14:50,360 --> 01:14:54,650 et celle-ci devra être comparé contre le premier à être déplacé en arrière. 1730 01:14:54,650 --> 01:14:56,710 Et comme nous obtenons vers l'extrémité de queue, nous avons 1731 01:14:56,710 --> 01:14:59,440 à comparer, comparer, et comparer contre tout. 1732 01:14:59,440 --> 01:15:03,030 >> Donc, il finit par être n approximativement carré. 1733 01:15:03,030 --> 01:15:09,510 Si elle est correcte, alors vous dites, OK, 2, vous êtes bon. 1734 01:15:09,510 --> 01:15:11,330 3, vous êtes par rapport à 2. 1735 01:15:11,330 --> 01:15:12,310 Vous êtes doué. 1736 01:15:12,310 --> 01:15:14,150 4, vous comparez juste à la queue. 1737 01:15:14,150 --> 01:15:14,990 Vous êtes doué. 1738 01:15:14,990 --> 01:15:17,140 6, comparer à la queue, vous êtes très bien. 1739 01:15:17,140 --> 01:15:20,870 Ainsi, pour chaque place si elle est déjà triés, vous faites une comparaison. 1740 01:15:20,870 --> 01:15:22,320 Donc, il est juste n. 1741 01:15:22,320 --> 01:15:26,840 Et parce que nous avons une meilleure exécution de cas de n et le pire des cas l'exécution de n 1742 01:15:26,840 --> 01:15:28,680 carré, on n'a pas d'autonomie prévu. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Cela dépend de la chaos de notre liste il. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 Et encore une fois, un autre graphique et une autre table. 1747 01:15:39,530 --> 01:15:41,170 Donc, les différences entre les genres. 1748 01:15:41,170 --> 01:15:44,180 Je vais passer à travers de, je l'impression que nous avons parlé longuement 1749 01:15:44,180 --> 01:15:46,570 sur la façon dont ils ont tous genre de varier et de lier ensemble. 1750 01:15:46,570 --> 01:15:50,564 Donc, le tri par fusion est le dernier Je vais vous ennuyer avec les gars. 1751 01:15:50,564 --> 01:15:52,105 Nous avons une image assez coloré. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Donc, le tri par fusion est un algorithme récursif. 1754 01:15:56,040 --> 01:15:59,910 Donc, ne vous les gars savent ce que une fonction récursive est? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Tout le monde veut dire? 1757 01:16:03,320 --> 01:16:04,739 Vous voulez essayer? 1758 01:16:04,739 --> 01:16:07,280 Ainsi, une fonction récursive est juste une fonction qui appelle lui-même. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Donc, si vous les gars sont familiers avec la suite de Fibonacci, 1761 01:16:11,590 --> 01:16:15,670 qui est réputé récursive car vous prenez les deux précédents 1762 01:16:15,670 --> 01:16:17,530 et ajoutez-les ensemble pour obtenir votre prochain. 1763 01:16:17,530 --> 01:16:21,440 Donc récursif, je pense toujours de la récursivité comme une spirale 1764 01:16:21,440 --> 01:16:24,430 si vous êtes comme la spirale vers le bas en elle. 1765 01:16:24,430 --> 01:16:27,150 Mais il est juste une fonction qui se dit. 1766 01:16:27,150 --> 01:16:32,660 >> Et, en fait, très rapidement je peut vous montrer à quoi ça ressemble. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Donc récursif ici, si l'on regarde, ce sont la façon récursive à somme sur un tableau. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Donc, tout ce que nous faisons est nous avons fonction de somme 1771 01:16:47,880 --> 01:16:52,210 somme qui prend une taille et un tableau. 1772 01:16:52,210 --> 01:16:55,210 Et si vous remarquez, la taille décrémente de un à chaque fois. 1773 01:16:55,210 --> 01:17:00,365 Et tout ce qu'il fait est si x est égal à zero-- donc si la taille de la matrice 1774 01:17:00,365 --> 01:17:02,710 est égale à zero-- elle renvoie zéro. 1775 01:17:02,710 --> 01:17:10,440 >> Sinon, il résume ce dernier élément du tableau, 1776 01:17:10,440 --> 01:17:14,790 et prend alors une somme de le reste de la matrice. 1777 01:17:14,790 --> 01:17:17,555 Donc, il est juste de le décomposer en problèmes plus petits et plus petits. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Longue histoire courte, la récursivité, fonction que lui-même appelle. 1780 01:17:21,890 --> 01:17:25,740 Si cela est tout ce que vous avez sur ce, qui est ce qui est une fonction récursive. 1781 01:17:25,740 --> 01:17:29,870 Si vous prenez 51, vous obtiendrez très, très à l'aise avec la récursivité. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Il est vraiment cool. 1784 01:17:32,370 --> 01:17:34,660 Il avait un sens à comme 3 heures une nuit. 1785 01:17:34,660 --> 01:17:37,900 Et je me suis dit, pourquoi ai-je jamais l'utiliser? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Donc, pour le tri par fusion, essentiellement ce qu'il va faire est qu'il est 1788 01:17:42,430 --> 01:17:45,620 aller à le décomposer et de le briser vers le bas jusqu'à ce qu'il soit seulement des éléments simples. 1789 01:17:45,620 --> 01:17:47,570 Les éléments simples sont faciles à trier. 1790 01:17:47,570 --> 01:17:48,070 Nous voyons que. 1791 01:17:48,070 --> 01:17:50,760 Si vous avez un élément, il est déjà considéré triée. 1792 01:17:50,760 --> 01:17:53,800 Donc, sur une entrée de n éléments, si n est inférieur à 2, 1793 01:17:53,800 --> 01:17:58,120 il suffit de retourner parce que les moyens il est soit 0 ou 1 comme nous l'avons vu. 1794 01:17:58,120 --> 01:18:00,050 Ceux-ci sont considérés comme des éléments triés. 1795 01:18:00,050 --> 01:18:02,170 >> Sinon briser en deux. 1796 01:18:02,170 --> 01:18:06,336 Trier la première moitié, trier la deuxième la moitié, puis de les fusionner. 1797 01:18:06,336 --> 01:18:07,460 Pourquoi il est appelé tri par fusion. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Nous avons donc ici nous allons régler ces. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Donc, nous continuons à les avoir jusqu'à ce que la taille du tableau est 1. 1802 01:18:17,210 --> 01:18:20,790 Alors, quand il est 1, nous revenons juste parce que cela est un tableau trié, 1803 01:18:20,790 --> 01:18:23,940 et cela est un tableau trié, et qui est un tableau trié, nous sommes tous triée. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Alors ce que nous faisons est que nous commencer à les fusionner ensemble. 1806 01:18:29,420 --> 01:18:31,820 >> Donc, la façon dont vous pouvez penser à la fusion est 1807 01:18:31,820 --> 01:18:36,240 vous suffit de retirer le plus petit nombre de chacun des sous-réseaux 1808 01:18:36,240 --> 01:18:38,330 et juste ajouter à la gamme émergé. 1809 01:18:38,330 --> 01:18:44,290 Donc, si vous regardez ici, lorsque nous avons ces jeux nous ont 4, 6, et 1. 1810 01:18:44,290 --> 01:18:47,280 Quand nous voulons fusionner celles-ci, nous regardons ces deux premiers 1811 01:18:47,280 --> 01:18:50,730 et nous disons, OK, 1 est plus petit, il va vers l'avant. 1812 01:18:50,730 --> 01:18:54,330 4 et 6, il n'y a rien à comparer à, juste marquer sur la fin. 1813 01:18:54,330 --> 01:18:58,020 >> Lorsque nous combinons les deux, nous avons juste prendre la plus petite des deux, 1814 01:18:58,020 --> 01:18:59,310 il est donc 1. 1815 01:18:59,310 --> 01:19:01,690 Et maintenant, nous prenons la plus petit de ces deux, de sorte que deux. 1816 01:19:01,690 --> 01:19:03,330 Plus petite de ces deux, trois. 1817 01:19:03,330 --> 01:19:06,260 Plus petit de ces deux, quatre, cinq, six. 1818 01:19:06,260 --> 01:19:08,630 Donc, vous êtes juste arracher ces. 1819 01:19:08,630 --> 01:19:11,210 Et parce qu'ils ont été triés au préalable, 1820 01:19:11,210 --> 01:19:14,300 vous avez juste un comparaison chaque fois. 1821 01:19:14,300 --> 01:19:19,610 Donc, plus de code ici, juste représentation. 1822 01:19:19,610 --> 01:19:24,410 Donc, vous commencez au milieu et vous triez gauche et la droite 1823 01:19:24,410 --> 01:19:26,180 et puis vous venez de fusionner ces. 1824 01:19:26,180 --> 01:19:30,080 >> Et nous ne disposons pas de code pour fusionner ici. 1825 01:19:30,080 --> 01:19:34,110 Mais, encore une fois, si vous allez sur étudier 50, il sera là. 1826 01:19:34,110 --> 01:19:36,860 Sinon venir me parler si vous êtes encore confus. 1827 01:19:36,860 --> 01:19:42,340 Alors qui est cool ici est que meilleur des cas, pire des cas, et l'exécution prévu 1828 01:19:42,340 --> 01:19:46,250 sont tous en log n, qui est beaucoup mieux que nous avons 1829 01:19:46,250 --> 01:19:48,000 vu pour le reste de nos sortes. 1830 01:19:48,000 --> 01:19:51,840 Nous avons vu n au carré et ce que nous en fait 1831 01:19:51,840 --> 01:19:54,380 obtenir ici est n log n, ce qui est excellent. 1832 01:19:54,380 --> 01:19:55,830 >> Regardez comment beaucoup mieux ce qui est. 1833 01:19:55,830 --> 01:19:56,780 Cette une belle courbe. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Donc beaucoup plus efficace. 1836 01:20:00,120 --> 01:20:03,510 Si jamais vous pouvez, utilisez le tri par fusion. 1837 01:20:03,510 --> 01:20:04,810 Elle vous fera économiser du temps. 1838 01:20:04,810 --> 01:20:07,670 Là encore, comme nous l'avons dit, si vous êtes dans cette région inférieure, 1839 01:20:07,670 --> 01:20:09,480 il ne fait pas que beaucoup de différence. 1840 01:20:09,480 --> 01:20:11,360 Vous vous levez à des milliers et des milliers d'entrées, 1841 01:20:11,360 --> 01:20:13,318 vous voulez absolument un algorithme plus efficace. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 Et, encore une fois, notre belle table de tous sortes que vous les gars ont appris aujourd'hui. 1844 01:20:19,400 --> 01:20:21,157 >> Donc, je sais que ça fait une journée dense. 1845 01:20:21,157 --> 01:20:23,490 Ce ne va pas nécessairement pour vous aider avec votre jeu de processeurs. 1846 01:20:23,490 --> 01:20:28,250 Mais je veux juste faire une mise en garde cet article ne concerne pas seulement psets. 1847 01:20:28,250 --> 01:20:31,240 Tout ce matériel est juste jeu pour vos examens trimestriels. 1848 01:20:31,240 --> 01:20:35,430 Et aussi si vous continuer avec CS, Ce sont ces points réellement importants 1849 01:20:35,430 --> 01:20:37,870 que vous devez savoir. 1850 01:20:37,870 --> 01:20:41,700 Ainsi, certains jours seront un peu plus d'aide pset, 1851 01:20:41,700 --> 01:20:44,600 mais quelques semaines seront beaucoup plus de contenu réel 1852 01:20:44,600 --> 01:20:46,600 cela peut ne pas sembler super- utile pour vous maintenant, 1853 01:20:46,600 --> 01:20:51,215 mais je vous promets si vous continuez sur sera très, très utile. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Voilà donc pour la section. 1856 01:20:54,250 --> 01:20:55,250 Sur le fil. 1857 01:20:55,250 --> 01:20:56,570 Je l'ai fait en une minute. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Mais là vous allez. 1860 01:20:58,970 --> 01:21:01,240 Et je vais avoir des beignets ou des bonbons. 1861 01:21:01,240 --> 01:21:03,464 Quelqu'un est-il allergique à rien, d'ailleurs? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Les œufs et le lait. 1864 01:21:05,890 --> 01:21:08,120 Donc beignets sont un non? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 Dáccord. 1867 01:21:10,160 --> 01:21:10,770 Bien. 1868 01:21:10,770 --> 01:21:12,120 Chocolat non? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts sont bonnes. 1872 01:21:14,670 --> 01:21:15,170 Dáccord. 1873 01:21:15,170 --> 01:21:17,045 Nous allons avoir Starburst la semaine prochaine alors. 1874 01:21:17,045 --> 01:21:18,240 Voilà ce que je vais prendre. 1875 01:21:18,240 --> 01:21:19,690 Les gars, vous avez une très bonne semaine. 1876 01:21:19,690 --> 01:21:20,460 Lire vos spécifications. 1877 01:21:20,460 --> 01:21:22,130 >> Faites-moi savoir si vous avez des questions. 1878 01:21:22,130 --> 01:21:25,300 PSEt deux qualités doivent être à vous de jeudi. 1879 01:21:25,300 --> 01:21:28,320 Si vous avez des questions comment je graduée quelque chose 1880 01:21:28,320 --> 01:21:32,250 ou pourquoi je graduée quelque chose comme je ne, se il vous plaît écrivez-moi, venez me parler. 1881 01:21:32,250 --> 01:21:34,210 Je suis un peu cette folle semaine, mais je vous promets 1882 01:21:34,210 --> 01:21:36,340 Je vais quand même répondre dans les 24 heures. 1883 01:21:36,340 --> 01:21:38,240 Donc, avoir une grande semaine, tout le monde. 1884 01:21:38,240 --> 01:21:40,090 Bonne chance pour votre jeu de processeurs. 1885 01:21:40,090 --> 01:21:41,248