1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [BUBBLE SORT]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP HARVARD UNIVERSITY]

3
00:00:04,560 --> 00:00:07,500
[DIESES IST CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Blase Sortieren eines Beispiels eines Sortier-Algorithmus -

5
00:00:11,730 --> 00:00:14,460
das heißt, ein Verfahren zum Sortieren einer Gruppe von Elementen in

6
00:00:14,460 --> 00:00:15,840
aufsteigender oder absteigender Reihenfolge.

7
00:00:15,840 --> 00:00:18,710
Zum Beispiel, wenn Sie ein Array sortieren wollte bestehend aus den Zahlen

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], würde eine korrekte Umsetzung der Bubble Sort wieder die

9
00:00:23,060 --> 00:00:26,260
sortierte Array [2, 3, 5, 9] in aufsteigender Reihenfolge.

10
00:00:26,260 --> 00:00:28,850
Nun, ich werde in Pseudocode erklären, wie der Algorithmus funktioniert.

11
00:00:28,850 --> 00:00:34,000
>> Lassen Sie uns sagen, dass wir eine Liste sortieren von 5 Zahlen - 3, 2, 9, 6 und 5.

12
00:00:34,000 --> 00:00:37,650
Der Algorithmus beginnt, indem man die beiden ersten Elemente, 3 und 2,

13
00:00:37,650 --> 00:00:40,850
und Prüfen, ob sie außer Betrieb relativ zueinander sind.

14
00:00:40,850 --> 00:00:43,150
Sie sind - 3 größer als 2 ist.

15
00:00:43,150 --> 00:00:45,190
In aufsteigender Reihenfolge, sollten sie anders herum sein.

16
00:00:45,190 --> 00:00:46,610
So, tauschen wir sie.

17
00:00:46,610 --> 00:00:49,760
Nun ist die Liste sieht wie folgt aus: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Als nächstes betrachten wir die zweite und dritte Element, 3 und 9.

19
00:00:52,450 --> 00:00:55,770
Sie sind in der richtigen Reihenfolge relativ zueinander.

20
00:00:55,770 --> 00:00:58,800
Das heißt, 3 weniger als 9 so der Algorithmus nicht funktioniert tauschen sie.

21
00:00:58,800 --> 00:01:01,900
Als nächstes schauen wir auf 9 und 6. Sie sind nicht in Ordnung.

22
00:01:01,900 --> 00:01:04,260
>> Also brauchen wir, um sie auszutauschen, weil 9 ist größer als 6.

23
00:01:04,260 --> 00:01:08,840
Schließlich betrachten wir die letzten zwei Zahlen, 9 und 5.

24
00:01:08,840 --> 00:01:10,850
Sie sind nicht in Ordnung, so müssen sie ausgetauscht werden.

25
00:01:10,850 --> 00:01:13,360
Nach dem ersten Durchgang durch die vollständige Liste,

26
00:01:13,360 --> 00:01:17,140
es sieht wie folgt aus: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nicht schlecht. Es ist fast sortiert.

28
00:01:19,690 --> 00:01:22,450
Aber wir müssen in der Liste erneut ausführen, um es vollständig sortiert.

29
00:01:22,450 --> 00:01:29,250
Zwei weniger als 3, so dass wir nicht tauschen.

30
00:01:29,250 --> 00:01:31,700
>> Drei weniger als 6, so dass wir nicht tauschen.

31
00:01:31,700 --> 00:01:35,500
Sechs größer als 5 ist. Wir tauschten.

32
00:01:35,500 --> 00:01:38,460
Sechs von weniger als 9. Wir wissen nicht tauschen.

33
00:01:38,460 --> 00:01:42,170
Nach dem zweiten Durchgang, sieht es wie folgt aus: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Nun schreiben wir es in Pseudocode.

35
00:01:44,680 --> 00:01:48,450
Grundsätzlich für jedes Element in der Liste, müssen wir es betrachten

36
00:01:48,450 --> 00:01:50,060
und das Element direkt an ihrer rechten Seite.

37
00:01:50,060 --> 00:01:53,420
Wenn sie außerhalb der Reihenfolge zueinander - das heißt, wenn das Element auf der linken

38
00:01:53,420 --> 00:01:56,810
ist größer als die auf der rechten Seite -, wir sollten die beiden Elemente auszutauschen.

39
00:01:56,810 --> 00:02:01,270
>> Wir tun dies für jedes Element in der Liste, und wir haben ein Durchlauf gemacht.

40
00:02:01,270 --> 00:02:05,160
Jetzt müssen wir nur noch die Pass-Through oft genug tun, um die Liste zu sichern

