1
00:00:00,000 --> 00:00:03,360
>> [Musikwiedergabe]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Okay, so
Bubble-Sort ist ein Algorithmus,

4
00:00:06,730 --> 00:00:08,730
Sie verwenden, um eine Reihe von Elementen sortieren.

5
00:00:08,730 --> 00:00:10,850
Werfen wir einen Blick darauf, wie es funktioniert.

6
00:00:10,850 --> 00:00:13,240
>> So ist die Grundidee
Bubble-Sort ist dies.

7
00:00:13,240 --> 00:00:17,340
Wir wollen in der Regel zu höheren bewegen
geschätztes Elemente allgemein auf der rechten Seite,

8
00:00:17,340 --> 00:00:20,340
und senken Sie Wert Elemente allgemein
nach links, wie man erwarten würde.

9
00:00:20,340 --> 00:00:23,256
Wir wollen, dass die unteren Dinge zu sein,
der Anfang, und die höheren Dinge

10
00:00:23,256 --> 00:00:24,970
am Ende ist.

11
00:00:24,970 --> 00:00:26,130
>> Wie machen wir das?

12
00:00:26,130 --> 00:00:28,040
Nun in Pseudocode,
könnten wir sagen, lasst uns

13
00:00:28,040 --> 00:00:30,320
Set eine Swap-Zähler auf einen Wert ungleich Null.

14
00:00:30,320 --> 00:00:32,570
Wir werden sehen, warum wir das tun, in einer Sekunde.

15
00:00:32,570 --> 00:00:36,090
Und dann haben wir Wiederholen Sie die folgenden
Prozess, bis die Swap-Gegen 0,

16
00:00:36,090 --> 00:00:39,910
oder bis wir machen keine Swaps überhaupt.

17
00:00:39,910 --> 00:00:43,170
>> Setzen Sie den Swap-Zähler auf
0, wenn es nicht bereits 0.

18
00:00:43,170 --> 00:00:46,420
Schauen Sie sich jeden
benachbarten Elementpaar.

19
00:00:46,420 --> 00:00:49,550
Wenn diese beiden Elemente sind
nicht in Ordnung, tauschen sie,

20
00:00:49,550 --> 00:00:51,620
und fügen Sie 1 auf die Swap-Gegen.

21
00:00:51,620 --> 00:00:53,870
Wenn du denkst
diese, bevor Sie es zu visualisieren,

22
00:00:53,870 --> 00:00:57,471
bemerken, dass dies zu bewegen unteren
geschätztes Elemente links

23
00:00:57,471 --> 00:01:00,720
und höherwertigen Elemente rechts,
effektiv zu tun, was wir tun wollen,

24
00:01:00,720 --> 00:01:03,940
die bewegen diese Gruppen ist
von Elementen auf diese Weise.

25
00:01:03,940 --> 00:01:07,035
Lassen Sie uns zu vergegenwärtigen, wie diese
aussehen könnte, mit unser Angebot

26
00:01:07,035 --> 00:01:10,504
, dass wir zum Testen verwendet werden,
aus dieser Algorithmen.

27
00:01:10,504 --> 00:01:13,420
Wir haben eine unsortierte Array wieder hier,
von allen der Elemente angegeben

28
00:01:13,420 --> 00:01:14,840
wobei in rot.

29
00:01:14,840 --> 00:01:17,970
Und ich meine Swap-Gegen
um einen Wert ungleich Null.

30
00:01:17,970 --> 00:01:20,610
Ich willkürlich gewählt
negativen 1-- es ist nicht 0.

31
00:01:20,610 --> 00:01:23,840
Wir wollen diesen Vorgang wiederholen
bis der Swap-Gegen 0.

32
00:01:23,840 --> 00:01:26,540
Das ist, warum ich meine Swap-
Zähler bis zu einem gewissen Wert ungleich Null,

33
00:01:26,540 --> 00:01:29,400
weil sonst die
Swap-Gegen würde 0 sein.

34
00:01:29,400 --> 00:01:31,610
Wir würden nicht einmal ansatzweise die
Prozess des Algorithmus.

