1
00:00:00,000 --> 00:00:03,332
>> [Jouer de la musique]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Bienvenue à la semaine 3 de l'article.

3
00:00:06,490 --> 00:00:09,550
Merci, vous les gars, pour tous à venir
à cette heure de début plus tôt aujourd'hui.

4
00:00:09,550 --> 00:00:11,466
Nous avons un beau petit
groupe intime d'aujourd'hui.

5
00:00:11,466 --> 00:00:14,570
Donc, nous espérons que nous arriverons à
finition, peut-être, au début,

6
00:00:14,570 --> 00:00:15,780
un peu plus tôt aujourd'hui.

7
00:00:15,780 --> 00:00:22,057
Alors vite, quelques-uns
annonces pour l'ordre du jour aujourd'hui.

8
00:00:22,057 --> 00:00:23,890
Avant de commencer, nous sommes
va aller un peu plus

9
00:00:23,890 --> 00:00:28,910
certains problèmes logistiques brèves, pset
questions, débriefing, des choses comme ça.

10
00:00:28,910 --> 00:00:30,250
Et puis nous allons plonger en plein.

11
00:00:30,250 --> 00:00:34,710
Nous allons utiliser un débogueur GDB appelé à
commencer à démystifier notre code, que David

12
00:00:34,710 --> 00:00:36,550
expliqué dans la leçon l'autre jour.

13
00:00:36,550 --> 00:00:39,420
Nous allons passer en revue les quatre types de sortes.

14
00:00:39,420 --> 00:00:42,310
Nous allons passer en revue les assez rapidement
car ils sont assez intensive.

15
00:00:42,310 --> 00:00:45,710
Mais sachez que toutes les diapositives et
code source sont toujours en ligne.

16
00:00:45,710 --> 00:00:50,810
Donc, se sentir libre, à votre lecture, à
revenir en arrière et prendre un coup d'oeil.

17
00:00:50,810 --> 00:00:53,930
>> Nous allons passer par
notation asymptotique, qui

18
00:00:53,930 --> 00:00:55,944
est juste une façon de fantaisie
de dire «runtimes»

19
00:00:55,944 --> 00:00:58,360
où nous avons le grand O, qui
David a expliqué dans la leçon.

20
00:00:58,360 --> 00:01:01,550
Et nous avons aussi Omega, qui
est le runtime limite inférieure.

21
00:01:01,550 --> 00:01:06,450
Et nous allons parler un peu plus
en profondeur sur la façon dont ces travaux.

22
00:01:06,450 --> 00:01:10,160
Et enfin, nous allons passer en revue la recherche binaire,
parce que beaucoup d'entre vous qui ont déjà

23
00:01:10,160 --> 00:01:15,190
regarda vos psets savez probablement que
qui est une question qui est dans votre pset.

24
00:01:15,190 --> 00:01:17,470
Donc, vous serez tous heureux
que nous couvrons aujourd'hui.

25
00:01:17,470 --> 00:01:20,610
>> Et enfin, pour votre
la section des commentaires, je fait

26
00:01:20,610 --> 00:01:23,000
de gauche à environ 15 minutes
la fin pour aller un peu plus

27
00:01:23,000 --> 00:01:27,730
logistique de pset3, des questions,
peut-être un peu d'orientation, si vous voulez,

28
00:01:27,730 --> 00:01:28,990
avant de commencer la programmation.

29
00:01:28,990 --> 00:01:30,890
Essayons donc de passer à travers
le matériau assez rapidement.

30
00:01:30,890 --> 00:01:33,880
Et alors nous pouvons passer du temps
prendre plus de questions pour le jeu de processeurs.

31
00:01:33,880 --> 00:01:35,230
D'ACCORD.

32
00:01:35,230 --> 00:01:39,570
>> Rapidement, de sorte que quelques-uns
annonces avant de commencer aujourd'hui.

33
00:01:39,570 --> 00:01:45,410
Tout d'abord, bienvenue à faire
à travers deux de vos psets.

34
00:01:45,410 --> 00:01:49,432
Je pris un coup d'oeil à your-- oui, nous allons
obtenir une salve d'applaudissements pour celui-là.

35
00:01:49,432 --> 00:01:51,140
En fait, je suis vraiment,
vraiment impressionné.

36
00:01:51,140 --> 00:01:55,800
Je graduée le premier pset pour vous les gars
semaine et vous dernières gars ont fait incroyable.

37
00:01:55,800 --> 00:01:58,290
>> Style était sur le point
à part quelques commentaires.

38
00:01:58,290 --> 00:02:00,660
Assurez-vous que vous êtes toujours
commenter votre code.

39
00:02:00,660 --> 00:02:03,040
Mais vos psets étaient sur le point.

40
00:02:03,040 --> 00:02:05,549
Et garder.

41
00:02:05,549 --> 00:02:08,090
Et il est bon pour la niveleuse
voir que vous les gars mettent

42
00:02:08,090 --> 00:02:10,704
autant d'efforts dans votre style
et votre conception dans votre code

43
00:02:10,704 --> 00:02:12,120
que nous aimerions pour vous de voir.

44
00:02:12,120 --> 00:02:16,450
Donc, je suis de passage le long de ma gratitude
pour le reste de l'AT.

45
00:02:16,450 --> 00:02:19,210
>> Cependant, il ya un
quelques questions de débriefing

46
00:02:19,210 --> 00:02:22,010
Je veux juste revenir là-dessus
rendrait ma vie à la fois

47
00:02:22,010 --> 00:02:24,900
et beaucoup de l'autre
AT 'vit un peu plus facile.

48
00:02:24,900 --> 00:02:28,220
Tout d'abord, je l'ai remarqué
week-- passé combien d'entre vous

49
00:02:28,220 --> 00:02:32,301
ont été en cours d'exécution sur check50
votre code avant de vous présenter?

50
00:02:32,301 --> 00:02:32,800
D'ACCORD.

51
00:02:32,800 --> 00:02:36,690
Donc tout le monde devrait faire check50,
because-- un secret-- nous fait

52
00:02:36,690 --> 00:02:41,540
check50 exécuter dans le cadre de notre rectitude
scripts pour tester votre code.

53
00:02:41,540 --> 00:02:45,480
Donc, si votre code est un échec
check50, selon toute vraisemblance,

54
00:02:45,480 --> 00:02:47,570
il va probablement
l'échec de notre vérification ainsi.

55
00:02:47,570 --> 00:02:49,320
Parfois, vous les gars
avoir les bonnes réponses.

56
00:02:49,320 --> 00:02:52,200
Comme, dans gourmand, certains
vous avez les bons numéros,

57
00:02:52,200 --> 00:02:53,960
vous venez d'imprimer quelques trucs supplémentaires.

58
00:02:53,960 --> 00:02:55,940
Et ce truc supplémentaire
ne parvient pas fait le chèque,

59
00:02:55,940 --> 00:02:58,440
parce que l'ordinateur ne fonctionne pas
vraiment savoir ce qu'il cherche.

60
00:02:58,440 --> 00:03:00,981
Et il suffit d'exécuter à travers,
voir que votre sortie ne

61
00:03:00,981 --> 00:03:03,810
comparons ce que nous attendons la réponse
être, et marquer il est faux.

62
00:03:03,810 --> 00:03:06,560
>> Et je sais ce qui est arrivé dans
certains de vos cas cette semaine.

63
00:03:06,560 --> 00:03:09,870
Je suis donc retourné et manuellement
reclassé le code de tout le monde.

64
00:03:09,870 --> 00:03:12,780
Dans l'avenir, cependant,
s'il vous plaît, s'il vous plaît assurez-

65
00:03:12,780 --> 00:03:14,570
que vous êtes en cours d'exécution
50 vérifier sur votre code.

66
00:03:14,570 --> 00:03:17,970
Parce qu'il est une sorte de douleur pour la TA
d'avoir à revenir en arrière et reclasser manuellement

67
00:03:17,970 --> 00:03:21,197
chaque pset pour chaque
unique, par exemple peu raté.

68
00:03:21,197 --> 00:03:22,530
Donc, je ne prenais pas hors des points.

69
00:03:22,530 --> 00:03:25,210
Je pense que je suis parti peut-être
un ou deux pour la conception.

70
00:03:25,210 --> 00:03:27,710
À l'avenir cependant, si
vous ne check50,

71
00:03:27,710 --> 00:03:31,330
points seront prises
off pour l'exactitude.

72
00:03:31,330 --> 00:03:35,020
>> En outre, psets sont
en raison vendredi à midi.

73
00:03:35,020 --> 00:03:38,990
Je pense qu'il ya un sept minutes
période de grâce tard que nous vous donnons.

74
00:03:38,990 --> 00:03:42,434
Par temps de Harvard, ils sont autorisés à
sept minutes de retard à tout.

75
00:03:42,434 --> 00:03:44,350
Donc, ici, à Yale, nous allons
adhérer à cela aussi.

76
00:03:44,350 --> 00:03:47,910
Mais à peu près, à 12:07,
si votre pset est pas,

77
00:03:47,910 --> 00:03:49,720
ça va être marqué comme fin.

78
00:03:49,720 --> 00:03:53,160
Et alors qu'il est marqué
plus tard, je suis l'TA--

79
00:03:53,160 --> 00:03:54,870
toujours en cours pour être titrant vos psets.

80
00:03:54,870 --> 00:03:56,760
Donc, vous verrez toujours une note apparaît.

81
00:03:56,760 --> 00:03:58,820
Cependant, à savoir que
la fin du semestre,

82
00:03:58,820 --> 00:04:02,270
tous les psets fin sera juste
automatiquement mis à zéro par l'ordinateur.

83
00:04:02,270 --> 00:04:04,490
>> Nous faisons cela pour deux raisons.

84
00:04:04,490 --> 00:04:09,220
Un, parfois nous sommes
excusé, comme les excuses de Dean,

85
00:04:09,220 --> 00:04:10,762
plus tard que je ne sais pas encore.

86
00:04:10,762 --> 00:04:13,761
Donc, nous nous plaisons à nous assurer que nous classement
tout juste au cas où, comme, je suis

87
00:04:13,761 --> 00:04:15,080
manquant l'excuse d'un doyen.

88
00:04:15,080 --> 00:04:17,000
Et d'autre part, garder à
l'esprit, vous pouvez toujours

89
00:04:17,000 --> 00:04:19,370
déposer un pset que
a des points d'intégrales.

90
00:04:19,370 --> 00:04:21,430
Et si nous aimons au grade
tous vos psets juste

91
00:04:21,430 --> 00:04:24,730
pour vous assurer que votre champ de
là et vous les essayer.

92
00:04:24,730 --> 00:04:29,150
Donc, même si il est tard, vous aurez toujours
obtenir un crédit pour les points de portée, je pense.

93
00:04:29,150 --> 00:04:33,730
>> Donc morale de l'histoire est, assurez-
vous que vos psets sont en sur-temps.

94
00:04:33,730 --> 00:04:38,350
Et si elles ne sont pas dans le temps,
sachez qu'il est pas très grande.

95
00:04:38,350 --> 00:04:41,678
Ouais, avant de passer, quelqu'un at-
Pour toute question concernant les commentaires des pset?

96
00:04:41,678 --> 00:04:42,178
Ouais.

97
00:04:42,178 --> 00:04:43,630
>> Public: Avez-vous dit que nous
peut déposer l'un des psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI PENG: Ouais.

99
00:04:44,296 --> 00:04:47,050
Donc, il ya neuf psets globale
au cours du semestre.

100
00:04:47,050 --> 00:04:50,610
Et si vous avez portée
points-- donc portée est juste,

101
00:04:50,610 --> 00:04:53,567
assez bien, essayez-vous le
problème, faites-vous mettre dans le temps,

102
00:04:53,567 --> 00:04:56,150
montrez-vous que vous avez
démontré que vous avez lu la spec.

103
00:04:56,150 --> 00:04:57,191
Voilà à peu près la portée.

104
00:04:57,191 --> 00:04:59,370
Et si vous accomplissez
points de périmètre, nous

105
00:04:59,370 --> 00:05:03,360
peut déposer le plus bas
un sur la pleine portée.

106
00:05:03,360 --> 00:05:06,790
Voilà donc à votre avantage de
compléter et essayer chaque jeu de processeurs.

107
00:05:06,790 --> 00:05:10,320
>> Même si aucun des upload--
les travailler, de les télécharger tous.

108
00:05:10,320 --> 00:05:13,711
Et puis nous espérons être en mesure de
vous donner certains de ces points derrière.

109
00:05:13,711 --> 00:05:14,210
Frais.

110
00:05:14,210 --> 00:05:16,780
D'autres questions?

111
00:05:16,780 --> 00:05:17,840
Génial.

112
00:05:17,840 --> 00:05:21,960
>> Deuxièmement, bureau heures-- quelques-uns
notes rapides sur les heures de bureau.

113
00:05:21,960 --> 00:05:24,300
Alors d'abord, venir plus tôt dans la semaine.

114
00:05:24,300 --> 00:05:26,909
Personne est jamais à
les heures de bureau le lundi.

115
00:05:26,909 --> 00:05:28,700
Christabel est venu à
les heures de bureau la nuit dernière.

116
00:05:28,700 --> 00:05:29,691
Ouais, Christabel.

117
00:05:29,691 --> 00:05:32,190
Et qu'est-ce que nous avons au bureau
heures la nuit dernière, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> PUBLIC: Nous avons eu de la crème glacée.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Donc, ce qui est juste, nous avions
crème glacée à des heures de bureau la nuit dernière.

120
00:05:36,160 --> 00:05:39,390
Bien que je ne peux pas vous promettre que
nous aurons de la crème glacée aux heures de bureau

121
00:05:39,390 --> 00:05:43,230
chaque semaine, ce que je peux vous promettre
est qu'il y aura un significativement

122
00:05:43,230 --> 00:05:45,380
mieux ratio élève TA.

123
00:05:45,380 --> 00:05:47,650
Comme légitime, il est comme trois à un.

124
00:05:47,650 --> 00:05:50,350
Considérant que, qui contraste avec
Jeudi, vous avez environ 150

125
00:05:50,350 --> 00:05:52,830
vraiment insisté sur les enfants et pas de crème glacée.

126
00:05:52,830 --> 00:05:55,360
Et il est tout simplement pas productif pour tout le monde.

127
00:05:55,360 --> 00:05:58,730
Donc morale de l'histoire est, venir tôt
pour les heures de bureau et de bonnes choses

128
00:05:58,730 --> 00:06:00,310
qui va se passer.

129
00:06:00,310 --> 00:06:02,110
>> Aussi, être prêts à poser des questions.

130
00:06:02,110 --> 00:06:03,200
Tu sais?

131
00:06:03,200 --> 00:06:05,420
Indépendamment de ce que PS, je
penser, ont été dit,

132
00:06:05,420 --> 00:06:10,710
nous avons reçu quelques étudiants
qui viennent de jeudi à, comme 10:50

133
00:06:10,710 --> 00:06:15,100
ne pas avoir lu la spec
être comme aide-moi, aidez-moi.

134
00:06:15,100 --> 00:06:18,200
Malheureusement, à ce moment-là, il ya
pas beaucoup que nous pouvons faire pour vous aider.

135
00:06:18,200 --> 00:06:19,590
Donc, s'il vous plaît venez tôt dans la semaine.

136
00:06:19,590 --> 00:06:22,040
Venez tôt pour les heures de bureau.

137
00:06:22,040 --> 00:06:23,350
Soyez prêts à poser des questions.

138
00:06:23,350 --> 00:06:25,310
Assurez-vous que vous, en tant
un étudiant, où sont

139
00:06:25,310 --> 00:06:27,620
vous devez être de sorte que la
AT peut vous guider le long,

140
00:06:27,620 --> 00:06:32,850
qui est ce que les heures de bureau
doit être attribuée à.

141
00:06:32,850 --> 00:06:37,380
>> Deuxièmement, donc je sais professeurs
tenons à nous surprendre avec des tests.

142
00:06:37,380 --> 00:06:39,439
Je devais un professeur ceux
comme, yo, par la manière,

143
00:06:39,439 --> 00:06:41,230
rappeler que mi-parcours
vous avez lundi prochain.

144
00:06:41,230 --> 00:06:42,855
Ouais, je ne savais pas à ce sujet mi-parcours.

145
00:06:42,855 --> 00:06:45,630
Donc, je vais être que TA
qui vous rappelle tout ce quizz

146
00:06:45,630 --> 00:06:47,270
0-- parce que, vous savez, nous sommes CS.

147
00:06:47,270 --> 00:06:50,730
Maintenant que nous avons des tableaux fait, vous obtenez
pourquoi il est quizz 0, pas interroger 1, hein?

148
00:06:50,730 --> 00:06:51,320
D'ACCORD.

149
00:06:51,320 --> 00:06:52,490
Oh, je suis arrivé quelques rires sur celui-là.

150
00:06:52,490 --> 00:06:53,120
D'ACCORD.

151
00:06:53,120 --> 00:06:59,710
>> Donc quizz 0 sera le 14 Octobre si
vous êtes dans la section du lundi au mercredi

152
00:06:59,710 --> 00:07:02,920
et 15 Octobre si vous êtes dans
la section du mardi au jeudi.

153
00:07:02,920 --> 00:07:05,630
Cela ne vaut pas pour les
ceux d'entre vous à Harvard

154
00:07:05,630 --> 00:07:10,350
who-- Je pense que vous serez tous
prendre vos quiz sur la 14e.

155
00:07:10,350 --> 00:07:13,560
>> Donc oui, la semaine prochaine, si
David, en cours, va,

156
00:07:13,560 --> 00:07:15,747
Ouais, donc à ce sujet
Quiz semaine prochaine, vous tous

157
00:07:15,747 --> 00:07:17,580
ne sera pas choqué parce
vous êtes venu à l'article

158
00:07:17,580 --> 00:07:19,664
et vous savez que votre
Quiz 0 est dans deux semaines.

159
00:07:19,664 --> 00:07:21,580
Et nous aurons avis
sessions et tout.

160
00:07:21,580 --> 00:07:26,360
Donc pas de soucis au sujet
avoir peur pour ça.

161
00:07:26,360 --> 00:07:29,890
Toutes les questions before-- des questions
à toutes les questions logistiques relatives,

162
00:07:29,890 --> 00:07:32,591
classement, les heures de bureau, les articles?

163
00:07:32,591 --> 00:07:33,090
Ouais.

164
00:07:33,090 --> 00:07:35,100
>> Auditoire: Alors, le quiz est
va être durant conférence?

165
00:07:35,100 --> 00:07:35,766
>> ANDI PENG: Ouais.

166
00:07:35,766 --> 00:07:39,460
Donc, le quiz, je pense, est de 60
minutes allouées dans cet intervalle de temps

167
00:07:39,460 --> 00:07:42,240
que vous venez de prendre
dans la salle de conférence.

168
00:07:42,240 --> 00:07:44,810
Donc, vous ne devez pas venir
sur, comme un hasard 19h00.

169
00:07:44,810 --> 00:07:46,140
C'est parfait.

170
00:07:46,140 --> 00:07:47,100
Ouais.

171
00:07:47,100 --> 00:07:50,060
Frais.

172
00:07:50,060 --> 00:07:50,840
>> Bien.

173
00:07:50,840 --> 00:07:54,330
Nous allons donc
introduire un concept de vous

174
00:07:54,330 --> 00:08:00,760
cette semaine que David a déjà genre
de touché dans cette conférence la semaine dernière.

175
00:08:00,760 --> 00:08:02,010
Il a appelé GDB.

176
00:08:02,010 --> 00:08:05,570
Et combien d'entre vous, tandis que dans
au cours de la rédaction de vos psets,

177
00:08:05,570 --> 00:08:09,981
ont remarqué un gros bouton qui dit
"Debug" sur le haut de votre IDE?

178
00:08:09,981 --> 00:08:10,480
D'ACCORD.

179
00:08:10,480 --> 00:08:13,770
Alors maintenant, nous allons réellement obtenir pour déterrer
le mystère de ce qui touche effectivement

