1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [マージソート]

2
00:00:02,000 --> 00:00:04,000
[ロブボーデン - ハーバード大学]

3
00:00:04,000 --> 00:00:07,000
[これはCS50です。 -  CS50.TV]

4
00:00:07,000 --> 00:00:09,000
マージソートについてお話しましょう​​。

5
00:00:09,000 --> 00:00:14,000
ここまでは、バブルソート、挿入ソート、選択ソートを見てきました。

6
00:00:14,000 --> 00:00:17,000
私は良いが何を意味するのかで私の手を波のようなものだけどね、

7
00:00:17,000 --> 00:00:21,000
マージソートは、一般的に、これらの3種類のどれよりも高いパフォーマンスを発揮します。

8
00:00:22,000 --> 00:00:27,000
>> しかし、マージソートの話の前に、のは2ソートされたリストをマージすることについてお話ししましょう​​。

9
00:00:27,000 --> 00:00:31,000
我々は、これらのように、2つのソートされたリストを取る処理を呼ぶことにします、

10
00:00:31,000 --> 00:00:35,000
そしてそれらのシングルソートされたリストを作ることを - リストをマージする。

11
00:00:35,000 --> 00:00:37,750
どのように我々はこれを行うことができますか？

12
00:00:37,750 --> 00:00:41,290
まあ、ひとつのアイデアは、ちょうど他のリストの最後にあるリストを堅持することです

13
00:00:41,290 --> 00:00:43,830
し、結果のリストをソートします。

14
00:00:43,830 --> 00:00:47,220
>> この作品が、それは不必要な多くの作業。

15
00:00:47,220 --> 00:00:49,900
私達はちょうどソートよりも高速に行うことができます。

16
00:00:49,900 --> 00:00:54,100
1間違った考えはちょうど各リストから交互にコップを取ることであることに注意してください。

17
00:00:54,100 --> 00:00:56,460
それは、最初はその作品のように思えるかもしれませんが、

18
00:00:56,460 --> 00:01:05,760
16と23は場違いであることに注意してください - 私たちは4、8、15、23、16で終わるのをやって。

19
00:01:05,760 --> 00:01:09,380
これは、マージされたリスト内の連続表示される2つの要素

20
00:01:09,380 --> 00:01:11,720
同じ初期リストにあります。

21
00:01:11,720 --> 00:01:14,850
15と16の両方が左のリストに表示されます。

22
00:01:14,850 --> 00:01:19,810
トリックは、両方のリストが既にソートされているという事実を活用することです。

23
00:01:19,810 --> 00:01:23,320
これは、我々はちょうど両方のリストの最初の要素を見ればことを意味します - 

24
00:01:23,320 --> 00:01:29,580
ここで、4,8  - そのうちの一つはまた、マージされたリストの最初の要素でなければなりません。

25
00:01:29,580 --> 00:01:31,620
さて、その理由は何ですか？

26
00:01:31,620 --> 00:01:33,520
これらのリストの両方がすでにソートされている、

27
00:01:33,520 --> 00:01:38,410
我々は2つ​​のリストを結合するときなど、4または8のいずれかが最小の要素でなければなりません。

28
00:01:38,410 --> 00:01:41,770
この場合、最小は4であり、

29
00:01:41,770 --> 00:01:46,370
ので、我々は4を取り出して私達のマージされたリストの最初の要素にすることができます。

30
00:01:46,370 --> 00:01:50,710
今、私たちは最初のリストの残りの3つの要素をマージし続ける

31
00:01:50,710 --> 00:01:52,920
2番目のリストの4つの要素。

32
00:01:52,920 --> 00:01:57,150
>> もう一度、我々は唯一の両方のリストの最初の要素に注目する必要があります。

33
00:01:57,150 --> 00:02:01,060
2の小さい方が、私たちのマージされたリストの二番目の要素でなければなりません。

34
00:02:01,060 --> 00:02:05,440
今回は、8と15の間に最小は8ですので、私たちはその挿入

35
00:02:05,440 --> 00:02:09,240
私たちのソートされたリストの2番目の要素として。

36
00:02:09,240 --> 00:02:12,180
我々は両方のリストの最初の要素を比較続けることができます

37
00:02:12,180 --> 00:02:14,420
と2のうち小さい方を削除します。