35
00:01:31,610 --> 00:01:33,610
Also noch einmal, die Schritte sind--
setzen Sie die Swap-Gegen

36
00:01:33,610 --> 00:01:37,900
auf 0, dann auf jeder benachbarten suchen
Paar, und wenn sie nicht in Ordnung sind,

37
00:01:37,900 --> 00:01:40,514
tauschen sie, und fügen Sie 1
auf die Swap-Gegen.

38
00:01:40,514 --> 00:01:41,680
Lassen Sie uns also beginnen diesen Prozess.

39
00:01:41,680 --> 00:01:44,430
Das erste, was wir tun, ist
setzen wir die Swap-Zähler auf 0,

40
00:01:44,430 --> 00:01:46,660
und dann werden wir beginnen,
an jedem benachbarten Paar.

41
00:01:46,660 --> 00:01:49,140
>> So dass wir zuerst beginnen, 5 und 2.

42
00:01:49,140 --> 00:01:52,410
Wir sehen, dass sie aus sind
bestellen und so tauschen wir sie.

43
00:01:52,410 --> 00:01:53,830
Und wir 1 hinzufügen, um die Swap-Gegen.

44
00:01:53,830 --> 00:01:57,860
So, jetzt unseren Swap-Zähler 1,
und 2 und 5 umgeschaltet worden sind.

45
00:01:57,860 --> 00:01:59,370
Jetzt haben wir den Prozess zu wiederholen.

46
00:01:59,370 --> 00:02:03,540
>> Wir schauen uns den nächsten benachbarten Paar,
5 und 1-- sie sind auch nicht in Ordnung,

47
00:02:03,540 --> 00:02:06,960
so dass wir tauschen sie und fügen Sie
1 auf die Swap-Gegen.

48
00:02:06,960 --> 00:02:08,900
Dann schauen wir uns 5 und 3.

49
00:02:08,900 --> 00:02:13,830
Sie sind nicht in Ordnung, so dass wir tauschen
sie und wir 1 hinzufügen, um die Swap-Gegen.

50
00:02:13,830 --> 00:02:15,550
Dann schauen wir uns 5 und 6.

51
00:02:15,550 --> 00:02:18,630
Sie sind in Ordnung, so dass wir nicht wirklich
müssen Sie nichts dieses Mal tauschen.

52
00:02:18,630 --> 00:02:20,250
Dann schauen wir uns 6 und 4.

53
00:02:20,250 --> 00:02:24,920
Sie sind auch nicht in Ordnung, so dass wir tauschen
sie und wir 1 hinzufügen, um die Swap-Gegen.

54
00:02:24,920 --> 00:02:26,230
>> Jetzt bemerken, was passiert ist.

55
00:02:26,230 --> 00:02:29,514
Wir haben 6 bewegt den ganzen Weg bis zum Ende.

56
00:02:29,514 --> 00:02:32,180
So bei der Auswahl zu sortieren, wenn Sie schon
gesehen, dass Videos, was wir taten, war

57
00:02:32,180 --> 00:02:35,290
Wir sind dann schließlich die
kleinsten Elemente im Gebäude

58
00:02:35,290 --> 00:02:39,640
sortierten Array im Wesentlichen aus
von links nach rechts, vom kleinsten zum größten.

59
00:02:39,640 --> 00:02:43,200
Im Falle von Bubble Sort, wenn wir
nach diesem speziellen Algorithmus,

60
00:02:43,200 --> 00:02:46,720
wir tatsächlich zu bauen
sortierten Array von rechts

61
00:02:46,720 --> 00:02:49,100
zu, der größten zur kleinsten verlassen.

62
00:02:49,100 --> 00:02:53,840
Wir haben effektiv sprudelte 6, die
größten Wert, den ganzen Weg bis zum Ende.

63
00:02:53,840 --> 00:02:56,165
>> Und so können wir nun erklären,
dass diese sortiert,

64
00:02:56,165 --> 00:02:59,130
und in Zukunft iterations--
Durchlaufen des Arrays again--

