1
00:00:00,000 --> 00:00:11,100

2
00:00:11,100 --> 00:00:12,300
>> Sprecher 1: Hey everyone!

3
00:00:12,300 --> 00:00:13,890
Willkommen zurück in Abschnitt.

4
00:00:13,890 --> 00:00:17,480
So froh, dass so viele von euch beiden hier zu sehen,
und jeder, der ist online beobachten.

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
Also, wie üblich willkommen zurück.

7
00:00:20,920 --> 00:00:24,360
Ich hoffe, dass Sie alle einen schönen hatten
Wochenende voller Ruhe, Entspannung.

8
00:00:24,360 --> 00:00:26,026
Es war schön gestern.

9
00:00:26,026 --> 00:00:27,525
So, ich hoffe Sie die Natur genossen.

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> Also erstmal ein paar Ankündigungen.

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
Grading.

14
00:00:32,700 --> 00:00:37,350
Also, die meisten von euch sollte bekommen haben ein
E-Mail von mir über Ihre Scratch Pset,

15
00:00:37,350 --> 00:00:39,920
sowie Bewertung für Pset 1.

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
Also, nur ein paar Dinge.

18
00:00:42,220 --> 00:00:45,150
Achten Sie darauf, check50 in style50 verwenden.

19
00:00:45,150 --> 00:00:47,250
Diese sollen zu sein
Ressourcen für euch,

20
00:00:47,250 --> 00:00:50,660
um sicherzustellen, dass Sie bekommen
so viele Punkte wie möglich

21
00:00:50,660 --> 00:00:52,390
ohne sie unnötig zu verlieren.

22
00:00:52,390 --> 00:00:54,407
Also Dinge wie Stil
sind sehr wichtig.

23
00:00:54,407 --> 00:00:55,740
Wir werden für sie ab zu nehmen.

24
00:00:55,740 --> 00:00:58,115
Einige von euch haben vielleicht schon
aufgefallen, dass von Ihrem Pset.

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
Und check50 ist nur eine
wirklich einfache Möglichkeit, um sicherzustellen,

27
00:01:01,450 --> 00:01:05,050
dass wir tatsächlich zurückkehren, was
braucht, um an den Benutzer zurückgegeben werden,

28
00:01:05,050 --> 00:01:06,690
und dass alles ordnungsgemäß funktioniert.

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> Auf der zweiten Note, sicherzustellen, dass Ihre
Hochladen Dinge in den richtigen Ordner.

31
00:01:12,040 --> 00:01:14,470
Es macht mein Leben nur eine
etwas schwieriger

32
00:01:14,470 --> 00:01:18,836
wenn Sie Pset 2 in Pset 1 laden
denn wenn ich Dinge herunterzuladen,

33
00:01:18,836 --> 00:01:20,085
sie nicht richtig downloaden weiß.

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
Und ich weiß, es ist ein wenig wackelig
in einem System zu gewöhnen,

36
00:01:24,560 --> 00:01:26,950
aber einfach super sein
Vorsicht, wenn auch nur für mich,

37
00:01:26,950 --> 00:01:30,080
so dass, wenn Sie immer E-Mails
an wie 02.00 und ich bin Grading.

38
00:01:30,080 --> 00:01:33,710
Wenn nicht dazu führen, muss ich schauen
rundum für Ihre Pset.

39
00:01:33,710 --> 00:01:34,440
Cool.

40
00:01:34,440 --> 00:01:37,270
>> Ich weiß, es ist früh, aber ich
völlig unvorbereitet getroffen habe

41
00:01:37,270 --> 00:01:40,800
durch einen Aufsatz, der aufgrund dieser Freitag, dass
Meine Professoren waren wie, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Denken Sie daran, ein müssen Sie
Essay am Freitag fällig.

43
00:01:42,550 --> 00:01:45,780
Also, ich weiß, niemand mag
über Mittelklausuren denke,

44
00:01:45,780 --> 00:01:50,620
aber Ihre erste Quiz ist am 15. Oktober,
was Oktober wird ab dieser Woche.

45
00:01:50,620 --> 00:01:53,290
So könnte es früher sein
als Sie erwartet haben ist alles.

46
00:01:53,290 --> 00:01:57,510
Also, dass man nicht unvorbereitet, wenn sie geworfen
Ich erwähne Abschnitt der nächsten Woche, die oh,

47
00:01:57,510 --> 00:02:00,560
Ihr Quiz nächste Woche, ich dachte,
Ich würde Ihnen ein wenig mehr zu geben

48
00:02:00,560 --> 00:02:01,500
der ein Heads-up jetzt.

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> Also, Ihr Problem zu setzen, die Nummer drei.

51
00:02:04,660 --> 00:02:07,070
Wie die Leute gelesen haben die
spec aus Neugier?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
Ok.

54
00:02:09,199 --> 00:02:10,229
Wir bekamen ein Paar.

55
00:02:10,229 --> 00:02:12,320
Art von unten von den letzten
Woche, aber das ist OK.

56
00:02:12,320 --> 00:02:13,650
Ich weiß, es war wunderschön aus.

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
Also Break Out.

59
00:02:16,660 --> 00:02:21,010
Definitiv, nachdem Sie erledigen
lesen Sie noch heute Ihr spec mindestens

60
00:02:21,010 --> 00:02:25,240
versuchen wie das Herunterladen von
Verteilungscode und Lauf

61
00:02:25,240 --> 00:02:27,430
wie der erste Anfangs
Sache, die sie Sie bitten,.

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
Weil wir mit
Verteilungscode und eine Bibliothek

64
00:02:32,590 --> 00:02:36,790
dass wir erst seit using-- --Es nur
das zweite Mal, dass wir dieses Pset getan,

65
00:02:36,790 --> 00:02:38,650
verrückte Dinge passieren können
mit Ihrem Gerät,

66
00:02:38,650 --> 00:02:41,370
und Sie möchten, dass finden wollen
out now gegenüber später.

67
00:02:41,370 --> 00:02:45,570
>> Denn wenn es am Donnerstagabend ist, oder es ist
Mittwochabend und aus irgendeinem Grund

68
00:02:45,570 --> 00:02:48,912
Ihr Gerät funktioniert einfach nicht
will mit der Bibliothek laufen

69
00:02:48,912 --> 00:02:50,620
oder mit der Verteilung
Code, das bedeutet

70
00:02:50,620 --> 00:02:52,309
Sie können nicht einmal angefangen zu Codierung.

71
00:02:52,309 --> 00:02:54,100
Weil Sie nicht überprüfen können
um zu sehen, ob es funktioniert.

72
00:02:54,100 --> 00:02:55,975
Ihr nicht gonna zu können
zu sehen, wenn es kompiliert.

73
00:02:55,975 --> 00:03:00,500
Sie möchten die kümmern, früh zu nehmen
in der Woche, wenn Sie mich noch eine E-Mail

74
00:03:00,500 --> 00:03:03,100
oder einer der anderen TFs,
und wir bekommen können diejenigen fixiert.

75
00:03:03,100 --> 00:03:05,410
Denn das sind Fragen
die gehen, Sie zu stoppen sind

76
00:03:05,410 --> 00:03:07,120
von dem jede echte Fortschritte.

77
00:03:07,120 --> 00:03:10,055
Es ist nicht wie ein Bug, dass
Sie können nur irgendwie überspringen.

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
Wenn Sie Probleme mit Ihrer bist
Appliance oder Vertriebscode,

80
00:03:13,420 --> 00:03:16,211
Sie wirklich wollen, zu bekommen, dass getroffen
Pflege eher früher als später.

81
00:03:16,211 --> 00:03:20,410
Also selbst wenn du nicht wirklich Gonna
Programmieren beginnen, laden Sie die Verteilung

82
00:03:20,410 --> 00:03:24,040
Code, lesen Sie die spec, stellen Sie sicher,
Alles ist dort arbeiten.

83
00:03:24,040 --> 00:03:25,134
OK?

84
00:03:25,134 --> 00:03:27,675
Wenn Sie können einfach tun, ich
versprechen euer Leben wird leichter.

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
Und so sind Sie wahrscheinlich
um es jetzt richtig machen?

87
00:03:31,410 --> 00:03:32,100
Ok.

88
00:03:32,100 --> 00:03:33,950
Also, irgendwelche Fragen gibt?

89
00:03:33,950 --> 00:03:35,850
Alle logistischen Dinge?

90
00:03:35,850 --> 00:03:36,910
Jeder ist gut?

91
00:03:36,910 --> 00:03:38,270
Ok.

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer für die von
Sie in den Raum und online.

93
00:03:41,700 --> 00:03:45,437
Ich werde versuchen, zu wechseln
zwischen Powerpoint in der Appliance

94
00:03:45,437 --> 00:03:47,270
denn wir werden
zu sein, wenn Sie einige Codierung

95
00:03:47,270 --> 00:03:53,630
heute aufgrund der großen Nachfrage des anonymen
Vorschlag Umfrage schickte ich letzte Woche.

96
00:03:53,630 --> 00:03:55,480
Also, wir werden tun, einige Codierung.

97
00:03:55,480 --> 00:03:57,800
Also, wenn Sie nie wieder ausziehen wollen auch
zu feuern Ihre Geräte,

98
00:03:57,800 --> 00:04:02,910
und Sie sollten eine E-Mail bekommen haben
von mir, mit einer Beispieldatei.

99
00:04:02,910 --> 00:04:04,310
Bitte zögern Sie nicht, das zu tun.

100
00:04:04,310 --> 00:04:07,340
>> Also, wir gehen, darüber zu sprechen
GDB, die ein Debugger ist.

101
00:04:07,340 --> 00:04:09,970
Es wird Ihnen helfen
Art herauszufinden, wo

102
00:04:09,970 --> 00:04:11,860
etwas falsch läuft in Ihrem Code.

103
00:04:11,860 --> 00:04:15,370
Es ist wirklich nur eine Möglichkeit für Sie zu Schritt
durch den Code, wie es geschieht,

104
00:04:15,370 --> 00:04:19,100
und in der Lage zu drucken Variablen
oder sehen, was wirklich passiert

105
00:04:19,100 --> 00:04:22,980
Unter der Haube Verse Ihr Programm
nur läuft, ist es wie Verwerfungen,

106
00:04:22,980 --> 00:04:25,030
und du, keine Ahnung bist
was gerade hier passiert ist.

107
00:04:25,030 --> 00:04:26,730
Ich weiß nicht, welche Zeile es gescheitert.

108
00:04:26,730 --> 00:04:29,040
Ich weiß nicht, wo es schief ging.

109
00:04:29,040 --> 00:04:31,280
Also, GDB wird Ihnen dabei helfen.

110
00:04:31,280 --> 00:04:35,240
Auch, wenn Sie sich entscheiden,
weiterhin ja, und nehmen Sie 61,

111
00:04:35,240 --> 00:04:38,430
es wird wirklich, wirklich dein
bester Freund, denn ich kann Ihnen sagen,

112
00:04:38,430 --> 00:04:40,840
weil ich durch diese Klasse gehen.

113
00:04:40,840 --> 00:04:43,620
>> Wir werden bei binären aussehen
Suche, die, wenn euch erinnern

114
00:04:43,620 --> 00:04:47,540
das große Telefonbuch beispiels
Schauspiel von Klasse.

115
00:04:47,540 --> 00:04:50,620
Wir werden die Umsetzung das, und
zu Fuß durch, dass ein bisschen mehr,

116
00:04:50,620 --> 00:04:54,650
und dann sind wir durch vier gehen
verschiedene Sorten, die Blase sind,

117
00:04:54,650 --> 00:04:56,285
Auswahl, Insertion und Zusammenführen.

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
Cool.

120
00:04:58,330 --> 00:05:00,390
Also, GDB wie ich bereits erwähnt, ist ein Debugger.

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
Und das sind Art des großen
Dinge, die großen Funktionen oder Befehle

123
00:05:09,370 --> 00:05:13,240
dass Sie innerhalb GDB verwenden, und ich werde gehen
Sie durch eine Demo davon in einer Sekunde.

124
00:05:13,240 --> 00:05:15,360
>> So ist dies nicht nur
werde abstrakt bleiben.

125
00:05:15,360 --> 00:05:18,000
Ich werde versuchen, es so konkret
als für euch möglich.

126
00:05:18,000 --> 00:05:19,870
Also, zu brechen.

127
00:05:19,870 --> 00:05:22,200
Es wird entweder Pause
wie einige Nummer, die

128
00:05:22,200 --> 00:05:26,900
stellt eine Zeile in Ihrem Programm,
oder Sie können eine Funktion zu nennen.

129
00:05:26,900 --> 00:05:30,150
Also, wenn Sie sagen, brechen Haupt,
es wird am Haupt zu stoppen,

130
00:05:30,150 --> 00:05:32,400
und lassen Sie sich durch diese Funktion zu gehen.

131
00:05:32,400 --> 00:05:36,350
>> Ebenso, wenn Sie einige externe haben
funktionieren wie Tausch oder Würfel,

132
00:05:36,350 --> 00:05:38,450
dass wir sah letzte Woche.

133
00:05:38,450 --> 00:05:41,780
Wenn Sie sagen, brechen einer von denen,
wenn Ihr Programm geht, dass,

134
00:05:41,780 --> 00:05:44,290
es werde auf dich warten, um
sagen, was zu tun ist.

135
00:05:44,290 --> 00:05:47,860
Bevor es nur ausführen, so dass Sie
könnte tatsächlich innerhalb der Funktion Schritt

136
00:05:47,860 --> 00:05:49,020
und sehen, was los ist.

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
Also, das nächste, überspringt gerade über die
nächste Zeile, geht über Funktionen.

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
Step.

141
00:05:55,560 --> 00:05:56,810
Diese sind alle wenig abstrakt.

142
00:05:56,810 --> 00:06:00,530
Also, ich bin gerade dabei, durch sie laufen,
aber du wirst sie in den Einsatz in einem zweiten zu sehen.

143
00:06:00,530 --> 00:06:01,810
>> Treten Sie ein in einer Funktion.

144
00:06:01,810 --> 00:06:04,170
So als wollte ich sagen,
wie bei Swap, wäre es

145
00:06:04,170 --> 00:06:07,110
können Sie eigentlich, wenn Sie in
wie physisch innerhalb Schritt,

146
00:06:07,110 --> 00:06:10,990
Sie verwirren kann mit dieser Variablen, drucken
herauszufinden, was sie sind, zu sehen, was los ist.

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
Liste wird buchstäblich nur drucken
aus dem umgebenden Code.

149
00:06:14,830 --> 00:06:17,570
Also, wenn Sie Art von Vergessen
wo Sie in Ihrem Programm haben,

150
00:06:17,570 --> 00:06:19,880
oder Sie sich fragen,
was los ist um ihn herum,

151
00:06:19,880 --> 00:06:23,790
dies nur Ausdruck eines Segments
der gerne fünf oder sechs Zeilen um ihn herum.

152
00:06:23,790 --> 00:06:26,080
Also, Sie orientieren können
darüber, wo Sie sind.

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> Gibt einige Variablen.

155
00:06:28,650 --> 00:06:34,590
Also, wenn Sie den Schlüssel wie haben
Cäsar, die wir zu betrachten.

156
00:06:34,590 --> 00:06:36,220
Man kann sagen, Print-Taste an einem beliebigen Punkt.

157
00:06:36,220 --> 00:06:40,070
Es wird Ihnen sagen, was der Wert ist, so
dass, vielleicht irgendwo auf dem Weg,

158
00:06:40,070 --> 00:06:42,070
Sie Ihren Schlüssel überschrieb.

159
00:06:42,070 --> 00:06:45,495
Sie können tatsächlich sagen, dass, weil
kann man tatsächlich beobachten diesen Wert.

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> In den Einheimischen, nur Drucke
Ihre lokalen Variablen.

162
00:06:48,780 --> 00:06:53,120
Also, wenn Sie innerhalb einer Schleife sind,
und Sie wollen einfach nur wie zu sehen, oh.

163
00:06:53,120 --> 00:06:54,270
Was ist mein Ich?

164
00:06:54,270 --> 00:06:57,020
Was ist das Schlüsselwert
dass ich zu initialisieren hier?

165
00:06:57,020 --> 00:06:58,537
Was ist die Botschaft an dieser Stelle?

166
00:06:58,537 --> 00:07:00,370
Es wird einfach alles ausdrucken
von denen, so dass Sie

167
00:07:00,370 --> 00:07:04,330
nicht einzeln müssen
sagen, Print I. Meldung drucken.

168
00:07:04,330 --> 00:07:04,970
Print Key.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
Und dann auf Anzeige.

171
00:07:07,700 --> 00:07:10,370
Was das bedeutet ist, wie Sie
Schritt durch das Programm,

172
00:07:10,370 --> 00:07:13,980
es wird einfach nur sicherstellen, dass es
Anzeige einige bestimmte variable

173
00:07:13,980 --> 00:07:14,780
an jedem Punkt.

174
00:07:14,780 --> 00:07:17,160
Damit Sie also-- --IT ist
Art der Verknüpfung, wo

175
00:07:17,160 --> 00:07:19,530
Sie müssen nicht, um weiterzumachen wie, oh.

176
00:07:19,530 --> 00:07:23,150
Druck Tasten oder Print I. Es ist einfach
wird automatisch für Sie erledigen.

177
00:07:23,150 --> 00:07:25,959
>> Also, mit, dass, wir gehen
zu sehen, wie das geht.

178
00:07:25,959 --> 00:07:28,000
Ich werde versuchen und Schalter
zu meinem Gerät.

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
Sehen Sie, wenn ich das tun kann.

181
00:07:31,271 --> 00:07:31,770
Alle.

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
Wir sind noch dabei, es zu spiegeln.

184
00:07:42,370 --> 00:07:44,530
Es gibt nichts verrückt
auf meinem Laptop sowieso.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
Ok.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
Dies muss diese sein.

189
00:08:01,054 --> 00:08:01,795
Es ist so winzig.

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
Mal sehen, ob wir dies tun können.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> Ok.

194
00:08:10,940 --> 00:08:15,305
Alice ist offensichtlich kämpfen
hier nur ein wenig,

195
00:08:15,305 --> 00:08:17,995
aber wir werden es in einem momento bekommen.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
Ok.

198
00:08:22,020 --> 00:08:25,900
Wir sind gerade dabei, diese zu erhöhen.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
Ok.

201
00:08:29,380 --> 00:08:31,679
Kann jeder Art sehen, dass?

202
00:08:31,679 --> 00:08:32,470
Vielleicht ein bisschen?

203
00:08:32,470 --> 00:08:33,594
Ich weiß, es ist ein wenig klein.

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
Man kann nicht ganz herausfinden
wie man diese größer.

206
00:08:37,530 --> 00:08:38,350
Wenn jemand weiß.

207
00:08:38,350 --> 00:08:40,309
Weiß jemand, wie man es größer zu machen?

208
00:08:40,309 --> 00:08:40,932
Ok.

209
00:08:40,932 --> 00:08:42,140
Wir werden mit ihm rollen.

210
00:08:42,140 --> 00:08:45,801
Nicht sowieso egal, denn es ist nur
das ist der Code, den Sie Jungs sollten

211
00:08:45,801 --> 00:08:46,300
haben.

212
00:08:46,300 --> 00:08:48,310
>> Was ist wichtiger
ist der Anschluss hier.

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
Und wir haben hier Warum ist es so klein?

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
Einstellungen.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
Oh.