180
00:08:13,770 --> 00:08:14,270
Est-ce que.

181
00:08:14,270 --> 00:08:16,790
Et je vous garantis, il est un
belle, belle chose.

182
00:08:16,790 --> 00:08:20,740
>> Donc, jusqu'à présent, je pense
il ya eu deux choses

183
00:08:20,740 --> 00:08:23,320
les étudiants ont été généralement
faire lors du débogage psets.

184
00:08:23,320 --> 00:08:27,635
Un, ils ajoutent soit dans
printf () - donc, tous les quelques lignes,

185
00:08:27,635 --> 00:08:29,760
ajoutent-ils dans un printf () -
Oh, quelle est cette variable?

186
00:08:29,760 --> 00:08:32,551
Oh, quelle est cette variable maintenant--
et vous sorte de voir la progression

187
00:08:32,551 --> 00:08:33,940
de votre code tel qu'il fonctionne.

188
00:08:33,940 --> 00:08:37,030
Ou la deuxième méthode enfants font est
qu'ils suffit d'écrire le tout

189
00:08:37,030 --> 00:08:38,610
puis aller comme ça à la fin.

190
00:08:38,610 --> 00:08:39,970
Espérons que cela fonctionne.

191
00:08:39,970 --> 00:08:44,851
Je vous garantis, GDB est mieux
que ces deux méthodes.

192
00:08:44,851 --> 00:08:45,350
Ouais.

193
00:08:45,350 --> 00:08:46,980
Donc, ce sera votre nouveau meilleur ami.

194
00:08:46,980 --> 00:08:51,780
Parce qu'il est une belle chose
que, visuellement, affiche à la fois

195
00:08:51,780 --> 00:08:54,850
ce qui fait votre code
à un point spécifique

196
00:08:54,850 --> 00:08:57,486
ainsi que ce que l'ensemble de votre
les variables sont porteurs,

197
00:08:57,486 --> 00:08:59,610
comme ce que leurs valeurs sont,
à ce point précis.

198
00:08:59,610 --> 00:09:02,670
Et de cette façon, vous pouvez vraiment
définir des points d'arrêt dans votre code.

199
00:09:02,670 --> 00:09:04,350
Vous pouvez exécuter ligne par ligne.

200
00:09:04,350 --> 00:09:07,324
Et GDB devra simplement pour
vous, affiché pour vous,

201
00:09:07,324 --> 00:09:09,490
ce que toutes vos variables
sont, que font-ils,

202
00:09:09,490 --> 00:09:10,656
ce qui se passe dans le code.

203
00:09:10,656 --> 00:09:13,240
Et de telle manière, il est
tellement plus facile de voir

204
00:09:13,240 --> 00:09:17,120
ce qui se passe à la place de printf-ing
ou l'écriture de vos déclarations.

205
00:09:17,120 --> 00:09:19,160
>> Donc, nous allons faire un exemple de cela plus tard.

206
00:09:19,160 --> 00:09:20,660
Donc, cela semble un peu abstrait.

207
00:09:20,660 --> 00:09:23,490
Pas de soucis, nous ferons des exemples.

208
00:09:23,490 --> 00:09:29,170
Et si essentiellement, les trois plus grands,
fonctions les plus utilisées dont vous aurez besoin dans GDB

209
00:09:29,170 --> 00:09:32,500
sont l'étape suivante, au cours,
et l'étape en boutons.

210
00:09:32,500 --> 00:09:34,860
Je vais diriger
là, en fait, à l'heure actuelle.

211
00:09:34,860 --> 00:09:40,930
>> Ainsi, vous pouvez voir que tous les gars
ou devrais-je agrandir un peu?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
À l'arrière, pouvez-vous le voir?

214
00:09:44,470 --> 00:09:45,730
Devrais-je agrandir?

215
00:09:45,730 --> 00:09:46,480
Juste un petit peu?

216
00:09:46,480 --> 00:09:49,390
OK cool.

217
00:09:49,390 --> 00:09:50,280
Nous y voilà.

218
00:09:50,280 --> 00:09:50,960
D'ACCORD.

219
00:09:50,960 --> 00:09:57,000
>> Je dois donc, ici, mon
mise en œuvre pour les gourmands.

220
00:09:57,000 --> 00:10:01,430
Et tandis que beaucoup d'entre vous les gars écrit
gourmand en boucle while que form--

221
00:10:01,430 --> 00:10:04,890
est une manière parfaitement acceptable de le faire
it-- une autre façon de le faire est de simplement

222
00:10:04,890 --> 00:10:06,280
diviser dans le modulo.

223
00:10:06,280 --> 00:10:09,290
Parce que vous pouvez avoir votre
valeur, puis ont votre reste.

224
00:10:09,290 --> 00:10:11,150
Et puis vous pouvez juste
ajouter tous ensemble.

225
00:10:11,150 --> 00:10:13,390
Est-ce que la logique de ce que je fais
ici donner un sens à tout le monde,

226
00:10:13,390 --> 00:10:14,117
avant de commencer?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Genre de?

229
00:10:17,980 --> 00:10:18,710
Frais.

230
00:10:18,710 --> 00:10:19,210
Génial.

231
00:10:19,210 --> 00:10:21,290
Il est un morceau sexy
de code, je dirais.

232
00:10:21,290 --> 00:10:23,502
Comme je le disais, David, dans
sermonner, après un certain temps,

233
00:10:23,502 --> 00:10:25,960
vous commencez à voir tout le code
comme quelque chose qui est beau.

234
00:10:25,960 --> 00:10:29,950
Et parfois, quand vous voyez belle
code, il est un tel sentiment merveilleux.

235
00:10:29,950 --> 00:10:35,410
>> Donc, cependant, alors que ce code est très
beau, il ne fonctionne pas correctement.

236
00:10:35,410 --> 00:10:37,750
Donc, nous allons courir sur cette check50.

237
00:10:37,750 --> 00:10:39,440
Vérifiez 50 20-- oop.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
Est-ce que pset2?

241
00:10:44,990 --> 00:10:46,870
Ouais.

242
00:10:46,870 --> 00:10:47,520
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
D'ACCORD.

245
00:10:52,890 --> 00:10:53,900
Donc, nous courons check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> Et comme vous pouvez le voir ici les gars,
il est à défaut d'un couple de cas.

248
00:11:07,170 --> 00:11:10,165
Et pour certains d'entre vous, dans la
Bien sûr de faire vos ensembles de problèmes,

249
00:11:10,165 --> 00:11:11,110
vous êtes comme, ah, pourquoi ça ne marche pas.

250
00:11:11,110 --> 00:11:13,318
Pourquoi est-il travaille depuis un certain
valeurs, mais pas pour d'autres?

251
00:11:13,318 --> 00:11:17,760
Eh bien, GDB va vous aider à comprendre
pourquoi ces entrées ne fonctionnaient pas.

252
00:11:17,760 --> 00:11:18,320
>> D'ACCORD.

253
00:11:18,320 --> 00:11:21,640
Voyons donc, l'un des
Je contrôles échouait dans check50

254
00:11:21,640 --> 00:11:24,920
est la valeur d'entrée de 0,41.

255
00:11:24,920 --> 00:11:27,830
Alors que la réponse correcte
vous devriez obtenir est un 4.

256
00:11:27,830 --> 00:11:33,090
Mais au lieu de quoi je imprimer
est le 3-n, ce qui est incorrect.

257
00:11:33,090 --> 00:11:36,190
Alors disons simplement exécuter manuellement, juste
assurez-vous que check50 travaille.

258
00:11:36,190 --> 00:11:36,940
Faisons ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Oups, je dois faire gourmand.

261
00:11:43,340 --> 00:11:43,840
Nous y voilà.

262
00:11:43,840 --> 00:11:44,381
Maintenant ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Combien est dû?

265
00:11:47,670 --> 00:11:49,550
Faisons 0,41.

266
00:11:49,550 --> 00:11:52,590
Et oui, nous voyons ici
qu'il est en sortie 3

267
00:11:52,590 --> 00:11:55,160
quand la bonne réponse,
en fait, devrait être de 4.

268
00:11:55,160 --> 00:12:01,460
Donc, nous allons entrer GDB et voir comment nous
peut aller sur la fixation de ce problème.

269
00:12:01,460 --> 00:12:03,992
>> Donc, la première étape
débogage toujours votre code

270
00:12:03,992 --> 00:12:05,950
est de mettre un point d'arrêt,
ou un point à laquelle vous

271
00:12:05,950 --> 00:12:09,079
vouloir l'ordinateur ou le
débogueur pour commencer à regarder.

272
00:12:09,079 --> 00:12:11,120
Donc, si vous ne faites pas vraiment
savoir ce que votre problème est,

273
00:12:11,120 --> 00:12:14,670
généralement, la chose typique que nous voulons
faire est de régler notre point d'arrêt à principal.

274
00:12:14,670 --> 00:12:18,520
Donc, si vous les gars pouvez voir cette
bouton rouge juste là,

275
00:12:18,520 --> 00:12:22,860
yep, qui me fixant un
point d'arrêt pour la fonction principale.

276
00:12:22,860 --> 00:12:24,130
Je clique sur cela.

277
00:12:24,130 --> 00:12:26,130
>> Et puis je peux aller jusqu'à mon bouton de débogage.

278
00:12:26,130 --> 00:12:27,036
Je frappe ce bouton.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Permettez-moi de faire un zoom arrière si je peux.

281
00:12:36,555 --> 00:12:38,020
Nous y voilà.

282
00:12:38,020 --> 00:12:40,730
Donc, nous avons, ici, un panneau sur la droite.

283
00:12:40,730 --> 00:12:43,680
Je suis désolé, les gars dans le dos, vous
ne peut pas vraiment voir vraiment bien.

284
00:12:43,680 --> 00:12:49,090
Mais essentiellement, tous les
ce panneau de droite est en train de faire

285
00:12:49,090 --> 00:12:53,130
est de garder une trace de l'évidence à la fois
ligne, qui est la ligne de code

286
00:12:53,130 --> 00:12:56,640
que l'ordinateur est en cours d'exécution,
ainsi que tous vos variables

287
00:12:56,640 --> 00:12:57,600
ici.

288
00:12:57,600 --> 00:13:00,487
>> Donc, vous avez cents, pièces de monnaie, n,
tous déclaré à des choses différentes

289
00:13:00,487 --> 00:13:01,070
à ce point.

290
00:13:01,070 --> 00:13:04,850
Pas de soucis, parce que nous avons pas réellement
les initialisée à toutes les variables encore.

291
00:13:04,850 --> 00:13:07,200
Donc, dans votre ordinateur, votre
ordinateur est juste de voir,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 était la dernière fonction utilisée
de cet espace de mémoire dans mon ordinateur.

293
00:13:14,376 --> 00:13:16,000
Et donc voilà où cents est actuellement.

294
00:13:16,000 --> 00:13:19,360
Mais pas une fois que vous exécutez le code,
il devrait devenir initialisé.

295
00:13:19,360 --> 00:13:24,110
>> Donc, nous allons passer par ligne par
ligne, ce qui se passe ici.

296
00:13:24,110 --> 00:13:25,350
D'ACCORD.

297
00:13:25,350 --> 00:13:29,400
Donc ici sont les trois
boutons que je viens expliqué.

298
00:13:29,400 --> 00:13:34,090
Vous avez le jeu, ou la fonction Exécuter,
bouton, vous avez la Étape sur le bouton,

299
00:13:34,090 --> 00:13:36,600
et vous avez également l'étape en touche.

300
00:13:36,600 --> 00:13:41,260
Et essentiellement, tous les trois
leur suffit d'aller dans votre code

301
00:13:41,260 --> 00:13:42,690
et faire des choses différentes.

302
00:13:42,690 --> 00:13:45,680
>> Donc, généralement, quand vous êtes le débogage,
nous ne voulons pas simplement sur Lecture,

303
00:13:45,680 --> 00:13:47,930
Parce que le jeu sera juste courir
votre code à la fin de celui-ci.

304
00:13:47,930 --> 00:13:49,070
Et puis vous ne sera pas réellement
savoir ce que votre problème

305
00:13:49,070 --> 00:13:51,432
est sauf si vous définissez plusieurs points d'arrêt.

306
00:13:51,432 --> 00:13:53,890
Si vous définissez plusieurs points d'arrêt,
Il va juste automatiquement

307
00:13:53,890 --> 00:13:56,030
courir d'un point d'arrêt,
à l'autre, à l'autre.

308
00:13:56,030 --> 00:13:58,030
Mais dans ce cas, nous avons
juste celui-là, parce que nous

309
00:13:58,030 --> 00:13:59,970
vouloir travailler notre chemin
de haut en bas en bas.

310
00:13:59,970 --> 00:14:04,830
Donc, nous allons ignorer ce bouton
en ce moment aux fins de ce programme.

311
00:14:04,830 --> 00:14:08,230
>> Donc l'étape sur la fonction juste
étapes sur chaque ligne

312
00:14:08,230 --> 00:14:11,510
et vous dit ce
l'ordinateur est en train de faire.

313
00:14:11,510 --> 00:14:14,630
L'étape en fonction va
dans la fonction réelle

314
00:14:14,630 --> 00:14:16,000
qui est sur votre ligne de code.

315
00:14:16,000 --> 00:14:19,070
Ainsi, par exemple, comme printf (),
qui est fonction, non?

316
00:14:19,070 --> 00:14:21,980
Si je voulais physiquement étape
dans la fonction printf (),

317
00:14:21,980 --> 00:14:25,610
Je voudrais aller effectivement dans le morceau de
code où printf () a été écrit et voir

318
00:14:25,610 --> 00:14:26,730
que se passe-t-il ici.

319
00:14:26,730 --> 00:14:29,924
>> Mais généralement, nous supposons que
le code que nous vous donnons fonctionne.

320
00:14:29,924 --> 00:14:31,340
Nous supposons que le printf () fonctionne.

321
00:14:31,340 --> 00:14:33,170
Nous supposons que getint () fonctionne.

322
00:14:33,170 --> 00:14:35,170
Il n'y a donc pas besoin de
entrer dans ces fonctions.

323
00:14:35,170 --> 00:14:37,170
Mais si il ya des fonctions
que vous vous écrivez

324
00:14:37,170 --> 00:14:39,060
que vous souhaitez vérifier
sur ce qui se passe,

325
00:14:39,060 --> 00:14:41,200
vous voulez à l'étape
dans cette fonction.

326
00:14:41,200 --> 00:14:43,940
>> Donc maintenant, nous allons juste
enjamber ce morceau de code.

327
00:14:43,940 --> 00:14:44,485
Voyons donc.

328
00:14:44,485 --> 00:14:46,547
Oh, impression, "Oh hai, comment
beaucoup de changement est dû? "

329
00:14:46,547 --> 00:14:47,130
Nous ne nous soucions pas.

330
00:14:47,130 --> 00:14:49,830
Nous savons que ce travail,
donc nous intervenons sur elle.

331
00:14:49,830 --> 00:14:53,290
>> Alors n, qui est notre flotteur
Nous avons initialized-- ou declared--

332
00:14:53,290 --> 00:14:56,810
au sommet, nous sommes maintenant
égale à celle de GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Donc, nous allons passer par-dessus cela.

334
00:14:57,810 --> 00:14:59,580
Et nous voyons à la
en bas ici, le programme

335
00:14:59,580 --> 00:15:03,360
me demandant de saisir une valeur.

336
00:15:03,360 --> 00:15:08,580
Donc, nous allons saisir la valeur que nous voulons
pour tester ici, qui est de 0,41.

337
00:15:08,580 --> 00:15:09,160
Génial.

338
00:15:09,160 --> 00:15:12,780
>> Alors maintenant n-- Avez-vous les gars voir
ici, au bottom-- il est

339
00:15:12,780 --> 00:15:15,140
stored-- parce que nous
ne sont pas encore arrondi, il est

340
00:15:15,140 --> 00:15:19,540
stockée dans ce géant comme
flotteur qui est 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
qui est assez proche de notre
fins, dès maintenant, à 0,41.

342
00:15:22,550 --> 00:15:26,090
Et puis, nous le verrons plus tard, comme nous
continuer d'intensifier sur le programme,

343
00:15:26,090 --> 00:15:29,850
après ici, n est devenu
arrondie et est devenu 41 cents.

344
00:15:29,850 --> 00:15:30,350
Génial.

345
00:15:30,350 --> 00:15:32,230
Donc, nous savons que le travail de notre arrondissement.

346
00:15:32,230 --> 00:15:34,700
Nous savons que nous avons la
bon nombre de cents,

347
00:15:34,700 --> 00:15:36,990
de sorte que nous savons que cela est
pas vraiment le problème.

348
00:15:36,990 --> 00:15:40,050
>> Donc nous continuons pas à pas
dans ce programme.

349
00:15:40,050 --> 00:15:40,900
Nous allons ici.

350
00:15:40,900 --> 00:15:46,139
Et donc après cette ligne de code, nous
devrait savoir combien de trimestres que nous avons.

351
00:15:46,139 --> 00:15:46,680
Nous intervenons plus.

352
00:15:46,680 --> 00:15:52,040
Et vous voyez que nous faisons, en fait, avons une
trimestre parce que nous avons soustrait 25

353
00:15:52,040 --> 00:15:53,790
de notre valeur initiale de 41.

354
00:15:53,790 --> 00:15:55,890
Et nous avons 16 gauche pour nos cents.

355
00:15:55,890 --> 00:15:58,830
>> Tout le monde comprend comment
le programme multiplie par

356
00:15:58,830 --> 00:16:02,980
et pourquoi cents est maintenant devenu 16
et pourquoi, aujourd'hui, des pièces de monnaie est devenue 1?

357
00:16:02,980 --> 00:16:04,610
Tout le monde est cette logique?

358
00:16:04,610 --> 00:16:05,110
Frais.

359
00:16:05,110 --> 00:16:07,860
Donc à partir de ce point, le
le travail de programme, non?

360
00:16:07,860 --> 00:16:09,797
Nous savons qu'il fait exactement
ce que nous voulons.

361
00:16:09,797 --> 00:16:11,880
Et nous avons fait pas réellement
avoir à imprimer, oh, ce

362
00:16:11,880 --> 00:16:14,430
est cents à ce point,
ce qui est des pièces à ce stade.

363
00:16:14,430 --> 00:16:17,170
>> Nous continuons à passer par le programme.

364
00:16:17,170 --> 00:16:18,100
Enjamber.

365
00:16:18,100 --> 00:16:18,620
Frais.

366
00:16:18,620 --> 00:16:19,700
Nous passons en revue dimes.

367
00:16:19,700 --> 00:16:20,200
Génial.

368
00:16:20,200 --> 00:16:22,367
Nous voyons que cela a pris
off 0,10 $ pour un sou.

369
00:16:22,367 --> 00:16:23,450
Et maintenant nous avons deux pièces.

370
00:16:23,450 --> 00:16:25,260
C'est correct.

371
00:16:25,260 --> 00:16:31,555
>> Nous passons en revue quelques centimes et nous voyons
qui nous reste plus cents.

372
00:16:31,555 --> 00:16:32,680
Hmm, qui est étrange.

373
00:16:32,680 --> 00:16:37,540
Jusqu'à ici, au programme, je devais
avoir soustrait mes sous.

374
00:16:37,540 --> 00:16:39,400
Peut-être tout simplement je ne suis pas
faire ce droit en ligne.

375
00:16:39,400 --> 00:16:42,190
Et hélas, vous pouvez voir
ici, parce que nous savons

376
00:16:42,190 --> 00:16:44,360
que nous intensifions
à travers les lignes 32 et 33,

377
00:16:44,360 --> 00:16:50,560
qui est là notre programme
avait indûment les variables courent.

378
00:16:50,560 --> 00:16:55,136
Donc, nous pouvons regarder et voir, oh,
Je soustrayant cents ici,

379
00:16:55,136 --> 00:16:57,010
mais je ne suis pas fait
ajouter à ma valeur de la pièce.