41
00:02:05,160 --> 00:02:06,480
vollständig, richtig sortiert.

42
00:02:06,480 --> 00:02:08,889
Aber wie oft haben wir, um die Liste zu passieren

43
00:02:08,889 --> 00:02:10,400
garantieren, dass wir fertig sind?

44
00:02:10,400 --> 00:02:14,730
Nun, das ist das Worst-Case-Szenario, wenn wir eine vollständig rückwärts Liste haben.

45
00:02:14,730 --> 00:02:17,840
Dann dauert es eine Reihe von Durchreichen gleich der Anzahl

46
00:02:17,840 --> 00:02:19,730
der Elemente n-1.

47
00:02:19,730 --> 00:02:24,720
Wenn dies keinen Sinn macht intuitiv, von einem einfachen Fall zu denken - die Liste [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Das wird ein Pass-Through zu ergreifen, um korrekt zu sortieren.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Der schlimmste Fall ist, dass mit drei Elementen sortiert rückwärts,

50
00:02:33,060 --> 00:02:34,830
es geht um 2 Iterationen zu sortieren nehmen.

51
00:02:34,830 --> 00:02:37,980
Nach einer Iteration, es ist [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Die zweite ergibt das sortierte Array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Damit Sie wissen, Sie müssen nie durch das Array zu gehen, in der Regel

54
00:02:43,350 --> 00:02:46,790
mehr als n-1 mal, wobei n die Anzahl der Elemente in dem Array.

55
00:02:47,090 --> 00:02:50,470
Es heißt Bubble Sort, weil die größten Elemente zu "bubble-up" eher

56
00:02:50,470 --> 00:02:51,950
auf der rechten Seite ziemlich schnell.

57
00:02:51,950 --> 00:02:53,980
In der Tat hat dieser Algorithmus sehr interessantes Verhalten.

58
00:02:53,980 --> 00:02:57,410
>> Nach m Iterationen durch das gesamte Array,

59
00:02:57,410 --> 00:02:59,000
die rechten m Elemente sind garantiert

60
00:02:59,000 --> 00:03:01,000
in ihren richtigen Platz sortiert werden.

61
00:03:01,000 --> 00:03:02,280
Wenn Sie diese für sich selbst zu sehen,

62
00:03:02,280 --> 00:03:05,500
wir können es auf einem völlig rückwärts list [9, 6, 5, 3, 2] versuchen.

63
00:03:05,500 --> 00:03:08,220
Nach einem Durchgang durch die gesamte Liste,

64
00:03:08,220 --> 00:03:09,220
[Sound des Schreibens]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
die rechte 9 ist an der richtigen Stelle.

67
00:03:21,250 --> 00:03:24,760
Nach dem zweiten Pass-Through wird der 6 haben 'gesprudelt-up' der

68
00:03:24,760 --> 00:03:26,220
Sekunden rechten Ort.

69
00:03:26,220 --> 00:03:28,840
Die zwei Elemente auf der rechten Seite - 6 und 9 - wird in ihrer richtigen Orten sein

70
00:03:28,840 --> 00:03:30,580
nach den ersten beiden Durchführungen.

71
00:03:30,580 --> 00:03:32,590
>> Also, wie können wir nutzen, um den Algorithmus zu optimieren?

72
00:03:32,590 --> 00:03:34,850
Nun, nach einer Iteration durch das Array

73
00:03:34,850 --> 00:03:37,690
wir nicht wirklich brauchen, um die am weitesten rechts Element überprüfen

74
00:03:37,690 --> 00:03:39,200
weil wir wissen, dass es sortiert.

75
00:03:39,200 --> 00:03:43,050
Nach zwei Iterationen, wissen wir, dass die beiden rechten Elemente sind vorhanden.

76
00:03:43,050 --> 00:03:48,260
So im allgemeinen nach k Iterationen durch die vollständige Anordnung,

77
00:03:48,260 --> 00:03:51,550
Überprüfung der letzten k Elemente ist überflüssig, da wir wissen,

78
00:03:51,550 --> 00:03:52,360
sie sind an der richtigen Stelle schon.

79
00:03:52,360 --> 00:03:54,870
>> Also, wenn Sie das Sortieren eines Arrays von n Elementen,

80
00:03:54,870 --> 00:03:57,870
bei der ersten Iteration - Sie werden müssen alle Elemente sortiert werden - die erste n-0.

81
00:03:57,870 --> 00:04:04,170
Bei der zweiten Iteration, haben Sie auf alle Elemente, aber die letzte aussehen -

82
00:04:04,170 --> 00:04:07,090
die erste n-1.

83
00:04:07,090 --> 00:04:10,520
Eine weitere Optimierung könnte zu überprüfen, ob die Liste bereits sortiert ist

84
00:04:10,520 --> 00:04:11,710
nach jeder Iteration.

85
00:04:11,710 --> 00:04:13,900
Wenn es bereits sortiert ist, brauchen wir nicht zu einem mehr Iterationen machen

86
00:04:13,900 --> 00:04:15,310
durch die Liste.

87
00:04:15,310 --> 00:04:16,220
Wie können wir das tun?

88
00:04:16,220 --> 00:04:19,360
Nun, wenn wir machen keine Swaps auf einer Pass-Through auf der Liste,

89
00:04:19,360 --> 00:04:22,350
es ist klar, dass die Liste bereits sortiert wurde, weil wir nicht tauschen nichts.

90
00:04:22,350 --> 00:04:24,160
Also haben wir definitiv nicht noch einmal zu sortieren.

91
00:04:24,160 --> 00:04:27,960
>> Vielleicht könnten Sie initialisieren eine Flag-Variable namens "nicht sortiert", um

92
00:04:27,960 --> 00:04:30,990
false und ändern Sie ihn auf true, wenn Sie keine Elemente auf Auslagerung von

93
00:04:30,990 --> 00:04:32,290
eine Iteration durch das Array.

94
00:04:32,290 --> 00:04:35,350
Oder ähnlich, einen Zähler zu zählen, wie viele Swaps Sie

95
00:04:35,350 --> 00:04:37,040
an einem bestimmten Iteration.

96
00:04:37,040 --> 00:04:40,040
Am Ende einer Iteration, wenn Sie nicht tauschen eines der Elemente,

97
00:04:40,040 --> 00:04:41,780
Sie wissen, die Liste bereits sortiert ist und du bist fertig.

98
00:04:41,780 --> 00:04:44,090
Bubble Sort, wie andere Sortieralgorithmen, kann

99
00:04:44,090 --> 00:04:46,960
optimiert, um für alle Elemente, die eine Bestellung Verfahren haben zu arbeiten.

100
00:04:46,960 --> 00:04:50,610
>> Das ist, da zwei Elemente haben Sie eine Möglichkeit zu sagen, wenn das erste ein

101
00:04:50,610 --> 00:04:53,770
größer als, gleich oder kleiner als die zweite.

102
00:04:53,770 --> 00:04:56,870
Zum Beispiel könnten Sie die Buchstaben des Alphabets mit den Worten sortieren

103
00:04:56,870 --> 00:05:00,520
dass a <b, b <c usw.

104
00:05:00,520 --> 00:05:03,830
Oder Sie könnten sortieren Tag der Woche, wobei Sonntag weniger als Montag

105
00:05:03,830 --> 00:05:05,110
das ist weniger als Dienstag.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sort ist keineswegs eine sehr effiziente und schnelle Sortier-Algorithmus.

107
00:05:09,630 --> 00:05:12,370
Sein Worst-Case-Laufzeit ist Big O von n ²

108
00:05:12,370 --> 00:05:14,810
da muss man n Iterationen durch eine Liste zu machen

109
00:05:14,810 --> 00:05:18,430
Überprüfung aller n Elemente jeweils pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Diese Laufzeit bedeutet, dass die Anzahl der Elemente Sie Sortier steigt,

111
00:05:22,730 --> 00:05:24,330
die Laufzeit steigt quadratisch.

112
00:05:24,330 --> 00:05:27,330
>> Aber wenn Effizienz ist nicht ein wichtiges Anliegen des Programms

113
00:05:27,330 --> 00:05:29,550
oder wenn Sie nur Sortieren einer kleinen Anzahl von Elementen,

114
00:05:29,550 --> 00:05:31,660
finden Sie vielleicht Bubble Sort nützlich, weil

115
00:05:31,660 --> 00:05:33,360
Es ist eine der einfachsten Sortieralgorithmen zu verstehen

116
00:05:33,360 --> 00:05:34,250
und codieren.

117
00:05:34,250 --> 00:05:37,270
Es ist auch ein guter Weg, um Erfahrungen mit der Übersetzung eine theoretische bekommen

118
00:05:37,270 --> 00:05:40,220
Algorithmus in tatsächliche Funktionieren Code.

119
00:05:40,220 --> 00:05:43,000
Nun, das ist Bubble Sort für Sie. Danke fürs Zuschauen.

120
00:05:43,000 --> 00:05:44,000
CS50.TV