219
00:09:08,420 --> 00:09:09,500
Wahre Ike.

220
00:09:09,500 --> 00:09:10,880
Wie ist das?

221
00:09:10,880 --> 00:09:11,770
Von dort.

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
Ist das besser für alle?

224
00:09:21,810 --> 00:09:22,525
Ok ,.

225
00:09:22,525 --> 00:09:23,025
Cool.

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> Sie wissen, wenn Sie in einer CS sind
Klasse technische Schwierigkeiten

228
00:09:28,220 --> 00:09:32,971
sind so eine Art Teil the--
Also, lasst uns klar, dass dies.

229
00:09:32,971 --> 00:09:33,470
Ok.

230
00:09:33,470 --> 00:09:38,060
Also, hier im Schnitt,
was wir hier hatten.

231
00:09:38,060 --> 00:09:40,830
Caesar ist eine ausführbare Datei.

232
00:09:40,830 --> 00:09:41,800
Also machte ich es.

233
00:09:41,800 --> 00:09:46,370
Also, das ist eine Sache, mit GDB realisieren
dass es funktioniert nur auf ausführbare Dateien.

234
00:09:46,370 --> 00:09:48,040
So können Sie nicht führen Sie es auf einer Dotsy.

235
00:09:48,040 --> 00:09:50,532
Sie müssen tatsächlich machen
sicher, dass Ihr Code kompiliert,

236
00:09:50,532 --> 00:09:51,865
und dass sie tatsächlich ausgeführt werden.

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> Also, stellen Sie sicher, dass, wenn es nicht
kompilieren, bekommen es zu kompilieren,

239
00:09:56,186 --> 00:09:57,810
so dass Sie Art von durch sie laufen.

240
00:09:57,810 --> 00:10:04,590
Also, um GDB starten, alles, was Sie tun,
Gloria Typ GDB, und dann erst der

241
00:10:04,590 --> 00:10:06,250
Datei, die Sie wollen.

242
00:10:06,250 --> 00:10:08,240
Ich falsch schreiben immer Caesar.

243
00:10:08,240 --> 00:10:11,730
Aber Sie sicherstellen möchten,
da es eine ausführbare,

244
00:10:11,730 --> 00:10:14,210
TI dot Flash, so dass
bedeutet du gehst

245
00:10:14,210 --> 00:10:19,240
zu laufen CSI wirst du auszuführen sind
diese Dateien entweder mit dem Debugger.

246
00:10:19,240 --> 00:10:19,910
Ok.

247
00:10:19,910 --> 00:10:22,885
Also, Sie das tun, erhalten Sie
diese Art von Kauderwelsch.

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
Es ist nur alles über Debugger.

250
00:10:25,750 --> 00:10:28,200
Sie haben nicht wirklich zu
Sorgen über es jetzt.

251
00:10:28,200 --> 00:10:31,460
Und wie Sie sehen, dieses haben wir
offene Pars, BIP, in der Nähe Pars,

252
00:10:31,460 --> 00:10:34,690
und nur irgendwie aussieht
unsere Befehlszeile, oder?

253
00:10:34,690 --> 00:10:37,010
>> Also, was wir wollen do--
SO, das erste, was

254
00:10:37,010 --> 00:10:39,570
ist, dass wir wählen möchten
ein Ort, um sie zu brechen.

255
00:10:39,570 --> 00:10:42,332
So gibt es eine Fehler
in diesem Caesar Programm

256
00:10:42,332 --> 00:10:44,290
dass ich vorstellen, dass
wir werden es herausfinden.

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
Was es tut, ist es die Eingabe erfolgt
Barfoo in Großbuchstaben, und aus irgendeinem Grund

259
00:10:56,350 --> 00:11:01,950
es nicht A. ändern Er lässt nur
sie allein, alles andere ist richtig,

260
00:11:01,950 --> 00:11:03,980
aber der zweite Buchstabe
A bleibt unverändert.

261
00:11:03,980 --> 00:11:07,120
Also, wir werden versuchen,
herauszufinden, warum das so ist.

262
00:11:07,120 --> 00:11:10,440
Also, das erste, was Sie in der Regel
tun wollen, wann immer Sie auf GDB starten

263
00:11:10,440 --> 00:11:12,010
ist herauszufinden, wo es zu brechen.

264
00:11:12,010 --> 00:11:14,956
>> So Caesar ist ein ziemlich kurzes Programm.

265
00:11:14,956 --> 00:11:16,330
Wir haben nur eine Funktion, nicht wahr?

266
00:11:16,330 --> 00:11:18,520
Was war unsere Funktion in Caesar?

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
Es gibt nur eine Funktion, Main oder?

269
00:11:24,350 --> 00:11:26,490
Main ist eine Funktion
für alle Programme.

270
00:11:26,490 --> 00:11:29,230
Wenn Sie nicht über Haupt, könnte ich
Seien Sie ein wenig besorgt gerade jetzt,

271
00:11:29,230 --> 00:11:31,000
aber ich hoffe, Sie alle Haupt drin hatte.

272
00:11:31,000 --> 00:11:34,150
Also, was wir tun können, ist, dass wir
nur brechen Main, einfach so.

273
00:11:34,150 --> 00:11:35,190
So heißt es, OK.

274
00:11:35,190 --> 00:11:37,430
Wir setzen unsere Haltepunkt dort.

275
00:11:37,430 --> 00:11:42,870
>> So, jetzt ist die Sache zu erinnern Caesar
nimmt ein Kommandozeilenparameter rechts

276
00:11:42,870 --> 00:11:45,150
und wir haben nicht das in der noch nicht fertig.

277
00:11:45,150 --> 00:11:47,560
Also, was Sie tun, ist, wenn
Sie tatsächlich gehen zu laufen

278
00:11:47,560 --> 00:11:51,540
das Programm, jedes Programm, das Sie
in GDB läuft, die Befehlszeile muss

279
00:11:51,540 --> 00:11:55,010
Argumente, du bist zur Eingabe gehen
beim ersten Ausführen starten.

280
00:11:55,010 --> 00:11:59,280
Also, in diesem Fall, wir tun
Führen Sie mit einem Schlüssel von drei.

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
Und es wird tatsächlich beginnen.

283
00:12:02,040 --> 00:12:08,480
>> Also, wenn Sie hier sehen, haben wir
Wenn RC nicht gleich 2 ist.

284
00:12:08,480 --> 00:12:12,210
Also, wenn euch alle
die Datei, die ich schickte up

285
00:12:12,210 --> 00:12:15,100
Sie sehen, dass das ist, wie die
erste Zeile unserer Hauptfunktion, oder?

286
00:12:15,100 --> 00:12:17,890
Es ist zu überprüfen, ob wir
die richtige Anzahl von Argumenten.

287
00:12:17,890 --> 00:12:20,620
Also, wenn Sie sich fragen,
wenn RC korrekt ist,

288
00:12:20,620 --> 00:12:23,250
Sie können etwas wie Print RC tun.

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC zwei ist, das ist
was wir erwartet hatten, nicht wahr?

291
00:12:28,640 --> 00:12:32,010
>> Also, können wir gehen nächstes
und weiter durch.

292
00:12:32,010 --> 00:12:33,200
So haben wir einige Schlüssel dort.

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
Und wir können Sie ausdrucken unser Schlüssel
um sicherzustellen, dass ist richtig.

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
Interessant.

297
00:12:39,500 --> 00:12:41,210
Nicht ganz das, was wir erwartet hatten.

298
00:12:41,210 --> 00:12:44,810
Also, eine Sache zu erkennen,
mit GDB Auch ist

299
00:12:44,810 --> 00:12:49,000
dass es nicht, bis Sie wirklich getroffen
Als nächstes, dass die Linie, die Sie gerade gesehen

300
00:12:49,000 --> 00:12:50,720
tatsächlich ausgeführt wird.

301
00:12:50,720 --> 00:12:53,870
So, in diesem Fall Key
wurde noch nicht zugeordnet.

302
00:12:53,870 --> 00:12:57,050
Also, ist Key einige Müll Wert
dass Sie sehen auf der Unterseite befindet.

303
00:12:57,050 --> 00:13:03,680
Negative $ 120-- --Es eine Milliarde
und etwas seltsame Dinge richtig?

304
00:13:03,680 --> 00:13:05,340
Es ist nicht der Schlüssel, der uns erwartet.

305
00:13:05,340 --> 00:13:10,720
Aber wenn wir getroffen Weiter, und dann werden wir
versuchen und Print-Taste, es ist drei.

306
00:13:10,720 --> 00:13:11,710
>> Alle sehen, dass?

307
00:13:11,710 --> 00:13:13,780
Also, wenn Sie etwas zu bekommen
dass Sie wie sie sind, zu warten.

308
00:13:13,780 --> 00:13:15,540
Dies ist völlig
falsch, und ich weiß nicht,

309
00:13:15,540 --> 00:13:20,150
wie dies geschehen würde, weil alles was ich will
tun müssen, ist eine Nummer, eine Variable,

310
00:13:20,150 --> 00:13:22,900
versuchen schlagen nächstes versuchen Druck
es wieder, und sehen, ob das funktioniert.

311
00:13:22,900 --> 00:13:27,830
Weil es nur geht, um auszuführen und
etwas, nachdem Sie tatsächlich zuweisen

312
00:13:27,830 --> 00:13:29,340
Treffer nächster.

313
00:13:29,340 --> 00:13:30,336
Sinnvoll, alle?

314
00:13:30,336 --> 00:13:30,836
Uh huh?

315
00:13:30,836 --> 00:13:33,220
>> Sprecher 2: Wenn Sie zufällig
Zahlen, was bedeutet das?

316
00:13:33,220 --> 00:13:34,790
>> Sprecher 1: Es ist nur zufällig.

317
00:13:34,790 --> 00:13:35,710
Es ist nur Müll.

318
00:13:35,710 --> 00:13:38,320
Es ist nur etwas, das Ihre
Computer nach dem Zufallsprinzip vergeben.

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
Cool.

321
00:13:40,220 --> 00:13:45,760
So, jetzt können wir durch bewegen, und so
Jetzt haben wir diese Klartext GetString.

322
00:13:45,760 --> 00:13:48,600
Also, lassen Sie mich nur vorstellen, was
wird passieren, wenn wir getroffen Next hier.

323
00:13:48,600 --> 00:13:51,320
Unsere GDB Art verschwindet, oder?

324
00:13:51,320 --> 00:13:55,720
Das ist, weil GetString
wird nun die Ausführung, nicht wahr?

325
00:13:55,720 --> 00:14:01,460
Also, als wir sahen, Klartext ist gleich
GetString, offene Pars und Pars,

326
00:14:01,460 --> 00:14:04,380
und wir schlagen nächstes hat, dass
eigentlich jetzt ausgeführt.

327
00:14:04,380 --> 00:14:06,580
Also, es wartet
uns zur Eingabe etwas.

328
00:14:06,580 --> 00:14:13,560
>> Also, wir fahren nach Eingang geht unsere Nahrung, die
ist, was es in Ermangelung wie gesagt

329
00:14:13,560 --> 00:14:18,020
und sagt nur, dass es
beendet die Ausführung, dass der geschlossene

330
00:14:18,020 --> 00:14:19,980
Klammer bedeutet, es ist
Verlassen entlastet wird.

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
So können wir Treffer nächster, und jetzt, wie ich bin
sicher, Sie alle sind von Caesar vertraut,

333
00:14:25,420 --> 00:14:27,260
das ist, was ist diese Linie tun.

334
00:14:27,260 --> 00:14:32,030
Es ist für Int I gleich 0, N gleich
Strlen, Klartext, und dann

335
00:14:32,030 --> 00:14:33,960
I kleiner als n, I, und, und.

336
00:14:33,960 --> 00:14:35,210
Was ist diese Schleife tun?

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
Öffnen Sie Ihre Nachricht.

339
00:14:39,160 --> 00:14:39,770
Cool.

340
00:14:39,770 --> 00:14:41,330
Also, lassen Sie uns beginnen zu tun.

341
00:14:41,330 --> 00:14:47,210
>> Also, sollten diese Bedingung
entsprechen, für unsere erste?

342
00:14:47,210 --> 00:14:52,250
Wenn es ein B, es ist Klartext I. Wir
erhalten Sie Informationen über unsere Einheimischen.

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
Also, ich Null, und wenn sechs, die
wir erwarten, und unsere wichtigsten ist drei.

345
00:14:57,970 --> 00:14:59,227
Alle, die Sinn machen, oder?

346
00:14:59,227 --> 00:15:01,310
Diese Zahlen sind alle
genau, was sie sein sollte.

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
Also, summen?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Ich habe
Zufallszahlen für meine.

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
Sprecher 1: Nun, wir können --wir check--
kann etwa, dass in einem zweiten chatten.

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
Aber man sollte immer diese.

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
Also, wenn wir eine Kapital
B für unsere erste,

356
00:15:20,130 --> 00:15:22,080
Dieser Zustand sollte es zu fangen, oder?

357
00:15:22,080 --> 00:15:27,120
Also, wenn wir getroffen nächstes sehen wir
dass dieses Falls tatsächlich ausführt.

358
00:15:27,120 --> 00:15:29,220
Denn wenn Sie mitlesen
entlang in Ihrem Code,

359
00:15:29,220 --> 00:15:33,460
diese Linie hier, wo Klartext I
Mit diesem Rechen ersetzt,

360
00:15:33,460 --> 00:15:35,720
nur ausgeführt, wenn die If
Bedingung ist richtig oder?

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB ist nur zu zeigen,
Dinge, die tatsächlich ausgeführt werden.

363
00:15:40,240 --> 00:15:45,140
Also, wenn dies Wenn Bedingung nicht erfüllt wurde, ist es
gerade dabei, in die nächste Zeile springen.

364
00:15:45,140 --> 00:15:46,540
OK?

365
00:15:46,540 --> 00:15:48,510
So haben wir das.

366
00:15:48,510 --> 00:15:51,171
Diese Halterung bedeutet, es ist
entlastet wird jetzt geschlossen.

367
00:15:51,171 --> 00:15:52,420
Also, es geht wieder von vorne anfangen.

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
Einfach so.

370
00:15:56,280 --> 00:15:59,120
So, dass wir Informationen zu erhalten
über unsere Einheimischen hier,

371
00:15:59,120 --> 00:16:02,575
und wir sehen, dass unsere erste
Brief, rechts geändert?

372
00:16:02,575 --> 00:16:05,150
Es ist jetzt ein E, wie es sein sollte.

373
00:16:05,150 --> 00:16:07,360
So können wir weiter auf.

374
00:16:07,360 --> 00:16:08,500
>> Und wir haben dieses Kontroll.

375
00:16:08,500 --> 00:16:09,916
Und diese Prüfung sollte funktionieren, oder?

376
00:16:09,916 --> 00:16:12,570
Es ist A. Es sollte geändert werden
drei Buchstaben nach vorn.

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
Aber wenn Sie, wir merken
bekommen etwas anderes.

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
Also in diesem Fall hier, fing es
, und so diese Zeile ausgeführt wird,

381
00:16:22,860 --> 00:16:28,620
die unsere B. modifiziert
Aber im hier vorliegenden Fall