380
00:16:57,010 --> 00:16:57,860
Je ajoutant cents.

381
00:16:57,860 --> 00:17:00,234
Et je ne veux pas ajouter à
cents, je tiens à ajouter aux pièces.

382
00:17:00,234 --> 00:17:05,420
Donc, si nous changeons cela à pièces de monnaie,
nous avons un programme de travail.

383
00:17:05,420 --> 00:17:06,730
Je peux courir check50.

384
00:17:06,730 --> 00:17:11,063
Vous pouvez juste sortir sur GDB droit
ici et puis exécutez à nouveau check50.

385
00:17:11,063 --> 00:17:11,938
Je ne pouvais le faire.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Je dois faire gourmand.

388
00:17:18,480 --> 00:17:19,940
0,41.

389
00:17:19,940 --> 00:17:22,819
Et ici, il est l'impression
la bonne réponse.

390
00:17:22,819 --> 00:17:26,569
>> Donc, comme vous les gars pouvez le voir, GDB
est un outil vraiment puissant

391
00:17:26,569 --> 00:17:29,940
quand nous avons tellement de code
passe et tellement de variables

392
00:17:29,940 --> 00:17:32,510
qu'il est difficile pour nous, comme
un être humain, à garder la trace.

393
00:17:32,510 --> 00:17:35,360
L'ordinateur, dans la BDG
débogueur, a la capacité

394
00:17:35,360 --> 00:17:37,020
de garder une trace de tout.

395
00:17:37,020 --> 00:17:40,480
Je sais que, dans Visionaire, vous les gars probablement
aurait pu frapper quelques erreurs de segmentation

396
00:17:40,480 --> 00:17:43,150
parce que vous dirigiez
en dehors des limites de votre tableau.

397
00:17:43,150 --> 00:17:46,510
Dans l'exemple de César, qui est
exactement ce que je l'ai mis en œuvre ici.

398
00:17:46,510 --> 00:17:50,060
>> Donc je oublié de vérifier
ce qui se passerait si je

399
00:17:50,060 --> 00:17:52,510
ne pas avoir deux arguments de ligne de commande.

400
00:17:52,510 --> 00:17:53,880
Je ne ai pas mis dans ce chèque.

401
00:17:53,880 --> 00:17:57,380
Et si je cours je me mis Debug--
mon point d'arrêt pour y droite.

402
00:17:57,380 --> 00:17:58,055
Je cours de débogage.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> D'ACCORD.

405
00:18:16,550 --> 00:18:17,050
Ouais.

406
00:18:17,050 --> 00:18:20,350
Donc en fait, GDB était censé
pour moi ont dit qu'il y

407
00:18:20,350 --> 00:18:22,300
était une erreur de segmentation il.

408
00:18:22,300 --> 00:18:24,883
Je ne sais pas ce qui se passait
là, mais quand je l'ai couru,

409
00:18:24,883 --> 00:18:25,590
il travaillait.

410
00:18:25,590 --> 00:18:29,410
Lorsque vous exécutez lignes de code et à travers
GDB pourrait juste soudainement cesser de fumer sur vous,

411
00:18:29,410 --> 00:18:31,540
monter et regarder ce que l'erreur est rouge.

412
00:18:31,540 --> 00:18:33,930
Il vous dira, hey, vous
eu une erreur de segmentation,

413
00:18:33,930 --> 00:18:38,550
ce qui signifie que vous avez essayé de l'accès
espace dans un tableau qui n'a pas existé.

414
00:18:38,550 --> 00:18:39,050
Ouais.

415
00:18:39,050 --> 00:18:43,280
>> Ainsi, dans le prochain problème
prévues cette semaine, les gars

416
00:18:43,280 --> 00:18:45,600
va probablement avoir beaucoup de
les variables flottant autour.

417
00:18:45,600 --> 00:18:48,560
Tu ne vas pas être sûr de ce que
ils signifient tous à un certain point.

418
00:18:48,560 --> 00:18:53,560
Donc GDB va vraiment vous aider à déterminer
ce qu'ils sont tous égalant

419
00:18:53,560 --> 00:18:55,940
et être en mesure de voir que visuellement.

420
00:18:55,940 --> 00:19:01,995
Quelqu'un est confus sur la façon
tout cela a été de travailler?

421
00:19:01,995 --> 00:19:02,495
Frais.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Bien.

424
00:19:10,620 --> 00:19:14,260
Donc, après cela, nous sommes
aller à plonger

425
00:19:14,260 --> 00:19:17,562
en sont quatre différents
types de tri pour cette semaine.

426
00:19:17,562 --> 00:19:19,520
Combien d'entre vous, d'abord
de tous, avant de commencer,

427
00:19:19,520 --> 00:19:23,020
avoir lu l'ensemble de spécifications pour pset3?

428
00:19:23,020 --> 00:19:23,824
D'ACCORD.

429
00:19:23,824 --> 00:19:24,740
Je suis fier de vous les gars.

430
00:19:24,740 --> 00:19:29,110
Voilà comme la moitié de la classe, qui
est beaucoup plus que la dernière fois.

431
00:19:29,110 --> 00:19:33,950
>> Voilà donc grande, parce que quand
nous parlons du contenu

432
00:19:33,950 --> 00:19:36,170
dans lecture-- ou désolé,
dans section-- Je aime

433
00:19:36,170 --> 00:19:38,210
de rapporter beaucoup de cela
revenir à ce que le pset est

434
00:19:38,210 --> 00:19:40,210
et comment vous voulez
mettre en œuvre que dans votre pset.

435
00:19:40,210 --> 00:19:42,400
Donc, si vous venez d'avoir
lire la spec, il va

436
00:19:42,400 --> 00:19:45,510
être beaucoup plus facile pour vous de comprendre
de quoi je parle quand je dis,

437
00:19:45,510 --> 00:19:48,720
Oh hey, cela pourrait être une très
bon endroit pour mettre en œuvre ce genre.

438
00:19:48,720 --> 00:19:52,870
Donc ceux d'entre vous qui ont lu le
spec savoir que, dans le cadre de votre pset,

439
00:19:52,870 --> 00:19:54,900
vous allez avoir à
écrire un type de tri.

440
00:19:54,900 --> 00:19:58,670
Donc, cela peut être très utile
pour beaucoup d'entre vous aujourd'hui.

441
00:19:58,670 --> 00:20:01,760
>> Donc, nous allons commencer avec,
essentiellement, le type le plus simple,

442
00:20:01,760 --> 00:20:04,580
de tri, le tri de sélection.

443
00:20:04,580 --> 00:20:06,800
L'algorithme typique pour
comment nous allions à ce sujet

444
00:20:06,800 --> 00:20:10,460
est-- David a traversé ces tout en
conférence, donc je vais rapidement passer le long

445
00:20:10,460 --> 00:20:13,900
ici-- est essentiellement, vous
avoir un tableau de valeurs.

446
00:20:13,900 --> 00:20:17,170
Et puis, vous trouvez la
plus petite valeur non triés

447
00:20:17,170 --> 00:20:20,200
et vous changez cette valeur avec
la première valeur non triés.

448
00:20:20,200 --> 00:20:22,700
Et puis vous continuez à répéter
avec le reste de votre liste.

449
00:20:22,700 --> 00:20:25,740
>> Et voici une explication visuelle
de la façon dont cela pourrait fonctionner.

450
00:20:25,740 --> 00:20:30,460
Ainsi, par exemple, si nous devions commencer
avec un tableau de cinq éléments, l'index

451
00:20:30,460 --> 00:20:35,910
0 à 4, avec 3, 5, 2, 6, 4 et valeurs
placé dans le array-- tellement en ce moment,

452
00:20:35,910 --> 00:20:38,530
nous allons juste à assumer
qu'ils sont tous non triés

453
00:20:38,530 --> 00:20:41,130
parce que nous avons pas testé autrement.

454
00:20:41,130 --> 00:20:44,130
>> Alors, comment une sorte de sélection serait
le travail est qu'il serait premier

455
00:20:44,130 --> 00:20:46,800
courir à travers la totalité
de la matrice non triés.

456
00:20:46,800 --> 00:20:49,120
Il serait choisir la plus petite valeur.

457
00:20:49,120 --> 00:20:51,750
Dans ce cas, 3, droit
maintenant, est la plus petite.

458
00:20:51,750 --> 00:20:52,680
Il obtient à 5.

459
00:20:52,680 --> 00:20:55,620
Nope, 5 ne soit pas supérieure than--
ou désolé, est pas inférieure: 3.

460
00:20:55,620 --> 00:20:57,779
Ainsi, la valeur minimale est toujours 3.

461
00:20:57,779 --> 00:20:58,695
Et puis vous arrivez à 2.

462
00:20:58,695 --> 00:21:00,990
L'ordinateur voit, oh, 2 est inférieure à 3.

463
00:21:00,990 --> 00:21:02,750
2 doit désormais être la valeur minimale.

464
00:21:02,750 --> 00:21:06,630
Et ainsi de 2 swaps avec cette première valeur.

465
00:21:06,630 --> 00:21:10,702
>> Donc, après un passage, nous ne voyons en effet
que le 2 et le 3 sont inversés.

466
00:21:10,702 --> 00:21:13,910
Et nous allons tout simplement continuer à faire
cette fois avec le reste de la matrice.

467
00:21:13,910 --> 00:21:17,660
Nous allons donc à courir seulement à travers
les quatre derniers index de la matrice.

468
00:21:17,660 --> 00:21:20,670
Nous verrons que 3 est
la valeur minimale suivante.

469
00:21:20,670 --> 00:21:23,240
Donc, nous allons échanger qu'avec 4.

470
00:21:23,240 --> 00:21:26,900
Et puis nous allons juste garder
qui traverse jusqu'à ce que, finalement, vous

471
00:21:26,900 --> 00:21:33,730
arriver à un tableau trié dans laquelle
2, 3, 4, 5, et 6 sont tous classés.

472
00:21:33,730 --> 00:21:37,530
Tout le monde comprend la logique
de la façon dont une sorte de sélection fonctionne?

473
00:21:37,530 --> 00:21:39,669
>> Vous avez juste une sorte
d'une valeur minimale.

474
00:21:39,669 --> 00:21:41,210
Vous gardez une trace de ce qui est.

475
00:21:41,210 --> 00:21:45,170
Et chaque fois que vous le trouvez, vous échangez
avec la première valeur de la array--

476
00:21:45,170 --> 00:21:48,740
ou, pas la première value--
la valeur suivante dans le tableau.

477
00:21:48,740 --> 00:21:50,150
Frais.

478
00:21:50,150 --> 00:21:55,460
>> Donc, comme vous les gars genre de
vu d'un bref aperçu,

479
00:21:55,460 --> 00:21:58,450
nous allons Pseudocode cela.

480
00:21:58,450 --> 00:22:02,510
Donc, si vous les gars dans le dos voulez
former un groupe, tout le monde à une table

481
00:22:02,510 --> 00:22:06,170
peut former un petit partenaire, je vais
pour vous donner des gars comme trois minutes

482
00:22:06,170 --> 00:22:08,190
de parler seulement à travers
la logique, en anglais,

483
00:22:08,190 --> 00:22:14,161
de la façon dont nous pourrions être en mesure de mettre en œuvre
pseudo pour écrire une sorte de sélection.

484
00:22:14,161 --> 00:22:14,910
Et il ya des bonbons.

485
00:22:14,910 --> 00:22:16,118
S'il vous plaît venir et obtenir des bonbons.

486
00:22:16,118 --> 00:22:19,520
Si vous êtes dans le dos et que vous voulez
Candy, je peut jeter des bonbons à vous.

487
00:22:19,520 --> 00:22:22,850
En fait, le faire refroidir vous--.

488
00:22:22,850 --> 00:22:23,552
Oh pardon.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
D'ACCORD.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Donc, si nous aimerions, en tant
une classe, écriture pseudo-

493
00:25:27,140 --> 00:25:30,466
pour savoir comment on pourrait approcher
ce problème, se sentent juste libre.

494
00:25:30,466 --> 00:25:32,340
Je vais faire un tour et,
dans l'ordre, demander aux groupes

495
00:25:32,340 --> 00:25:35,065
pour la ligne suivante de
ce que nous devrions faire.

496
00:25:35,065 --> 00:25:37,840
Donc, si vous voulez les gars pour commencer
off, quelle est la première chose

497
00:25:37,840 --> 00:25:40,600
à faire lorsque vous essayez de
mettre en œuvre un moyen de résoudre ce programme

498
00:25:40,600 --> 00:25:43,480
pour trier sélectivement une liste?

499
00:25:43,480 --> 00:25:46,349
Disons simplement supposer que nous
avoir un tableau, d'accord?

500
00:25:46,349 --> 00:25:49,088
>> AUDIENCE: Vous voulez créer une certaine
sorte de [inaudible] que vous êtes

501
00:25:49,088 --> 00:25:50,420
qui traverse l'ensemble de votre réseau.

502
00:25:50,420 --> 00:25:51,128
>> ANDI PENG: Droit.

503
00:25:51,128 --> 00:25:54,100
Donc, vous allez vouloir pour itérer
dans chacun des espaces, non?

504
00:25:54,100 --> 00:26:05,490
Tellement bon.

505
00:26:05,490 --> 00:26:08,600
Si vous voulez les gars de me donner le
line-- prochaine ouais, dans le dos.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> AUDIENCE: Vérifiez-les
tout pour la plus petite.

508
00:26:13,290 --> 00:26:14,248
>> PENG ANDI: Il nous allons.

509
00:26:14,248 --> 00:26:17,438
Donc, nous voulons passer et vérifiez
voir ce que la valeur minimale est, non?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Je vais abréger que pour "min."

512
00:26:24,840 --> 00:26:27,658
Qu'est-ce que vous voulez les gars à faire après
vous avez trouvé la valeur minimum?

513
00:26:27,658 --> 00:26:28,533
>> AUDIENCE: [inaudible]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Donc, vous allez vouloir
changer avec le premier de ce tableau,

516
00:26:33,150 --> 00:26:33,650
droit?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Voilà le début, je vais dire.

519
00:26:46,850 --> 00:26:47,220
Bien.

520
00:26:47,220 --> 00:26:50,386
Alors, maintenant que vous avez troqué la première
l'un, que voulez-vous faire après?

521
00:26:50,386 --> 00:26:54,840
Alors maintenant, nous savons que celui-là
doit être la plus petite valeur, non?

522
00:26:54,840 --> 00:26:58,310
Ensuite, vous avez un repos supplémentaire
de la matrice qui est non triés.

523
00:26:58,310 --> 00:27:01,569
Donc ce que vous voulez faire ici, si vous
gars veulent me donner la ligne suivante?

524
00:27:01,569 --> 00:27:04,610
AUDIENCE: Alors vous voulez parcourir
pendant le reste de la matrice.

525
00:27:04,610 --> 00:27:05,276
ANDI PENG: Ouais.

526
00:27:05,276 --> 00:27:09,857
Et ce qui ne itérer
sorte de impliquons nous aurons probablement besoin?

527
00:27:09,857 --> 00:27:10,440
Quel genre de--

528
00:27:10,440 --> 00:27:12,057
>> AUDIENCE: Oh, une variable supplémentaire?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Probablement
une autre boucle, non?

530
00:27:13,890 --> 00:27:28,914
Donc, nous allons probablement vouloir
pour itérer through-- grande.

531
00:27:28,914 --> 00:27:31,830
Et puis vous allez revenir en arrière et
vérifier probablement le minimum à nouveau,

532
00:27:31,830 --> 00:27:32,100
droit?

533
00:27:32,100 --> 00:27:34,975
Et vous allez continuer à répéter
ce, parce que les boucles juste aller

534
00:27:34,975 --> 00:27:36,010
pour continuer à fonctionner, non?

535
00:27:36,010 --> 00:27:39,190
>> Donc, comme vous les gars pouvez le voir, nous avons
juste avoir un pseudo générale

536
00:27:39,190 --> 00:27:41,480
de la façon dont nous voulons que ce programme à regarder.

537
00:27:41,480 --> 00:27:46,646
Cette itération ici, ce que nous faisons
généralement besoin d'écrire dans notre code

538
00:27:46,646 --> 00:27:49,270
si nous voulons pour parcourir une
tableau, ce type de structure?

539
00:27:49,270 --> 00:27:51,030
Je pense que Christabel
déjà dit cela avant.

540
00:27:51,030 --> 00:27:51,500
>> PUBLIC: Une boucle for.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: Une boucle for?

542
00:27:52,160 --> 00:27:52,770
Exactement.

543
00:27:52,770 --> 00:27:56,060
Donc, ce qui est probablement
va être une boucle for.

544
00:27:56,060 --> 00:27:59,240
Qu'est-ce qu'un chèque ici va impliquer?

545
00:27:59,240 --> 00:28:02,536
Typiquement, si vous souhaitez vérifier
si quelque chose est quelque chose else--

546
00:28:02,536 --> 00:28:03,270
>> Audience: Si.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: Un si, à droite?

548
00:28:06,790 --> 00:28:10,790
Et puis le swap Ici, nous allons
aller plus tard, parce que David

549
00:28:10,790 --> 00:28:12,770
a traversé qu'en conférence ainsi.

550
00:28:12,770 --> 00:28:14,580
Et puis la deuxième itération implies--

551
00:28:14,580 --> 00:28:15,120
>> PUBLIC: Une autre boucle.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another boucle for, exactement.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Donc, si nous sommes à la recherche
à cela correctement, nous

555
00:28:22,000 --> 00:28:24,680
peut voir que nous sommes probablement
allez avoir besoin d'un imbriquée boucle

556
00:28:24,680 --> 00:28:28,330
avec une instruction conditionnelle là
puis une pièce réelle de code qui est

557
00:28:28,330 --> 00:28:31,360
aller à échanger les valeurs.

558
00:28:31,360 --> 00:28:35,980
Donc, je viens généralement écrits
un code de pseudo ici.

559
00:28:35,980 --> 00:28:38,910
Et puis nous allons en fait
physiquement, en tant que classe,

560
00:28:38,910 --> 00:28:40,700
essayer de mettre en œuvre aujourd'hui.

561
00:28:40,700 --> 00:28:42,486
Revenons dans cet IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Uh-oh.

564
00:28:50,230 --> 00:28:51,754
Pourquoi est-ce que pas-- il est là.

565
00:28:51,754 --> 00:28:52,253
D'ACCORD.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Désolé, je vais essayer de zoomer un peu plus.

568
00:28:57,500 --> 00:28:59,310
Nous y voilà.

569
00:28:59,310 --> 00:29:05,060
Tout ce que je fais ici est que je avez créé
un programme appelé «sélection / sort.c."

570
00:29:05,060 --> 00:29:10,860
Je ai créé un tableau de neuf
valeurs, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Actuellement, que vous le pouvez
voient, ils ne sont pas ordonnés.

572
00:29:14,370 --> 00:29:17,880
n va être le numéro
vous indique la quantité de valeurs

573
00:29:17,880 --> 00:29:18,920
vous avez dans votre tableau.

574
00:29:18,920 --> 00:29:20,670
Dans ce cas, nous avons neuf valeurs.

575
00:29:20,670 --> 00:29:23,760
Et je viens de recevoir une boucle ici
qui imprime le tableau non trié.

576
00:29:23,760 --> 00:29:28,370
>> Et à la fin, je dois aussi pour un
boucle qui imprime simplement à nouveau.

577
00:29:28,370 --> 00:29:32,070
Donc, théoriquement, si ce programme
fonctionne correctement, à la fin,

578
00:29:32,070 --> 00:29:35,670
vous devriez voir un imprimé pour la boucle
dans lequel 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 sont tous correctement dans l'ordre.

580
00:29:39,310 --> 00:29:43,410
>> Donc, nous avons notre pseudo ici.

581
00:29:43,410 --> 00:29:46,090
Quelqu'un veut to-- Je suis juste
va aller demander volunteers--

