1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Merge Sort]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Dies ist CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Reden wir über merge sort.

5
00:00:09,000 --> 00:00:14,000
Bisher haben Sie bubble sort, insertion sort und Auswahl Art gesehen.

6
00:00:14,000 --> 00:00:17,000
Obwohl ich werde Art von Welle meiner Hand, was ich damit meine, besser,

7
00:00:17,000 --> 00:00:21,000
Mergesort führt in der Regel besser als eine dieser 3 Sorten.

8
00:00:22,000 --> 00:00:27,000
>> Aber bevor wir über Mergesort, lassen Sie uns über die Verschmelzung von 2 sortierte Listen zu sprechen.

9
00:00:27,000 --> 00:00:31,000
Wir rufen den Prozess der Übernahme 2 sortierte Listen, wie diese,

10
00:00:31,000 --> 00:00:35,000
und macht einen einzigen sortierten Liste von ihnen - die Zusammenführung der Listen.

11
00:00:35,000 --> 00:00:37,750
Wie können wir das tun?

12
00:00:37,750 --> 00:00:41,290
Nun, das ist eine Idee, um nur Stick eine Liste an das Ende der anderen Liste

13
00:00:41,290 --> 00:00:43,830
und dann sortieren Sie die Liste aus.

14
00:00:43,830 --> 00:00:47,220
>> Während dies funktioniert, ist es eine Menge unnötiger Arbeit.

15
00:00:47,220 --> 00:00:49,900
Wir können es schneller tun als nur sorting.

16
00:00:49,900 --> 00:00:54,100
Beachten Sie, dass eine falsche Idee, nur nehmen abwechselnd Becher aus jeder Liste ist.

17
00:00:54,100 --> 00:00:56,460
Während das mag das funktioniert auf den ersten Blick,

18
00:00:56,460 --> 00:01:05,760
tun, dass wir am Ende mit 4, 8, 15, 23, 16 - Ankündigung, dass 16 und 23 fehl am Platze sind.

19
00:01:05,760 --> 00:01:09,380
Dies liegt daran, 2 Elemente, die angezeigt Folge sollte in der zusammengeführte Liste

20
00:01:09,380 --> 00:01:11,720
sind in der gleichen ursprünglichen Liste.

21
00:01:11,720 --> 00:01:14,850
Beide 15 und 16 sind in der Liste auf der linken Seite.

22
00:01:14,850 --> 00:01:19,810
Der Trick ist, den Vorteil der Tatsache, dass beide Listen bereits sortiert sind zu nehmen.

23
00:01:19,810 --> 00:01:23,320
Dies bedeutet, dass, wenn wir nur auf die ersten Elemente der beiden Listen aussehen -

24
00:01:23,320 --> 00:01:29,580
Hier, 4 und 8 - muß eine von ihnen auch das erste Element der vereinigten Liste sein.

25
00:01:29,580 --> 00:01:31,620
Nun, warum ist das so?

26
00:01:31,620 --> 00:01:33,520
Beide Listen sind bereits sortiert,

27
00:01:33,520 --> 00:01:38,410
und so entweder 4 oder 8 muss das kleinste Element sein, wenn wir die 2 Listen zu kombinieren.

28
00:01:38,410 --> 00:01:41,770
In diesem Fall ist die kleinste 4,

29
00:01:41,770 --> 00:01:46,370
so können wir nehmen 4 und machen es das erste Element unserer zusammengeführten Liste.

30
00:01:46,370 --> 00:01:50,710
Jetzt haben wir weiterhin die Zusammenlegung der verbleibenden 3 Elemente der ersten Liste

31
00:01:50,710 --> 00:01:52,920
und 4 Elemente der zweiten Liste.

32
00:01:52,920 --> 00:01:57,150
>> Wieder einmal müssen wir nur auf das erste Element der beiden Listen zu suchen.

33
00:01:57,150 --> 00:02:01,060
Je kleiner der 2 ist der zweite Bestandteil unserer vereinigten Liste sein.

34
00:02:01,060 --> 00:02:05,440
Dieses Mal zwischen 8 und 15 die kleinste ist 8, und so fügen wir, dass

35
00:02:05,440 --> 00:02:09,240
als zweites Element der sortierten Liste.

36
00:02:09,240 --> 00:02:12,180
Wir können weiterhin das Vergleichen der ersten Elemente der beiden Listen

37
00:02:12,180 --> 00:02:14,420
und Entfernen des kleineren der zwei.

38
00:02:14,420 --> 00:02:19,460
Vergleichens 15 und 23, 15 ist kleiner und so daß die das dritte Element.

39
00:02:21,000 --> 00:02:23,910
Nun Vergleichens 16 und 23, 16 ist kleiner.