382
00:16:28,620 --> 00:16:32,860
wir, dass es einfach übersprungen es,
und ging auf die [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
So etwas ist da los.

384
00:16:34,660 --> 00:16:37,780
Was das erzählt, ist, dass,
wir wissen, dass es hier zu fangen,

385
00:16:37,780 --> 00:16:39,200
aber es ist nicht.

386
00:16:39,200 --> 00:16:42,210
Kann jemand sehen, was unsere
Problem ist in dieser Zeile?

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
Es ist eine sehr kleine Sache.

389
00:16:46,969 --> 00:16:48,510
Und man konnte auch auf den Code schauen.

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
Es ist auch line-- vergessen, was Linie ist es
in sind-- aber es ist in der [unverständlich].

392
00:16:54,940 --> 00:16:55,480
Ja?

393
00:16:55,480 --> 00:16:58,639
>> Lautsprecher 4: Es ist an der mehr als
Seite, wenn Sie es in dem Buch zu lesen.

394
00:16:58,639 --> 00:16:59,430
Sprecher 1: Genau.

395
00:16:59,430 --> 00:17:02,620
Also, der Debugger nicht sagen
Sie das, aber der Debugger

396
00:17:02,620 --> 00:17:05,880
könnten Sie auf eine Linie zu bekommen
dass Sie wissen, funktioniert nicht.

397
00:17:05,880 --> 00:17:09,319
Und manchmal, wenn vor allem
später im Semester, wenn

398
00:17:09,319 --> 00:17:12,910
Sie mit einem hundert, Umgang
hundert paar Zeilen Code, und Sie

399
00:17:12,910 --> 00:17:16,190
weiß nicht, wo es andernfalls,
dies ist eine gute Möglichkeit, es zu tun.

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
So fanden wir unsere Fehler.

402
00:17:18,989 --> 00:17:21,530
Sie können es in Ihrer Datei zu beheben,
und dann könnte man es erneut ausführen,

403
00:17:21,530 --> 00:17:23,029
und alles wäre perfekt.

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
Und die größte Sache ist
dies kann scheinen, wie, OK.

406
00:17:30,590 --> 00:17:31,090
Ja.

407
00:17:31,090 --> 00:17:31,370
Cool.

408
00:17:31,370 --> 00:17:32,744
Sie wussten, was Sie suchen.

409
00:17:32,744 --> 00:17:34,910
So wusste man, was zu tun ist.

410
00:17:34,910 --> 00:17:39,021
>> GDB kann super hilfsbereit, weil Sie sein
ausdrucken können all diese Dinge, die Sie

411
00:17:39,021 --> 00:17:39,520
wollte nicht.

412
00:17:39,520 --> 00:17:41,160
Es ist viel nützlicher als printf.

413
00:17:41,160 --> 00:17:43,440
Wie viele von euch nutzen
wie printf-Anweisungen

414
00:17:43,440 --> 00:17:46,200
um herauszufinden, wo ein Fehler war, nicht wahr?

415
00:17:46,200 --> 00:17:48,450
Also, mit diesem können Sie nicht tun
müssen immer wieder zurück,

416
00:17:48,450 --> 00:17:51,139
und gerne kommentieren in
Printf oder auskommentieren,

417
00:17:51,139 --> 00:17:52,930
und herauszufinden, was
sollten Sie den Druck.

418
00:17:52,930 --> 00:17:55,670
Diese eigentlich nur ermöglicht es Ihnen,
Schritt durch, ausdrucken Dinge

419
00:17:55,670 --> 00:18:00,000
wie du durchmachst, so können Sie
beobachten, wie sie in Echtzeit zu ändern,

420
00:18:00,000 --> 00:18:02,190
wie Ihr Programm ausgeführt wird.

421
00:18:02,190 --> 00:18:04,390
>> Und es sieht ein wenig dauern
etwas gewöhnungsbedürftig.

422
00:18:04,390 --> 00:18:07,850
Ich würde empfehlen, nur irgendwie
des Seins ein wenig frustriert mit ihr

423
00:18:07,850 --> 00:18:08,930
für jetzt.

424
00:18:08,930 --> 00:18:13,450
Wenn Sie eine Stunde über die verbringen
nächste Woche lernen, wie man GDB verwenden,

425
00:18:13,450 --> 00:18:16,140
Sie sparen sich
so viel Zeit später.

426
00:18:16,140 --> 00:18:18,750
Und wörtlich. wir sagen
dies Menschen jedes Jahr,

427
00:18:18,750 --> 00:18:23,890
und ich erinnere mich, als ich die
Klasse, ich war wie, ich werde in Ordnung sein.

428
00:18:23,890 --> 00:18:24,700
Nein.

429
00:18:24,700 --> 00:18:27,030
Pset 6 kam auf und ich war
wie, Ich werde lernen

430
00:18:27,030 --> 00:18:29,500
wie GDB verwenden, weil ich nicht
wissen, was hier vor sich geht.

431
00:18:29,500 --> 00:18:32,940
>> Also, wenn Sie die Zeit so nehmen
verwenden Sie es auf kleinere Programme

432
00:18:32,940 --> 00:18:35,697
dass Sie sein wirst
Arbeiten an, wie die Arbeit

433
00:18:35,697 --> 00:18:37,530
durch so etwas wie
Visionäre, wie diese.

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
Oder wenn Sie zusätzliche Übung wollen, bin ich sicher
Ich könnte mit fehlerhafte Programme,

436
00:18:42,850 --> 00:18:45,300
für Sie debuggen, wenn Sie möchten.

437
00:18:45,300 --> 00:18:49,300
>> Aber wenn man nur etwas Zeit nehmen, um
daran gewöhnt, nur spielen, um mit ihm,

438
00:18:49,300 --> 00:18:50,550
es wird wirklich gute Dienste leisten.

439
00:18:50,550 --> 00:18:52,591
Und es ist wirklich eine der
die Dinge, die Sie gerade

440
00:18:52,591 --> 00:18:57,340
müssen versuchen, und sich die Hände schmutzig
mit, bevor Sie wirklich verstehen.

441
00:18:57,340 --> 00:19:02,090
Ich wirklich nur verstanden es einmal
Ich musste Debug Dinge mit ihm,

442
00:19:02,090 --> 00:19:08,170
und es ist viel schöner, eine Vorstellung davon haben,
wie man eher früher als später zu debuggen.

443
00:19:08,170 --> 00:19:08,850
Ok.

444
00:19:08,850 --> 00:19:09,625
Cool.

445
00:19:09,625 --> 00:19:12,960
Ich weiß, das ist eine Art, wie
ein Crash-Kurs in GDB,

446
00:19:12,960 --> 00:19:16,400
und ich werde auf jeden Fall funktionieren auf immer
diese zu größeren nächste Mal freuen.

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
Cool.

449
00:19:18,280 --> 00:19:20,390
>> Also, wenn wir gehen zurück zu unseren Powerpoint.

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
Wird das funktionieren?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
Awh.

454
00:19:30,210 --> 00:19:31,101
Ja.

455
00:19:31,101 --> 00:19:31,600
Ok.

456
00:19:31,600 --> 00:19:35,480
Also, wenn Sie jemals brauchen einem
diese wiederum gibt es die Liste.

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
So Binary Search, die jeder
erinnert sich an den großen Schauspiel David

459
00:19:40,830 --> 00:19:42,259
Ripping Telefon-Bücher in zwei Hälften.

460
00:19:42,259 --> 00:19:44,050
Ich glaube nicht wirklich das
Telefon-Bücher mehr,

461
00:19:44,050 --> 00:19:46,530
denn wie, wo wollen Sie
bekommen Telefon-Bücher in diesen Tagen?

462
00:19:46,530 --> 00:19:48,220
Ich weiß wirklich nicht,.

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
Die binäre Suche.

465
00:19:50,590 --> 00:19:52,464
Erinnert sich noch jemand
wie Binäre Suche funktioniert?

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
Wer überhaupt?

468
00:19:55,220 --> 00:19:56,325
Ja?

469
00:19:56,325 --> 00:19:58,283
Lautsprecher 5: Sie wissen, wann
Sie bei der die Hälfte aussehen

470
00:19:58,283 --> 00:20:01,146
es würde, basierend auf dem,
und der anderen Hälfte loszuwerden.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER1 Genau.

472
00:20:01,896 --> 00:20:06,290
Also, Binäre Suche, es ist irgendwie A--
--wir gerne nennen es teilen und zu erobern.

473
00:20:06,290 --> 00:20:09,170
Also, was du tun wirst ist
Sie in der Mitte zu suchen,

474
00:20:09,170 --> 00:20:11,990
und Sie werden sehen, ob es passt
was Sie suchen.

475
00:20:11,990 --> 00:20:15,420
Und wenn es das nicht tut, dann Sie versuchen,
herauszufinden, ist es werde gelassen werden

476
00:20:15,420 --> 00:20:16,450
die Hälfte oder die rechte Hälfte.

477
00:20:16,450 --> 00:20:19,325
Also, das könnte sein, wenn Sie suchen
auf etwas, das alphabetisiert ist,

478
00:20:19,325 --> 00:20:20,720
Sie sehen, oh.

479
00:20:20,720 --> 00:20:22,750
Hat Allison vor M gekommen?

480
00:20:22,750 --> 00:20:23,250
Ja.

481
00:20:23,250 --> 00:20:25,030
Also, wir sind zu gehen
Blick auf die erste Hälfte.

482
00:20:25,030 --> 00:20:26,450
>> Oder es könnte, wie mit Zahlen.

483
00:20:26,450 --> 00:20:28,830
Alles, was du kannst
vergleichen kann sortiert werden.

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
Sie können binäre Suche weiter verwenden.

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
Also, jemand erinnern diese
Grafik oder was das ist?

488
00:20:37,455 --> 00:20:39,520
Es ist Asymptotische Komplexität.

489
00:20:39,520 --> 00:20:42,830
Also, dieser Graph nur
beschreibt, wie lange es

490
00:20:42,830 --> 00:20:46,230
Sie gelangen auf ein Problem zu lösen, wie
Sie die Anzahl der Dinge, zu erhöhen

491
00:20:46,230 --> 00:20:47,090
dass Sie verwenden.

492
00:20:47,090 --> 00:20:51,260
>> Also, wir haben N, die lineare Zeit ist.

493
00:20:51,260 --> 00:20:54,560
Wenn N als zwei, die leicht ist
besser, wächst noch super schnell.

494
00:20:54,560 --> 00:20:58,360
Und dann haben wir Einloggen, was ist
was wir als Binary Search.

495
00:20:58,360 --> 00:21:03,630
Wenn wir feststellen, wie Ihr Problem
wird viel und viel größer,

496
00:21:03,630 --> 00:21:06,600
die Zeit, die Sie, es zu lösen
nicht wirklich so viel zu erhöhen.

497
00:21:06,600 --> 00:21:09,010
Es ist wie vergleichbare
hier am Anfang.

498
00:21:09,010 --> 00:21:10,060
Du bist wie, OK.

499
00:21:10,060 --> 00:21:13,000
Alles hier ist nicht wirklich
Gleichgültig, welches wir verwenden,

500
00:21:13,000 --> 00:21:16,220
aber Sie bekommen bis zu einer Million, eine Milliarde.

501
00:21:16,220 --> 00:21:20,010
Du versuchst, some-- --you're finden
versucht, eine Nadel im Heuhaufen zu finden.

502
00:21:20,010 --> 00:21:21,550
>> Ich denke, dieses Problem soll.

503
00:21:21,550 --> 00:21:25,850
Sie möchten diese Komplexität nicht
linear, da für alles, was Sie

504
00:21:25,850 --> 00:21:30,049
wissen Ihre gonna werden durch die Suche
jede einzelne Nadel, was von Heu,

505
00:21:30,049 --> 00:21:31,340
versucht, für Ihre Nadel aussehen.

506
00:21:31,340 --> 00:21:34,730
Und das ist nicht zu Spaß meiner Meinung nach.

507
00:21:34,730 --> 00:21:35,500
Ich mag schnell.

508
00:21:35,500 --> 00:21:36,620
Ich mag effizient.

509
00:21:36,620 --> 00:21:40,450
Und als fleißige Studenten Sie
Jungs sind, weißt du intelligenter zu arbeiten,

510
00:21:40,450 --> 00:21:43,010
nicht härter Typ Sache, wie Sie
können bis diese Algorithmen.

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> Also, wir gehen zu Fuß
durch nur ein kleines Beispiel.

513
00:21:47,910 --> 00:21:51,090
Ich glaube, Sie Jungs haben sollte
eine Hand auf Binäre Suche,

514
00:21:51,090 --> 00:21:54,352
aber falls jemand ein wenig ist
Fuzzy, möchte es zu verstärken,

515
00:21:54,352 --> 00:21:56,310
wir werden einfach gehen
durch ein Beispiel hier.

516
00:21:56,310 --> 00:21:59,490
Also suchen wir nach, wenn auf der Suche
das Array enthält sieben.

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> Also, erste, was wir tun, ist
schauen Sie in der Mitte, oder?

519
00:22:06,010 --> 00:22:09,340
Und auch du gehst zu codierenden bist
Binäre Suche in nur einer Sekunde.

520
00:22:09,340 --> 00:22:11,310
Also, es wird Spaß machen.

521
00:22:11,310 --> 00:22:13,710
Also haben wir in der Suche
Mitte kleine Arrays 3.

522
00:22:13,710 --> 00:22:15,501
Enthält 3 gleich 7?

523
00:22:15,501 --> 00:22:16,000
Nicht.

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
Es ist sechs.

526
00:22:19,550 --> 00:22:21,480
So ist es weniger als
oder mehr als sieben?

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
Weniger als.

529
00:22:23,960 --> 00:22:24,570
Ja.

530
00:22:24,570 --> 00:22:25,170
Nice job Jungs.

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
Ich fühle Ich mag ich sollte
haben Süßigkeiten, weil ich

533
00:22:27,360 --> 00:22:29,460
wollen, um es in den Werften werfen.

534
00:22:29,460 --> 00:22:30,270
Es ist, was ich in der nächsten Woche zu tun.

535
00:22:30,270 --> 00:22:31,436
Es wird euch scharf zu halten.

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> Also, wir wegwerfen, dass
ersten Hälfte, nicht wahr?

538
00:22:34,690 --> 00:22:35,670
es war weniger als.

539
00:22:35,670 --> 00:22:39,325
wir wissen, dass alles, was
auf dieser linken Seite

540
00:22:39,325 --> 00:22:41,700
wird kleiner sein als das, was
wir eigentlich suchen.

541
00:22:41,700 --> 00:22:43,491
Also, es gibt keine Notwendigkeit,
achten Sie darauf.

542
00:22:43,491 --> 00:22:45,120
Vergiss es einfach.

543
00:22:45,120 --> 00:22:48,720
So, jetzt schauen wir auf unserer rechten Seite,
und wir freuen in der Mitte dort,

544
00:22:48,720 --> 00:22:50,510
und jetzt ist es neun.

545
00:22:50,510 --> 00:22:55,510
So, 9 ist-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Größer als das, was wir sind
auf der Suche nach, oder?

547
00:22:57,470 --> 00:22:59,860
Also, wir gehen zu werfen
alles weg nach rechts.

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
So.

550
00:23:01,940 --> 00:23:03,700
Nun sind alle verließen wir mit einer ist.

551
00:23:03,700 --> 00:23:07,760
So prüfen wir, das ist man sich, was
wir suchen? es ist.

552
00:23:07,760 --> 00:23:08,970
Wir fanden, was wir wollten.

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
Also wir sind fertig.

555
00:23:11,690 --> 00:23:12,550
Bilineare suchen.

556
00:23:12,550 --> 00:23:15,740
>> Und wenn Sie, wir bemerken,
hatte sieben Eingänge gibt.

557
00:23:15,740 --> 00:23:24,320
Es dauerte nur wie drei Mal,
aber wenn Sie wie ein Milliarden tut,

558
00:23:24,320 --> 00:23:28,190
Sie Jungs wissen, wie viele Schritte es würde
nehmen, wenn wir hatten vier Milliarden Dinge?

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
Irgendwelche Vermutungen?

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
Es ist 32.

563
00:23:33,960 --> 00:23:37,110
32 Schritte, um etwas zu finden
in vier Milliarden

564
00:23:37,110 --> 00:23:39,650
Elementanordnung, weil von Zweierpotenzen.

565
00:23:39,650 --> 00:23:43,550
Also zwei ist bis 32, ist zu vier Milliarden Euro.

566
00:23:43,550 --> 00:23:50,430
>> So ziemlich verrückt, wie du bist immer noch in
wie eine ziemlich kleine Anzahl von Schritten

567
00:23:50,430 --> 00:23:52,650
etwas in finden
vier Milliarden Elementen.

568
00:23:52,650 --> 00:23:55,730
Also in diesem Sinne, wir sind
werde diesen Code

569
00:23:55,730 --> 00:23:58,950
so euch kann eigentlich
Art sehen, wie das funktioniert.

570
00:23:58,950 --> 00:24:01,520
Alles klar, so euch kann codieren.

571
00:24:01,520 --> 00:24:04,100
Ich werde euch lassen
sprechen für ein wenig.

572
00:24:04,100 --> 00:24:07,970
Lernen Sie Menschen um Sie wissen, das ist,
was jemand wollte von den letzten Abschnitt.

573
00:24:07,970 --> 00:24:10,280
>> So lernen Sie die Menschen um Sie herum wissen.

574
00:24:10,280 --> 00:24:11,305
Sprechen Sie für ein wenig.

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
Und alles, was ich von dir will
Jungs ist jetzt nur

577
00:24:15,730 --> 00:24:17,575
versuchen, einen Umriss eines Pseudocodes zu erstellen.

578
00:24:17,575 --> 00:24:18,075
OK?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
Whoa.

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
Alles was ich will von euch ist du bist
gerade dabei, in diesem Fall, während zu füllen.

583
00:24:29,520 --> 00:24:32,170
So habe ich diese oberen gesetzt
und die untere Grenze der

584
00:24:32,170 --> 00:24:35,250
stellen den Anfang
und Ende unserer Array.

585
00:24:35,250 --> 00:24:40,440
Und Sie gehen, um tatsächlich
Schleife durch und herauszufinden,

586
00:24:40,440 --> 00:24:42,470
was wir in dieser while-Schleife zu tun.

587
00:24:42,470 --> 00:24:45,810
>> Also, wenn Sie heraus out-- kann ich
ein Hauch sind-- was sind die Fälle

588
00:24:45,810 --> 00:24:46,640
dass wir hier?

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
Also, wenn Sie herausfinden, die wollen
Fällen werden wir solche Pseudo

591
00:24:51,560 --> 00:24:53,350
und dann werden wir tatsächlich codieren.

592
00:24:53,350 --> 00:24:55,330
Und es geht um sein, ich
denke, hoffentlich ist das dann

593
00:24:55,330 --> 00:24:56,788
ein wenig leichter, als Sie erwarten.

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
Denn es ist nicht so viel Code,
tatsächlich, das ist wirklich cool.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> STUDENT: [unverständlich]?

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
LEHRER: Ja.

601
00:25:37,650 --> 00:25:38,595
Es war etwas
in der Mitte zu finden.

602
00:25:38,595 --> 00:25:39,552
>> STUDENT: So können wir dafür verwenden.

603
00:25:39,552 --> 00:25:39,770
Ok.

604
00:25:39,770 --> 00:25:40,603
>> LEHRER: Perfect.

605
00:25:40,603 --> 00:25:42,950
Also das ist das erste, was wir tun müssen.

606
00:25:42,950 --> 00:25:44,330
So finden Sie die Mitte.

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
Großartig.

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
So haben Sie eine Vorstellung davon haben, wie wir
tatsächlich in der Mitte mit dem Code finden?

611
00:25:55,010 --> 00:25:55,980
>> STUDENT: Ja.

612
00:25:55,980 --> 00:25:57,000
n mehr als 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
LEHRER: Also n über 2.

615
00:25:59,500 --> 00:26:05,170
So eine Sache zu erinnern ist, dass
Ihre oberen und unteren Grenzen ändern.

616
00:26:05,170 --> 00:26:08,110
Wir halten gende den Teil
des Arrays wir uns auf.

617
00:26:08,110 --> 00:26:11,970
So n über 2 funktioniert nur,
für das erste, was wir tun.

618
00:26:11,970 --> 00:26:17,810
So nehmen oberen und unteren berücksichtigt,
wie könnten wir diese mittlere Element zu bekommen?

619
00:26:17,810 --> 00:26:20,640
Weil wir wollen, dass die Mitte
zwischen oberen und unteren, nicht wahr?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> STUDENT: [unverständlich].

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> LEHRER: Also müssen wir einen Mittelweg.

625
00:26:28,080 --> 00:26:32,730
Und es wird oberen zzgl unteren als 2 sein.

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
Genial.

628
00:26:35,690 --> 00:26:36,570
Dort gehen wir.

629
00:26:36,570 --> 00:26:37,280
Eine Zeile nach unten.

630
00:26:37,280 --> 00:26:38,560
Ihr seid auf dem Weg.

631
00:26:38,560 --> 00:26:41,400
So, jetzt, da wir unsere
Mitte, was wollen wir tun?

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
Nur im Allgemeinen.

634
00:26:45,900 --> 00:26:47,734
Sie müssen nicht, um es zu codieren.

635
00:26:47,734 --> 00:26:48,335
Ja.

636
00:26:48,335 --> 00:26:49,210
STUDENT: [unverständlich]?

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
LEHRER: So ist es und weil Sie
Ermitteln des Durchschnitts zwischen den beiden

639
00:27:10,310 --> 00:27:10,810
von ihnen.

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
Also, wenn Sie von ihnen denken, als eine Art
der von den Seiten zunimmt,

642
00:27:17,370 --> 00:27:21,640
denken Sie darüber nach, wie Sie nähern
der mittlere, möchten Sie so.

643
00:27:21,640 --> 00:27:27,150
Also, wenn Sie auf beiden Seiten die waren
Mitte, und wir haben wie 5 und 7.

644
00:27:27,150 --> 00:27:31,440
Wenn Sie sie Sie addieren
erhalten 12, um 2 dividieren Sie ist 6.

645
00:27:31,440 --> 00:27:33,726
>> Manchmal ist es schwer,
erklären, warum das funktioniert,

646
00:27:33,726 --> 00:27:35,600
aber wenn Sie durcharbeiten
ein Beispiel manchmal,

647
00:27:35,600 --> 00:27:37,962
es wird Ihnen helfen, herauszufinden, ob
es sollte plus oder minus ist.

648
00:27:37,962 --> 00:27:38,846
Ja.

649
00:27:38,846 --> 00:27:40,830
>> STUDENT: [unverständlich]
genau in der Mitte

650
00:27:40,830 --> 00:27:43,950
wenn sie einen Fall, wo hatten
es gibt eine Menge von kleineren Zahlen

651
00:27:43,950 --> 00:27:45,860
und wie einer großen Zahl?

652
00:27:45,860 --> 00:27:49,750
>> LEHRER: Also alles was Sie brauchen
ist die Mitte des Arrays.

653
00:27:49,750 --> 00:27:53,010
Also, wenn Sie ein paar kleine Zahlen hatten
und dann ein wirklich große Anzahl

654
00:27:53,010 --> 00:27:54,799
am Ende, spielt es keine Rolle.

655
00:27:54,799 --> 00:27:56,840
Alles was zählt ist, dass
sie, die Sie gerade sortiert

656
00:27:56,840 --> 00:27:59,339
möchte in der Mitte aussehen
das Array, weil du bist immer noch

657
00:27:59,339 --> 00:28:00,700
Schneiden Sie Ihr Problem in der Hälfte.

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
Cool.

660
00:28:03,680 --> 00:28:06,430
So, jetzt, dass wir die
Mitte, was machen wir als nächstes?

661
00:28:06,430 --> 00:28:07,150
>> STUDENT: Vergleichen.

662
00:28:07,150 --> 00:28:08,150
LEHRER: Die zu vergleichen.

663
00:28:08,150 --> 00:28:11,670
So vergleichen mittleren bis value_wanted.

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
Cool.

666
00:28:15,160 --> 00:28:17,950
So können Sie bis hier sehen wir
dieser Wert wollen wir hier oben.

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
Vergessen, das ist ein Array.

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
Also Mitte bezieht sich auf den Index.

671
00:28:26,970 --> 00:28:29,785
So wollen wir Werte von Mitte zu tun.

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
Vergessen Sie nicht, wenn Sie wollen
zu, Doppel equals vergleichen.

674
00:28:35,650 --> 00:28:38,250
Sie tun einzigen gleich du bist
gerade dabei, es neu zuzuweisen,

675
00:28:38,250 --> 00:28:41,090
und natürlich ist es
gehen, um den Wert Sie wollen.

676
00:28:41,090 --> 00:28:42,300
Also tun Sie das nicht.

677
00:28:42,300 --> 00:28:44,350
>> Also, wir werden sehen, ob
die Werte in der Mitte

678
00:28:44,350 --> 00:28:46,460
ist gleich dem Wert, den wir wollen.

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
Vergessen Sie nicht Ihre Zahnspange.

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox sollten weggehen.

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
Also, was tun wir in diesem Fall tun?

685
00:28:56,200 --> 00:28:59,360
Wenn es was wollen wir zurückkehren wollen?

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
Wir versuchen zu sagen.

688
00:29:02,626 --> 00:29:03,440
>> STUDENT: Drucken aus.

689
00:29:03,440 --> 00:29:05,314
>> LEHRER: Nun, wir
wollen nicht ausdrucken.

690
00:29:05,314 --> 00:29:08,220
Das ist also ein bool hier, so dass wir
want true oder false zurück.

691
00:29:08,220 --> 00:29:12,280
Wir sagen, ist diese Nummer
ein [? RRA? ?] Also, wenn es heißt,

692
00:29:12,280 --> 00:29:13,788
wir bringen Sie ihn einfach wahr.

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
Wenn ich kann wahr buchstabieren.

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> STUDENT: Warum würden Sie nicht Null zurück?

697
00:29:20,805 --> 00:29:22,930
LEHRER: so konnte man
Null zurück, wenn man wollte.

698
00:29:22,930 --> 00:29:26,780
Aber in diesem Fall, weil
unsere Funktion gibt einen bool,

699
00:29:26,780 --> 00:29:28,962
wir brauchen, um zurückzukehren entweder wahr oder falsch.

700
00:29:28,962 --> 00:29:30,920
STUDENT: Wenn man
sagen Booleschen Ausdruck,

701
00:29:30,920 --> 00:29:33,450
können Sie es gleich falsch gesetzt?

702
00:29:33,450 --> 00:29:39,860
Wie, wenn ich sagen will, wenn diese Bedingung
nicht erfüllt ist, wie ist Ober gleich falsch.

703
00:29:39,860 --> 00:29:42,332
Wird es, wenn Sie nur zu verstehen
legte falsche auf der anderen Seite?

704
00:29:42,332 --> 00:29:43,040
LEHRER: Yeah.

705
00:29:43,040 --> 00:29:44,820
Also eigentlich, wenn Sie
immer etwas zu tun

706
00:29:44,820 --> 00:29:49,600
wie ist oberen oder niedriger ist,
die wahr oder falsch zurück

707
00:29:49,600 --> 00:29:53,850
und es ist eigentlich schlechter Stil,
sagen wir gleich gleich wahr oder equals

708
00:29:53,850 --> 00:29:54,840
gleich falsch.

709
00:29:54,840 --> 00:30:00,210
Sie wollen dieses Ergebnis nutzen
als sich als Ihr Scheck.

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
Nicht das, was ich wollte.

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
Das ist, was ich wollte.

714
00:30:09,240 --> 00:30:13,205
So im Fall der du fragst
über so etwas wie speichern Sie diese in c.

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> Wenn wir also int main (void)
und so etwas wie dieses.

717
00:30:25,150 --> 00:30:31,922
Und Sie haben, wenn obere ist
einiger Eingangs und du bist

718
00:30:31,922 --> 00:30:33,630
gefragt, ob Sie tun können
so etwas?

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
Richtig?

721
00:30:35,679 --> 00:30:37,470
Student: Ich habe versucht
es zu tun [unverständlich].

722
00:30:37,470 --> 00:30:38,450
Denn wenn it's--

723
00:30:38,450 --> 00:30:39,200
LEHRER: Richtig.

724
00:30:39,200 --> 00:30:41,197
Sie wollen dies falsch sein, oder?

725
00:30:41,197 --> 00:30:41,780
STUDENT: Ja.

726
00:30:41,780 --> 00:30:45,960
LEHRER: Also in diesem Fall, dass Sie
wollen, dass es ausgeführt wird, wenn es nicht wahr ist.

727
00:30:45,960 --> 00:30:50,510
Also die coole Sache, die Sie tun, gibt es diese.

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
Also denken Sie daran Ausrufe
Punkt negiert Dinge?

730
00:30:55,650 --> 00:30:58,270
Er sagt, [unverständlich] bedeutet nicht.

731
00:30:58,270 --> 00:31:03,590
Also, wenn wir uns nur
dieser Teil hier, würden Sie

732
00:31:03,590 --> 00:31:05,740
sagen, dass ausgewertet wird
falsch, wie Sie es wollen.

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
Nicht falsch ist wahr was
bedeutet dies auszuführen.

735
00:31:09,880 --> 00:31:11,037
Ist das sinnvoll?

736
00:31:11,037 --> 00:31:11,620
STUDENT: Ja.

737
00:31:11,620 --> 00:31:12,453
LEHRER: Awesome.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
Ok.

740
00:31:14,300 --> 00:31:16,330
So dass wir nur zurückkehren konnte
in diesem Fall wahr.

741
00:31:16,330 --> 00:31:20,357
So, jetzt haben wir zwei andere haben
Fälle, in diesem Fall.

742
00:31:20,357 --> 00:31:21,565
Was sind unsere beiden anderen Fällen?

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
Lassen Sie uns gerade tun es auf diese Weise.

745
00:31:32,900 --> 00:31:40,660
Lassen Sie uns also mit anderen starten
wenn Werte in der Mitte

746
00:31:40,660 --> 00:31:43,230
kleiner als der Wert, den wir wollen.

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
Also unsere Wert in der Mitte weniger ist
als der Wert, den wir suchen.

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> Also die verpflichtet Sie tun
denke, wir aktualisieren möchten?

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
Obere oder untere?

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
Ober?

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
Also die Seite des Arrays
werden wir auf der Suche an?

757
00:32:06,470 --> 00:32:07,500
>> STUDENT: Je niedriger.

758
00:32:07,500 --> 00:32:09,750
>> LEHRER: Wir werden wir
auf der Suche auf der linken Seite.

759
00:32:09,750 --> 00:32:11,120
So else if wenig Wert geringer ist.

760
00:32:11,120 --> 00:32:14,730
Also Ihr Mittelwert hier
weniger als das, was wir wollen.

761
00:32:14,730 --> 00:32:17,202
Also, um das nehmen wir wollen
rechten Seite unser Angebot.

762
00:32:17,202 --> 00:32:18,910
Also sind wir zu gehen
aktualisieren unsere untere Schranke.

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
Also werden wir unsere Unter zuweisen.

765
00:32:23,020 --> 00:32:25,221
Und was denken Sie, niedriger sein sollte?

766
00:32:25,221 --> 00:32:26,304
STUDENT: Der mittlere Wert?

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
LEHRER: Also das mittlere value--

769
00:32:28,820 --> 00:32:30,136
STUDENT: Plus 1.

770
00:32:30,136 --> 00:32:31,010
LEHRER: --plus 1.

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
Kann mir jemand sagen, warum
wir haben, dass plus 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Kein Wert?]
ist gleich zu ihm.