582
00:29:46,090 --> 00:29:49,540
me dire exactement ce à taper si
nous voulons, d'abord, simplement itérer

583
00:29:49,540 --> 00:29:52,840
à travers le début de ce tableau?

584
00:29:52,840 --> 00:29:55,204
Quelle est la ligne de code Je suis
probablement avoir besoin ici?

585
00:29:55,204 --> 00:29:56,990
>> AUDIENCE: [inaudible]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Ouais, sentir
to-- désolé gratuitement, vous

587
00:29:59,010 --> 00:30:02,318
ne pas avoir à tenir up-- sensation
sans élever la voix un peu.

588
00:30:02,318 --> 00:30:08,190
>> Public: Pour int i vaut 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Ouais, bon.

590
00:30:10,690 --> 00:30:15,220
>> AUDIENCE: i est inférieur à la longueur du tableau.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Donc, gardez à
l'esprit ici, parce que nous

592
00:30:19,630 --> 00:30:23,060
ne pas avoir une fonction que
nous dit la longueur d'un tableau,

593
00:30:23,060 --> 00:30:25,790
nous avons déjà un
valeur qui stocke cela.

594
00:30:25,790 --> 00:30:27,920
Droit?

595
00:30:27,920 --> 00:30:31,010
Une autre chose à garder
dans mind-- dans un tableau

596
00:30:31,010 --> 00:30:33,940
des neuf valeurs, ce sont les indices?

597
00:30:33,940 --> 00:30:38,720
Disons simplement que ce tableau était de 0 à 3.

598
00:30:38,720 --> 00:30:41,500
Vous voyez que le dernier
l'indice est en fait 3.

599
00:30:41,500 --> 00:30:45,530
Il est pas 4, même si il ya
quatre valeurs dans le tableau.

600
00:30:45,530 --> 00:30:49,866
>> Donc, ici, nous devons être très prudents
de ce que notre condition pour la longueur

601
00:30:49,866 --> 00:30:50,490
CA va etre.

602
00:30:50,490 --> 00:30:51,948
>> Public: Ce ne serait pas n moins 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: Ça va
n moins 1, exactement.

604
00:30:54,440 --> 00:30:57,379
Est-ce logique, pourquoi
il est n moins 1, tout le monde?

605
00:30:57,379 --> 00:30:58,920
Il est parce que les tableaux sont indexés zéro.

606
00:30:58,920 --> 00:31:02,010
Ils commencent à 0 et vont jusqu'à n moins 1.

607
00:31:02,010 --> 00:31:03,210
Ouais, il est un peu délicat.

608
00:31:03,210 --> 00:31:03,730
D'ACCORD.

609
00:31:03,730 --> 00:31:05,929
Et alors--

610
00:31:05,929 --> 00:31:08,054
AUDIENCE: Isnt'1 que
déjà pris soin de bien,

611
00:31:08,054 --> 00:31:11,400
par tout simplement pas dire "inférieur ou
égal à "et juste en disant" moins? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: Voilà une
très bonne question.

613
00:31:13,108 --> 00:31:13,630
Donc oui.

614
00:31:13,630 --> 00:31:17,410
Mais aussi, la façon dont nous sommes
la mise en œuvre le droit de vérifier,

615
00:31:17,410 --> 00:31:19,120
vous devez comparer deux valeurs.

616
00:31:19,120 --> 00:31:21,009
Donc, vous voulez réellement
quitter le »à« vide.

617
00:31:21,009 --> 00:31:23,050
Parce que si vous comparez
celui-ci, tu ne vas pas

618
00:31:23,050 --> 00:31:25,530
rien avoir après
à comparer, à droite?

619
00:31:25,530 --> 00:31:27,460
Ouais.

620
00:31:27,460 --> 00:31:29,297
Donc i ++.

621
00:31:29,297 --> 00:31:30,380
Ajoutons nos crochets dans.

622
00:31:30,380 --> 00:31:30,880
Oups.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Génial.

625
00:31:34,710 --> 00:31:39,117
Donc, nous avons le début
de notre boucle externe.

626
00:31:39,117 --> 00:31:41,450
Alors maintenant, nous voulons probablement
créer une variable pour garder

627
00:31:41,450 --> 00:31:43,085
la trace de la plus petite valeur, non?

628
00:31:43,085 --> 00:31:45,751
Quelqu'un veut-il me donner le
ligne de code qui ferait cela?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Que devons-nous si nous allons
à vouloir stocker quelque chose?

631
00:31:53,570 --> 00:31:55,047
>> Droit.

632
00:31:55,047 --> 00:31:57,630
Peut-être un meilleur nom pour que
serait être-- "temp" totalement works--

633
00:31:57,630 --> 00:32:00,655
peut-être un plus bien nommé serait,
si nous voulons le plus petit value--

634
00:32:00,655 --> 00:32:01,624
>> AUDIENCE: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, là nous allons.

636
00:32:02,790 --> 00:32:05,230
min serait bon.

637
00:32:05,230 --> 00:32:08,340
Et là, qu'est-ce que nous
vouloir initialiser à?

638
00:32:08,340 --> 00:32:09,620
Ceci est un peu délicat.

639
00:32:09,620 --> 00:32:13,580
Parce que maintenant à la
à compter de ce tableau,

640
00:32:13,580 --> 00:32:15,730
vous avez rien regardé, non?

641
00:32:15,730 --> 00:32:19,200
Alors quoi, automatiquement, si
nous sommes juste sur i est égal à 0,

642
00:32:19,200 --> 00:32:22,302
Que voulons-nous pour initialiser
notre première valeur minimale à?

643
00:32:22,302 --> 00:32:22,802
AUDIENCE: i.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: i, exactement.

645
00:32:24,790 --> 00:32:27,040
Christabel, pourquoi voulons-nous
pour l'initialiser à i?

646
00:32:27,040 --> 00:32:28,510
>> AUDIENCE: Parce que, eh bien,
nous commençons à 0.

647
00:32:28,510 --> 00:32:31,660
Donc, parce que nous avons rien à comparer
à, au minimum finira par être 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Exactement.

649
00:32:32,451 --> 00:32:34,400
Alors, elle est tout à fait exact.

650
00:32:34,400 --> 00:32:36,780
Parce que nous avons pas réellement
regardé encore rien,

651
00:32:36,780 --> 00:32:38,680
nous ne savons pas ce que notre valeur minimale est.

652
00:32:38,680 --> 00:32:41,960
Nous voulons simplement l'initialiser à
i, qui, actuellement, se trouve ici.

653
00:32:41,960 --> 00:32:44,750
Et comme nous continuons à
déplacer vers le bas de ce tableau,

654
00:32:44,750 --> 00:32:48,122
nous verrons que, à chaque
passe supplémentaire, i incréments.

655
00:32:48,122 --> 00:32:49,830
Et à ce moment,
i va probablement

656
00:32:49,830 --> 00:32:52,329
à vouloir être le minimum,
parce que ça va être tout ce que

657
00:32:52,329 --> 00:32:54,520
est le début de la matrice non triés.

658
00:32:54,520 --> 00:32:55,270
Frais.

659
00:32:55,270 --> 00:32:58,720
>> Alors maintenant, nous voulons ajouter
une boucle qui est ici

660
00:32:58,720 --> 00:33:03,225
va parcourir la
non triés, ou dans le reste de ce tableau.

661
00:33:03,225 --> 00:33:05,808
Quelqu'un veut-il me donner un
ligne de code qui ferait cela?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- Que devons-nous ici?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Qu'est-ce qui va se passer dans cette boucle?

666
00:33:18,820 --> 00:33:19,465
Ouais.

667
00:33:19,465 --> 00:33:21,590
PUBLIC: Nous aimerions donc voulons
avoir un nombre entier différent,

668
00:33:21,590 --> 00:33:25,080
parce que nous sommes en cours d'exécution à travers le reste
du tableau au lieu de la i, alors peut-être

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Ouais, j sonne bien pour moi.

671
00:33:27,301 --> 00:33:27,850
Égal?

672
00:33:27,850 --> 00:33:33,930
>> Auditoire: Alors, serait i + 1, parce
vous commencez à la valeur suivante.

673
00:33:33,930 --> 00:33:40,395
Ensuite, à la end-- à nouveau, j est
moins de n moins 1, et ensuite j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI PENG: Grande.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> Et puis ici, nous allons vouloir
de vérifier pour voir si notre condition est remplie,

677
00:33:52,750 --> 00:33:53,250
droit?

678
00:33:53,250 --> 00:33:55,740
Parce que vous voulez
changer la valeur minimale

679
00:33:55,740 --> 00:33:58,700
si elle est effectivement plus petit que ce que
vous êtes en le comparant, non?

680
00:33:58,700 --> 00:34:01,146
Alors qu'est-ce qu'on va vouloir ici?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Vérifiez.

683
00:34:04,897 --> 00:34:06,730
Quel type de déclaration
sans doute allons-nous

684
00:34:06,730 --> 00:34:08,389
ti veulent utiliser si nous
vouloir vérifier quelque chose?

685
00:34:08,389 --> 00:34:09,360
>> PUBLIC: Une instruction if.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: Une instruction if.

687
00:34:10,485 --> 00:34:13,155
Donc si-- et ce qui va être
la condition que nous voulons l'intérieur

688
00:34:13,155 --> 00:34:13,988
de notre if?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> Audience: Si la valeur de j
est inférieure à la valeur de i--

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Exactement.

692
00:34:24,600 --> 00:34:27,480
Donc si-- donc ce tableau est appelé «tableau».

693
00:34:27,480 --> 00:34:27,980
Génial.

694
00:34:27,980 --> 00:34:30,465
Donc, si ce array-- était-ce?

695
00:34:30,465 --> 00:34:31,090
Répète ça.

696
00:34:31,090 --> 00:34:39,590
>> Audience: Si array-j est inférieure à
array-i, alors nous changerais min.

697
00:34:39,590 --> 00:34:41,590
Ainsi, le min serait j.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Est-ce logique?

700
00:34:47,249 --> 00:34:48,670
D'ACCORD.

701
00:34:48,670 --> 00:34:52,929
Et maintenant, ici-bas, nous avons fait
vouloir mettre en œuvre l'échange, non?

702
00:34:52,929 --> 00:34:58,285
Donc, rappeler, en conférence, que David, quand
il essayait de the-- ce qui était échanger

703
00:34:58,285 --> 00:34:59,996
jus d'orange et milk-- it--

704
00:34:59,996 --> 00:35:01,150
>> Public: Ce fut brut.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Ouais, ça était une sorte de brute.

706
00:35:02,816 --> 00:35:05,310
Mais ce fut une assez bonne
notion de temps démontrer.

707
00:35:05,310 --> 00:35:08,430
Alors, pensez à vos valeurs ici.

708
00:35:08,430 --> 00:35:10,794
Vous avez un tableau
de min, un tableau de i,

709
00:35:10,794 --> 00:35:12,460
ou ce que nous avons essayé de permuter ici.

710
00:35:12,460 --> 00:35:15,310
Et vous avez probablement ne pouvez pas les verser dans
l'autre dans le même temps, non?

711
00:35:15,310 --> 00:35:17,180
Alors qu'allons-nous
au besoin de créer ici

712
00:35:17,180 --> 00:35:19,126
afin d'échanger les valeurs correctement?

713
00:35:19,126 --> 00:35:19,820
>> PUBLIC: Une variable temporaire.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: Une variable temporaire.

715
00:35:21,370 --> 00:35:22,570
Alors, faisons int température.

716
00:35:22,570 --> 00:35:25,681
Voir, ce serait une meilleure
temps to-- whoa, ce qui était-ce?

717
00:35:25,681 --> 00:35:26,180
D'ACCORD.

718
00:35:26,180 --> 00:35:29,800
Donc, cela aurait été une meilleure
le temps de nommer le "temp." variable

719
00:35:29,800 --> 00:35:30,730
Alors, faisons int température.

720
00:35:30,730 --> 00:35:32,563
Qu'allons-nous à
la température de consigne égale à ici?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
AUDIENCE: Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
PENG ANDI: Il est un peu délicat.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
Il ne fait pas d'importance à la fin.

727
00:35:44,880 --> 00:35:47,690
Il n'a pas d'importance ce que
Pour vous choisissez d'échanger en

728
00:35:47,690 --> 00:35:50,862
aussi longtemps que vous vous assurez que vous êtes
garder une trace de ce que vous échanger.

729
00:35:50,862 --> 00:35:52,250
>> PUBLIC: Il pourrait être array-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Ouais, faisons ensemble-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
Et puis, ce qui est la ligne suivante
de code que nous voulons avoir ici?

733
00:35:59,305 --> 00:36:00,680
AUDIENCE: array-i est égal tableau-j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: Et enfin?

736
00:36:08,070 --> 00:36:12,070
AUDIENCE: array-j est égal tableau-i.

737
00:36:12,070 --> 00:36:14,525
Audience: ou un tableau-j égaux
array-temp-- ou, temp.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Donc, nous allons courir et de voir ce
si elle va travailler.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Où en est-il?

743
00:36:39,335 --> 00:36:40,210
Oh, cela pose un problème.

744
00:36:40,210 --> 00:36:44,320
Voir, sur la ligne 40, nous sommes
essayer d'utiliser array-j?

745
00:36:44,320 --> 00:36:47,022
Mais d'où vient j exister que dans?

746
00:36:47,022 --> 00:36:48,402
>> AUDIENCE: Dans la boucle.

747
00:36:48,402 --> 00:36:49,110
ANDI PENG: Droit.

748
00:36:49,110 --> 00:36:51,730
Alors qu'est-ce qu'on va avoir besoin de faire?

749
00:36:51,730 --> 00:36:53,170
>> AUDIENCE: Définir l'extérieur the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
AUDIENCE: Ouais, je suppose que vous avez
à utiliser une autre instruction if, non?

752
00:37:00,610 --> 00:37:05,230
Donc, comme, si le minimum--
tout droit, laissez-moi réfléchir.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Les gars, essayez
de prendre un coup d'oeil de Let

755
00:37:09,990 --> 00:37:11,270
Voir, ce qui est quelque chose que nous pouvons faire ici?

756
00:37:11,270 --> 00:37:11,811
>> AUDIENCE: OK.

757
00:37:11,811 --> 00:37:15,900
Donc, si le minimum ne correspond pas à
j-- si la peine minimale est encore i--

758
00:37:15,900 --> 00:37:17,570
alors nous aurions pas à échanger.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Est-ce que l'égalité de i?

761
00:37:24,712 --> 00:37:25,920
Que voulez-vous dire ici?

762
00:37:25,920 --> 00:37:30,494
>> AUDIENCE: Ou oui, si le
minimum ne correspond pas à i, ouais.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI PENG: OK.

765
00:37:40,210 --> 00:37:42,040
Eh bien cela résout, en quelque sorte, nos problèmes.

766
00:37:42,040 --> 00:37:47,265
Mais cela ne résout toujours pas le
problème de ce qui se passe si j-- depuis j

767
00:37:47,265 --> 00:37:49,890
ne pas exister en dehors d'elle, ce qui
pensez-vous que nous voulons faire avec elle?

768
00:37:49,890 --> 00:37:50,698
Déclarer à l'extérieur?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Essayons d'exécuter ce.

771
00:38:02,730 --> 00:38:04,435
Uh-oh.

772
00:38:04,435 --> 00:38:06,200
Notre tri ne fonctionne pas.

773
00:38:06,200 --> 00:38:10,060
>> Comme vous pouvez le constater, notre première
tableau avait ces valeurs.

774
00:38:10,060 --> 00:38:14,800
Et après, il devrait avoir
été dans une, deux, trois, quatre, cinq, six, sept, huit, neuf.

775
00:38:14,800 --> 00:38:15,530
Ça ne fonctionne pas.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
Qu'est-ce qu'on fait?

778
00:38:17,184 --> 00:38:17,850
AUDIENCE: Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: Très bien, nous pouvons essayer.

781
00:38:23,370 --> 00:38:25,030
Nous pouvons déboguer.

782
00:38:25,030 --> 00:38:26,042
Rétrécir un peu.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Fixons notre point d'arrêt.

785
00:38:33,656 --> 00:38:37,280
Allons OK like--.

786
00:38:37,280 --> 00:38:40,444
>> Donc, parce que nous savons déjà que
ces lignes 15 à 22,

787
00:38:40,444 --> 00:38:43,610
sont working-- parce que tout que je fais est
simplement itérer et printing--

788
00:38:43,610 --> 00:38:45,406
Je peux aller de l'avant et sauter cela.

789
00:38:45,406 --> 00:38:47,280
Commençons à la ligne 25.

790
00:38:47,280 --> 00:38:48,712
Oop, permettez-moi de vous débarrasser de cette.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> Auditoire: Alors, le point d'arrêt de
où commence la mise au point?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: Ou arrêts.

794
00:38:54,890 --> 00:38:55,670
AUDIENCE: Ou arrêts.

795
00:38:55,670 --> 00:38:55,930
ANDI PENG: Ouais.

796
00:38:55,930 --> 00:38:58,640
Vous pouvez définir plusieurs points d'arrêt et
il peut juste passer de l'un à l'autre.

797
00:38:58,640 --> 00:39:01,590
Mais dans ce cas, nous ne savons pas
où l'erreur se produit.

798
00:39:01,590 --> 00:39:03,780
Donc, nous voulons juste
commencer par le haut vers le bas.

799
00:39:03,780 --> 00:39:05,020
Yep.

800
00:39:05,020 --> 00:39:05,550
D'ACCORD.

801
00:39:05,550 --> 00:39:08,460
>> Donc, cette ligne ici, on peut intervenir.

802
00:39:08,460 --> 00:39:11,499
Vous pouvez voir ici-bas,
nous avons un tableau.

803
00:39:11,499 --> 00:39:13,290
Ce sont les valeurs
qui se trouvent dans le tableau.

804
00:39:13,290 --> 00:39:16,360
Voyez-vous, comment l'index 0, il
correspond à la value-- oh,

805
00:39:16,360 --> 00:39:17,526
Je vais essayer d'agrandir.

806
00:39:17,526 --> 00:39:20,650
Désolé, il est vraiment difficile
à see-- indice de tableau 0,

807
00:39:20,650 --> 00:39:24,090
nous avons une valeur de 4 et
puis ainsi de suite et ainsi de suite.

808
00:39:24,090 --> 00:39:25,670
Nous avons nos variables locales.

809
00:39:25,670 --> 00:39:28,570
En ce moment, i est égal à
0, que nous voulons qu'il soit.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> Et gardons pas à pas à travers.

812
00:39:33,690 --> 00:39:36,850
Notre minimum est égal à 0,
que nous voulons également qu'il soit.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
Et puis nous entrons dans notre deuxième pour
boucle, si le tableau est-j moins de tableau-i,

815
00:39:45,560 --> 00:39:46,380
qui il n'a pas été.

816
00:39:46,380 --> 00:39:48,130
Donc, vous avez vu comment
que sauté sur cela?

817
00:39:48,130 --> 00:39:52,430
>> Auditoire: Alors, si le cas
minimum, tout that-- qui ne devrait pas

818
00:39:52,430 --> 00:39:55,424
être à l'intérieur de la première boucle?

819
00:39:55,424 --> 00:39:57,340
PENG ANDI: Non, parce que
vous voulez continuer à tester.

820
00:39:57,340 --> 00:40:00,329
Vous voulez faire une comparaison tous les
temps, même après que vous exécutez à travers elle.

821
00:40:00,329 --> 00:40:02,620
Vous ne voulez pas juste de le faire
sur la première transmission.

822
00:40:02,620 --> 00:40:05,240
Vous voulez faire avec
chaque passage supplémentaire à nouveau.

823
00:40:05,240 --> 00:40:07,198
Donc, vous voulez vérifier
votre état intérieur.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Donc, nous allons juste
continuer à courir par ici.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Je vais vous donner un indice gars.

828
00:40:18,420 --> 00:40:23,910
Il est à voir avec le fait que, lorsque
vous vérifiez votre conditionnelle,