65
00:02:59,130 --> 00:03:01,280
wir haben nicht mehr zu berücksichtigen 6.

66
00:03:01,280 --> 00:03:03,850
Wir haben nur zu prüfen,
die unsortierten Elemente

67
00:03:03,850 --> 00:03:06,299
wenn wir bei benachbarten Paaren suchen.

68
00:03:06,299 --> 00:03:08,340
Also haben wir einen fertig sind
passieren Bubble-Sort.

69
00:03:08,340 --> 00:03:11,941
So, jetzt gehen wir zurück zu der Frage,
wiederholen, bis die Swap-Gegen 0.

70
00:03:11,941 --> 00:03:13,690
Nun, die Swap-Gegen
4 ist, also werden wir

71
00:03:13,690 --> 00:03:15,410
zum Wiederholen Sie diesen Vorgang erneut.

72
00:03:15,410 --> 00:03:19,180
>> Wir werden die Swap-Zähler zurückzusetzen
auf 0, und schauen Sie sich jedem benachbarten Paar.

73
00:03:19,180 --> 00:03:21,890
So beginnen wir mit 2 und 1-- sie
nicht in Ordnung, so tauschen wir sie

74
00:03:21,890 --> 00:03:23,620
und wir 1 hinzufügen, um die Swap-Gegen.

75
00:03:23,620 --> 00:03:25,490
2 und 3, sind sie in Ordnung.

76
00:03:25,490 --> 00:03:27,060
Wir brauchen nicht, etwas zu tun.

77
00:03:27,060 --> 00:03:28,420
3 und 5 sind in Ordnung.

78
00:03:28,420 --> 00:03:30,150
Wir brauchen nicht, etwas zu tun gibt.

79
00:03:30,150 --> 00:03:32,515
>> 5 und 4 aus sind sie
der Ordnung, und so haben wir

80
00:03:32,515 --> 00:03:35,130
brauchen, um sie zu tauschen, und fügen Sie
1 auf die Swap-Gegen.

81
00:03:35,130 --> 00:03:38,880
Und jetzt haben wir 5 bewegt wird,
der nächstgrößte Element,

82
00:03:38,880 --> 00:03:40,920
bis zum Ende des unsortierten Abschnitt.

83
00:03:40,920 --> 00:03:44,360
So können wir heute sagen, dass
Teil des sortiert Teil.

84
00:03:44,360 --> 00:03:47,180
>> Jetzt können Sie auf die gesuchte
Bildschirm und wahrscheinlich kann sagen,

85
00:03:47,180 --> 00:03:50,130
wie kann ich, daß das Array
wird jetzt sortiert.

86
00:03:50,130 --> 00:03:51,820
Aber wir können nicht beweisen, dass noch kann.

87
00:03:51,820 --> 00:03:54,359
Wir haben nicht eine Garantie
dass es sortiert.

88
00:03:54,359 --> 00:03:56,900
Aber das ist, wo das Swap-
Gegen geht um ins Spiel kommen.

89
00:03:56,900 --> 00:03:59,060
>> Also haben wir einen Pass abgeschlossen.

90
00:03:59,060 --> 00:04:00,357
Die Swap-Zähler 2.

91
00:04:00,357 --> 00:04:02,190
So werden wir wiederholen
dieser Prozess wieder,

92
00:04:02,190 --> 00:04:04,290
wiederholen, bis die Swap-Gegen 0.

93
00:04:04,290 --> 00:04:05,550
Setzen Sie den Swap-Zähler auf 0.

94
00:04:05,550 --> 00:04:06,820
Also werden wir es zurückzusetzen.

95
00:04:06,820 --> 00:04:09,810
>> Nun ein Blick auf jedem benachbarten Paar.

96
00:04:09,810 --> 00:04:11,880
Das ist in Ordnung, 1 und 2.

97
00:04:11,880 --> 00:04:13,590
2 und 3 sind in Ordnung.

98
00:04:13,590 --> 00:04:15,010
3 und 4 sind in Ordnung.