774
00:32:35,730 --> 00:32:36,120
>> LEHRER: Richtig.

775
00:32:36,120 --> 00:32:38,661
Weil wir wissen bereits, dass
unsere mittlere Wert ist ungleich

776
00:32:38,661 --> 00:32:42,750
es und wir wollen es ausschließen möchten
von allen nachfolgenden Such.

777
00:32:42,750 --> 00:32:46,360
Wenn Sie vergessen, dass plus 1, dieses
auf unbestimmte Zeit gefallen Schleife.

778
00:32:46,360 --> 00:32:49,620
Und Sie werden nur in ein gefangen werden
Endlosschleife und dann wirst du segfault

779
00:32:49,620 --> 00:32:50,370
und die Dinge schlecht.

780
00:32:50,370 --> 00:32:54,780
Also immer darauf achten, dass Sie nicht
einschließlich dem Wert, den Sie gerade

781
00:32:54,780 --> 00:32:55,380
sah.

782
00:32:55,380 --> 00:32:58,530
Also kümmern wir uns, dass mit einem plus 1.

783
00:32:58,530 --> 00:33:04,840
>> So, jetzt haben wir unsere letzte Bedingung
die ich immer für die Sicherheit willen

784
00:33:04,840 --> 00:33:12,664
Sie können hier überprüfen, sonst, wenn der Wert bei
der mittlere größer als der Wert ist

785
00:33:12,664 --> 00:33:13,163
wir wollen.

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
Das heißt, wir wollen
die linke Hälfte.

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
So das man werden wir aktualisieren?

790
00:33:23,260 --> 00:33:23,760
Ober.

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
Und was ist dies einer werde gleich?

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
Naher minus 1, da,
natürlich wollen wir

795
00:33:33,690 --> 00:33:38,370
um sicherzustellen, dass wir nicht
Suche in diesem mittleren Wert wieder.

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
Und dann haben wir es.

798
00:33:45,110 --> 00:33:45,610
Das ist es.

799
00:33:45,610 --> 00:33:46,820
Das ist alles, binäre Suche ist.

800
00:33:46,820 --> 00:33:48,190
Es ist nicht so schlecht, oder?

801
00:33:48,190 --> 00:33:51,590
Es ist wie 10 Zeilen
Code mit weißen Raum.

802
00:33:51,590 --> 00:33:57,510
So sehr mächtig, sehr nützlich, werden Sie
verwenden es in einem Ihrer späteren psets.

803
00:33:57,510 --> 00:33:59,360
Vielleicht nicht dieses, aber später.

804
00:33:59,360 --> 00:34:00,670
So lernen.

805
00:34:00,670 --> 00:34:01,510
Liebe es.

806
00:34:01,510 --> 00:34:02,980
Es wird Ihnen gut zu behandeln.

807
00:34:02,980 --> 00:34:05,370
Also weiß jemand welche haben
Fragen über binäre Suche?

808
00:34:05,370 --> 00:34:06,196
Ja.

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Spielt es eine Rolle
ob Ihr n gerade oder ungerade?

810
00:34:09,840 --> 00:34:10,750
>> LEHRER: No.

811
00:34:10,750 --> 00:34:18,150
Weil wir es gegossen, um die Mitte als
ein int, wird es nur abzuschneiden.

812
00:34:18,150 --> 00:34:21,600
So wird es eine ganze Zahl zu bleiben und es wird
schließlich durch alles zu sortieren.

813
00:34:21,600 --> 00:34:23,909
So müssen Sie nicht zu befürchten, dass.

814
00:34:23,909 --> 00:34:24,580
Jeder gut?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Genial.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
So bekam diese euch.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Slideshow.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
So wie wir redeten, ich weiß
David erwähnt Komplexität Laufzeiten.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Also im besten Fall ist es nur
ein, die wir konstante Zeit nennen.

825
00:34:50,340 --> 00:34:51,909
Kann mir jemand sagen, warum das so sein könnte?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Welche Art von Szenario würde das zur Folge haben?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> STUDENT: [unverständlich] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
LEHRER: Also das mittlere wobei der
erste Element, das wir kommen, oder?

833
00:35:03,830 --> 00:35:08,167
Also entweder eine Anordnung von einer oder
was auch immer wir für nur suchen

834
00:35:08,167 --> 00:35:09,750
passiert genau in der Mitte sein.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Also das ist unsere beste Fall.

837
00:35:13,380 --> 00:35:17,540
Sie erhalten in echte Probleme, wahrscheinlich nicht
werde, dass oft zu erreichen [unverständlich].

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Was ist mit unseren schlimmsten Fall?

840
00:35:19,750 --> 00:35:21,270
Unsere schlimmsten Fall ist log n.

841
00:35:21,270 --> 00:35:25,360
Und daß, um mit der gesamten zu tun
Potenzen von zwei, was ich darüber gesprochen.

842
00:35:25,360 --> 00:35:30,930
>> Also im schlimmsten Fall würde es bedeuten,
dass wir, um das Array zu fällen

843
00:35:30,930 --> 00:35:33,270
bis es ein Element von einem.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Also mussten wir es in der Hälfte fällen
so oft wie wir nur konnte.

846
00:35:38,930 --> 00:35:41,430
Das ist, warum es ist log n, weil
Sie halten gerade durch zwei geteilt.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Also Annahmen, Dinge, die Sie
müssen wissen, ob Sie überhaupt

849
00:35:45,830 --> 00:35:48,050
werde eine binäre Suche verwenden.

850
00:35:48,050 --> 00:35:50,680
Ihre Elemente müssen sortiert werden.

851
00:35:50,680 --> 00:35:53,890
Sie müssen sortiert werden, weil
das ist der einzige Weg,

852
00:35:53,890 --> 00:35:57,060
kann wissen, ob Sie in der Lage sind
daran zu werfen Hälfte.

853
00:35:57,060 --> 00:36:00,260
>> Wenn Sie diese wirre Tasche hatte
von Zahlen und du sagst,

854
00:36:00,260 --> 00:36:05,380
OK, ich werde die Mitte zu überprüfen
Nummer und die Nummer Ich suche nach

855
00:36:05,380 --> 00:36:08,510
ist geringer als die, ich bin gerade dabei
willkürlich werfen die Hälfte.

856
00:36:08,510 --> 00:36:11,130
Sie würden nicht wissen, ob Ihre
Zahlen in dieser anderen Hälfte.

857
00:36:11,130 --> 00:36:12,655
Ihre Liste muss sortiert werden.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Wie gut, dies auch sein mag
gehen voran ein wenig,

860
00:36:16,560 --> 00:36:18,360
aber Sie müssen mit wahlfreiem Zugriff haben.

861
00:36:18,360 --> 00:36:21,940
Sie müssen in der Lage zu sein, nur
gehen Sie zu diesem mittleren Element.

862
00:36:21,940 --> 00:36:25,110
Wenn Sie durchlaufen haben
durch etwas

863
00:36:25,110 --> 00:36:28,630
oder es dauert zusätzliche Schritte
um zu diesem mittleren Element zu bekommen,

864
00:36:28,630 --> 00:36:31,750
es ist nicht log n mehr, weil
Sie hinzufügen mehr Arbeit hinein.

865
00:36:31,750 --> 00:36:34,800
Und das wird ein wenig zu machen
mehr Sinn in zwei Wochen,

866
00:36:34,800 --> 00:36:37,950
aber ich nur irgendwie wollte Vorwort
geben euch eine Vorstellung von dem, was

867
00:36:37,950 --> 00:36:38,999
zu kommen.

868
00:36:38,999 --> 00:36:40,790
Aber diejenigen, die beiden sind
Wichtige Annahmen

869
00:36:40,790 --> 00:36:44,804
dass Sie für eine binäre Liste.

870
00:36:44,804 --> 00:36:45,720
Stellen Sie sicher, es ist sortiert.

871
00:36:45,720 --> 00:36:47,920
Das ist die große für
euch jetzt.

872
00:36:47,920 --> 00:36:52,170
Und dass wir in zu gehen
der Rest unserer Sorten.

873
00:36:52,170 --> 00:36:56,444
Also vier sorts-- Blase,
Insertion, Auswahl und Zusammenführen.

874
00:36:56,444 --> 00:36:57,485
Sie sind alle ziemlich cool.

875
00:36:57,485 --> 00:37:02,860
Wenn euch entscheiden, CS 124 zu nehmen,
Sie über alle möglichen Arten zu lernen.

876
00:37:02,860 --> 00:37:07,575
Und wenn Sie ein XKCD Fan bist, gibt
ist eine wirklich coole Comic über

877
00:37:07,575 --> 00:37:11,530
wie wirklich unwirksam Sorten, die ich
empfehlen Sie gehen, zu betrachten.

878
00:37:11,530 --> 00:37:16,170
Einer von ihnen ist wie Panik Art, die
ist wie, oh nein, zurück zufälligen Anordnung.

879
00:37:16,170 --> 00:37:16,991
Shutdown-System.

880
00:37:16,991 --> 00:37:17,490
Zu verlassen.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
So geeky Humor ist immer gut.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Also hat jemand erinnern Art
der wie nur eine allgemeine Vorstellung

885
00:37:25,750 --> 00:37:27,810
wie Bubble-Sort arbeitet.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Sie erinnern sich?

888
00:37:32,155 --> 00:37:32,755
>> STUDENT: Ja.

889
00:37:32,755 --> 00:37:33,970
>> LEHRER: Go for it.

890
00:37:33,970 --> 00:37:38,980
>> Student: Sie durchmachen und
wenn es größer ist, dann haben Sie die beiden tauschen.

891
00:37:38,980 --> 00:37:39,820
>> LEHRER: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Genau.

893
00:37:40,564 --> 00:37:41,730
Sie haben also nur durch Iteration.

894
00:37:41,730 --> 00:37:43,050
Sie überprüfen zwei Zahlen.

895
00:37:43,050 --> 00:37:46,510
Wenn die davor ist größer
als die danach

896
00:37:46,510 --> 00:37:50,230
einfach tauschen sie damit in
auf diese Weise alle höheren Nummern

897
00:37:50,230 --> 00:37:54,990
Blase gegen Ende der Liste
und all die niedrigeren Zahlen Blase nach unten.

898
00:37:54,990 --> 00:37:59,355
>> Hat er euch die kühle
Sound-Effekt Sortier Video?

899
00:37:59,355 --> 00:38:00,480
Es ist irgendwie cool.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
So wie Robert sagte nur, den Algorithmus
dass Sie nur Schritt durch die Liste,

902
00:38:05,200 --> 00:38:07,930
Vertauschen der benachbarten Werten
wenn sie nicht in Ordnung.

903
00:38:07,930 --> 00:38:10,975
Und dann nur immer wiederholen
bis Sie nicht machen keine Swaps.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Also nicht schlecht, oder?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Also müssen wir nur ein kleines Beispiel hier.

908
00:38:16,319 --> 00:38:18,360
Es wird also zu sortieren
sie in aufsteigender Reihenfolge.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Wenn wir also über den ersten zu gehen
Zeit, durch acht freuen wir