829
00:40:23,910 --> 00:40:26,600
vous n'êtes pas le contrôle
pour l'indice correct.

830
00:40:26,600 --> 00:40:32,510
Donc maintenant vous vérifiez pour
indice de tableau du j est inférieure à tableau

831
00:40:32,510 --> 00:40:33,970
Indice de i.

832
00:40:33,970 --> 00:40:36,580
Mais que faites-vous en place au
le début de la boucle?

833
00:40:36,580 --> 00:40:38,260
Ne définissez pas vous j égal à i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Ouais, afin que nous puissions
quitter le débogueur ici.

836
00:40:45,415 --> 00:40:47,040
Donc, nous allons jeter un oeil à notre pseudo.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
Pour-- nous allons
commencer à i est égal à 0.

839
00:40:52,580 --> 00:40:54,760
Nous allons aller jusqu'à n moins 1.

840
00:40:54,760 --> 00:40:58,040
Voyons, ne nous avons ce droit?

841
00:40:58,040 --> 00:40:59,580
Yep, qui était juste.

842
00:40:59,580 --> 00:41:02,080
>> Alors l'intérieur ici, nous sommes
va créer une valeur minimale

843
00:41:02,080 --> 00:41:03,630
et définir ce que égale à i.

844
00:41:03,630 --> 00:41:04,950
Avons-nous fait cela?

845
00:41:04,950 --> 00:41:06,270
Yep, l'a fait.

846
00:41:06,270 --> 00:41:10,430
Maintenant, dans notre intérieur pour la boucle, nous sommes
va faire j est égal à i à n moins 1.

847
00:41:10,430 --> 00:41:11,950
Avons-nous fait cela?

848
00:41:11,950 --> 00:41:15,540
En effet, nous l'avons fait.

849
00:41:15,540 --> 00:41:19,922
>> Donc, cependant, ce que nous comparons ici?

850
00:41:19,922 --> 00:41:20,925
>> AUDIENCE: j + 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Exactement.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Et puis vous allez vouloir définir
votre minimum égal à j + 1 ainsi.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Alors je suis allé à travers ce très rapidement.

856
00:41:32,640 --> 00:41:36,190
Comprenez-vous les gars
pourquoi il est j + 1?

857
00:41:36,190 --> 00:41:36,890
D'ACCORD.

858
00:41:36,890 --> 00:41:40,700
>> Donc, dans votre tableau, en
votre premier passage,

859
00:41:40,700 --> 00:41:44,850
votre boucle, pour int
i est égal à 0, disons simplement

860
00:41:44,850 --> 00:41:46,740
supposer cela n'a pas encore été modifié.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Nous avons une gamme de, complètement,
seulement quatre éléments non triés, non?

863
00:41:56,760 --> 00:42:00,760
Donc, nous voulons initialiser i égal à 0.

864
00:42:00,760 --> 00:42:03,650
Et je vais tout est
courir à travers cette boucle.

865
00:42:03,650 --> 00:42:08,560
Et si dans le premier passage, nous allons
à initialiser une variable appelée "min"

866
00:42:08,560 --> 00:42:11,245
Cela équivaut aussi je, parce
nous ne disposons pas d'une valeur minimale.

867
00:42:11,245 --> 00:42:12,870
Alors qui est actuellement égal à 0 ainsi.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Et puis nous allons passer.

870
00:42:17,640 --> 00:42:19,270
Et nous voulons réitérer à nouveau.

871
00:42:19,270 --> 00:42:22,900
Maintenant que nous avons trouvé ce que notre minimum
est, nous voulons pour parcourir

872
00:42:22,900 --> 00:42:25,190
à nouveau pour voir si elle est de comparer, non?

873
00:42:25,190 --> 00:42:40,440
Donc j, ici, va
à l'égalité de i, qui est 0.

874
00:42:40,440 --> 00:42:46,320
Et puis si le tableau J Plus i, qui
est celui qui est à côté, comme moins

875
00:42:46,320 --> 00:42:49,270
que ce que votre minimum actuel
valeur est, vous voulez échanger.

876
00:42:49,270 --> 00:42:56,850
>> Alors disons simplement que nous avons
obtenu, comme, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
À l'heure actuelle, i est égal à
0 et j est égal à 0.

878
00:43:01,610 --> 00:43:05,210
Et voilà notre valeur minimale.

879
00:43:05,210 --> 00:43:09,950
Si array-J Plus i-- si une
qui est après celui que nous étudions

880
00:43:09,950 --> 00:43:13,450
est supérieure à celle qui la précède,
il va devenir le minimum.

881
00:43:13,450 --> 00:43:18,120
>> Donc, ici, nous voyons que 5
est pas moins que cela.

882
00:43:18,120 --> 00:43:19,730
Donc, ça va pas 5.

883
00:43:19,730 --> 00:43:23,580
Nous voyons que 1 est inférieur à 2, à droite?

884
00:43:23,580 --> 00:43:32,970
Alors maintenant, nous savons que notre minimum est
va être la valeur de l'indice à 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Ouais?

886
00:43:34,030 --> 00:43:39,170
Et puis quand vous arrivez ici,
vous pouvez échanger les valeurs correctes.

887
00:43:39,170 --> 00:43:42,610
>> Alors, quand vous étiez juste avoir l'j
avant, vous ne cherchiez pas à une

888
00:43:42,610 --> 00:43:43,260
après cela.

889
00:43:43,260 --> 00:43:44,520
Vous regardiez
la même valeur, ce qui

890
00:43:44,520 --> 00:43:46,290
est pourquoi il juste ne faisait rien.

891
00:43:46,290 --> 00:43:49,721
Est-ce que de sens pour tout le monde,
pourquoi nous avons besoin que plus 1 là-bas?

892
00:43:49,721 --> 00:43:50,220
D'ACCORD.

893
00:43:50,220 --> 00:43:53,345
Maintenant, nous allons courir juste à travers elle à faire
que le reste du code est correct.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Pourquoi en est-il?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, il est le min ici.

898
00:44:16,364 --> 00:44:17,780
Nous avons comparé la valeur erronée.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh non.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh oui, ici-bas, nous étions
échangeant les mauvaises valeurs.

903
00:44:33,482 --> 00:44:34,940
Parce que nous cherchions à i et j.

904
00:44:34,940 --> 00:44:36,440
Ce sont ceux que nous partions.

905
00:44:36,440 --> 00:44:39,160
Nous voulons effectivement d'échanger le
minimum, le minimum actuel,

906
00:44:39,160 --> 00:44:40,550
avec tout ce que l'on est à l'extérieur.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Et comme vous les gars pouvez voir en bas
ici, nous avons un tableau trié.

909
00:45:05,402 --> 00:45:07,110
Il a juste eu à voir avec
le fait que lorsque

910
00:45:07,110 --> 00:45:09,350
nous devions le
valeurs que nous comparions,

911
00:45:09,350 --> 00:45:11,226
nous ne cherchions pas à les bonnes valeurs.

912
00:45:11,226 --> 00:45:13,850
Nous étions à la recherche à la même
ici, il ne fait l'échange.

913
00:45:13,850 --> 00:45:17,135
Vous devez regarder l'un à côté
à elle et puis vous pouvez échanger.

914
00:45:17,135 --> 00:45:19,260
Voilà ce que était une sorte de
bugger notre code avant.

915
00:45:19,260 --> 00:45:22,460
Et ce que je faisais ici est tout
le débogueur aurait pu le faire pour vous

916
00:45:22,460 --> 00:45:23,810
Je l'ai fait sur le
bord, car il est plus facile

917
00:45:23,810 --> 00:45:26,320
de voir plutôt que d'essayer
de zoomer sur le débogueur.

918
00:45:26,320 --> 00:45:29,391
Est-ce que de sens pour tout le monde?

919
00:45:29,391 --> 00:45:29,890
Frais.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Bien.

922
00:45:35,410 --> 00:45:41,070
Nous pouvons passer à parler
notation asymptotique, qui

923
00:45:41,070 --> 00:45:44,580
est juste une façon élégante de dire la
runtimes de toutes ces sortes.

924
00:45:44,580 --> 00:45:47,650
Donc, je sais David, en conférence,
effleuré runtimes.

925
00:45:47,650 --> 00:45:52,124
Et il est passé par toute la formule
la façon de calculer les temps d'exécution.

926
00:45:52,124 --> 00:45:53,040
Pas de soucis à ce sujet.

927
00:45:53,040 --> 00:45:54,660
Si vous êtes vraiment curieux
sur la façon dont cela fonctionne,

928
00:45:54,660 --> 00:45:55,810
hésitez pas à me parler après l'article.

929
00:45:55,810 --> 00:45:57,560
Nous pouvons marcher à travers
les formules ensemble.

930
00:45:57,560 --> 00:46:00,689
Mais tous les gars vous avez vraiment
savoir est que n carré plus de 2

931
00:46:00,689 --> 00:46:01,980
est la même chose que n carré.

932
00:46:01,980 --> 00:46:04,710
En raison du plus grand nombre,
l'exposant, se développe le plus.

933
00:46:04,710 --> 00:46:06,590
Et donc pour nos fins,
tous nous nous soucions

934
00:46:06,590 --> 00:46:09,470
est ce nombre géant qui est en pleine croissance.

935
00:46:09,470 --> 00:46:13,340
>> Alors, quel est le meilleur des cas
l'exécution de la sélection sorte?

936
00:46:13,340 --> 00:46:15,830
Si vous allez avoir
pour parcourir une liste

937
00:46:15,830 --> 00:46:18,712
puis itérer
le reste de cette liste,

938
00:46:18,712 --> 00:46:20,420
combien de fois sont
vous allez sans doute,

939
00:46:20,420 --> 00:46:24,612
dans le pire des case-- dans le
meilleur des cas, sorry-- courir à travers?

940
00:46:24,612 --> 00:46:27,070
Peut-être que la meilleure question est
à demander, ce qui est le pire des cas

941
00:46:27,070 --> 00:46:28,153
l'exécution de la sélection sorte.

942
00:46:28,153 --> 00:46:29,366
AUDIENCE: n carré.

943
00:46:29,366 --> 00:46:30,740
PENG ANDI: Il est n carré, droite.

944
00:46:30,740 --> 00:46:36,986
Donc un moyen facile de penser à cela ressemble,
chaque fois que vous avez deux boucles for imbriquées,

945
00:46:36,986 --> 00:46:38,110
ça va être n carré.

946
00:46:38,110 --> 00:46:40,386
Parce que non seulement vous êtes
qui traverse une fois de plus,

947
00:46:40,386 --> 00:46:42,260
vous devez revenir en arrière
autour et courir à travers elle

948
00:46:42,260 --> 00:46:44,980
une fois de plus à l'intérieur pour chaque valeur.

949
00:46:44,980 --> 00:46:48,640
Donc, dans ce cas, vous n courir
n fois au carré, qui est-- désolé,

950
00:46:48,640 --> 00:46:50,505
n fois n, ce qui équivaut n carré.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Et Trier est aussi un peu
unique en ce sens

953
00:46:56,360 --> 00:46:59,774
qu'il n'a pas d'importance si ceux-ci
les valeurs sont déjà en commande.

954
00:46:59,774 --> 00:47:01,440
Il va toujours à courir à travers toute façon.

955
00:47:01,440 --> 00:47:03,872
Disons que ce fut 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Indépendamment du fait que oui ou non il est en
ordre, il aurait quand même couru à travers

957
00:47:07,080 --> 00:47:08,620
et encore vérifié la valeur minimale.

958
00:47:08,620 --> 00:47:10,100
Il aurait fait la
même nombre de contrôles

959
00:47:10,100 --> 00:47:12,780
à chaque fois, même si elle
n'a pas réellement toucher à rien.

960
00:47:12,780 --> 00:47:16,940
>> Ainsi, dans un tel cas, le meilleur et le pire
runtimes sont en fait équivalent.

961
00:47:16,940 --> 00:47:19,160
Donc l'exécution attendue
de la sélection sorte,

962
00:47:19,160 --> 00:47:23,790
que l'on désigne par le symbole
de thêta, thêta, dans ce cas,

963
00:47:23,790 --> 00:47:24,790
n serait également carré.

964
00:47:24,790 --> 00:47:26,480
Chacune de ces trois serait n carré.

965
00:47:26,480 --> 00:47:29,653
Tout le monde est clairement pourquoi
l'exécution est n carré?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Bien.

968
00:47:33,980 --> 00:47:39,120
Donc je vais juste courir vite
à travers le reste des sortes.

969
00:47:39,120 --> 00:47:41,137
L'algorithme de
bulle sort-- rappelez-vous,

970
00:47:41,137 --> 00:47:43,220
ce fut le premier
David passa en conférence.

971
00:47:43,220 --> 00:47:46,000
Essentiellement, vous faites un pas
toute la liste

972
00:47:46,000 --> 00:47:48,950
et vous vous swap-- juste
comparer les deux à la fois.

973
00:47:48,950 --> 00:47:51,350
Et si l'on est plus grande,
que vous venez de les échanger.

974
00:47:51,350 --> 00:47:53,590
Donc, si ceux-ci sont plus importants, vous souhaitez échanger.

975
00:47:53,590 --> 00:47:56,180
Je dois officielle ici.

976
00:47:56,180 --> 00:47:59,100
>> Alors disons simplement que vous aviez 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Vous souhaitez comparer le 8 et un 6.

978
00:48:00,571 --> 00:48:01,570
Vous aurez besoin de les échanger.

979
00:48:01,570 --> 00:48:02,610
Vous voulez comparer le 8 et un 4.

980
00:48:02,610 --> 00:48:03,609
Vous aurez besoin de les échanger.

981
00:48:03,609 --> 00:48:07,000
Si vous avez d'échanger le 8 et
le 2, changer eux aussi.

982
00:48:07,000 --> 00:48:10,760
Ainsi, dans un tel sens, vous pouvez voir,
joué sur une longue période de temps,

983
00:48:10,760 --> 00:48:13,730
comment les valeurs sorte de bulle à
les extrémités, ce qui est pourquoi nous appellent

984
00:48:13,730 --> 00:48:15,320
tri à bulles.

985
00:48:15,320 --> 00:48:19,950
>> Nous voudrions simplement parcourir à nouveau sur
notre deuxième passe, et notre troisième passage,

986
00:48:19,950 --> 00:48:21,150
et notre quatrième passe.

987
00:48:21,150 --> 00:48:25,820
Essentiellement, bulle pistes Tri juste
jusqu'à ce que vous ne faites pas plus de swaps.

988
00:48:25,820 --> 00:48:31,109
Donc, dans ce sens, cela est juste
le pseudo générale pour elle.

989
00:48:31,109 --> 00:48:32,650
Pas de soucis, ceux-ci seront en ligne.

990
00:48:32,650 --> 00:48:34,990
Nous ne disposons pas d'aller effectivement à ce sujet.

991
00:48:34,990 --> 00:48:38,134
>> On initialise juste un compteur
variable qui commence à 0.

992
00:48:38,134 --> 00:48:39,800
Et nous parcourons l'ensemble du réseau.

993
00:48:39,800 --> 00:48:43,420
Et si une valeur est-- si cela
valeur est supérieure à cette valeur,

994
00:48:43,420 --> 00:48:44,610
vous allez les échanger.

995
00:48:44,610 --> 00:48:46,860
Et puis vous êtes juste
va continuer.

996
00:48:46,860 --> 00:48:47,970
Et vous allez compter.

997
00:48:47,970 --> 00:48:50,845
Et vous allez juste de continuer à faire
ce tandis que le compteur est supérieur

998
00:48:50,845 --> 00:48:53,345
à 0, ce qui signifie que
chaque fois que vous avez à échanger,

999
00:48:53,345 --> 00:48:55,220
vous savez que vous voulez aller
arrière et vérifier à nouveau.

1000
00:48:55,220 --> 00:48:59,510
Vous voulez garder le contrôle jusqu'à ce que vous savez
que vous ne devez pas échanger plus.

1001
00:48:59,510 --> 00:49:05,570
>> Alors quels sont les meilleurs et les pires
cas pour les moteurs d'exécution tri à bulles?

1002
00:49:05,570 --> 00:49:09,300
Et hint-- cela est réellement différente
de la sélection sorte dans le sens

1003
00:49:09,300 --> 00:49:11,810
que ces deux réponses ne sont pas les mêmes.

1004
00:49:11,810 --> 00:49:14,709
Pensez à ce qui se passerait dans
une affaire si elle a été déjà trié.

1005
00:49:14,709 --> 00:49:16,500
Et penser à ce que
qui se passerait si elle était

1006
00:49:16,500 --> 00:49:18,372
dans le cas où il n'a pas été trié.

1007
00:49:18,372 --> 00:49:20,580
Et vous pouvez sorte de courir
travers pourquoi ce qui se passe.

1008
00:49:20,580 --> 00:49:22,954
Je vais vous donner les gars, comme, 30
secondes pour réfléchir à cela.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> D'ACCORD.

1011
00:49:53,540 --> 00:49:57,462
Quelqu'un at-il une conjecture à ce que le
pire des cas, l'exécution du tri à bulles est?

1012
00:49:57,462 --> 00:49:57,962
Ouais.

1013
00:49:57,962 --> 00:50:07,810
>> AUDIENCE: Serait-il, comme, n fois
n moins 1 ou quelque chose comme ça?

1014
00:50:07,810 --> 00:50:10,650
Comme, à chaque fois qu'il est exécuté,
il est juste, comme, un swap de moins

1015
00:50:10,650 --> 00:50:10,960
que tout ce qu'il était.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Ouais, donc
vous avez tout à fait raison.

1017
00:50:12,668 --> 00:50:15,940
Et ceci est un cas dans lequel votre
réponse était en fait plus complexe

1018
00:50:15,940 --> 00:50:17,240
que celui que nous devons donner.

1019
00:50:17,240 --> 00:50:19,772
Donc ça va run-- je suis
va effacer tout cela ici.

1020
00:50:19,772 --> 00:50:20,480
Tout le monde est bon?

1021
00:50:20,480 --> 00:50:21,869
Puis-je effacer cela?

1022
00:50:21,869 --> 00:50:22,368
D'ACCORD.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Vous allez courir à travers n
fois la première fois, non?

1025
00:50:30,320 --> 00:50:33,200
Et ils vont courir à travers
n moins 1 pour la deuxième fois, non?

1026
00:50:33,200 --> 00:50:37,130
Et puis vous allez garder
aller, la mine n 2, et cetera.

1027
00:50:37,130 --> 00:50:40,210
David a fait cela dans une conférence, où,
si vous avez ajouté toutes ces valeurs,

1028
00:50:40,210 --> 00:50:48,080
vous obtenez quelque chose qui est like-- Yeah
plus de 2, ce qui réduit essentiellement juste

1029
00:50:48,080 --> 00:50:49,784
vers le bas à n au carré.

1030
00:50:49,784 --> 00:50:51,700
Vous allez obtenir une
fraction bizarre là-dedans.

1031
00:50:51,700 --> 00:50:53,892
Et si juste savoir que
le carré n toujours

1032
00:50:53,892 --> 00:50:55,350
a préséance sur la fraction.

1033
00:50:55,350 --> 00:50:58,450
Et dans ce cas, le pire
exécution serait n au carré.

1034
00:50:58,450 --> 00:51:00,210
Si elle était en décroissant
afin, pense, vous

1035
00:51:00,210 --> 00:51:02,530
avoir à faire un échange à chaque fois unique.

1036
00:51:02,530 --> 00:51:05,170
>> Quel serait, potentiellement,
la meilleure exécution de cas?

1037
00:51:05,170 --> 00:51:08,580
Disons que, si la liste était déjà
dans l'ordre, ce qui serait le runtime être?

1038
00:51:08,580 --> 00:51:09,565
>> AUDIENCE: n.

1039
00:51:09,565 --> 00:51:10,690
PENG ANDI: Il est n, exactement.

1040
00:51:10,690 --> 00:51:11,600
Et pourquoi est-il n?