40
00:02:23,910 --> 00:02:26,820
Damit ist das vierte Element.

41
00:02:26,820 --> 00:02:30,390
>> Beachten Sie, dass 2 Elemente aus der gleichen Liste in einer Reihe kam.

42
00:02:30,390 --> 00:02:34,400
Deshalb ist das zusammengeführte Liste kann nicht einfach alternativen Elementen aus den 2 Listen.

43
00:02:34,400 --> 00:02:40,020
Vergleicht man 50 und 23, 23 ist kleiner, so wählen wir, dass.

44
00:02:40,770 --> 00:02:44,070
Zwischen 50 und 42, 42 ist kleiner.

45
00:02:44,070 --> 00:02:48,290
Zwischen 50 und 108, beträgt 50 kleiner.

46
00:02:48,290 --> 00:02:52,330
Und schließlich müssen wir nur noch 108, so muss es am Ende unserer Liste.

47
00:02:53,750 --> 00:02:56,180
Beachten Sie, dass wir eine schöne, sortierte Liste haben.

48
00:02:56,180 --> 00:02:59,040
Jedes Mal, verglichen wir die ersten 2 Elemente der 2 Listen

49
00:02:59,040 --> 00:03:02,730
konnten wir das nächste Element des fusionierten Liste zu bestimmen.

50
00:03:02,730 --> 00:03:08,070
Das heißt, wenn die endgültige Liste n Zahlen, wobei n hier 8 enthält,

51
00:03:08,070 --> 00:03:12,610
dann brauchen wir höchstens n Vergleiche alle diese Zahlen in den richtigen Ort gelangen.

52
00:03:13,230 --> 00:03:16,230
Ein solcher Algorithmus ist in der linearen Zeit ausführen,

53
00:03:16,230 --> 00:03:18,090
aber nicht über das hier machen.

54
00:03:18,570 --> 00:03:22,810
>> Mit unserem Algorithmus zur verschmelzen, können wir eine schnelle Mergesort-Algorithmus.

55
00:03:22,810 --> 00:03:25,170
Also, lasst uns setzen unseren Listen.

56
00:03:35,210 --> 00:03:37,750
Es gibt 2 große Schritte in den Prozess der Zusammenführung sort.

57
00:03:37,750 --> 00:03:41,500
Zunächst kontinuierlich spaltete die Liste der Becher in zwei Hälften

58
00:03:41,500 --> 00:03:44,860
bis wir eine Reihe von Listen mit nur 1 Tasse in ihnen.

59
00:03:44,860 --> 00:03:47,350
Mach dir keine Sorgen, wenn eine Liste eine ungerade Anzahl

60
00:03:47,350 --> 00:03:49,880
und man kann nicht einen perfekt sauberen Schnitt zwischen ihnen.

61
00:03:49,880 --> 00:03:53,750
Einfach willkürlich auswählen, welche Liste, um die zusätzliche Tasse in. gehören

62
00:03:53,750 --> 00:03:56,240
Also, lasst uns aufgeteilt diese Listen.

63
00:03:58,140 --> 00:04:01,310
Jetzt haben wir 2 Listen.

64
00:04:04,120 --> 00:04:06,570
Jetzt haben wir 4 Listen.

65
00:04:10,350 --> 00:04:13,870
>> Und jetzt haben wir 8 Listen mit einer einzigen Tasse in jeder Liste.

66
00:04:13,870 --> 00:04:16,630
Das ist es also für Schritt 1.

67
00:04:16,630 --> 00:04:22,230
Für Schritt 2 wir immer wieder verschmelze Paare von Listen mit der Merge-Algorithmus haben wir zuvor gelernt.

68
00:04:22,230 --> 00:04:29,160
Zusammenführen 108 und 15, landen wir mit der Liste 15, 108.

69
00:04:30,330 --> 00:04:36,250
Zusammenführen 50 und 4, landen wir mit 4, 50.

70
00:04:36,960 --> 00:04:41,400
Zusammenführen 8 und 42, landen wir mit 8, 42.

71
00:04:42,790 --> 00:04:48,130
Und Zusammenführen 23 und 16, landen wir mit 16, 23.

72
00:04:49,740 --> 00:04:52,450
Nun sind alle unsere Listen sind der Größe 2.

73
00:04:53,020 --> 00:04:56,180
Feststellen, dass jedes der vier Listen sortiert ist.

74
00:04:56,180 --> 00:04:59,160
>> So können wir beginnen Verschmelzung Paar von Listen wieder.

75
00:04:59,160 --> 00:05:03,240
Zusammenführen 15 und 108 und 4 und 50 -