911
00:38:23,470 --> 00:38:26,880
und sechs sind offensichtlich nicht
in Ordnung ist, tauschen wir sie.

912
00:38:26,880 --> 00:38:27,985
>> So sehen Sie die nächste.

913
00:38:27,985 --> 00:38:29,430
Acht und vier nicht in Ordnung.

914
00:38:29,430 --> 00:38:30,450
Tauschen sie.

915
00:38:30,450 --> 00:38:32,530
Und dann acht und zwei, tauschen sie.

916
00:38:32,530 --> 00:38:33,470
Dort gehen wir.

917
00:38:33,470 --> 00:38:39,519
Also nach dem ersten Durchgang, die Sie
wissen, dass Ihre größte Zahl

918
00:38:39,519 --> 00:38:41,810
wird sich den ganzen Weg sein
an der Spitze, weil es einfach

919
00:38:41,810 --> 00:38:44,210
werde ständig
größer als alles andere

920
00:38:44,210 --> 00:38:46,810
und es nur geht zu brodeln
bis hin zu dem Ende gibt.

921
00:38:46,810 --> 00:38:48,226
Macht das Sinn macht, alle?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Also schauen wir auf unserer zweiten Durchgang.

926
00:38:53,920 --> 00:38:54,980
Sechs und vier, Schalter.

927
00:38:54,980 --> 00:38:55,920
Sechs und zwei, Schalter.

928
00:38:55,920 --> 00:38:58,700
Und jetzt haben wir ein paar Dinge in Ordnung.

929
00:38:58,700 --> 00:39:02,240
So wird für jeden Pass, dass wir
machen durch unsere gesamte Liste,

930
00:39:02,240 --> 00:39:06,320
wir wissen, dass wie so vielen Zahlen
am Ende wird sortiert worden sind.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Also machen wir einen dritten Durchgang,
Das ist ein Swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Und dann auf unserer vierten
passieren, wir haben null Slots.

935
00:39:15,910 --> 00:39:18,570
Und so wissen wir, dass unsere
Array sortiert wurde.

936
00:39:18,570 --> 00:39:20,900
>> Und das ist die große
Sache mit Bubble-Sort.

937
00:39:20,900 --> 00:39:23,720
Wir wissen, dass, wenn wir
null Swaps, dass

938
00:39:23,720 --> 00:39:26,497
bedeutet, dass alles
steht in völligem Ordnung.

939
00:39:26,497 --> 00:39:27,580
Es ist eine Art, wie wir zu überprüfen.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Also wir gehen aber auch auf Blasen codieren
Art, die auch nicht so schlimm.

942
00:39:36,480 --> 00:39:38,120
Keiner von ihnen sind so schlecht.

943
00:39:38,120 --> 00:39:40,210
Ich weiß, sie ein wenig beängstigend erscheinen kann.

944
00:39:40,210 --> 00:39:42,124
Ich weiß, als ich
die Klasse, auch wenn ich

945
00:39:42,124 --> 00:39:44,290
wurde die Klasse für den Unterricht
das erste Mal im letzten Jahr,

946
00:39:44,290 --> 00:39:46,165
Ich war wie, wie mache ich das?

947
00:39:46,165 --> 00:39:48,540
Es macht Sinn, in der Theorie, sondern
wie wollen wir eigentlich tun?

948
00:39:48,540 --> 00:39:51,420
Deshalb möchte ich auch zu Fuß gehen
durch Code mit euch hier.

949
00:39:51,420 --> 00:39:54,915
So habe ich eine Pseudocode
für euch dieses Mal.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Also einfach bedenken Sie dies als
Wir sind dabei, den Übergang über.

952
00:39:58,970 --> 00:40:04,210
Also haben wir etwas Zähler,
verfolgt die Spuren unserer Swaps,

953
00:40:04,210 --> 00:40:08,370
denn wir müssen sicherstellen, dass
dass wir prüfen, ob.

954
00:40:08,370 --> 00:40:11,830
Und wir durchlaufen das gesamte Array
wie wir gerade getan mit diesem Beispiel.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Wenn das Element vor größer als
das Element nach dem, wo wir sind,

957
00:40:17,325 --> 00:40:20,760
wir tauschen sie und wir erhöhen unsere
Zähler, denn sobald wir tauschen,

958
00:40:20,760 --> 00:40:23,850
wollen wir lassen unsere Gegen wissen.

959
00:40:23,850 --> 00:40:26,247
Haben Sie noch Fragen gibt?

960
00:40:26,247 --> 00:40:27,580
Etwas scheint lustig hier.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: Haben Sie die Zähler auf Null gesetzt
jedes Mal, wenn Sie durch die Schleife zu gehen?

963
00:40:32,350 --> 00:40:34,339
Weißt du nicht weitermachen
zurück, jedes Mal Null?

964
00:40:34,339 --> 00:40:35,505
LEHRER: Nicht unbedingt.

965
00:40:35,505 --> 00:40:39,710
Also, was passiert ist, dass wir hier durch zu gehen.

966
00:40:39,710 --> 00:40:43,830
So zu tun, während, denken Sie daran, diese
wird einmal ohne fehler auszuführen.

967
00:40:43,830 --> 00:40:46,480
Also es geht um den Satz
Zähler gleich Null ist,

968
00:40:46,480 --> 00:40:48,070
dann, es wird durch Iteration.

969
00:40:48,070 --> 00:40:50,590
Wie es durch läuft,
es wird Gegen aktualisieren.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Da es Zähler aktualisiert, wenn es fertig ist,
wenn es das Ende der Anordnung erreicht hat,

972
00:40:56,900 --> 00:41:00,830
wenn unsere Liste noch nicht sortiert,
Zähler wird aktualisiert wurden.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> So dann prüft er den Zustand und
sagt, OK, ist Zähler größer als Null ist.

975
00:41:07,150 --> 00:41:09,290
Wenn es ist, es wieder tun.

976
00:41:09,290 --> 00:41:14,340
Sie wollen, so dass, wenn Sie zurückgesetzt
durchlaufen, ist Zähler gleich Null.

977
00:41:14,340 --> 00:41:18,240
Wenn Sie über einen sortierten gehen
Array, ändert sich nichts,

978
00:41:18,240 --> 00:41:21,355
dies fehlschlägt, und Sie
Rückkehr der sortierten Liste.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Macht das Sinn macht?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: Es könnte in ein wenig.

983
00:41:26,356 --> 00:41:27,147
LEHRER: OK.

984
00:41:27,147 --> 00:41:28,980
Wenn es irgendwelche anderen
Frage, die aufkommt.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Ja.

987
00:41:30,680 --> 00:41:33,760
>> STUDENT: Was würde die Funktion
für das Vertauschen der Elemente?

988
00:41:33,760 --> 00:41:36,900
>> LEHRER: So können wir eigentlich schreiben
dass, wenn wir gehen, um nun mit der rechten.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Also in diesem Sinne, ist Alison gehen
zurück zum Gerät einzuschalten.

992
00:41:42,155 --> 00:41:43,080
Es wird Spaß machen.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Und wir haben unsere schöne
Bubble-Sort Sache hier.

995
00:41:47,390 --> 00:41:50,800
So habe ich schon Radfahren
durch die Anordnung.

996
00:41:50,800 --> 00:41:53,030
Wir haben unsere Swaps
gleich Null sind.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
So zum Tauschen benachbarter wollen wir
Elemente, wenn sie nicht in Ordnung.

999
00:41:58,440 --> 00:42:03,020
Das erste, was wir brauchen, um
Sie wird durch unsere Arrays durchlaufen.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> So wie Sie denken, wir könnten
durchlaufen unser Angebot?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Wir haben für und i gleich 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Wir wollen i kleiner sein
als n minus 1 minus k.

1006
00:42:22,454 --> 00:42:23,870
Und das werde ich in einem zweiten zu erklären.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Das ist also eine Optimierung hier, wo,
erinnere mich, wie ich sagte, nach jedem Durchlauf

1009
00:42:32,830 --> 00:42:36,655
durch das Array wir
wissen, dass was auch immer on-- ist

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> So nach einem Durchgang wir
wissen, dass diese sortiert.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Nach zwei Durchgängen wir wissen
dass dies alles sortiert.

1014
00:42:50,060 --> 00:42:52,750
Nach drei Durchgängen wir
weiß, das ist sortiert.

1015
00:42:52,750 --> 00:42:55,620
So, wie ich bin Iteration
durch hier das Array,

1016
00:42:55,620 --> 00:43:01,090
wird es macht Sie nur gehen
durch das, was wir wissen, ist unsortiert.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Das ist nur eine Optimierung.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Man könnte es naiv einfach schreiben
Iteration durch alles,

1021
00:43:08,210 --> 00:43:09,970
es nur länger dauern würde.

1022
00:43:09,970 --> 00:43:12,470
Mit diesem Vier-Schleife ist es
nur eine nette Optimierung

1023
00:43:12,470 --> 00:43:18,460
weil wir wissen, dass nach jeder vollen
Iteration hier durch die Anordnung,

1024
00:43:18,460 --> 00:43:24,050
wie jedes volle Schleife hier, wir wissen,
daß man mehrere dieser Elemente

1025
00:43:24,050 --> 00:43:25,760
wird am Ende sortiert werden.

1026
00:43:25,760 --> 00:43:28,294
>> Also haben wir nicht haben, um über diejenigen zu kümmern.

1027
00:43:28,294 --> 00:43:29,710
Macht das Sinn macht, alle?

1028
00:43:29,710 --> 00:43:30,950
Das kühle kleine Trick?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
So dass in diesem Fall, wenn
wir durchlaufen,

1031
00:43:37,270 --> 00:43:50,590
wir wissen, dass wir, wenn überprüfen möchten
Array n und n + 1 sind in Ordnung.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
Ok.

1034
00:43:53,559 --> 00:43:54,600
Also hier ist der Pseudocode.

1035
00:43:54,600 --> 00:43:57,540
Wir wollen, wenn überprüfen Array n
und n plus 1 sind in Ordnung.

1036
00:43:57,540 --> 00:43:59,520
Also, was können wir denn da?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Es wird etwas bedingter sein.

1039
00:44:03,120 --> 00:44:04,220
Es wird eine, wenn.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Wenn Array n
weniger als Array n plus 1.

1041
00:44:07,066 --> 00:44:07,816
LEHRER: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Nun, kleiner oder größer als.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Größer als.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Dann wollen wir sie zu tauschen.

1047
00:44:17,620 --> 00:44:18,570
Genau.

1048
00:44:18,570 --> 00:44:23,570
So, jetzt zu dem, was ist das bekommen wir
Mechanismus für den Tausch?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Also gingen wir durch diese kurz,
eine Art von Swap-Funktion in der vergangenen Woche.

1051
00:44:28,137 --> 00:44:29,595
Erinnert sich noch jemand, wie es funktioniert?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
So können wir nicht nur neu zuweisen ihnen, nicht wahr?

1054
00:44:34,950 --> 00:44:36,640
Weil einer von ihnen verloren geht.

1055
00:44:36,640 --> 00:44:41,696
Wenn wir die A gleich B und dann B
ist gleich A, die alle eine plötzliche beide

1056
00:44:41,696 --> 00:44:43,150
sind nur gleich B.

1057
00:44:43,150 --> 00:44:45,720
>> Also, was wir tun müssen, ist, dass wir
haben eine temporäre Variable, die ist

1058
00:44:45,720 --> 00:44:49,055
werde einer von uns, während halten
wir sind in den Prozess der Swapping.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Also, was wir haben, ist wir einige int haben
Temp gleich zu-- können Sie es zuordnen

1061
00:44:56,464 --> 00:44:59,130
zu welcher sie benutzen möchten, gerade
stellen Sie sicher, Sie verfolgen es-- halten

1062
00:44:59,130 --> 00:45:01,840
so in diesem Fall, ich bin zu gehen
weisen Sie ihn Array n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Also, das wird halten unabhängig
Wert in diesem zweiten Block ist

1065
00:45:07,674 --> 00:45:08,590
dass wir auf der Suche.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Und dann wir tun können ist, dass wir gehen können
vor und weisen Array n plus 1,

1068
00:45:13,240 --> 00:45:14,990
weil wir wissen, dass wir
haben diese gespeicherten Wert.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Dies ist auch einer der großen
things-- Ich weiß nicht, ob jemand von euch

1071
00:45:19,270 --> 00:45:23,780
hatte Probleme, wo, wenn Sie zwei Schalter
Codezeilen plötzlich Dinge funktionierten.

1072
00:45:23,780 --> 00:45:25,880
Sortieren ist in CS sehr wichtig.

1073
00:45:25,880 --> 00:45:29,450
So stellen Sie sicher Diagramm
Dinge aus, wenn möglich

1074
00:45:29,450 --> 00:45:31,230
darüber, was tatsächlich passiert.

1075
00:45:31,230 --> 00:45:34,256
So, jetzt sind wir zu gehen
neu zuweisen Array n plus 1,

1076
00:45:34,256 --> 00:45:36,005
weil wir wissen, dass wir
haben diese gespeicherten Wert.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Und wir können das zu Array zuweisen
n oder in diesem Fall Array i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Zu viele Variablen.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
Ok.

1083
00:45:55,470 --> 00:46:01,500
So, jetzt haben wir neu zugewiesen habe Array i
plus 1 auf gleichen, was in Array i.

1084
00:46:01,500 --> 00:46:08,240
Und jetzt können wir zurückgehen und
zuweisen Array i zu was?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Anyone?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> STUDENT: 10.

1089
00:46:14,010 --> 00:46:14,680
>> LEHRER: 10.

1090
00:46:14,680 --> 00:46:15,180
Genau.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Und eine letzte Sache.

1093
00:46:18,640 --> 00:46:21,840
Wenn wir sie jetzt ausgelagert,
was müssen wir tun?

1094
00:46:21,840 --> 00:46:23,740
Was ist die eine Sache,
das wird uns sagen

1095
00:46:23,740 --> 00:46:27,542
wenn wir jemals dieses Programm zu beenden?

1096
00:46:27,542 --> 00:46:29,250
Was sagt uns, dass wir
eine sortierte Liste?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Wenn wir keine Swaps, die nicht durchführen, oder?

1099
00:46:33,750 --> 00:46:36,900
Wenn Swaps gleich ist
Null am Ende von diesem.

1100
00:46:36,900 --> 00:46:42,975
Also, wenn Sie eine Swap durchführen, wie wir
gerade hier getan hat, wollen wir Swaps aktualisieren.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Und ich weiß, gab es eine
Frage früher über können Sie

1103
00:46:47,210 --> 00:46:49,689
verwenden Null oder Eins statt
von wahr oder falsch.

1104
00:46:49,689 --> 00:46:50,980
Und das ist, was dieser tut hier.

1105
00:46:50,980 --> 00:46:52,750
Also das sagt, wenn nicht Swaps.

1106
00:46:52,750 --> 00:47:01,310
Also, wenn Swaps null ist, was ich immer ist--
meine Wahrheiten und meine Falschen durcheinander.

1107
00:47:01,310 --> 00:47:03,960
Wir wollen uns zu bewerten
auf true und es ist nicht.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Also, wenn es Null ist, dann ist es falsch.

1110
00:47:09,630 --> 00:47:12,560
Wenn Sie es mit einem negieren
[? Knall?] wird es wahr.

1111
00:47:12,560 --> 00:47:13,975
Also dann ist diese Linie führt.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Wahrheiten und falsche und
Nullen und Einsen verrückt.

1114
00:47:17,370 --> 00:47:20,690
Nur, wenn Sie langsam gehen
durch sie wird es Sinn machen.

1115
00:47:20,690 --> 00:47:23,320
Aber das ist, was dieses kleine
Stück Code hier tut.

1116
00:47:23,320 --> 00:47:26,490
Also das überprüft,
haben wir getan, keine Swaps.

1117
00:47:26,490 --> 00:47:30,054
Also, wenn es etwas anderes
Null, es geht um falsch zu sein

1118
00:47:30,054 --> 00:47:31,970
und die ganze Sache ist
werde erneut ausführen.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> STUDENT: Was bedeutet Pause machen?

1123
00:47:36,000 --> 00:47:38,990
>> LEHRER: gerade Pause
bricht man aus der Schleife.

1124
00:47:38,990 --> 00:47:41,570
So dass in diesem Fall wäre es
genau wie das Programm beenden

1125
00:47:41,570 --> 00:47:43,828
und Sie nur würde
Ihre sortierte Liste.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
LEHRER: Es tut mir leid?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Weil wir vorher
Gebraucht geschrieben 1 überschrieben Null

1130
00:47:52,110 --> 00:47:54,170
zu präsentieren, wenn
das funktionieren wird oder nicht.

1131
00:47:54,170 --> 00:47:54,878
>> LEHRER: Yeah.

1132
00:47:54,878 --> 00:47:56,410
So können Sie Null oder 1 zurück.

1133
00:47:56,410 --> 00:47:58,950
In diesem Fall, weil wir nicht wirklich
etwas zu tun mit der Funktion,

1134
00:47:58,950 --> 00:48:00,150
wir wollen nur, dass es zu brechen.

1135
00:48:00,150 --> 00:48:02,680
Wir wissen nicht wirklich darum.

1136
00:48:02,680 --> 00:48:06,960
Brake ist auch gut, wenn
es ist für Ausbrechen verwendet

1137
00:48:06,960 --> 00:48:10,710
von vier Schleifen oder Bedingungen,
Sie wollen nicht zu halten Ausführen.

1138
00:48:10,710 --> 00:48:12,110
Es dauert einfach aus ihnen heraus.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Es ist ein bisschen wie ein Nuance Sache.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Ich fühle mich, als gäbe es
eine Menge von Hand einwirken,

1143
00:48:18,445 --> 00:48:19,740
wie du darüber bald lernen.

1144
00:48:19,740 --> 00:48:20,955
>> Aber Sie werden darüber bald lernen.

1145
00:48:20,955 --> 00:48:21,500
Ich verspreche.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
Ok.

1148
00:48:23,170 --> 00:48:24,840
So kann jeder bekommen hat Bubble Sort?

1149
00:48:24,840 --> 00:48:25,550
Nicht schlecht.

1150
00:48:25,550 --> 00:48:31,910
Durch eine Iteration, Swap Dinge mit ein
TEMP-Variable, und wir sind alle dort eingestellt?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Genial.

1153
00:48:34,080 --> 00:48:34,807
Ok.

1154
00:48:34,807 --> 00:48:35,765
Zurück zu den Powerpoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Alle Fragen im Allgemeinen
über diese so weit?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Cool.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> STUDENT: [unverständlich] int main Regel.

1162
00:48:45,279 --> 00:48:46,695
Haben Sie zu haben, dass für diese?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> LEHRER: So waren wir gerade auf der Suche
gerade bei der aktuellen Sortieralgorithmus.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Wenn Sie hatte es innerhalb
wie ein größeres Programm,

1167
00:48:56,350 --> 00:48:57,891
Sie würde einen int main irgendwo.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Je nachdem wo Sie
verwenden diesen Algorithmus,

1170
00:49:02,880 --> 00:49:05,860
es wäre festzustellen, was ist
von ihr zurück.

1171
00:49:05,860 --> 00:49:09,960
Aber für unseren Fall, wir sind strikt
schauen, wie funktioniert das eigentlich