38
00:02:14,420 --> 00:02:19,460
15と23を比較すると、15が小さくなるので、それは我々の3番目の要素です。

39
00:02:21,000 --> 00:02:23,910
今では16と23を比較すると、16が小さくなっています。

40
00:02:23,910 --> 00:02:26,820
だからそれは第四の要素です。

41
00:02:26,820 --> 00:02:30,390
>> 2要素は行の同じリストから来ていることに注意してください。

42
00:02:30,390 --> 00:02:34,400
これはなぜマージリストが2つのリストから別の要素だけではできません。

43
00:02:34,400 --> 00:02:40,020
50と23を比較すると、23が小さいので、我々はそれを選択します。

44
00:02:40,770 --> 00:02:44,070
50と42の間、42が小さくなっています。

45
00:02:44,070 --> 00:02:48,290
50と108の間に、50が小さくなっています。

46
00:02:48,290 --> 00:02:52,330
そして最後に、我々はちょうど108を持っているので、それは私たちのリストの最後に行く必要があります。

47
00:02:53,750 --> 00:02:56,180
我々は素晴らしい、ソートされたリストを持っていることに注意してください。

48
00:02:56,180 --> 00:02:59,040
我々は2つ​​のリストの最初の2つの要素を比較して毎回

49
00:02:59,040 --> 00:03:02,730
我々は、マージされたリストの次の要素を決定することができた。

50
00:03:02,730 --> 00:03:08,070
これは、もし最終的なリストはここに、nは8であるn個の数字が含まれていることを意味します

51
00:03:08,070 --> 00:03:12,610
その後、我々は適切な場所にそれらの数字のすべてを取得するために最大nの比較であります。

52
00:03:13,230 --> 00:03:16,230
そのようなアルゴリズムは、線形時間で実行するように言われています

53
00:03:16,230 --> 00:03:18,090
しかしここではその心配はありません。

54
00:03:18,570 --> 00:03:22,810
>> マージのために我々のアルゴリズムを使用して、我々は、高速マージソートアルゴリズムを作ることができます。

55
00:03:22,810 --> 00:03:25,170
それでは、私たちのリストをリセットしてみましょう。

56
00:03:35,210 --> 00:03:37,750
マージソートの過程で、2つの大きなステップがあります。

57
00:03:37,750 --> 00:03:41,500
まず、継続的に半分にコップのリストを分ける

58
00:03:41,500 --> 00:03:44,860
我々はそれらのちょうど1カップとリストの束を持っているまで。

59
00:03:44,860 --> 00:03:47,350
リストには、奇数が含まれている場合は心配しないでください

60
00:03:47,350 --> 00:03:49,880
そして、それらの間完全にきれいにカットすることはできません。

61
00:03:49,880 --> 00:03:53,750
ちょうど任意インチ余分なカップを含めるリスト選ぶ

62
00:03:53,750 --> 00:03:56,240
それでは、これらのリストを分割できます。

63
00:03:58,140 --> 00:04:01,310
今、私たちは2つのリストを持っています。

64
00:04:04,120 --> 00:04:06,570
今、私たちは4リストを持っている。

65
00:04:10,350 --> 00:04:13,870
>> そして今、我々は各リストの1杯で8リストを持っている。

66
00:04:13,870 --> 00:04:16,630
だからステップ1のそれだ。

67
00:04:16,630 --> 00:04:22,230
ステップ2では、我々は繰り返し我々の前に学習したマージ·アルゴリズムを使用してリストのペアをマージします。

68
00:04:22,230 --> 00:04:29,160
108と15のマージは、リスト15、108で終わる。

69
00:04:30,330 --> 00:04:36,250
50と4のマージ、我々は4、50で終わる。

70
00:04:36,960 --> 00:04:41,400
8と42のマージ、我々は8、42で終わる。

71
00:04:42,790 --> 00:04:48,130
と23と16をマージ、私たちは16日、23日で終わる。

72
00:04:49,740 --> 00:04:52,450
これで、すべての私達のリストのサイズは2である。

73
00:04:53,020 --> 00:04:56,180
4の各リストがソートされていることに注意してください。

74
00:04:56,180 --> 00:04:59,160
>> だから我々は再びリストのペアをマージを開始することができます。

75
00:04:59,160 --> 00:05:03,240
15と108と4と50のマージ - 