99
00:04:15,010 --> 00:04:19,250
Also an dieser Stelle bemerken wir abgeschlossen haben
Suche in jedem benachbarten Paar,

100
00:04:19,250 --> 00:04:22,530
aber die Swap-Gegen ist immer noch 0.

101
00:04:22,530 --> 00:04:25,520
>> Wenn wir nicht haben, um umzuschalten
alle Elemente, dann

102
00:04:25,520 --> 00:04:28,340
muss in Ordnung sein, durch
Aufgrund dieses Prozesses.

103
00:04:28,340 --> 00:04:32,000
Und so eine Effizienz von Art,
dass wir Informatiker lieben,

104
00:04:32,000 --> 00:04:35,560
ist können wir nun erklären,
die gesamte Anordnung muss

105
00:04:35,560 --> 00:04:38,160
sortiert werden, weil wir nicht
müssen alle Elemente zu vertauschen.

106
00:04:38,160 --> 00:04:40,380
Das ist ziemlich nett.

107
00:04:40,380 --> 00:04:43,260
>> Also, was ist der schlimmste Fall
Szenario mit Bubble-Sort?

108
00:04:43,260 --> 00:04:46,240
Im schlimmsten Fall ist das Array
in völlig umgekehrter Reihenfolge,

109
00:04:46,240 --> 00:04:49,870
und so müssen wir jede Blase
der großen Elemente alle

110
00:04:49,870 --> 00:04:51,780
die Art und Weise über das Array.

111
00:04:51,780 --> 00:04:55,350
Und wir effektiv auch haben
bubble alle kleinen Elementen zurück

112
00:04:55,350 --> 00:04:57,050
den ganzen Weg über die Anordnung, zu.

113
00:04:57,050 --> 00:05:01,950
So dass jedes der n Elemente zu bewegen
in all den anderen n-Elemente.

114
00:05:01,950 --> 00:05:04,102
Also das ist der schlimmste Fall.

115
00:05:04,102 --> 00:05:05,810
Im besten Fall
Szenario ist dies jedoch

116
00:05:05,810 --> 00:05:07,880
geringfügig von Selection Sort.

117
00:05:07,880 --> 00:05:10,040
Das Array ist bereits
sortiert, wenn wir gehen.

118
00:05:10,040 --> 00:05:12,550
Wir haben nicht zu einem zu machen
Swaps im ersten Durchgang.

119
00:05:12,550 --> 00:05:14,940
So haben wir vielleicht zu schauen
bei weniger Elemente, nicht wahr?

120
00:05:14,940 --> 00:05:18,580
Wir haben nicht, dies zu wiederholen,
Verarbeiten einer Anzahl von Faches.

121
00:05:18,580 --> 00:05:19,540
>> Also, was bedeutet das?

122
00:05:19,540 --> 00:05:22,390
Also, was ist das schlimmste Szenario
für Bubble-Sort, und was

123
00:05:22,390 --> 00:05:25,330
das beste Szenario für Bubble-Sort?

124
00:05:25,330 --> 00:05:27,770
Haben Sie denke, dies?

125
00:05:27,770 --> 00:05:32,420
Im schlimmsten Fall, dass Sie durchlaufen haben
über alle n Elemente n-fach.

126
00:05:32,420 --> 00:05:34,220
So der schlimmste Fall ist n quadriert.

127
00:05:34,220 --> 00:05:36,550
>> Wenn das Array vollkommen
obwohl sortierten, nur du

128
00:05:36,550 --> 00:05:38,580
muss bei jedem Blick
der Elemente gleichzeitig.

129
00:05:38,580 --> 00:05:42,670
Und wenn die Swap-Gegen ist immer noch 0,
Sie sagen, dass dieses Array sortiert.

130
00:05:42,670 --> 00:05:45,780
Und so im besten Fall, ist dies
sogar besser als Auswahl

131
00:05:45,780 --> 00:05:49,230
sort-- es Omega der n.

132
00:05:49,230 --> 00:05:50,270
>> Ich bin Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Dies ist CS50.

134
00:05:52,140 --> 00:05:54,382