1172
00:49:09,960 --> 00:49:11,300
durchlaufen ein Array.

1173
00:49:11,300 --> 00:49:12,570
So wissen wir nicht darum kümmern.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> So waren wir über die besten Fall reden und
Worst-Case-Szenarien für binäre Suche.

1176
00:49:19,830 --> 00:49:22,470
So ist es auch wichtig, zu tun
daß für jede der Arten.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Also, was denken Sie, ist das Schlimmste
Bei Laufzeit von Bubble Sort?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Ihr Jungs erinnern?

1181
00:49:30,700 --> 00:49:31,784
>> STUDENT: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
LEHRER: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Das heißt also, es gibt
n minus 1 Vergleiche.

1184
00:49:35,070 --> 00:49:40,060
So eine Sache zu realisieren ist,
dass bei der ersten Iteration,

1185
00:49:40,060 --> 00:49:43,360
wir durchmachen, vergleichen wir
diese two-- damit ist 1.

1186
00:49:43,360 --> 00:49:46,685
Diese zwei, drei, vier.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
So nach einer Iteration wir
bereits vier Vergleiche.

1189
00:49:55,050 --> 00:49:58,230
Wenn ich über Laufzeit und n reden.

1190
00:49:58,230 --> 00:50:04,680
N repräsentiert die Anzahl der Vergleiche
in Abhängigkeit davon, wie viele Elemente

1191
00:50:04,680 --> 00:50:05,570
wir haben.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> So durchlaufen wir, haben wir vier.

1194
00:50:08,860 --> 00:50:11,780
Das nächste Mal, wenn Sie wissen, dass wir nicht
muss sich darum kümmern.

1195
00:50:11,780 --> 00:50:15,140
Wir vergleichen diese beiden,
diese beiden, diese beiden,

1196
00:50:15,140 --> 00:50:20,050
und wenn wir nicht haben, dass die Optimierung
mit den vier Schleife, die ich schrieb,

1197
00:50:20,050 --> 00:50:22,750
Sie würden hier werden sowieso vergleichen.

1198
00:50:22,750 --> 00:50:26,170
Also Sie müssten
durch das Array laufen

1199
00:50:26,170 --> 00:50:34,380
und machen n Vergleiche n
Zeiten, da jedes Mal, wenn wir

1200
00:50:34,380 --> 00:50:36,670
laufen wir durch sie sort eine Sache.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Und jedes Mal, wenn wir durchlaufen
das Array, wir machen n Vergleiche.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Also unsere Laufzeit dafür ist
tatsächlich n quadriert, die

1205
00:50:46,330 --> 00:50:48,400
ist in viel schlechterem unserer
log Ende, denn das

1206
00:50:48,400 --> 00:50:51,965
bedeutet, wenn wir vier
Milliarden-Elemente, ist es

1207
00:50:51,965 --> 00:50:55,260
wird uns nehmen vier Milliarden
statt 32 quadriert.

1208
00:50:55,260 --> 00:51:01,240
Also nicht die beste Laufzeit,
aber für einige Dinge,

1209
00:51:01,240 --> 00:51:04,610
Sie wissen, wenn Sie innerhalb bist
ein bestimmter Bereich von Elementen

1210
00:51:04,610 --> 00:51:06,540
Bubble-Sort kann gut zu nutzen.

1211
00:51:06,540 --> 00:51:07,530
>> Ok.

1212
00:51:07,530 --> 00:51:12,290
So jetzt, was ist der beste Fall, Laufzeit?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
STUDENT: Zero?

1215
00:51:14,940 --> 00:51:16,420
Oder 1?

1216
00:51:16,420 --> 00:51:18,140
>> LEHRER: Also eins würde
sein ein Vergleich.

1217
00:51:18,140 --> 00:51:19,114
Richtig.

1218
00:51:19,114 --> 00:51:20,002
>> STUDENT: N minus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> LEHRER: Also, ja.

1221
00:51:22,320 --> 00:51:22,990
So n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Wann immer Sie ein Konzept, wie n
minus 1, neigen wir dazu, nur fallen sie ab

1223
00:51:26,510 --> 00:51:31,680
und wir einfach sagen, n, weil Sie
zu jedem der these-- jedem Paar zu vergleichen.

1224
00:51:31,680 --> 00:51:36,470
Es wäre also n minus 1, die wir
wir würden einfach sagen, etwa n.

1225
00:51:36,470 --> 00:51:39,280
Wenn Sie mit der Laufzeit zu tun haben,
alles in nahekommt.

1226
00:51:39,280 --> 00:51:43,860
Solange der Exponent
richtig, du bist ziemlich gut.

1227
00:51:43,860 --> 00:51:45,700
>> Das ist, wie wir damit umgehen.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
So, dass der beste Fall ist N, die
bedeutet, dass die Liste bereits sortiert ist,

1230
00:51:51,780 --> 00:51:54,320
und alles, was wir tun müssen, ist durchlaufen
und überprüfen Sie, dass es sortiert.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Cool.

1233
00:51:56,855 --> 00:51:57,355
In Ordnung.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
So wie Sie hier sehen, haben wir
müssen nur noch ein paar Grafiken.

1236
00:52:01,920 --> 00:52:02,660
So n quadriert.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Viel schlimmer als n wie wir sehen, und
viel, viel schlimmer als log 2n.

1240
00:52:09,730 --> 00:52:12,060
Und dann auch noch in protokoll protokolle erhalten Sie.

1241
00:52:12,060 --> 00:52:18,020
Und Sie nehmen 124, in erhalten Sie
wie Protokoll Stern, der wie verrückt ist.

1242
00:52:18,020 --> 00:52:20,172
Also, wenn Sie interessiert sind,
Lookup Protokoll star.

1243
00:52:20,172 --> 00:52:20,880
Es ist eine Art Spaß.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
So haben wir diese große Diagramm.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Nur ein Heads-up, das ein
wunderbaren Chart zu haben

1248
00:52:28,720 --> 00:52:31,350
für Ihre mittelfristige, weil wir
lange, Sie zu bitten, diese verdünnt.

1249
00:52:31,350 --> 00:52:36,090
Also nur ein Heads-up, habe dieses auf Ihrem
Halbzeit auf Ihrem schönen Spickzettel

1250
00:52:36,090 --> 00:52:36,616
da.

1251
00:52:36,616 --> 00:52:37,990
So dass wir nur sah Bubble Sort.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Schlimmsten Fall n quadriert, best case, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Und wir werden auf die anderen schauen.

1256
00:52:44,950 --> 00:52:47,940
>> Und wie Sie sehen, die nur können
eine, die wirklich gut tut

1257
00:52:47,940 --> 00:52:50,910
ist Mergesort, die wir, warum bekommen.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
So werden wir auf dem Sprung
nächste hier-- Auswahl sortieren.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Erinnert sich noch jemand, wie
Auswahl Art gearbeitet?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Go for it.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: Grundsätzlich durchlaufen
eine Ordnung und eine neue Liste.

1265
00:53:08,210 --> 00:53:11,001
Und so, wie Sie setzen Elemente sind
in, legte sie an der richtigen Stelle

1266
00:53:11,001 --> 00:53:11,750
in der neuen Liste.

1267
00:53:11,750 --> 00:53:14,040
>> LEHRER: Also das klingt
mehr wie Insertion Sort.

1268
00:53:14,040 --> 00:53:15,040
Aber du bist wirklich in der Nähe.

1269
00:53:15,040 --> 00:53:15,915
Sie sind sehr ähnlich.

1270
00:53:15,915 --> 00:53:17,440
Sogar ich sie manchmal gemischt.

1271
00:53:17,440 --> 00:53:18,981
Vor diesem Abschnitt Ich war wie, warten.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
Ok.

1274
00:53:20,630 --> 00:53:24,141
Also, was Sie wollen
tun, ist Selection Sort,

1275
00:53:24,141 --> 00:53:25,890
die Art, wie Sie denken können
darüber und die Art und Weise

1276
00:53:25,890 --> 00:53:30,140
Ich achte darauf, ich versuche nicht zu bekommen
sie auf, vermischt ist es durchgeht

1277
00:53:30,140 --> 00:53:33,280
und es wählt die
kleinste Zahl, und es

1278
00:53:33,280 --> 00:53:36,070
legt, dass am Anfang der Liste.

1279
00:53:36,070 --> 00:53:37,730
Es tauscht sie mit diesem ersten Punkt.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Sie haben tatsächlich ein Beispiel für mich.

1282
00:53:45,370 --> 00:53:46,540
Genial.

1283
00:53:46,540 --> 00:53:50,130
Also nur ein Weg, um von es-- Auswahl denken
sortieren, wählen Sie den kleinsten Wert.

1284
00:53:50,130 --> 00:53:51,940
Und wir sind zu gehen
durch ein Beispiel ausführen

1285
00:53:51,940 --> 00:53:55,320
dass ich denke, wird da helfen
Ich denke, Visuals immer helfen.

1286
00:53:55,320 --> 00:53:58,510
Also wir beginnen mit etwas
das ist völlig unsortiert.

1287
00:53:58,510 --> 00:54:00,730
Rot werden unsortiert sein,
grün sortiert werden.

1288
00:54:00,730 --> 00:54:02,190
Es wird alles Sinn machen in einer Sekunde.

1289
00:54:02,190 --> 00:54:08,950
>> So gehen wir durch, und wir durchlaufen
vom Anfang bis zum Ende.

1290
00:54:08,950 --> 00:54:12,320
Und wir sagen, OK, 2
unsere kleinste Zahl.

1291
00:54:12,320 --> 00:54:15,680
So werden wir 2 nehmen und wir werden
um es in den Vordergrund unserer Array bewegen

1292
00:54:15,680 --> 00:54:17,734
weil es das
kleinste Zahl, die wir haben.

1293
00:54:17,734 --> 00:54:19,150
Also das ist, was dies hier tun.

1294
00:54:19,150 --> 00:54:20,820
Es ist gerade dabei, diese beiden zu tauschen.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
So, jetzt haben wir eine sortierte haben
Teil und einem unsortierten Teil.

1297
00:54:25,450 --> 00:54:27,810
Und was ist gut daran zu erinnern,
über Selection Sort

1298
00:54:27,810 --> 00:54:30,690
ist, dass wir nur die Auswahl
aus dem unsortierten Teil.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Die sortierten Teil einfach in Ruhe lassen.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Woher weiß er, was ist
die kleinste ohne Vergleich

1303
00:54:38,452 --> 00:54:39,868
zu jedem anderen Wert in dem Array.

1304
00:54:39,868 --> 00:54:41,250
LEHRER: Es tut vergleichen.

1305
00:54:41,250 --> 00:54:42,041
Wir mögen es übersprungen.

1306
00:54:42,041 --> 00:54:43,850
Dies ist nur allgemeine insgesamt.

1307
00:54:43,850 --> 00:54:44,831
Ja.

1308
00:54:44,831 --> 00:54:47,205
Wenn wir den Code Ich bin zu schreiben
sicher, du wirst mehr zufrieden sein.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Aber Sie diese zunächst speichern
Element als kleinste.

1311
00:54:53,030 --> 00:54:56,110
Sie vergleichen und Sie
sagen, OK, es ist kleiner?

1312
00:54:56,110 --> 00:54:56,660
Ja.

1313
00:54:56,660 --> 00:54:57,460
Halten Sie es.

1314
00:54:57,460 --> 00:54:58,640
Hier ist es kleiner?

1315
00:54:58,640 --> 00:54:59,660
Nein?

1316
00:54:59,660 --> 00:55:02,510
>> Das ist Ihre kleinsten,
neu zuweisen, um sie Ihren Wert.

1317
00:55:02,510 --> 00:55:06,340
Und Sie werden viel glücklicher sein
wenn wir gehen durch den Code.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
So gehen wir durch, tauschen wir sie, so ist, dann
wir uns diese unsortierten Teil.

1320
00:55:13,970 --> 00:55:15,810
So werden wir drei auswählen.

1321
00:55:15,810 --> 00:55:18,890
Wir werden es an zu setzen bei
das Ende unserer sortierten Teils.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Und wir sind gerade dabei, weiterhin tun,
dass, das tun, und tun.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Also das ist unsere Art von Pseudo hier.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Wir werden es hier in einem zweiten Code oben.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Aber nur etwas zu Fuß
durch auf einem hohen Niveau.

1330
00:55:37,270 --> 00:55:40,275
Du wirst aus gehen
i gleich 0 bis n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Das ist ein weiterer Optimierung.

1333
00:55:43,530 --> 00:55:45,020
Sie nicht zu viel Sorgen.

1334
00:55:45,020 --> 00:55:46,620
So sagten Sie.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Als Jacob sagte, wie gehen wir
zu verfolgen, was unsere Mindest ist?

1337
00:55:54,406 --> 00:55:55,030
Wie können wir wissen?

1338
00:55:55,030 --> 00:55:57,060
Wir haben zum Vergleich
alles in unserer Liste.

1339
00:55:57,060 --> 00:55:59,600
>> Also mindestens gleich i.

1340
00:55:59,600 --> 00:56:03,870
Es ist einfach zu sagen in diesem Fall
der Index unserer Minimalwert.

1341
00:56:03,870 --> 00:56:07,660
Also, es wird durch Iteration
und es geht von j gleich i plus 1.

1342
00:56:07,660 --> 00:56:11,420
So wissen wir bereits, dass
das ist unser erstes Element.

1343
00:56:11,420 --> 00:56:13,240
Wir brauchen nicht, um es sich zu vergleichen.

1344
00:56:13,240 --> 00:56:16,970
So beginnen wir den Vergleich mit dem nächsten
eine, die ist, warum es i plus 1 bis n

1345
00:56:16,970 --> 00:56:20,110
minus 1, die ist
Ende des Arrays gibt.

1346
00:56:20,110 --> 00:56:25,090
Und wir, wenn Array an dem
j kleiner als Array min,

1347
00:56:25,090 --> 00:56:29,200
dann werden wir neu zuzuweisen, wo
unsere Mindestindizes ist.

1348
00:56:29,200 --> 00:56:37,470
>> Und wenn min nicht gleich i, wie
in denen wir waren hier zurück.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
So gerne, wenn wir zuerst tat dieses.

1351
00:56:41,790 --> 00:56:49,310
In diesem Fall wäre es am Start
Null, wäre es am Ende als zwei.

1352
00:56:49,310 --> 00:56:53,010
Also min würde nicht gleich i am Ende.

1353
00:56:53,010 --> 00:56:55,720
Das lässt uns wissen, dass
wir brauchen, um sie zu tauschen.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Ich fühle mich wie ein konkretes Beispiel
wird viel mehr als dieses zu helfen.

1356
00:57:00,470 --> 00:57:04,970
Also werde ich dieses oben Code mit euch
schon jetzt und ich denke, es wird besser sein.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Art in der Regel so, dass Arbeit
es ist oft besser, nur um sie zu sehen.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Also, was wir tun wollen, ist
wollen wir zuerst die kleinste

1361
00:57:17,280 --> 00:57:19,890
Element in seiner Position in der Anordnung.

1362
00:57:19,890 --> 00:57:21,280
Genau das, was Jacob sagte.

1363
00:57:21,280 --> 00:57:23,090
Sie müssen das irgendwie zu speichern.

1364
00:57:23,090 --> 00:57:25,900
Also werden wir hier starten
Iteration über das Array.

1365
00:57:25,900 --> 00:57:28,970
Wir werden sagen, es ist unsere
erste nur für den Anfang.

1366
00:57:28,970 --> 00:57:38,308
So werden wir int haben
kleinste gleich Array bei i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> So eine Sache zu bemerken, jede
Mal in dieser Schleife führt,

1369
00:57:45,050 --> 00:57:48,550
wir beginnen einen Schritt weiter entlang.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Wenn wir beginnen wir auf dieser.

1372
00:57:57,440 --> 00:58:00,840
Das nächste Mal, wenn wir durch Iteration,
wir an diesem einen Start

1373
00:58:00,840 --> 00:58:02,680
zugeordnet wird unsere kleinsten Wert.

1374
00:58:02,680 --> 00:58:10,450
So ist es sehr ähnlich zu Bubble-Sort
wenn wir wissen, daß nach einem Durchgang,

1375
00:58:10,450 --> 00:58:11,700
Dieses letzte Element wird sortiert.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Mit Selection Sort,
es ist genau das Gegenteil.

1378
00:58:15,120 --> 00:58:18,950
>> Bei jedem Durchgang, wissen wir, dass
Der erste wird sortiert.

1379
00:58:18,950 --> 00:58:21,360
Nach dem zweiten Durchlauf, der
zweite sortiert werden.

1380
00:58:21,360 --> 00:58:26,470
Und wie Sie mit den Schiebe Beispielen sahen,
unsere sortiert Teil wächst und wächst.

1381
00:58:26,470 --> 00:58:34,020
Also, indem Sie unsere kleinsten
Arrays i, alles was man tut

1382
00:58:34,020 --> 00:58:37,340
schränkt das, was
Wir sind am so suchen

1383
00:58:37,340 --> 00:58:40,164
um die Anzahl zu minimieren
Vergleiche die wir machen.

1384
00:58:40,164 --> 00:58:41,770
Ist das sinnvoll, um alle?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Haben Sie mich brauchen, um durch die ausgeführt
wieder langsamer oder mit anderen Worten?

1387
00:58:46,380 --> 00:58:47,180
Ich bin glücklich,.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
Ok.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Also sind wir die Speicherung der
Wert an dieser Stelle,

1392
00:58:55,540 --> 00:58:57,840
aber wir wollen auch, um den Index zu speichern.

1393
00:58:57,840 --> 00:59:01,010
Also wir gehen in den Laden
Position des kleinsten

1394
00:59:01,010 --> 00:59:02,770
eine, die gerade dabei ist, um i sein.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Jetzt so Jacob ist zufrieden.

1397
00:59:05,440 --> 00:59:06,870
Wir haben Dinge gespeichert.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Und jetzt müssen wir schauen durch
die unsortierten Teil des Arrays.

1400
00:59:11,870 --> 00:59:18,170
Also in diesem Fall diese
wäre unsere unsortiert.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Dies ist i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
Ok.

1405
00:59:26,210 --> 00:59:30,040
>> Also, was wir tun werden
wird zu einer Schleife.

1406
00:59:30,040 --> 00:59:32,066
Wann immer Sie wollen
durchlaufen ein Array,

1407
00:59:32,066 --> 00:59:33,440
Ihre Meinung könnte für eine Schleife gehen.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Also für einige int k
equals-- was wir denken

1410
00:59:38,090 --> 00:59:39,700
k wird sich gleich mit zu beginnen?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Dies ist, was wir als unsere kleinste gesetzt
Wert, und wir wollen es zu vergleichen.

1413
00:59:44,766 --> 00:59:47,090
Was wollen wir, um es zu vergleichen?

1414
00:59:47,090 --> 00:59:48,730
Es wird diese nächste sein, richtig?

1415
00:59:48,730 --> 00:59:53,200
So wollen wir k initialisiert werden
i plus 1 zu starten.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Und wir wollen, k wir in diesem Fall
bereits Größe bis hier abgelegt,

1418
01:00:02,800 --> 01:00:03,930
so können wir nur nutzen Größe.

1419
01:00:03,930 --> 01:00:06,240
Größe durch die die Größe des Arrays.