1041
00:51:11,600 --> 00:51:13,850
AUDIENCE: Parce que vous venez
devoir vérifier chaque fois.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Exactement.

1043
00:51:14,770 --> 00:51:17,150
Donc, dans le meilleur exécution possible,
si cette liste était déjà

1044
00:51:17,150 --> 00:51:20,270
sorted-- disons 1, 2, 3, 4-- vous
serait tout simplement passer, vous vérifiez,

1045
00:51:20,270 --> 00:51:21,720
vous verriez, oh, ils ont tous pan out.

1046
00:51:21,720 --> 00:51:22,636
Je ne dois échanger.

1047
00:51:22,636 --> 00:51:23,370
J'ai fini.

1048
00:51:23,370 --> 00:51:26,500
Donc, dans ce cas, il est juste n
ou le nombre d'étapes que vous venez

1049
00:51:26,500 --> 00:51:29,870
eu à vérifier dans la première liste.

1050
00:51:29,870 --> 00:51:33,990
>> Et après, nous avons maintenant atteint
tri par insertion, où

1051
00:51:33,990 --> 00:51:39,260
l'algorithme est essentiellement de fracture
dans une partie triés et non triés.

1052
00:51:39,260 --> 00:51:42,810
Et puis, un par un,
les valeurs non triés sont

1053
00:51:42,810 --> 00:51:46,880
inséré dans leur appropriée
positions dans le début de la liste.

1054
00:51:46,880 --> 00:51:52,120
>> Ainsi, par exemple, nous avons une
liste des 3, 5, 2, 6, 4 à nouveau.

1055
00:51:52,120 --> 00:51:54,750
Nous savons qu'il est actuellement
non triés parce que nous venons tout juste

1056
00:51:54,750 --> 00:51:57,030
commencé à regarder il.

1057
00:51:57,030 --> 00:52:00,610
Nous prenons un coup d'oeil et nous savons que
la première valeur est trié, non?

1058
00:52:00,610 --> 00:52:04,190
Si vous cherchez seulement à un éventail de
taille un, vous savez qu'il est triée.

1059
00:52:04,190 --> 00:52:08,230
>> Alors que nous savons que le
quatre autres sont non triés.

1060
00:52:08,230 --> 00:52:10,980
Nous allons à travers et nous voyons cette valeur.

1061
00:52:10,980 --> 00:52:11,730
Allons en arrière.

1062
00:52:11,730 --> 00:52:13,130
Voir cette valeur de 5?

1063
00:52:13,130 --> 00:52:14,110
Nous prenons un coup d'oeil.

1064
00:52:14,110 --> 00:52:15,204
Nous comparons à 3.

1065
00:52:15,204 --> 00:52:17,870
Nous savons qu'il est plus grand que
3, de sorte que nous savons que que ça triés.

1066
00:52:17,870 --> 00:52:22,940
Donc, nous savons maintenant que les deux premiers
sont triés et les trois derniers ne sont pas.

1067
00:52:22,940 --> 00:52:24,270
>> Nous prenons un oeil à 2.

1068
00:52:24,270 --> 00:52:25,720
Nous vérifions d'abord avec 5.

1069
00:52:25,720 --> 00:52:26,700
Est-il moins de 5?

1070
00:52:26,700 --> 00:52:27,240
Ce n'est pas.

1071
00:52:27,240 --> 00:52:29,510
Nous devons donc continuer à regarder vers le bas.

1072
00:52:29,510 --> 00:52:30,940
Ensuite, vous vérifiez 2 sur 3.

1073
00:52:30,940 --> 00:52:31,850
Est-il moins?

1074
00:52:31,850 --> 00:52:32,350
Non.

1075
00:52:32,350 --> 00:52:35,430
Donc, vous savez 2 doit être inséré
dans la partie avant 3 et 5 et

1076
00:52:35,430 --> 00:52:38,200
les deux doivent être poussé dehors.

1077
00:52:38,200 --> 00:52:42,190
Pour ce faire, à nouveau avec 6 et 4.

1078
00:52:42,190 --> 00:52:48,962
Et nous continuons à vérifier simplement l'essentiel,
où nous vérifions juste, vérifier, vérifier.

1079
00:52:48,962 --> 00:52:51,170
Et jusqu'à ce qu'il soit dans la bonne
position, nous sorte de juste

1080
00:52:51,170 --> 00:52:54,890
insérez-le dans la bonne position,
qui est où le nom de celui-ci est venu.

1081
00:52:54,890 --> 00:52:59,830
>> Voilà donc simplement l'algorithme,
pseudo-soi, en quelque sorte,

1082
00:52:59,830 --> 00:53:04,990
sur la façon dont nous pourrions mettre en œuvre
un tri par insertion.

1083
00:53:04,990 --> 00:53:05,954
Pseudocode est ici.

1084
00:53:05,954 --> 00:53:06,620
Il est tout en ligne.

1085
00:53:06,620 --> 00:53:10,720
Pas de soucis si vous les gars sont
essayant de copier cette baisse.

1086
00:53:10,720 --> 00:53:14,500
Donc encore une fois, même ce question--
serait la pire des runtimes meilleur et

1087
00:53:14,500 --> 00:53:16,120
pour le tri par insertion?

1088
00:53:16,120 --> 00:53:17,750
Il est très similaire à la dernière question.

1089
00:53:17,750 --> 00:53:20,479
Je vais vous donner les gars, comme, 30
secondes pour réfléchir à cela aussi.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Quelqu'un veut-
me donner la pire de l'exécution?

1092
00:53:50,071 --> 00:53:50,570
Ouais.

1093
00:53:50,570 --> 00:53:51,490
>> AUDIENCE: n carré.

1094
00:53:51,490 --> 00:53:52,573
>> PENG ANDI: Il est n carré.

1095
00:53:52,573 --> 00:53:53,730
Et pourquoi est-il n carré?

1096
00:53:53,730 --> 00:53:57,562
>> AUDIENCE: Parce que dans
l'ordre inverse, vous avez

1097
00:53:57,562 --> 00:54:02,619
de passer par n fois n, qui est--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Oui, exactement.

1099
00:54:03,660 --> 00:54:06,610
Donc même chose que dans le tri à bulles.

1100
00:54:06,610 --> 00:54:08,720
Si cette liste est en
ordre décroissant, vous êtes

1101
00:54:08,720 --> 00:54:11,240
allez avoir à vérifier une première fois.

1102
00:54:11,240 --> 00:54:13,470
Et puis avec tous les
valeur supplémentaire, vous êtes

1103
00:54:13,470 --> 00:54:16,390
allez avoir à vérifier contre
chaque valeur unique, non?

1104
00:54:16,390 --> 00:54:20,290
Et donc tout à fait, vous allez faire
une fois n de dépasser un autre n passent, qui

1105
00:54:20,290 --> 00:54:21,750
n est au carré.

1106
00:54:21,750 --> 00:54:22,860
Qu'en est-il le meilleur des cas?

1107
00:54:22,860 --> 00:54:24,360
Ouais.

1108
00:54:24,360 --> 00:54:28,840
>> AUDIENCE: n moins 1, parce que la
premier est déjà au carré.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Donc, à proximité.

1110
00:54:30,270 --> 00:54:31,850
La réponse est en fait n.

1111
00:54:31,850 --> 00:54:37,189
Parce que pendant que le premier est une
triés, il peut ne pas lui actually--

1112
00:54:37,189 --> 00:54:38,980
nous avons juste eu de la chance, dans
cet exemple, que deux

1113
00:54:38,980 --> 00:54:40,930
qui est arrivé à être le plus petit nombre.

1114
00:54:40,930 --> 00:54:43,680
Mais ce ne sera pas toujours le cas.

1115
00:54:43,680 --> 00:54:48,040
Si 2 est déjà trié dans le début
mais vous regardez et il ya un 1 ici,

1116
00:54:48,040 --> 00:54:49,144
le 1 va le heurter.

1117
00:54:49,144 --> 00:54:51,060
Et il va finir
jusqu'à être heurté de toute façon.

1118
00:54:51,060 --> 00:54:56,250
>> Donc, dans le meilleur des cas,
il est en fait juste va être n.

1119
00:54:56,250 --> 00:54:59,090
Si vous avez 1, 2, 3,
4, 5, 6, 7, 8, vous êtes

1120
00:54:59,090 --> 00:55:00,940
aller à courir à travers
toute cette liste une fois

1121
00:55:00,940 --> 00:55:03,430
de vérifier pour voir si tout va bien.

1122
00:55:03,430 --> 00:55:07,390
Tout le monde est clair sur la course
temps de sélection ainsi?

1123
00:55:07,390 --> 00:55:09,960
Je sais que je vais à travers
ces vraiment rapide.

1124
00:55:09,960 --> 00:55:13,330
Mais savez juste que si vous connaissez le
concepts généraux, vous devriez être bon.

1125
00:55:13,330 --> 00:55:16,070
D'ACCORD.

1126
00:55:16,070 --> 00:55:19,790
Donc, je vais vous donner les gars peut-être, comme,
une minute pour parler à vos voisins

1127
00:55:19,790 --> 00:55:21,890
sur ce que sont quelques-unes
des principales différences

1128
00:55:21,890 --> 00:55:23,540
entre ces types de sortes.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Nous allons passer en revue que bientôt.

1131
00:56:25,570 --> 00:56:26,444
AUDIENCE: Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Ouais.

1133
00:56:27,320 --> 00:56:28,380
D'ACCORD.

1134
00:56:28,380 --> 00:56:33,420
Cool, Reprenons en tant que classe.

1135
00:56:33,420 --> 00:56:34,330
D'ACCORD.

1136
00:56:34,330 --> 00:56:37,579
Donc, ce fut une sorte de
question ouverte dans le sens

1137
00:56:37,579 --> 00:56:39,120
qu'il ya beaucoup de réponses pour eux.

1138
00:56:39,120 --> 00:56:40,746
Et nous allons passer en revue certains d'entre eux brièvement.

1139
00:56:40,746 --> 00:56:43,411
Je voulais juste pour vous les gars
penser à ce différenciée

1140
00:56:43,411 --> 00:56:44,530
les trois types de sortes.

1141
00:56:44,530 --> 00:56:47,440
Et je entendu, aussi, un grand
question-- ce ne fusionne sorte faire?

1142
00:56:47,440 --> 00:56:50,110
Grande question, parce que ce
ce que nous sommes couvrant prochaine.

1143
00:56:50,110 --> 00:56:52,850
>> Donc, le tri par fusion est le
une sorte que les fonctions

1144
00:56:52,850 --> 00:56:56,100
très différemment des autres sortes.

1145
00:56:56,100 --> 00:56:58,180
Comme vous les gars peuvent see--
fait David cette démo

1146
00:56:58,180 --> 00:57:01,130
où il avait toute la fraîcheur
bruits de voir comment fusionner

1147
00:57:01,130 --> 00:57:04,010
Trier couru, comme, à l'infini
plus rapidement que les deux autres types?

1148
00:57:04,010 --> 00:57:04,510
D'ACCORD.

1149
00:57:04,510 --> 00:57:07,580
Voilà donc parce fusion
implémente sorte que fracture

1150
00:57:07,580 --> 00:57:11,020
et conquérir concept que nous avons
parlé de beaucoup de choses en cours.

1151
00:57:11,020 --> 00:57:14,550
En ce sens que nous aimons travailler
plus intelligemment, pas plus difficile, quand on divise

1152
00:57:14,550 --> 00:57:18,120
et conquérir des problèmes, et les briser
vers le bas, puis les mettre ensemble,

1153
00:57:18,120 --> 00:57:19,930
bonnes choses arrivent toujours.

1154
00:57:19,930 --> 00:57:21,960
>> Ainsi, la manière qui fusionnent
Trier travaille essentiellement

1155
00:57:21,960 --> 00:57:24,660
est qu'il divise une
tableau non trié dans la moitié.

1156
00:57:24,660 --> 00:57:26,500
Et puis, il a obtenu deux moitiés de tableaux.

1157
00:57:26,500 --> 00:57:28,220
Et il trie simplement les deux moitiés.

1158
00:57:28,220 --> 00:57:31,750
Il ne cesse de diviser en deux, en
la moitié, dans la moitié jusqu'à ce que tout est trié

1159
00:57:31,750 --> 00:57:33,680
puis de façon récursive
met tout cela ensemble.

1160
00:57:33,680 --> 00:57:36,550
>> Voilà donc vraiment abstrait.

1161
00:57:36,550 --> 00:57:38,750
Donc, ceci est juste un peu de pseudo-code.

1162
00:57:38,750 --> 00:57:41,040
Cela fait-il sens
la façon dont il fonctionne?

1163
00:57:41,040 --> 00:57:43,870
Alors disons simplement que vous avez un
tableau de n éléments, non?

1164
00:57:43,870 --> 00:57:45,450
Si n est inférieur à 2, vous pouvez retourner.

1165
00:57:45,450 --> 00:57:49,040
Parce que vous savez que si il ya
une seule chose, il doit être triée.

1166
00:57:49,040 --> 00:57:52,600
Sinon, vous triez la moitié gauche,
puis vous triez la moitié droite,

1167
00:57:52,600 --> 00:57:54,140
puis vous fusionnez.

1168
00:57:54,140 --> 00:57:56,979
>> Ainsi, alors que l'air vraiment facile,
en réalité, il est de penser à

1169
00:57:56,979 --> 00:58:00,270
un peu difficile. Parce que vous êtes comme,
Eh bien, voilà sorte de tournant sur lui-même.

1170
00:58:00,270 --> 00:58:00,769
Droit?

1171
00:58:00,769 --> 00:58:02,430
Il est en cours d'exécution sur elle-même.

1172
00:58:02,430 --> 00:58:05,479
Donc, dans ce sens, David touché
sur la récursivité en classe.

1173
00:58:05,479 --> 00:58:07,270
Et voilà un concept
nous parlerons plus.

1174
00:58:07,270 --> 00:58:11,430
Il est ce qui, ces deux lignes
ici, est en fait juste le programme

1175
00:58:11,430 --> 00:58:13,860
lui disant d'exécuter lui-même
avec entrée différente.

1176
00:58:13,860 --> 00:58:17,230
Alors plutôt que de lui-même exécuté avec
l'ensemble de n éléments,

1177
00:58:17,230 --> 00:58:20,530
vous pouvez le décomposer dans la
la moitié gauche et la moitié droite

1178
00:58:20,530 --> 00:58:22,680
et puis exécutez-le à nouveau.

1179
00:58:22,680 --> 00:58:26,050
>> Et puis nous allons examiner visuellement,
parce que je suis un apprenant visuel.

1180
00:58:26,050 --> 00:58:27,270
Il fonctionne mieux pour moi.

1181
00:58:27,270 --> 00:58:29,890
Donc, nous allons regarder un exemple visuel ici.

1182
00:58:29,890 --> 00:58:36,237
>> Disons que nous avons un tableau, six
éléments, 3, 5, 2, 6, 4, 1, non trié.

1183
00:58:36,237 --> 00:58:37,820
Très bien, il ya beaucoup sur cette page.

1184
00:58:37,820 --> 00:58:43,179
Donc, si vous les gars pouvez consulter le
première étape ici, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
vous pouvez diviser en deux.

1186
00:58:44,220 --> 00:58:45,976
Vous avez 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Vous savez que ceux-ci vous aren't--
Je ne sais pas si elles sont triées ou non,

1188
00:58:48,850 --> 00:58:52,517
si vous continuez à les briser, dans la moitié,
dans la moitié, dans la moitié, jusqu'à ce que finalement,

1189
00:58:52,517 --> 00:58:53,600
vous avez un seul élément.

1190
00:58:53,600 --> 00:58:56,790
Et un élément est toujours triée, non?

1191
00:58:56,790 --> 00:59:01,560
>> Nous savons donc que 3, 5, 2, 4, 6,
1, par eux-mêmes, sont triés.

1192
00:59:01,560 --> 00:59:05,870
Et maintenant, nous pouvons les remettre ensemble.

1193
00:59:05,870 --> 00:59:07,510
Donc, nous savons que le 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Nous mettons les ensemble.

1195
00:59:08,510 --> 00:59:09,617
Nous savons que ce tri.

1196
00:59:09,617 --> 00:59:10,450
Les 2 est toujours là.

1197
00:59:10,450 --> 00:59:11,830
Nous pouvons mettre le 4 et le 6 ensemble.

1198
00:59:11,830 --> 00:59:13,996
Nous savons que que ça triés,
alors nous avons mis cela ensemble.

1199
00:59:13,996 --> 00:59:14,940
Et la figure 1 est là.

1200
00:59:14,940 --> 00:59:18,720
>> Et puis vous regardez juste
ces deux moitiés ici.

1201
00:59:18,720 --> 00:59:21,300
Vous avez le 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Vous pouvez les comparer
commencement de tout.

1203
00:59:23,465 --> 00:59:26,340
Parce que vous savez que ceci est trié
et vous savez que que ça triés.

1204
00:59:26,340 --> 00:59:29,360
Ainsi donc, vous ne devez pas même à
comparer le 5, vous comparez juste le 3.

1205
00:59:29,360 --> 00:59:32,070
Et la figure 2 est inférieur à 3, de sorte que
vous savez 2 doit aller à la fin.

1206
00:59:32,070 --> 00:59:33,120
>> Même chose là-bas.

1207
00:59:33,120 --> 00:59:34,740
Le 1 doit aller ici.

1208
00:59:34,740 --> 00:59:37,330
Et puis quand vous allez mettre
ces deux valeurs,

1209
00:59:37,330 --> 00:59:39,950
vous savez que ce sont triés et
vous savez que ce sont triés.

1210
00:59:39,950 --> 00:59:43,240
Alors le 1 et le
2, la figure 1 est inférieur à 2.

1211
00:59:43,240 --> 00:59:45,570
Qui vous dit que le 1
devrait aller sur la fin de cette

1212
00:59:45,570 --> 00:59:47,480
sans même regarder 3 ou 5.

1213
00:59:47,480 --> 00:59:50,100
Et puis le 4, vous pouvez juste
vérifier, il va droit ici.

1214
00:59:50,100 --> 00:59:51,480
Vous ne devez pas regarder le 5.

1215
00:59:51,480 --> 00:59:52,570
Même chose avec la 6.

1216
00:59:52,570 --> 00:59:55,860
Vous savez que le 6-- juste
n'a pas besoin d'être regardé.

1217
00:59:55,860 --> 00:59:57,870
>> Et de cette façon, vous êtes
juste vous sauver

1218
00:59:57,870 --> 00:59:59,526
beaucoup d'étapes lorsque vous faites la comparaison.

1219
00:59:59,526 --> 01:00:02,150
Vous ne disposez pas de comparer tous les
élément contre d'autres éléments.

1220
01:00:02,150 --> 01:00:05,230
Vous comparez seulement contre ceux
que vous avez besoin de le comparer contre.

1221
01:00:05,230 --> 01:00:06,870
Voilà donc genre d'un concept abstrait.

1222
01:00:06,870 --> 01:00:10,540
Pas de soucis si elle est pas
tout droit de vous frapper encore.

1223
01:00:10,540 --> 01:00:14,740
Mais en général, cela est
comment une sorte de fusion fonctionne.

1224
01:00:14,740 --> 01:00:17,750
Questions, questions rapides,
avant de passer?

1225
01:00:17,750 --> 01:00:18,550
Ouais.

1226
01:00:18,550 --> 01:00:22,230
>> Auditoire: Alors, vous avez dit que vous prenez
le 1, puis le 4, 6 et la

1227
01:00:22,230 --> 01:00:23,860
et les mettre dans.

1228
01:00:23,860 --> 01:00:26,800
Donc, ne sont pas those-- ne sont pas
vous les regardant

1229
01:00:26,800 --> 01:00:28,544
comme des éléments distincts, et non comme l'ensemble?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Ouais.

1231
01:00:29,210 --> 01:00:32,020
Donc ce qui se passe
est que vous essentiellement

1232
01:00:32,020 --> 01:00:33,650
sont la création d'un réseau de nouvelle marque.