76
00:05:03,240 --> 00:05:11,170
zuerst den 4, dann die 15, dann die 50, dann die 108.

77
00:05:11,170 --> 00:05:15,120
Zusammenführen 8, 42 und 16, 23,

78
00:05:15,120 --> 00:05:22,440
wir zunächst die 8, dann die 16, dann die 23, dann die 42.

79
00:05:22,440 --> 00:05:27,370
So jetzt haben wir nur 2 Listen der Größe 4 haben, von denen jeder sortiert.

80
00:05:27,370 --> 00:05:30,980
So jetzt haben wir verschmelzen diese 2 Listen.

81
00:05:30,980 --> 00:05:33,440
Zuerst nehmen wir die 4.

82
00:05:33,440 --> 00:05:36,580
Dann nehmen wir die 8.

83
00:05:36,580 --> 00:05:50,700
Dann nehmen wir den 15 und 16, dann 23, dann 42, dann 50, dann 108.

84
00:05:50,700 --> 00:05:52,220
Und wir sind fertig.

85
00:05:52,220 --> 00:05:54,900
Wir haben jetzt eine sortierte Liste.

86
00:05:54,900 --> 00:05:57,890
So wie schnell war das genau?

87
00:05:57,890 --> 00:06:02,000
In technischer Hinsicht ist Mergesort O (n log n),

88
00:06:02,000 --> 00:06:07,380
während alle bubble sort, insertion sort und Auswahl sort O sind (n ²).

89
00:06:07,380 --> 00:06:11,120
In der Tat, wie Sie bald lernen, werden Sie nicht in der Lage zu kommen mit einer Art

90
00:06:11,120 --> 00:06:14,820
das funktioniert besser als O (n log n) im allgemeinen Fall.

91
00:06:14,820 --> 00:06:19,120
Auch nicht über diesen großen O-Notation Sorgen, wenn Sie es noch nicht gesehen.

92
00:06:19,120 --> 00:06:23,490
>> Genau wissen, dass dies bedeutet, wenn wir eine wirklich große Liste sortieren wollte

93
00:06:23,490 --> 00:06:26,820
bubble sort, insertion sort und Auswahl sort könnte dauern

94
00:06:26,820 --> 00:06:29,500
deutlich länger als Mergesort.

95
00:06:29,500 --> 00:06:33,210
Es bedeutet nicht, dass Mergesort schneller für alle Listen werden

96
00:06:33,210 --> 00:06:36,220
oder sogar für jede einzelne Liste unter einer bestimmten Größe.

97
00:06:36,220 --> 00:06:41,950
Zum Beispiel könnte insertion sort die schnellste Art für alle Listen kleiner als 5 Elemente.

98
00:06:41,950 --> 00:06:47,360
In der Praxis ist Mergesort in der Regel schneller für Listen so klein wie 50 Elemente.

99
00:06:47,360 --> 00:06:51,120
>> Aber diese zusätzliche Geschwindigkeit nicht ohne einen Preis zu kommen.

100
00:06:51,120 --> 00:06:54,770
Im Gegensatz zu unseren anderen Sorten nehmen, deren Liste und ändern Sie die Liste an Ort und Stelle

101
00:06:54,770 --> 00:06:58,740
bis wir eine sortierte Liste zu erhalten, muss Mergesort zusätzlichen Speicherplatz

102
00:06:58,740 --> 00:07:00,900
bis 2 Listen miteinander verschmelzen.

103
00:07:00,900 --> 00:07:04,690
Wir können nicht sofort verwenden Listen, die zusammengeführt werden, um die zusammengeführte Liste speichern

104
00:07:04,690 --> 00:07:08,880
da wir überschreiben können Elemente, die müssen noch zusammengeführt werden.

105
00:07:08,880 --> 00:07:13,540
Dieser Raum ist ein bisschen wie ein Preis, aber es ist in der Regel nicht unvernünftig.

106
00:07:13,540 --> 00:07:15,330
Und das ist es für merge sort.

107
00:07:15,330 --> 00:07:18,490
>> Mein Name ist Rob Bowden, und dies ist CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- Und die Auswahl sort.

110
00:07:24,000 --> 00:07:25,880
[Lacht]

111
00:07:25,880 --> 00:07:31,480
Oh, ich muss, dass nehmen Sie auch, weil ich, wie ich mich präsentieren sie eingeschaltet.

112
00:07:31,480 --> 00:07:35,680
Liste auf der linken Seite. Das war ein Tippfehler.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] Ich habe es vermasselt -

114
00:07:39,290 --> 00:07:41,190
[Lacht]

115
00:07:41,190 --> 00:07:44,190
Ich weiß nicht, was -