1420
01:00:06,240 --> 01:00:09,620
Und wir wollen einfach nur
Aktualisieren k jedesmal um eins.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
So, jetzt müssen wir herausfinden
das kleinste Element.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Also, wenn wir durch laufen, wir
will sagen, wenn Array bei k

1427
01:00:31,380 --> 01:00:37,080
weniger als unsere kleinste value--
das ist, wo wir sind eigentlich

1428
01:00:37,080 --> 01:00:42,950
Verfolgung, was
die kleinste hier--

1429
01:00:42,950 --> 01:00:47,740
dann neu zuweisen möchten wir
was unsere kleinste Wert ist.

1430
01:00:47,740 --> 01:00:50,645
>> Dies bedeutet, dass, oh, wir sind
Iteration durch hier.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Was auch immer Wert ist hier
nicht unsere kleinste Sache.

1433
01:00:53,740 --> 01:00:54,448
Wir wollen es nicht.

1434
01:00:54,448 --> 01:00:56,100
Wir wollen es neu zuweisen.

1435
01:00:56,100 --> 01:01:02,050
Also, wenn wir die Neuzuweisung von ihm, was zu tun
Sie vielleicht denken in diesem Code hier sein?

1436
01:01:02,050 --> 01:01:04,160
Wir wollen neu zuweisen
kleinste und Position.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Also, was ist kleinste jetzt?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
STUDENT: Array k.

1441
01:01:09,130 --> 01:01:09,963
LEHRER: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Und was ist die Position jetzt?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Was ist die Indizes
unsere kleinsten Wert?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Es ist nur k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
So Array k, k, passen sie auf.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Also wollten wir, dass neu zuweisen.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Und dann, nachdem wir fanden unsere kleinste,
so dass am Ende dieses für Schleifen

1454
01:01:39,950 --> 01:01:45,100
hier haben wir festgestellt, was unsere kleinsten
Wert ist, so dass wir tauschen es einfach.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
In diesem Fall sagen wie unsere
kleinste Wert ist hier draußen.

1457
01:01:50,816 --> 01:01:51,940
Dies ist unsere kleinste Wert.

1458
01:01:51,940 --> 01:01:57,690
>> Wir wollen einfach nur, um es hier zu tauschen, das ist
was das Swap-Funktion am unteren Rand

1459
01:01:57,690 --> 01:02:01,270
tat, was wir gerade schrieb
zusammen vor ein paar Minuten.

1460
01:02:01,270 --> 01:02:02,775
So sollte es bekannt vorkommen.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Und dann wird es nur durchlaufen
durch, bis er den ganzen Weg erreicht

1463
01:02:08,030 --> 01:02:13,100
an dem Ende, das bedeutet, dass man
null Elemente, die unsortiert sind

1464
01:02:13,100 --> 01:02:14,800
und alles andere wurde sortiert.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Sinnvoll?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Ein wenig konkreter?

1469
01:02:19,280 --> 01:02:19,990
Der Code Hilfe?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: Für eine Größe, die Sie nie
wirklich definieren oder zu ändern,

1472
01:02:26,410 --> 01:02:27,340
wie funktioniert es schon?

1473
01:02:27,340 --> 01:02:32,380
>> LEHRER: Also eine Sache,
bemerken hier oben ist int size.

1474
01:02:32,380 --> 01:02:35,680
So dass wir in diesem sort-- Art sagen
ist eine Funktion in dieser case-- es

1475
01:02:35,680 --> 01:02:40,770
Auswahl sortieren, es bestanden
in der Funktion.

1476
01:02:40,770 --> 01:02:43,460
Also, wenn es nicht übergeben wurde
in, würden Sie etwas tun

1477
01:02:43,460 --> 01:02:47,840
wie mit der Länge der Anordnung
oder Sie würden durch laufen

1478
01:02:47,840 --> 01:02:49,390
um die Länge zu finden.

1479
01:02:49,390 --> 01:02:52,680
Sondern weil es bestanden
in, können wir es einfach verwenden.

1480
01:02:52,680 --> 01:02:55,720
Sie übernehmen nur, dass der Benutzer
gaben Sie eine gültige Größe, dass

1481
01:02:55,720 --> 01:02:57,698
tatsächlich stellt
Größe Ihres Arrays.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Wenn Sie Jungs haben keine Probleme mit diesen
oder wollen mehr Praxis Codierungsarten

1486
01:03:05,870 --> 01:03:08,050
auf eigene Faust, sollten Sie
gehen Sie zu study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Es ist ein Werkzeug.

1489
01:03:12,670 --> 01:03:15,040
Sie haben ein Checker,
Sie tatsächlich schreiben.

1490
01:03:15,040 --> 01:03:16,180
Sie tun Pseudocode.

1491
01:03:16,180 --> 01:03:19,310
Sie haben mehr Videos und Dias
einschließlich die, die ich hier verwenden.

1492
01:03:19,310 --> 01:03:23,150
Also, wenn Sie immer noch das Gefühl bist ein
wenig unscharf, versuchen, dass aus.

1493
01:03:23,150 --> 01:03:25,670
Wie immer kommen mit mir reden, auch.

1494
01:03:25,670 --> 01:03:26,320
Question?

1495
01:03:26,320 --> 01:03:28,611
>> STUDENT: Wollen Sie sagen, die
Größe wird vorher festgelegt?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
LEHRER: Ja.

1498
01:03:29,900 --> 01:03:35,570
Die Größe wird zuvor festgelegt
hier in der Funktionsdeklaration.

1499
01:03:35,570 --> 01:03:39,060
So können Sie davon ausgehen, dass es in übergeben worden
durch den Benutzer, und der Einfachheit halber,

1500
01:03:39,060 --> 01:03:41,896
wir gehen davon aus, dass die
Benutzer gab uns die richtige Größe.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Also das ist Selection Sort.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Leute, ich weiß, dass wir eine Menge lernen heute.

1505
01:03:47,640 --> 01:03:49,710
Es ist eine dichte Daten für Abschnitt.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Also mit diesem werden wir
auf Insertion Sort gehen.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> Ok.

1510
01:04:02,510 --> 01:04:06,100
Also, bevor wir zu tun haben,
unsere Laufzeitanalyse hier.

1511
01:04:06,100 --> 01:04:10,190
Also im besten Fall,
gewährt, da ich Ihnen gezeigt,

1512
01:04:10,190 --> 01:04:11,960
Die Tabelle habe ich bereits
Art gab es weg.

1513
01:04:11,960 --> 01:04:15,430
Aber bestenfalls Laufzeit, was denken wir?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Alles sortiert.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N zum Quadrat.

1518
01:04:22,070 --> 01:04:24,780
Wer noch eine Erklärung
für Sie, warum?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> STUDENT: Du vergleichst through--

1521
01:04:30,519 --> 01:04:31,268
LEHRER: Richtig.

1522
01:04:31,268 --> 01:04:32,540
Du vergleichst durch.

1523
01:04:32,540 --> 01:04:35,630
Bei jeder Iteration, obwohl
wir Dekrementieren dies durch eine,

1524
01:04:35,630 --> 01:04:38,950
du bist immer noch durch die Suche
alles, das kleinste finden.

1525
01:04:38,950 --> 01:04:42,390
Also selbst wenn Sie Ihre kleinsten Wert
ist hier zu Beginn,

1526
01:04:42,390 --> 01:04:44,710
du bist immer noch den Vergleich
gegen alles andere

1527
01:04:44,710 --> 01:04:46,550
um sicherzustellen, dass es die kleinste Sache.

1528
01:04:46,550 --> 01:04:49,820
So werden Sie am Ende durchlauf
etwa n Quadrat mal.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
In Ordnung.

1531
01:04:51,590 --> 01:04:52,785
Und was ist der schlimmste Fall?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Auch n quadriert, weil du gehst
zu tun, dass die gleiche Prozedur.

1534
01:04:57,980 --> 01:05:01,670
So dass in diesem Fall Auswahl
hat Art etwas

1535
01:05:01,670 --> 01:05:04,010
dass wir auch anrufen erwartete Laufzeit.

1536
01:05:04,010 --> 01:05:07,400
Also in den anderen, wir wissen nur,
die oberen und unteren Grenzen.

1537
01:05:07,400 --> 01:05:11,180
Je nachdem, wie verrückt unsere
Liste ist oder wie unsortierte es,

1538
01:05:11,180 --> 01:05:15,350
sie variieren zwischen n oder n quadriert.

1539
01:05:15,350 --> 01:05:16,550
Wir wissen es nicht.

1540
01:05:16,550 --> 01:05:22,820
>> Aber weil Selection Sort hat die gleiche
schlimmsten und besten Fall erzählt, dass uns, dass

1541
01:05:22,820 --> 01:05:25,880
Egal, welche Art von Eingangs wir
haben, sei es vollständig

1542
01:05:25,880 --> 01:05:29,130
sortiert oder komplett
Reverse sortiert, es ist

1543
01:05:29,130 --> 01:05:30,740
würde die gleiche Menge an Zeit in Anspruch nehmen.

1544
01:05:30,740 --> 01:05:33,760
Also in diesem Fall, wenn Sie
erinnern von unserem Tisch,

1545
01:05:33,760 --> 01:05:38,610
sie einen Wert tatsächlich hatte,
diese beiden Arten nicht haben,

1546
01:05:38,610 --> 01:05:40,390
was erwartet der Laufzeit.

1547
01:05:40,390 --> 01:05:43,350
So wissen wir, dass, wann immer
wir laufen Selection Sort,

1548
01:05:43,350 --> 01:05:45,380
es ist gewährleistet
laufen eine n quadriert Zeit.

1549
01:05:45,380 --> 01:05:46,630
Es gibt keine Variabilität gibt.

1550
01:05:46,630 --> 01:05:47,630
Es ist nur zu erwarten.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Und wieder, wenn Sie lernen wollen
mehr nehmen CS 124 im Frühjahr.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
In Ordnung.

1555
01:05:56,712 --> 01:05:57,545
Wir haben diesen einen gesehen.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
So Insertion Sort.

1559
01:06:00,930 --> 01:06:03,330
Und ich bin wahrscheinlich
um durch diese lodern.

1560
01:06:03,330 --> 01:06:05,440
Ich will nicht, euch es zu codieren.

1561
01:06:05,440 --> 01:06:06,580
Wir werden einfach durch sie hindurchgehen.

1562
01:06:06,580 --> 01:06:10,500
So Insertion Sort ist eine Art
der ähnlich wie Selection Sort

1563
01:06:10,500 --> 01:06:14,460
in, dass wir sowohl eine unsortierte
und sortiert Teil des Arrays.

1564
01:06:14,460 --> 01:06:20,260
>> Aber was ist anders ist, dass
als wir durch einen Streich nach dem anderen,

1565
01:06:20,260 --> 01:06:24,210
wir nehmen nur was Nummer
ist als nächstes in unserem unsortiert,

1566
01:06:24,210 --> 01:06:28,507
und richtig sortieren sie
in unsere sortierten Array.

1567
01:06:28,507 --> 01:06:30,090
Es wird mehr Sinn mit einem Beispiel zu machen.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
So beginnt alles mit dem unsortierten,
Genau wie bei Selection Sort.

1570
01:06:35,430 --> 01:06:38,740
Und wir werden dies in sortieren
aufsteigender Reihenfolge, wie wir waren.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
So auf den ersten Pass
nehmen wir den ersten Wert

1573
01:06:43,340 --> 01:06:46,700
und wir sagen, OK, du bist
jetzt in einer Liste selbst.

1574
01:06:46,700 --> 01:06:49,150
>> Weil Sie in einer Liste sind
selbst, Sie sind sortiert.

1575
01:06:49,150 --> 01:06:52,460
Herzlichen Glückwunsch für Sein der
das erste Element in dieser Anordnung.

1576
01:06:52,460 --> 01:06:54,800
Sie sind bereits sortiert alle auf eigene Faust.

1577
01:06:54,800 --> 01:06:58,900
So, jetzt haben wir eine sortierte haben
und eine unsortierte Array.

1578
01:06:58,900 --> 01:07:01,760
So, jetzt haben wir die erste nehmen.

1579
01:07:01,760 --> 01:07:05,600
Was passiert zwischen hier
und hier ist, dass wir sagen,

1580
01:07:05,600 --> 01:07:08,890
OK, wir gehen auf der Suche
erste Wert unserer unsortierten Array

1581
01:07:08,890 --> 01:07:13,270
und wir den Eingang geht es in seinem
richtigen Stelle im sortierten Array.

1582
01:07:13,270 --> 01:07:21,460
>> Also, was wir tun, ist nehmen wir 5 und
wir sagen, OK, 5 größer als 3,

1583
01:07:21,460 --> 01:07:24,630
so fügen wir es genau richtig
auf der rechten Seite davon.

1584
01:07:24,630 --> 01:07:25,130
Wir sind gut.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Also wir gehen auf unsere nächste.

1587
01:07:28,420 --> 01:07:29,720
Und wir nehmen 2.

1588
01:07:29,720 --> 01:07:34,330
Wir sagen, OK, 2 weniger
als 3, so dass wir wissen, dass es

1589
01:07:34,330 --> 01:07:36,220
muss bei der sein
vor unserer Liste jetzt.

1590
01:07:36,220 --> 01:07:41,800
Also, was wir tun, ist schieben wir 3 und 5 nach unten
und wir bewegen 2 in diesem ersten Steckplatz.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Also sind wir nur Einsetzen in
der richtige Ort, es sein sollte.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Dann schauen wir auf unsere
nächste, und wir sagen, 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 ist größer als
alles in unserer sortierten Array,

1596
01:07:53,620 --> 01:07:56,000
so dass wir Tag setzen nur bis zum Ende.

1597
01:07:56,000 --> 01:07:56,960
Und dann schauen wir auf 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 ist kleiner als 6, dann ist es weniger
als 5, aber es ist mehr als 3.

1600
01:08:03,020 --> 01:08:06,270
Also fügen wir es genau richtig in
der Mitte zwischen 3 und 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
So zu machen, dass ein wenig
etwas mehr Beton,

1603
01:08:10,530 --> 01:08:12,280
hier ist eine Art der
Vorstellung davon, was passiert ist.

1604
01:08:12,280 --> 01:08:16,430
Also für jeden unsortierte Element, wir
festzustellen, wo in der sortierten Teil

1605
01:08:16,430 --> 01:08:17,090
es ist.

1606
01:08:17,090 --> 01:08:20,680
>> Also wenn man bedenkt, das
sortiert und unsortiert,

1607
01:08:20,680 --> 01:08:26,080
wir durchqueren und Figur
aus, wo es in der sortierten Array passt.

1608
01:08:26,080 --> 01:08:31,460
Und wir setzen Sie sie durch Verschieben des
Elemente auf der rechten Seite nach unten.

1609
01:08:31,460 --> 01:08:34,910
Und dann haben wir einfach weiter
durch Iteration, bis wir

1610
01:08:34,910 --> 01:08:39,270
haben eine völlig sortierte Liste
wo unsortiert ist jetzt Null

1611
01:08:39,270 --> 01:08:41,720
und sortierten nimmt die
Gesamtheit unserer Liste.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Also, noch einmal, um die Dinge noch zu machen
konkretere, haben wir Pseudocode.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Also im Grunde für i
gleich 0 bis n minus 1,

1616
01:08:52,410 --> 01:08:54,790
das ist nur die Länge unseres Arrays.

1617
01:08:54,790 --> 01:09:00,979
Wir haben einige Element, das gleich ist
die erste Anordnung oder die ersten Indizes.

1618
01:09:00,979 --> 01:09:03,200
Wir setzen j gleich.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
So, während j größer ist
Null, und die Anordnung, j minus 1

1621
01:09:09,210 --> 01:09:11,660
ist größer als die
Element, so alles, was zu tun

1622
01:09:11,660 --> 01:09:17,479
sorgt dafür, dass
Ihre j wirklich repräsentiert

1623
01:09:17,479 --> 01:09:20,010
die unsortierten Teil des Arrays.

1624
01:09:20,010 --> 01:09:30,745
>> So, während es immer noch Dinge,
zu sortieren und j minus eins ist-- was

1625
01:09:30,745 --> 01:09:31,840
ist das Element mit ihr?

1626
01:09:31,840 --> 01:09:34,760
J wurde hier nie definiert.

1627
01:09:34,760 --> 01:09:35,677
Es ist irgendwie nervig.

1628
01:09:35,677 --> 01:09:36,176
Ok.

1629
01:09:36,176 --> 01:09:36,689
Sowieso.

1630
01:09:36,689 --> 01:09:39,899
So j minus 1, Sie überprüfen sind
das Element, bevor es.

1631
01:09:39,899 --> 01:09:46,460
Sie sagen, OK, ist das Element
vor, wo immer ich am-- uns gelassen

1632
01:09:46,460 --> 01:09:47,540
tatsächlich ziehen dies.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Also lassen Sie uns sagen, das ist
wie auf unserem zweiten Durchgang.

1635
01:09:56,830 --> 01:09:59,525
Also i wird gleich sein
1, welches hier.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Also i wird gleich 1 zu sein.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Dies würde 2, 4, 5, 6, 7 sein.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
In Ordnung.

1642
01:10:16,750 --> 01:10:20,945
Also unser Element in diesem Fall
wird gleich 4 ist.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Und wir haben einige j, das ist
geht gleich 1 zu sein.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, ist j Dekrementieren.

1647
01:10:30,971 --> 01:10:31,720
Das ist, was es ist.

1648
01:10:31,720 --> 01:10:35,680
So j gleich i, so was das ist
Sprichwort ist, dass wie wir vorankommen,

1649
01:10:35,680 --> 01:10:37,530
wir nur dafür, dass
dass wir nicht über

1650
01:10:37,530 --> 01:10:43,520
Indizierung auf diese Weise, wenn wir versuchen,
die Dinge in unsere sortierte Liste einfügen.

1651
01:10:43,520 --> 01:10:49,850
>> So dass, wenn j gleich 1 ist, und in diesem Fall
Array j minus one-- so Array j minus 1

1652
01:10:49,850 --> 01:10:54,610
ist 2 in diesem case-- wenn das
größer als das Element,

1653
01:10:54,610 --> 01:10:57,700
dann all dies tut
verlagert sich die Dinge nach unten.

1654
01:10:57,700 --> 01:11:04,790
Also in diesem Fall, array j minus eins
würde Array Null, was 2 sein.

1655
01:11:04,790 --> 01:11:08,430
2 nicht größer als 4 ist,
so dass diese nicht ausgeführt.

1656
01:11:08,430 --> 01:11:11,460
So ist die Verschiebung nicht nach unten zu verschieben.

1657
01:11:11,460 --> 01:11:18,790
Was das bedeutet ist hier nur
Bewegen sortierten Array nach unten.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
In diesem Fall tatsächlich wir
könnte do-- wir machen diese 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Also, wenn wir durch mit zu gehen
Dieses Beispiel können wir jetzt hier.

1662
01:11:31,970 --> 01:11:32,740
Dies wird sortiert.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Dies ist unsortiert.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
So ist i gleich 2, so
unser Element ist gleich 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Und unsere j gleich 2 ist.

1670
01:11:52,270 --> 01:12:00,620
Also durch und wir freuen uns
sagen, OK, ist Array j minus eins