1233
01:00:33,650 --> 01:00:36,690
Donc, vous savez que, ici, je dois
deux tableaux de taille 3, non?

1234
01:00:36,690 --> 01:00:39,600
Donc, vous savez que mon tableau trié
doit avoir six éléments.

1235
01:00:39,600 --> 01:00:42,270
Alors que vous venez de créer un
nouvelle quantité de mémoire.

1236
01:00:42,270 --> 01:00:44,270
Donc, vous êtes un peu comme
gaspiller de la mémoire,

1237
01:00:44,270 --> 01:00:46,186
mais cela n'a pas d'importance
parce qu'il est si petit.

1238
01:00:46,186 --> 01:00:48,590
Alors vous regardez le 1
et vous regardez le 2.

1239
01:00:48,590 --> 01:00:50,770
Et vous savez que le 1 est inférieur à 2.

1240
01:00:50,770 --> 01:00:53,840
Donc, vous savez que 1 devrait aller dans
le début de l'ensemble de ceux-ci.

1241
01:00:53,840 --> 01:00:55,850
>> Vous ne même pas besoin de
regarder le 3 et le 5.

1242
01:00:55,850 --> 01:00:57,400
Donc, vous savez 1 y va.

1243
01:00:57,400 --> 01:00:59,300
Ensuite, vous essentiellement couper le 1.

1244
01:00:59,300 --> 01:01:00,370
Il est, comme, morts pour nous.

1245
01:01:00,370 --> 01:01:03,690
Ensuite, nous avons seulement 2,
3, 5, puis 4 et 6.

1246
01:01:03,690 --> 01:01:06,270
Et puis vous savez cela, vous
comparer le 4 et le 2,

1247
01:01:06,270 --> 01:01:07,560
oh, le 2 devrait aller là-bas.

1248
01:01:07,560 --> 01:01:09,685
Donc, vous l'écrasez 2 vers le bas, vous hachez-le.

1249
01:01:09,685 --> 01:01:12,060
Ainsi donc, vous avez juste le 3
et le 5 dans le 4 et le 6.

1250
01:01:12,060 --> 01:01:14,650
Et vous continuez à hacher le tout
jusqu'à ce que vous les mettez dans le tableau.

1251
01:01:14,650 --> 01:01:17,110
>> Auditoire: Alors, vous êtes juste toujours
comparant la [inaudible]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Exactement.

1253
01:01:17,710 --> 01:01:19,590
Donc, dans ce sens, vous êtes
simplement comparer, essentiellement,

1254
01:01:19,590 --> 01:01:21,240
un numéro contre l'autre numéro.

1255
01:01:21,240 --> 01:01:22,990
Et parce que vous savez
qu'il est triée, vous

1256
01:01:22,990 --> 01:01:24,350
ne pas avoir à regarder à travers
tous les nombres.

1257
01:01:24,350 --> 01:01:25,870
Vous avez juste à regarder le premier.

1258
01:01:25,870 --> 01:01:27,582
Et puis vous pouvez juste plop
les vers le bas, parce que vous savez

1259
01:01:27,582 --> 01:01:29,640
ils appartiennent où ils doivent appartenir.

1260
01:01:29,640 --> 01:01:31,030
Ouais.

1261
01:01:31,030 --> 01:01:32,920
Bonne question.

1262
01:01:32,920 --> 01:01:35,290
>> Et puis, si l'un de vous
sont un peu ambitieux,

1263
01:01:35,290 --> 01:01:38,660
hésitez pas à regarder ce code.

1264
01:01:38,660 --> 01:01:40,680
Ceci est en fait la
la mise en œuvre physique

1265
01:01:40,680 --> 01:01:42,150
de la façon dont nous pourrions écrire tri par fusion.

1266
01:01:42,150 --> 01:01:44,070
Et vous pouvez le voir, il est très courte.

1267
01:01:44,070 --> 01:01:46,310
Mais les idées derrière
il sont assez complexes.

1268
01:01:46,310 --> 01:01:50,865
Donc, si vous vous sentez comme ce dessin sur
dans vos devoirs ce soir, vous pouvez.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> D'ACCORD.

1271
01:01:54,740 --> 01:01:58,070
David est également rendu au cours de cette conférence dans.

1272
01:01:58,070 --> 01:02:00,660
Quels sont le meilleur des cas
runtimes, pires cas, runtimes

1273
01:02:00,660 --> 01:02:05,680
et les runtimes attendus de tri par fusion?

1274
01:02:05,680 --> 01:02:07,260
A quelques secondes pour réfléchir.

1275
01:02:07,260 --> 01:02:11,198
Ceci est assez difficile, mais un peu
intuitive si vous pensez à ce sujet.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Bien.

1278
01:02:23,054 --> 01:02:25,269
>> Public: Est ce que le pire des cas n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Exactement.

1280
01:02:26,060 --> 01:02:29,380
Et pourquoi est-il n log n.

1281
01:02:29,380 --> 01:02:32,230
>> AUDIENCE: est-ce pas parce qu'il
devient exponentiellement plus rapide,

1282
01:02:32,230 --> 01:02:35,390
il est donc comme une fonction de cette
lieu d'être juste tout simplement n

1283
01:02:35,390 --> 01:02:37,529
carré ou quelque chose?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Exactement.

1285
01:02:38,320 --> 01:02:40,750
Donc la raison pour laquelle la
runtime sur ce journal est n

1286
01:02:40,750 --> 01:02:44,310
n est ce que vous êtes because--
faire dans toutes ces étapes?

1287
01:02:44,310 --> 01:02:46,190
Vous êtes juste couper en deux, non?

1288
01:02:46,190 --> 01:02:48,750
Et donc quand nous faisons la
journal, tout ce qu'il fait

1289
01:02:48,750 --> 01:02:53,150
est de diviser un problème en deux,
dans la moitié, dans la moitié, en plus de moitiés.

1290
01:02:53,150 --> 01:02:56,430
Et dans ce sens, vous pouvez genre
d'éliminer le modèle linéaire

1291
01:02:56,430 --> 01:02:57,510
que nous avons utilisé.

1292
01:02:57,510 --> 01:03:00,254
Parce que quand vous hachez
choses dans la moitié, il est un journal.

1293
01:03:00,254 --> 01:03:02,420
Cela est juste la mathématique
façon de le représenter.

1294
01:03:02,420 --> 01:03:06,310
>> Et puis finalement, à la fin, vous êtes
juste faire une dernière passe à travers

1295
01:03:06,310 --> 01:03:07,930
de mettre tout en ordre, non?

1296
01:03:07,930 --> 01:03:10,330
Et donc si vous avez juste à
vérifier une chose, qui est n.

1297
01:03:10,330 --> 01:03:13,420
Et si vous êtes du genre
multipliant les deux ensemble.

1298
01:03:13,420 --> 01:03:17,660
Donc, il est comme vous avez cette finale
vérifier n ici avec un journal de n

1299
01:03:17,660 --> 01:03:18,390
ici.

1300
01:03:18,390 --> 01:03:21,060
Et si vous multipliez
eux, qui est n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Et donc le meilleur et le pire
affaire et attendu sont tout n log n.

1302
01:03:26,100 --> 01:03:27,943
Il est aussi comme une autre sorte.

1303
01:03:27,943 --> 01:03:30,090
Il est comme la sélection Trier
dans le sens où il

1304
01:03:30,090 --> 01:03:32,131
n'a pas d'importance ce que votre
la liste est, il va juste

1305
01:03:32,131 --> 01:03:34,801
à faire la même chose à chaque fois.

1306
01:03:34,801 --> 01:03:35,300
D'ACCORD.

1307
01:03:35,300 --> 01:03:39,950
Donc, comme vous les gars pouvez le voir, même si
les sortes que nous sommes passés through-- n

1308
01:03:39,950 --> 01:03:41,660
carré, il est pas très efficace.

1309
01:03:41,660 --> 01:03:47,060
Et même ce n log n est
pas la plus efficace.

1310
01:03:47,060 --> 01:03:49,720
Si vous les gars sont curieux,
il ya des mécanismes de tri

1311
01:03:49,720 --> 01:03:54,310
qui sont si efficaces qu'ils sont
presque essentiellement plat dans l'exécution.

1312
01:03:54,310 --> 01:03:55,420
>> Vous avez un peu de log n.

1313
01:03:55,420 --> 01:03:58,190
Vous avez un peu de log n log.

1314
01:03:58,190 --> 01:04:00,330
Nous ne touchons pas sur eux
dans cette classe en ce moment.

1315
01:04:00,330 --> 01:04:02,663
Mais si vous les gars sont curieux,
hésitez pas à Google, ce qui est

1316
01:04:02,663 --> 01:04:04,392
les mécanismes de tri les plus efficaces.

1317
01:04:04,392 --> 01:04:06,350
Je ne sais pas, il ya
certains ceux qui sont vraiment drôles,

1318
01:04:06,350 --> 01:04:09,860
like-- il ya certains vraiment
les drôles que les gens font.

1319
01:04:09,860 --> 01:04:12,210
Et vous vous demandez comment ils
jamais pensé à cela.

1320
01:04:12,210 --> 01:04:15,730
Donc Google, si vous avez un peu de secours
temps, sur, quels sont les moyens drôles

1321
01:04:15,730 --> 01:04:17,730
que personnes-- ainsi que
personnes ways-- efficaces

1322
01:04:17,730 --> 01:04:20,371
ont été en mesure de mettre en œuvre toutes sortes.

1323
01:04:20,371 --> 01:04:20,870
D'ACCORD.

1324
01:04:20,870 --> 01:04:22,880
Et voici juste un petit tableau à portée de main.

1325
01:04:22,880 --> 01:04:26,850
Je sais tout de vous, avant que quizz 0,
sera dans votre chambre sans doute essayer

1326
01:04:26,850 --> 01:04:27,960
à mémoriser que.

1327
01:04:27,960 --> 01:04:30,940
Voilà donc agréable là pour vous les gars.

1328
01:04:30,940 --> 01:04:37,120
Il suffit de ne pas oublier que la logique prises en vue:
pourquoi ces chiffres se produisaient.

1329
01:04:37,120 --> 01:04:39,870
Si vous êtes toujours perdu, juste faire
vous que vous savez ce que les sortes sont.

1330
01:04:39,870 --> 01:04:40,820
Et vous pouvez courir à travers
dans votre esprit

1331
01:04:40,820 --> 01:04:42,903
de comprendre pourquoi ceux
réponses sont ces réponses.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Bien.

1334
01:04:47,600 --> 01:04:49,680
Donc, nous allons déplacer
sur, enfin, à la recherche.

1335
01:04:49,680 --> 01:04:51,638
Parce que, comme ceux d'entre vous
qui ont lu le pset,

1336
01:04:51,638 --> 01:04:55,175
recherche fait également partie de
Le problème de cette semaine fixe.

1337
01:04:55,175 --> 01:04:57,300
Vous serez invité à mettre en œuvre
deux types de recherches.

1338
01:04:57,300 --> 01:05:00,070
L'un est une recherche linéaire et
on est une recherche binaire.

1339
01:05:00,070 --> 01:05:01,760
>> Ainsi, la recherche linéaire est assez facile.

1340
01:05:01,760 --> 01:05:04,070
Vous voulez juste à l'élément recherche
d'une liste pour voir si vous obtenez.

1341
01:05:04,070 --> 01:05:05,444
Vous avez juste à itérer.

1342
01:05:05,444 --> 01:05:08,170
Et si elle est égale à quelque chose,
vous pouvez simplement revenir, non?

1343
01:05:08,170 --> 01:05:10,890
Mais celui que nous sommes les plus
intéressé à parler

1344
01:05:10,890 --> 01:05:14,550
est binaire de recherche, à droite, qui est la
diviser et conquérir mécanisme

1345
01:05:14,550 --> 01:05:18,190
David a été la démonstration en cours.

1346
01:05:18,190 --> 01:05:20,810
>> Rappelez-vous l'exemple du livre de téléphone
qu'il continue à élever,

1347
01:05:20,810 --> 01:05:23,960
celui qu'il sorte de luttait
un peu sur cette dernière année,

1348
01:05:23,960 --> 01:05:27,530
où vous divisez le problème dans la moitié,
en deux, en deux, à plusieurs reprises,

1349
01:05:27,530 --> 01:05:30,730
jusqu'à ce que vous trouverez ce que vous cherchez?

1350
01:05:30,730 --> 01:05:33,727
Et vous avez le
l'exécution de cette ainsi.

1351
01:05:33,727 --> 01:05:35,810
Et vous pouvez le voir, il est
significativement plus efficace

1352
01:05:35,810 --> 01:05:39,080
que tout autre type de recherche.

1353
01:05:39,080 --> 01:05:41,880
>> Ainsi, la manière que nous irions à propos
la mise en œuvre d'une recherche binaire

1354
01:05:41,880 --> 01:05:46,510
est, si nous avions un tableau,
index 0 à 6, sept éléments,

1355
01:05:46,510 --> 01:05:49,790
nous pouvons regarder au milieu, droite-
désolé, si notre question first--

1356
01:05:49,790 --> 01:05:53,840
si nous voulons poser la question de, t-
le tableau contient l'élément de 7,

1357
01:05:53,840 --> 01:05:56,840
de toute évidence, être humain, et ayant
tel un petit tableau, il est facile pour nous

1358
01:05:56,840 --> 01:05:58,210
à dire oui.

1359
01:05:58,210 --> 01:06:05,750
Mais la façon de mettre en œuvre un fichier binaire
recherche serait de regarder dans le milieu.

1360
01:06:05,750 --> 01:06:08,020
>> Nous savons que l'indice 3 est
au milieu, parce que nous

1361
01:06:08,020 --> 01:06:09,270
savent qu'il ya sept éléments.

1362
01:06:09,270 --> 01:06:10,670
Qu'est-ce que 7 divisé par 2?

1363
01:06:10,670 --> 01:06:12,850
Vous pouvez couper ce supplément 1.

1364
01:06:12,850 --> 01:06:14,850
Vous avez 3 dans le milieu.

1365
01:06:14,850 --> 01:06:17,590
Donc, est un tableau de 3 égale à 7?

1366
01:06:17,590 --> 01:06:18,900
Il est pas, non?

1367
01:06:18,900 --> 01:06:21,050
Mais nous pouvons faire quelques vérifications.

1368
01:06:21,050 --> 01:06:25,380
Est un tableau de 3 à moins de 7 ou
est un tableau de 3 supérieur à 7?

1369
01:06:25,380 --> 01:06:27,240
>> Et nous savons qu'il est inférieur à 7.

1370
01:06:27,240 --> 01:06:30,259
Donc, nous savons que, oh, elle doit
ne pas être dans la moitié gauche.

1371
01:06:30,259 --> 01:06:32,300
Nous savons qu'il doit être
dans la moitié droite, non?

1372
01:06:32,300 --> 01:06:34,662
Donc, nous ne pouvons tout simplement couper la moitié du tableau.

1373
01:06:34,662 --> 01:06:36,370
Nous ne devons même pas
regarder plus.

1374
01:06:36,370 --> 01:06:38,711
Parce que nous savons que
la moitié de notre problem--

1375
01:06:38,711 --> 01:06:41,210
nous savons que la réponse est dans
la moitié droite de notre problème.

1376
01:06:41,210 --> 01:06:42,580
Donc, nous attendons juste à ce moment.

1377
01:06:42,580 --> 01:06:44,860
>> Alors maintenant, nous regardons le
milieu de ce qui reste.

1378
01:06:44,860 --> 01:06:46,880
Cet indice 5.

1379
01:06:46,880 --> 01:06:50,200
Nous faisons la même vérification à nouveau
et nous voyons qu'il est plus petit.

1380
01:06:50,200 --> 01:06:52,050
Donc, nous nous tournons vers la gauche de cela.

1381
01:06:52,050 --> 01:06:53,430
Et puis, nous voyons que l'enregistrement.

1382
01:06:53,430 --> 01:06:57,600
Est la valeur du tableau au
Indice 4 égale à 7?

1383
01:06:57,600 --> 01:06:58,260
C'est.

1384
01:06:58,260 --> 01:07:03,580
Donc, nous pouvons retourner vrai, parce que
nous avons trouvé la valeur dans notre liste.

1385
01:07:03,580 --> 01:07:06,738
Est-ce que la façon dont je suis passé par
qui font sens pour tout le monde?

1386
01:07:06,738 --> 01:07:08,760
D'ACCORD.

1387
01:07:08,760 --> 01:07:11,670
Je vais vous donner les gars peut-être, comme,
trois, quatre minutes pour comprendre

1388
01:07:11,670 --> 01:07:13,270
cette façon de pseudocode dans.

1389
01:07:13,270 --> 01:07:18,070
>> Alors, imaginez je vous ai demandé d'écrire une
fonction recherche appelé () qui a renvoyé

1390
01:07:18,070 --> 01:07:20,640
une valeur, une valeur booléenne,
cela était vrai ou false-- comme,

1391
01:07:20,640 --> 01:07:22,970
vrai si vous avez trouvé le
valeur false si vous ne l'avez pas.

1392
01:07:22,970 --> 01:07:25,230
Et puis, vous étiez
passé dans la valeur que vous

1393
01:07:25,230 --> 01:07:28,410
étaient à la recherche en valeurs, qui
est l'array-- oh, je mets définitivement

1394
01:07:28,410 --> 01:07:29,410
que, dans le mauvais endroit.

1395
01:07:29,410 --> 01:07:29,580
D'ACCORD.

1396
01:07:29,580 --> 01:07:31,829
Quoi qu'il en soit, cela devrait avoir
été à la droite des valeurs.

1397
01:07:31,829 --> 01:07:36,280
Et puis int n est le nombre
d'éléments dans ce tableau.

1398
01:07:36,280 --> 01:07:39,430
Comment feriez-vous pour essayer
à Pseudocode ce problème dans?

1399
01:07:39,430 --> 01:07:41,630
Je vais vous donner des gars comme
trois minutes pour le faire.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Non, je pense qu'il ya terre que:
oui, il ya un juste ici.

1402
01:08:02,595 --> 01:08:03,261
AUDIENCE: Puis-je?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Ouais, je vous avez obtenu.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Est-ce travail?

1406
01:08:11,050 --> 01:08:12,290
OK cool.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> D'ACCORD.

1409
01:10:44,720 --> 01:10:47,630
Tous les gars de droite, nous sommes
va freiner dans.

1410
01:10:47,630 --> 01:10:49,730
D'ACCORD.

1411
01:10:49,730 --> 01:10:54,020
Donc, supposons que nous avons cette belle
petit tableau avec n valeurs en elle.

1412
01:10:54,020 --> 01:10:55,170
Je ne dessine les lignes.

1413
01:10:55,170 --> 01:10:58,649
Mais comment pourrions-nous aller sur
en essayant d'écrire cela?

1414
01:10:58,649 --> 01:11:00,440
Quelqu'un veut-
me donner la première ligne?

1415
01:11:00,440 --> 01:11:02,814
Si vous voulez me donner le
première ligne de ce pseudo.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> AUDIENCE: [inaudible]

1418
01:11:08,430 --> 01:11:10,138
AUDIENCE: Vous voudriez
pour itérer through--

1419
01:11:10,138 --> 01:11:11,094
AUDIENCE: Juste une autre pour la boucle?

1420
01:11:11,094 --> 01:11:11,760
AUDIENCE: --pour.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Donc, celui est un peu délicat.

1423
01:11:17,780 --> 01:11:23,130
Pensez about-- vous voulez
pour continuer à fonctionner de cette boucle

1424
01:11:23,130 --> 01:11:27,950
encore et encore jusqu'à quand?

1425
01:11:27,950 --> 01:11:30,819
>> AUDIENCE: Jusqu'à ce que le [inaudible]
La valeur est égale à cette valeur.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Exactement.

1427
01:11:31,610 --> 01:11:33,900
Ainsi, vous pouvez en fait juste write--
nous pouvons même le simplifier plus encore.