76
00:05:03,240 --> 00:05:11,170
最初に108、次に50、15、4を取る。

77
00:05:11,170 --> 00:05:15,120
8、42、16、23、マージ

78
00:05:15,120 --> 00:05:22,440
我々はまずそれから、次に、8、16、23、42取る。

79
00:05:22,440 --> 00:05:27,370
だから今我々はソートされているそれぞれのサイズ4のちょうど2つのリストを持っています。

80
00:05:27,370 --> 00:05:30,980
だから今我々は、これらの2つのリストをマージします。

81
00:05:30,980 --> 00:05:33,440
まず4を取る。

82
00:05:33,440 --> 00:05:36,580
その後、我々は8を取る。

83
00:05:36,580 --> 00:05:50,700
その後、我々は次に次に次に次に15と16、23、42、50、108を取る。

84
00:05:50,700 --> 00:05:52,220
そして、我々は完了です。

85
00:05:52,220 --> 00:05:54,900
我々は今、ソートされたリストを持っています。

86
00:05:54,900 --> 00:05:57,890
だから、これは正確にはどのくらいの速さだったのですか？

87
00:05:57,890 --> 00:06:02,000
専門用語では、マージソートはO（n log n）である

88
00:06:02,000 --> 00:06:07,380
一方、バブルソート、挿入ソート、選択ソートのすべてはO（n²）である。

89
00:06:07,380 --> 00:06:11,120
あなたはすぐに学ぶように、実際には、あなたは、ソートを思い付くことができません

90
00:06:11,120 --> 00:06:14,820
それは一般的なケースではO（n log n）のよりもパフォーマンスが向上します。

91
00:06:14,820 --> 00:06:19,120
あなたはまだそれを見ていない場合は、再度、このビッグO記法の心配はありません。

92
00:06:19,120 --> 00:06:23,490
>> 私たちは本当に大きなリストをソートしたい場合だけ、これが意味することを知っている

93
00:06:23,490 --> 00:06:26,820
バブルソート、挿入ソート、選択ソートは、潜在的に取ることができる

94
00:06:26,820 --> 00:06:29,500
大幅に長くマージソートより。

95
00:06:29,500 --> 00:06:33,210
これは、マージソートは、すべてのリストに対して速くなることを意味するものではありません

96
00:06:33,210 --> 00:06:36,220
あるいは、特定のサイズの下の任意の単一のリストを表示してください。

97
00:06:36,220 --> 00:06:41,950
たとえば、挿入ソートは、5つの要素よりも小さいすべてのリストの最速のソートであるかもしれません。

98
00:06:41,950 --> 00:06:47,360
実際には、マージソートは50要素のような小さなリストのほうが高速です。

99
00:06:47,360 --> 00:06:51,120
>> しかし、この余分な速度は価格なしで来ていません。

100
00:06:51,120 --> 00:06:54,770
代わりにリストを取り、リストを変更し、当社の他の種類のとは異なり、

101
00:06:54,770 --> 00:06:58,740
私たちは、ソートされたリストを取得するまで、マージソートは、いくつかの追加のスペースを必要と

102
00:06:58,740 --> 00:07:00,900
一緒に2つのリストをマージすることができます。

103
00:07:00,900 --> 00:07:04,690
我々はすぐにマージされたリストを格納するためにマージされているリストを使用することはできません

104
00:07:04,690 --> 00:07:08,880
我々はまだマージする必要がある要素を上書きするかもしれないので。

105
00:07:08,880 --> 00:07:13,540
このスペースには、価格のビットですが、それは通常無理ではありません。

106
00:07:13,540 --> 00:07:15,330
そして、それはマージソートのためのそれだ。

107
00:07:15,330 --> 00:07:18,490
>> 私の名前はロブ·ボーデンであり、これはCS50です。

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

109
00:07:20,500 --> 00:07:24,000
 - と選択ソート。

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

111
00:07:25,880 --> 00:07:31,480
ああ、私はそれを提示された方法に切り替えているため、あまりにもを取るようになった。

112
00:07:31,480 --> 00:07:35,680
左側のリスト。それはタイプミスでした。

113
00:07:35,680 --> 00:07:39,290
[misspoke]私がしくじった - 

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

115
00:07:41,190 --> 00:07:44,190
私がわからない -