1671
01:12:00,620 --> 01:12:03,470
größer ist als die Element
dass wir bei der Suche?

1672
01:12:03,470 --> 01:12:05,540
Und die Antwort ist ja, nicht wahr?

1673
01:12:05,540 --> 01:12:11,275
4 größer als 3 ist und j
2 ist, sodass dieser Code ausführt.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> So jetzt, was wir tun ein Array an
2, so genau hier, tauschen wir sie.

1676
01:12:18,550 --> 01:12:25,620
Also haben wir einfach sagen, OK, Array
bei 2 wird jetzt auf 3 sein.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Und j wird sich gleich
j minus 1, 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Das ist schrecklich, aber
you guys get the idea.

1681
01:12:37,200 --> 01:12:38,360
J ist nun gleich 1 ist.

1682
01:12:38,360 --> 01:12:44,360
Und Array j gerade dabei zu sein
gleich unser Element, die 4 war.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Ich löschte etwas, was ich nicht sollte
haben oder miswrote etwas,

1685
01:12:48,570 --> 01:12:49,910
aber ihr Jungs bekommen die Idee.

1686
01:12:49,910 --> 01:12:50,640
>> Es bewegen sich n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Und dann, wenn dies, wäre es Schleife
wieder und es würde sagen, OK, j 1 jetzt.

1689
01:12:57,960 --> 01:13:00,665
Und Array j minus 1 ist jetzt 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Ist 2 weniger als unser Element?

1692
01:13:03,760 --> 01:13:04,540
Nein?

1693
01:13:04,540 --> 01:13:07,970
Das bedeutet, dass wir
eingefügt dieses Element

1694
01:13:07,970 --> 01:13:10,110
an der richtigen Stelle in unserem sortierten Array.

1695
01:13:10,110 --> 01:13:14,400
Dann können wir diese übernehmen und wir sagen,
OK, ist unsere sortierten Array hier.

1696
01:13:14,400 --> 01:13:19,940
Und es würde diese Nummer 6 zu nehmen und
wie, OK, 6 weniger als diese Zahl?

1697
01:13:19,940 --> 01:13:20,480
Nein?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Uns geht es gut.

1700
01:13:22,680 --> 01:13:23,530
>> Tun Sie es erneut.

1701
01:13:23,530 --> 01:13:24,740
Wir sagen 7.

1702
01:13:24,740 --> 01:13:29,010
Ist 7 weniger als zum Ende
unserer sortierten Array?

1703
01:13:29,010 --> 01:13:29,520
Nein.

1704
01:13:29,520 --> 01:13:30,430
Wir sind also in Ordnung.

1705
01:13:30,430 --> 01:13:32,760
So wäre sortiert werden.

1706
01:13:32,760 --> 01:13:38,610
Grundsätzlich alles tut
wird es sagen Take

1707
01:13:38,610 --> 01:13:42,060
das erste Element
Ihre unsortierten Array

1708
01:13:42,060 --> 01:13:46,010
herauszufinden, wo es geht
in Ihrem sortierten Array.

1709
01:13:46,010 --> 01:13:48,780
Und das dauert nur Pflege
von Swaps zu tun.

1710
01:13:48,780 --> 01:13:51,300
Sie sind im Grunde nur Swapping
bis es an der richtigen Stelle.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Das visuelle Bild ist, dass Sie
Bewegen alles auf diese Weise vor.

1713
01:13:56,990 --> 01:13:59,420
>> So ist es wie ein halb Bubble-Sort-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Check out Studie 50.

1716
01:14:03,420 --> 01:14:06,000
Ich kann empfehlen,
um dies an Ihrem eigenen Code.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Wenn Sie irgendwelche Fragen haben oder Sie wollen
siehe Beispielcode für eine Insertion Sort,

1719
01:14:12,450 --> 01:14:13,750
lass es mich wissen, bitte.

1720
01:14:13,750 --> 01:14:14,500
Ich bin immer in der Nähe.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Also worst case-Laufzeit
und best case-Laufzeit.

1723
01:14:20,200 --> 01:14:30,700
Wie Sie Kerl sah aus der Tabelle habe ich bereits
Ihnen gezeigt, es ist sowohl n quadriert und n.

1724
01:14:30,700 --> 01:14:35,590
>> So Art abgehend von dem, was wir sprachen
mit unseren früheren Sorten, am schlechtesten

1725
01:14:35,590 --> 01:14:38,760
Bei Laufzeit ist, dass wenn
es ist völlig unsortiert,

1726
01:14:38,760 --> 01:14:42,530
wir müssen alle diese n-mal zu vergleichen.

1727
01:14:42,530 --> 01:14:47,020
Wir tun eine ganze Menge von Vergleichen
denn wenn es in umgekehrter Reihenfolge,

1728
01:14:47,020 --> 01:14:50,360
wir gehen zu sagen, OK, diese
die gleiche ist, ist gut,

1729
01:14:50,360 --> 01:14:54,650
und diese müssen verglichen werden
gegen die erste, zurückbewegt werden.

1730
01:14:54,650 --> 01:14:56,710
Und wie wir in Richtung bekommen
das Schwanzende, haben wir

1731
01:14:56,710 --> 01:14:59,440
Vergleichen, vergleichen und
Vergleichen gegen alles.

1732
01:14:59,440 --> 01:15:03,030
>> Also es endet als
etwa n quadriert.

1733
01:15:03,030 --> 01:15:09,510
Wenn es richtig ist, dann
sagen, OK, 2, du bist gut.

1734
01:15:09,510 --> 01:15:11,330
3, Sie 2 verglichen sind.

1735
01:15:11,330 --> 01:15:12,310
Du bist gut.

1736
01:15:12,310 --> 01:15:14,150
4, einfach zu vergleichen, um den Schwanz.

1737
01:15:14,150 --> 01:15:14,990
Du bist gut.

1738
01:15:14,990 --> 01:15:17,140
6, zu vergleichen, um den Schwanz, es dir gut geht.

1739
01:15:17,140 --> 01:15:20,870
So wird für jeden Ort, wenn es schon
sortiert, du machst einen Vergleich.

1740
01:15:20,870 --> 01:15:22,320
So ist es nur n.

1741
01:15:22,320 --> 01:15:26,840
Und weil wir eine best case-Laufzeit
von n und einem Worst-Case-Laufzeit von n

1742
01:15:26,840 --> 01:15:28,680
quadriert, haben wir keine erwartete Laufzeit.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Es hängt nur von der
Chaos unserer Liste gibt.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Und wieder ein anderer
Grafik und eine andere Tabelle.

1747
01:15:39,530 --> 01:15:41,170
Also Unterschiede zwischen Arten.

1748
01:15:41,170 --> 01:15:44,180
Ich werde einfach Brise durch, ich
das Gefühl, wir haben ausgiebig gesprochen

1749
01:15:44,180 --> 01:15:46,570
darüber, wie sie aller Art
von variieren und miteinander zu verknüpfen.

1750
01:15:46,570 --> 01:15:50,564
So Mergesort ist die letzte
Ich werde mit der Bohrung euch.

1751
01:15:50,564 --> 01:15:52,105
Wir haben ein ziemlich buntes Bild.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
So Mergesort ist ein rekursiver Algorithmus.

1754
01:15:56,040 --> 01:15:59,910
Also euch wissen, was
eine rekursive Funktion ist?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Wer möchte sagen?

1757
01:16:03,320 --> 01:16:04,739
Sie wollen versuchen?

1758
01:16:04,739 --> 01:16:07,280
Also eine rekursive Funktion ist nur
eine Funktion, die sich selbst aufruft.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Also, wenn euch vertraut sind
mit der Fibonacci-Folge,

1761
01:16:11,590 --> 01:16:15,670
das ist als rekursive weil
Sie die vorherigen beiden nehmen

1762
01:16:15,670 --> 01:16:17,530
und addieren sie
um Ihren nächsten zu gelangen.

1763
01:16:17,530 --> 01:16:21,440
So rekursive, denke ich immer
der Rekursion als wie eine Spirale

1764
01:16:21,440 --> 01:16:24,430
so dass Sie wie Spirale nach unten hinein.

1765
01:16:24,430 --> 01:16:27,150
Aber es ist nur eine Funktion
dass nennt sich.

1766
01:16:27,150 --> 01:16:32,660
>> Und, tatsächlich, wirklich schnell ich
kann Ihnen zeigen, wie das aussieht.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
So rekursiven hier, wenn wir betrachten, ist dieses
die rekursive Weg zur Summe über ein Array.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Also alles, was wir tun, ist
wir Summenfunktion haben

1771
01:16:47,880 --> 01:16:52,210
Summe, die eine Größe und ein Array nimmt.

1772
01:16:52,210 --> 01:16:55,210
Und wenn Sie feststellen, Größe
dekrementiert jedesmal um eins.

1773
01:16:55,210 --> 01:17:00,365
Und alle es tut, ist, wenn x gleich ist
zero-- so dass, wenn die Größe des Arrays

1774
01:17:00,365 --> 01:17:02,710
gleich zero-- wird Null zurückgegeben.

1775
01:17:02,710 --> 01:17:10,440
>> Ansonsten fasst diese
letzte Element des Arrays,

1776
01:17:10,440 --> 01:17:14,790
und nimmt dann eine Summe von
der Rest des Arrays.

1777
01:17:14,790 --> 01:17:17,555
So ist es nur die Zerlegung
in immer kleinere Probleme.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Lange Rede kurzer Sinn, Rekursion,
Funktion, die sich selbst aufruft.

1780
01:17:21,890 --> 01:17:25,740
Wenn es das ist alles, was Sie von diesem bekam,
das ist, was eine rekursive Funktion ist.

1781
01:17:25,740 --> 01:17:29,870
Wenn Sie eine 51, werden Sie sehr zu bekommen,
sehr komfortabel mit Rekursion.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Es ist wirklich cool.

1784
01:17:32,370 --> 01:17:34,660
Es machte Sinn, wie
3.00 eine Nacht aus.

1785
01:17:34,660 --> 01:17:37,900
Und ich war wie, warum
habe ich nie verwenden das?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Also für Merge-Sort, im Grunde
was es zu tun ist, es ist

1788
01:17:42,430 --> 01:17:45,620
werde es brechen und brechen
nach unten, bis es nur einzelne Elemente.

1789
01:17:45,620 --> 01:17:47,570
Die einzelnen Elemente sind einfach zu sortieren.

1790
01:17:47,570 --> 01:17:48,070
Wir sehen, dass.

1791
01:17:48,070 --> 01:17:50,760
Wenn Sie ein Element haben, ist es
bereits als sortierte.

1792
01:17:50,760 --> 01:17:53,800
Usw. mit einem Eingang des n Elemente,
Wenn n kleiner als 2 ist,

1793
01:17:53,800 --> 01:17:58,120
nur zurück, weil das bedeutet
es ist entweder 0 oder 1, wie wir gesehen haben.

1794
01:17:58,120 --> 01:18:00,050
Diese werden als sortierte Elemente.

1795
01:18:00,050 --> 01:18:02,170
>> In Halb Sonst brechen.

1796
01:18:02,170 --> 01:18:06,336
Sortieren Sie die erste Hälfte, sortieren Sie die zweite
Hälfte, und dann verschmelzen sie zusammen.

1797
01:18:06,336 --> 01:18:07,460
Warum es heißt merge sort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
So haben wir hier wir diese zu sortieren.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
So halten wir mit ihnen
bis der Array-Größe ist 1.

1802
01:18:17,210 --> 01:18:20,790
Also, wenn es ein, wir zurückkehren
denn dies ist ein sortiertes Array,

1803
01:18:20,790 --> 01:18:23,940
und dies ist ein sortiertes Array, und das ist
ein sortiertes Array, wir sind alle sortiert.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Also dann, was wir tun ist, dass wir
starten gemeinsam ihre Zusammenlegung.

1806
01:18:29,420 --> 01:18:31,820
>> Also die Art und Weise können Sie
denke über Verschmelzung ist

1807
01:18:31,820 --> 01:18:36,240
Sie entfernen Sie einfach das kleinere
Anzahl der jedem der Subarrays

1808
01:18:36,240 --> 01:18:38,330
und hängen Sie einfach an die entstanden Array.

1809
01:18:38,330 --> 01:18:44,290
Also, wenn Sie hier sehen, wenn wir
Diese Sätze haben wir 4, 6 und 1.

1810
01:18:44,290 --> 01:18:47,280
Wenn wir diese zusammenführen möchten,
wir diese ersten zwei

1811
01:18:47,280 --> 01:18:50,730
und wir sagen, OK, ein kleiner,
es geht nach vorne.

1812
01:18:50,730 --> 01:18:54,330
4 und 6, es gibt nichts zu vergleichen
es, nur Tag setzen bis zum Ende.

1813
01:18:54,330 --> 01:18:58,020
>> Wenn wir diese beiden zu kombinieren, wir haben nur
nehmen Sie die kleinere von diesen beiden,

1814
01:18:58,020 --> 01:18:59,310
so ist es ein.

1815
01:18:59,310 --> 01:19:01,690
Und jetzt nehmen wir die
kleinere der beiden, also 2.

1816
01:19:01,690 --> 01:19:03,330
Kleinere von beiden ist, 3.

1817
01:19:03,330 --> 01:19:06,260
Kleinere der beiden, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Sie sind also nur Abziehen diesen.

1819
01:19:08,630 --> 01:19:11,210
Und weil sie
zuvor sortiert,

1820
01:19:11,210 --> 01:19:14,300
Sie müssen nur ein
Vergleich jedes Mal dort.

1821
01:19:14,300 --> 01:19:19,610
Also mehr Code hier, nur die Vertretung.

1822
01:19:19,610 --> 01:19:24,410
So können Sie in der Mitte beginnen und
Sie sortieren links und rechts

1823
01:19:24,410 --> 01:19:26,180
und dann muß man nur zusammenführen denen.

1824
01:19:26,180 --> 01:19:30,080
>> Und wir wissen nicht Code
für verschmelzen hier richtig.

1825
01:19:30,080 --> 01:19:34,110
Aber noch einmal, wenn Sie weitermachen
studieren 50, wird es da sein.

1826
01:19:34,110 --> 01:19:36,860
Ansonsten kommen talk to me
wenn Sie immer noch verwirrt.

1827
01:19:36,860 --> 01:19:42,340
So cool daran ist, dass bestenfalls
schlimmsten Fall und erwartete Laufzeit

1828
01:19:42,340 --> 01:19:46,250
sind alle in log n, die
ist weit besser als wir haben

1829
01:19:46,250 --> 01:19:48,000
für den Rest der Art gesehen.

1830
01:19:48,000 --> 01:19:51,840
Wir haben gesehen, n quadriert
und was wir tatsächlich

1831
01:19:51,840 --> 01:19:54,380
bekommen hier n log n, das ist toll.

1832
01:19:54,380 --> 01:19:55,830
>> Schauen Sie, wie viel besser das ist.

1833
01:19:55,830 --> 01:19:56,780
So ein netter Kurve.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
So viel effizienter.

1836
01:20:00,120 --> 01:20:03,510
Wenn Sie überhaupt möglich, die Verwendung Mergesort.

1837
01:20:03,510 --> 01:20:04,810
Es erspart Ihnen Zeit.

1838
01:20:04,810 --> 01:20:07,670
Dann wieder, wie gesagt, wenn
du unten bist in diesem unteren Bereich,

1839
01:20:07,670 --> 01:20:09,480
es macht keinen, dass
einen großen Unterschied.

1840
01:20:09,480 --> 01:20:11,360
Sie erhalten bis zu Tausenden
und Tausende von Eingängen,

1841
01:20:11,360 --> 01:20:13,318
Sie wollen auf jeden Fall ein
effizienter Algorithmus.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Und wieder unsere schöne Tabelle aller
Sorten, die euch heute gelernt.

1844
01:20:19,400 --> 01:20:21,157
>> Also ich weiß, es ist schon eine dichte Tag.

1845
01:20:21,157 --> 01:20:23,490
Dies ist nicht notwendigerweise
um Sie bei Ihrer pset helfen.

1846
01:20:23,490 --> 01:20:28,250
Aber ich will nur einen Haftungsausschluss zu machen
dieser Abschnitt ist nicht nur über psets.

1847
01:20:28,250 --> 01:20:31,240
All dieses Material Messe ist
Spiel für Ihr Mittelklausuren.

1848
01:20:31,240 --> 01:20:35,430
Und auch, wenn Sie weiter mit CS zu tun,
diese sind wirklich wichtige Grundlagen

1849
01:20:35,430 --> 01:20:37,870
dass Sie müssten es wissen.

1850
01:20:37,870 --> 01:20:41,700
So ein paar Tage wird ein
wenig mehr pset Hilfe

1851
01:20:41,700 --> 01:20:44,600
aber einige Wochen sein wird
viel mehr tatsächliche Inhalt

1852
01:20:44,600 --> 01:20:46,600
das kann nicht scheinen Super
nützlich für Sie gerade jetzt,

1853
01:20:46,600 --> 01:20:51,215
aber ich verspreche, wenn Sie weiterhin
auf wird sehr, sehr nützlich.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Das ist es also für den Abschnitt.

1856
01:20:54,250 --> 01:20:55,250
Auf Draht.

1857
01:20:55,250 --> 01:20:56,570
Ich habe es innerhalb einer Minute.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Aber dort gehen Sie.

1860
01:20:58,970 --> 01:21:01,240
Und ich muss Donuts oder Süßigkeiten.

1861
01:21:01,240 --> 01:21:03,464
Ist jemand allergisch auf
überhaupt, durch die Art und Weise?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Eier und Milch.

1864
01:21:05,890 --> 01:21:08,120
Also Donuts sind ein nein?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
Ok.

1867
01:21:10,160 --> 01:21:10,770
In Ordnung.

1868
01:21:10,770 --> 01:21:12,120
Schokolade nein?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts sind gut.

1872
01:21:14,670 --> 01:21:15,170
Ok.

1873
01:21:15,170 --> 01:21:17,045
Wir gehen zu müssen
Starburst nächste Woche dann.

1874
01:21:17,045 --> 01:21:18,240
Das ist, was ich erhalte.

1875
01:21:18,240 --> 01:21:19,690
Ihr habt eine tolle Woche.

1876
01:21:19,690 --> 01:21:20,460
Lesen Sie Ihre spec.

1877
01:21:20,460 --> 01:21:22,130
>> Lassen Sie mich wissen, wenn Sie irgendwelche Fragen haben.

1878
01:21:22,130 --> 01:21:25,300
Pset zwei Grade sein sollte
zu Ihnen bis Donnerstag.

1879
01:21:25,300 --> 01:21:28,320
Wenn Sie irgendwelche Fragen haben,
darüber, wie ich benotet etwas

1880
01:21:28,320 --> 01:21:32,250
oder warum ich benotet etwas so, wie ich
haben, mailen Sie mich bitte, komm mit mir reden.

1881
01:21:32,250 --> 01:21:34,210
Ich bin ein wenig verrückt diese
Woche, aber ich verspreche,

1882
01:21:34,210 --> 01:21:36,340
Werde ich noch antworten innerhalb von 24 Stunden.

1883
01:21:36,340 --> 01:21:38,240
So haben eine tolle Woche, jeder.

1884
01:21:38,240 --> 01:21:40,090
Viel Glück auf Ihrer pset.

1885
01:21:40,090 --> 01:21:41,248