1428
01:11:33,900 --> 01:11:35,630
Nous pouvons juste faire une boucle while, à droite?

1429
01:11:35,630 --> 01:11:39,380
Ainsi, vous pouvez juste avoir loop--
nous savons que cela est un tout.

1430
01:11:39,380 --> 01:11:42,850
Mais pour l'instant, je vais
à-dire «boucle» - par quoi?

1431
01:11:42,850 --> 01:11:46,640
Boucle until-- ce qui est
notre condition de fin?

1432
01:11:46,640 --> 01:11:47,510
Je pense que je l'ai entendu.

1433
01:11:47,510 --> 01:11:48,530
Je entendu quelqu'un dire.

1434
01:11:48,530 --> 01:11:51,255
>> Audience: Valeurs égale milieu.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Dites-le à nouveau.

1436
01:11:52,255 --> 01:11:54,470
AUDIENCE: Ou, jusqu'à ce que le
valeur que vous êtes à la recherche

1437
01:11:54,470 --> 01:11:58,470
pour est égale à la valeur moyenne.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Que faire si il est pas là?

1439
01:12:00,280 --> 01:12:03,113
Que faire si la valeur que vous êtes à la recherche
pour est pas réellement dans ce tableau?

1440
01:12:03,113 --> 01:12:05,890
AUDIENCE: Vous revenez 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Mais qu'est-ce que nous voulons
boucle jusqu'à ce que si nous avons une condition?

1442
01:12:08,850 --> 01:12:09,350
Ouais.

1443
01:12:09,350 --> 01:12:11,239
>> AUDIENCE: Jusqu'à il ya une seule valeur?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Vous pouvez faire une boucle
until-- Donc, vous savez que vous êtes

1445
01:12:13,530 --> 01:12:15,714
va avoir une valeur max, non?

1446
01:12:15,714 --> 01:12:18,130
Et vous savez que vous allez
pour avoir une valeur de minutes, non?

1447
01:12:18,130 --> 01:12:20,379
Parce que aussi, que quelque chose
Je oublié de dire avant,

1448
01:12:20,379 --> 01:12:22,640
que quelque chose qui est
critique sur la recherche binaire

1449
01:12:22,640 --> 01:12:24,182
est que votre réseau est déjà trié.

1450
01:12:24,182 --> 01:12:26,973
Parce qu'il n'y a aucun moyen de faire
ce si elles sont juste des valeurs aléatoires.

1451
01:12:26,973 --> 01:12:29,190
Vous ne savez pas si l'on est
plus grand que l'autre, non?

1452
01:12:29,190 --> 01:12:32,720
>> Donc, vous savez que votre max et
vos minutes sont ici, non?

1453
01:12:32,720 --> 01:12:35,590
Si vous allez à l'ajustement
votre maximum dans vos minutes et les mid--

1454
01:12:35,590 --> 01:12:38,470
disons simplement assumer votre
mi valeur est ici-- droit

1455
01:12:38,470 --> 01:12:43,910
vous allez essentiellement
boucle jusqu'à ce que votre minimum est

1456
01:12:43,910 --> 01:12:47,510
environ le même que votre maximum, à droite, ou
si votre max est pas le même que votre min.

1457
01:12:47,510 --> 01:12:48,040
Droit?

1458
01:12:48,040 --> 01:12:51,340
Parce que quand cela arrive, vous savez que
vous avez finalement atteint la même valeur.

1459
01:12:51,340 --> 01:12:59,135
Donc, vous voulez faire une boucle jusqu'à ce que votre min
est inférieure ou égale to-- oops,

1460
01:12:59,135 --> 01:13:01,510
pas moins de ou égal à,
dans l'autre sens est around-- max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Est-ce que de sens?

1463
01:13:16,160 --> 01:13:18,810
Je fis quelques essais pour obtenir ce droit.

1464
01:13:18,810 --> 01:13:21,869
Mais boucle jusqu'à ce que la valeur de votre max
est essentiellement presque moins

1465
01:13:21,869 --> 01:13:23,410
ou égale à votre minimum, non?

1466
01:13:23,410 --> 01:13:25,201
Voilà quand vous savez
que vous avez convergé.

1467
01:13:25,201 --> 01:13:29,290
PUBLIC: Quand serait votre maximum
valeur soit inférieure au minimum?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Si vous continuez à
réglage, ce qui

1469
01:13:31,040 --> 01:13:32,380
est ce que nous allons
à faire dans ce domaine.

1470
01:13:32,380 --> 01:13:33,460
Cela a-t-il du sens?

1471
01:13:33,460 --> 01:13:35,750
Minimum et maximum sont juste
entiers que nous sommes probablement

1472
01:13:35,750 --> 01:13:39,260
allez vouloir créer de garder
trace de où nous sommes à la recherche.

1473
01:13:39,260 --> 01:13:41,790
Parce que le tableau existe
indépendamment de ce que nous faisons.

1474
01:13:41,790 --> 01:13:45,030
Comme, nous ne sommes pas réellement physiquement
coupant le tableau, non?

1475
01:13:45,030 --> 01:13:47,261
Nous sommes en train de réglage
où nous sommes à la recherche.

1476
01:13:47,261 --> 01:13:48,136
Cela a-t-il du sens?

1477
01:13:48,136 --> 01:13:48,472
>> AUDIENCE: Ouais.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Donc, si cela est la condition de notre boucle,
Que voulons-nous à l'intérieur de cette boucle?

1480
01:13:57,090 --> 01:13:58,700
Qu'allons-nous à vouloir faire?

1481
01:13:58,700 --> 01:14:02,390
Donc maintenant, nous avons
un maximum et un minimum, à droite,

1482
01:14:02,390 --> 01:14:04,962
probablement créé ici quelque part.

1483
01:14:04,962 --> 01:14:07,170
Nous allons probablement envie
de trouver un milieu, à droite?

1484
01:14:07,170 --> 01:14:08,450
Comment allons-nous être
en mesure de trouver le milieu?

1485
01:14:08,450 --> 01:14:09,491
Quelle est la mathematical--

1486
01:14:09,491 --> 01:14:11,079
AUDIENCE: Max Plus min divisé par 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Exactement.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Cela a-t-il du sens?

1490
01:14:21,620 --> 01:14:25,780
Et avez-vous les gars vous verrez pourquoi nous
n'a pas seulement use-- pourquoi nous avons fait cette

1491
01:14:25,780 --> 01:14:27,850
au lieu de faire simplement n divisé par 2?

1492
01:14:27,850 --> 01:14:30,310
Il est parce que n est une valeur
que cela va rester le même.

1493
01:14:30,310 --> 01:14:30,979
Droit?

1494
01:14:30,979 --> 01:14:34,020
Mais comme nous ajustons notre minimum et
valeurs maximales, ils vont changer.

1495
01:14:34,020 --> 01:14:36,040
Et en conséquence, notre milieu
qui va changer aussi.

1496
01:14:36,040 --> 01:14:37,873
Voilà pourquoi nous voulons
pour ce faire ici.

1497
01:14:37,873 --> 01:14:38,510
D'ACCORD.

1498
01:14:38,510 --> 01:14:41,600
>> Et puis, maintenant que
nous avons trouvé our-- ouais.

1499
01:14:41,600 --> 01:14:44,270
>> AUDIENCE: Juste un question-- rapide
quand vous dites min et max,

1500
01:14:44,270 --> 01:14:46,410
supposons-nous que
il est déjà triée?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Ouais, qui est en fait un
condition préalable à une recherche binaire,

1502
01:14:48,400 --> 01:14:49,816
que vous devez savoir qu'il est triée.

1503
01:14:49,816 --> 01:14:53,660
Ce qui explique pourquoi sorte, vous écrivez dans votre
problème réglé avant votre recherche binaire.

1504
01:14:53,660 --> 01:14:55,910
D'ACCORD.

1505
01:14:55,910 --> 01:14:58,876
Alors, maintenant que nous savons où notre milieu
est, que voulez-vous faire ici?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> PUBLIC: Nous voulons comparer
que à l'autre.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Exactement.

1509
01:15:05,110 --> 01:15:12,280
Donc, vous allez comparer
milieu à la valeur, à droite?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Et qu'est-ce que dire
nous lorsque nous comparons?

1512
01:15:18,670 --> 01:15:22,226
Que voulons-nous faire ensuite?

1513
01:15:22,226 --> 01:15:25,389
>> Audience: Si la valeur est plus grande
que le milieu, nous voulons couper.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Exactement.

1515
01:15:26,180 --> 01:15:33,940
Donc, si la valeur est plus grande
que le milieu, nous sommes

1516
01:15:33,940 --> 01:15:36,550
allez vouloir modifier celles-ci
minimum et Maxes, non?

1517
01:15:36,550 --> 01:15:38,980
Que voulons-nous changer?

1518
01:15:38,980 --> 01:15:42,145
Donc, si nous connaissons la valeur est quelque part
ici, ce que vous faites, nous changer?

1519
01:15:42,145 --> 01:15:44,758
Nous voulons changer notre
minimales à mi, non?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Et puis d'autre, si elle est dans ce
la moitié, que voulons-nous changer?

1522
01:15:54,292 --> 01:15:55,306
>> Public: Votre maximale.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Ouais.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Et puis vous allez juste
de garder en boucle, non?

1526
01:16:04,680 --> 01:16:08,920
Parce que maintenant, après une itération
à travers, vous avez un max ici.

1527
01:16:08,920 --> 01:16:10,760
Et puis vous pouvez recalculer un milieu.

1528
01:16:10,760 --> 01:16:11,990
Et puis vous pouvez comparer.

1529
01:16:11,990 --> 01:16:14,766
Et vous allez continuer
jusqu'à ce que les minutes et les Maxes

1530
01:16:14,766 --> 01:16:15,890
ont essentiellement convergé.

1531
01:16:15,890 --> 01:16:17,890
Et qui est quand vous savez que
vous avez atteint la fin de celui-ci.

1532
01:16:17,890 --> 01:16:20,280
Et soit vous l'avez trouvé
ou si vous avez pas à ce point.

1533
01:16:20,280 --> 01:16:23,170
>> Cela fait-il sens pour tout le monde?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
D'ACCORD.

1536
01:16:26,770 --> 01:16:27,900
Ceci est très important,
parce que vous aurez

1537
01:16:27,900 --> 01:16:29,760
à écrire ce soir dans votre code.

1538
01:16:29,760 --> 01:16:32,660
Mais vous les gars avez une assez bonne
sens de ce que vous devriez faire,

1539
01:16:32,660 --> 01:16:34,051
ce qui est bon.

1540
01:16:34,051 --> 01:16:34,550
D'ACCORD.

1541
01:16:34,550 --> 01:16:38,840
Donc, nous avons environ sept
minutes partie gauche.

1542
01:16:38,840 --> 01:16:43,170
Donc, nous allons parler
pset ce que nous allons faire.

1543
01:16:43,170 --> 01:16:46,410
Ainsi, le jeu de processeurs est divisé en deux moitiés.

1544
01:16:46,410 --> 01:16:50,230
Le premier semestre implique
la mise en œuvre d'une découverte

1545
01:16:50,230 --> 01:16:54,210
dans lequel vous écrivez une recherche linéaire, un
recherche binaire, et un algorithme de tri.

1546
01:16:54,210 --> 01:16:56,690
>> Donc ceci est la première
temps dans un pset où

1547
01:16:56,690 --> 01:17:00,050
nous serons en vous donnant les gars ce qu'on appelle
code de distribution, qui est le code

1548
01:17:00,050 --> 01:17:02,740
que nous avons pré-écrite,
mais juste laissé quelques morceaux hors

1549
01:17:02,740 --> 01:17:04,635
pour vous de terminer l'écriture.

1550
01:17:04,635 --> 01:17:07,510
Alors vous les gars, quand vous regardez cette
code, vous pourriez obtenir vraiment peur.

1551
01:17:07,510 --> 01:17:08,630
Si vous êtes juste comme, ahh, je
ne savent pas ce que cela fait,

1552
01:17:08,630 --> 01:17:11,670
Je ne sais pas, comme, qui semble
si compliqué, ahh, se détendre.

1553
01:17:11,670 --> 01:17:12,170
C'est bon.

1554
01:17:12,170 --> 01:17:12,930
Lire la spécification.

1555
01:17:12,930 --> 01:17:16,920
La spécification va vous expliquer exactement
ce que tous ces programmes font.

1556
01:17:16,920 --> 01:17:20,560
>> Par exemple, un programme est generate.c
cela viendra avec votre pset.

1557
01:17:20,560 --> 01:17:24,060
Vous ne avez pas réellement besoin de le toucher, mais
vous devez comprendre ce qu'il fait.

1558
01:17:24,060 --> 01:17:28,550
Et generate.c, tout ce qu'il est fait est
soit générer des nombres aléatoires

1559
01:17:28,550 --> 01:17:32,400
ou vous pouvez lui donner une graine, comme un
nombre préétabli qu'il faut,

1560
01:17:32,400 --> 01:17:34,140
et elle génère d'autres numéros.

1561
01:17:34,140 --> 01:17:37,170
Donc, il ya une façon spécifique à
dans lequel la mise en œuvre generate.c

1562
01:17:37,170 --> 01:17:42,760
vous pouvez juste faire un tas de chiffres
pour vous de tester vos méthodes sur d'autres.

1563
01:17:42,760 --> 01:17:45,900
>> Donc, si vous voulez, pour
par exemple, tester votre trouvaille,

1564
01:17:45,900 --> 01:17:48,970
vous voulez exécuter generate.c,
générer un tas de chiffres,

1565
01:17:48,970 --> 01:17:50,880
et puis exécutez votre fonction des aides.

1566
01:17:50,880 --> 01:17:53,930
Votre fonction des aides est l'endroit où vous êtes
effectivement écrit physiquement code.

1567
01:17:53,930 --> 01:17:59,330
Et penser aides comme un fichier de bibliothèque
vous écrivez que find appelle.

1568
01:17:59,330 --> 01:18:02,950
Et au sein de helpers.c, vous aurez
faire recherche et de tri.

1569
01:18:02,950 --> 01:18:06,500
>> Et puis vous allez à l'essentiel
juste les mettre tous ensemble.

1570
01:18:06,500 --> 01:18:10,350
La spec vous dire comment
mettre ça sur la ligne de commande.

1571
01:18:10,350 --> 01:18:14,880
Et vous serez en mesure de tester si oui ou
pas votre tris et de recherches travaillent.

1572
01:18:14,880 --> 01:18:15,870
Frais.

1573
01:18:15,870 --> 01:18:18,720
Quelqu'un at-il déjà commencé et
problèmes ou des questions rencontrées

1574
01:18:18,720 --> 01:18:20,520
ils ont en ce moment avec ce?

1575
01:18:20,520 --> 01:18:21,020
D'ACCORD.

1576
01:18:21,020 --> 01:18:21,476
>> AUDIENCE: Attendez.

1577
01:18:21,476 --> 01:18:21,932
J'ai une question.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Ouais.

1579
01:18:22,844 --> 01:18:28,390
>> Auditoire: Alors, je commencé à faire
la recherche linéaire dans helpers.c

1580
01:18:28,390 --> 01:18:29,670
et il ne fonctionnait pas vraiment.

1581
01:18:29,670 --> 01:18:34,590
Mais plus tard, je découvert que nous venons
avoir à supprimer et faire une recherche binaire.

1582
01:18:34,590 --> 01:18:36,991
Qu'importe donc si ça ne fonctionne pas?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: La réponse courte est non.

1585
01:18:41,510 --> 01:18:42,642
Mais puisque nous sommes pas--

1586
01:18:42,642 --> 01:18:44,350
AUDIENCE: Mais pas son
effectivement le contrôle.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Nous ne sommes jamais
aller voir ça.

1588
01:18:46,058 --> 01:18:49,590
Mais vous voudrez probablement vous
assurer votre recherche fonctionne.

1589
01:18:49,590 --> 01:18:51,700
Parce que si votre linéaire
recherche ne fonctionne pas,

1590
01:18:51,700 --> 01:18:54,410
alors les chances sont de votre binaire
la recherche ne va pas fonctionner aussi bien.

1591
01:18:54,410 --> 01:18:56,646
Parce que vous avez similaires
logique dans chacun d'eux.

1592
01:18:56,646 --> 01:18:58,020
Et non, il n'a pas vraiment d'importance.

1593
01:18:58,020 --> 01:19:01,300
Donc les seuls vous tournez
en sont en quelque sorte et la recherche binaire.

1594
01:19:01,300 --> 01:19:02,490
Ouais.

1595
01:19:02,490 --> 01:19:06,610
>> Et aussi, beaucoup d'enfants étaient
d'essayer de compiler helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Vous n'êtes pas effectivement autorisé
pour ce faire, parce helpers.c

1597
01:19:09,550 --> 01:19:11,200
ne possède pas une fonction principale.

1598
01:19:11,200 --> 01:19:13,550
Et donc vous devriez seulement
être effectivement compilation

1599
01:19:13,550 --> 01:19:18,670
générer et trouver, parce que trouver des appels
helpers.c et les fonctions en son sein.

1600
01:19:18,670 --> 01:19:20,790
Alors que rend le débogage
une douleur dans le cul.

1601
01:19:20,790 --> 01:19:22,422
Mais voilà ce que nous avons à faire.

1602
01:19:22,422 --> 01:19:23,880
AUDIENCE: Vous venez de faire tout, non?

1603
01:19:23,880 --> 01:19:27,290
ANDI Peng: vous pouvez simplement
faire toute aussi bien, ouais.

1604
01:19:27,290 --> 01:19:28,060
D'ACCORD.

1605
01:19:28,060 --> 01:19:32,570
Voilà donc en termes de ce que
le pset vous demande tous de faire.

1606
01:19:32,570 --> 01:19:35,160
Si vous avez des questions, ne
libre pour me demander, après l'article.

1607
01:19:35,160 --> 01:19:37,580
Je serai là pour, comme, 20 minutes.

1608
01:19:37,580 --> 01:19:40,500
>> Et oui, les pset de
vraiment pas si mal que ça.

1609
01:19:40,500 --> 01:19:41,680
Vous devriez être OK.

1610
01:19:41,680 --> 01:19:43,250
Ceux-ci, il suffit de suivre les lignes directrices.

1611
01:19:43,250 --> 01:19:47,840
Type de avoir un sentiment de, logiquement, ce
devrait se passer et vous serez amende.

1612
01:19:47,840 --> 01:19:48,690
Ne soyez pas trop peur.

1613
01:19:48,690 --> 01:19:50,220
Il ya beaucoup de code
déjà écrit il.

1614
01:19:50,220 --> 01:19:53,011
Ne soyez pas trop peur si vous ne le faites pas
comprendre ce que tout cela signifie.

1615
01:19:53,011 --> 01:19:54,749
Si elle est beaucoup, il est tout à fait bien.

1616
01:19:54,749 --> 01:19:55,790
Et venir à des heures de bureau.

1617
01:19:55,790 --> 01:19:57,520
Nous vous aiderons à vous jetez un oeil.

1618
01:19:57,520 --> 01:20:00,810
>> Public: Avec le supplément
fonctions, ne nous regardons ceux en place?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Ouais, ceux qui sont dans le code.

1620
01:20:03,417 --> 01:20:05,750
Dans le jeu de 15, la moitié des
il est déjà écrit pour vous.

1621
01:20:05,750 --> 01:20:09,310
Donc, ces fonctions sont
déjà dans le code.

1622
01:20:09,310 --> 01:20:12,020
Yep.

1623
01:20:12,020 --> 01:20:12,520
Bien.

1624
01:20:12,520 --> 01:20:14,000
Eh bien, bonne chance.

1625
01:20:14,000 --> 01:20:15,180
Il est un jour dégoûtant.

1626
01:20:15,180 --> 01:20:19,370
Donc, nous espérons que vous les gars ne se sentent pas trop
mal à rester à l'intérieur et de codage.

1627
01:20:19,370 --> 01:20:22,133