1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [挿入ソート]

2
00:00:02,290 --> 00:00:04,240
[トミーM​​acWilliam] [ハーバード大学]

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

4
00:00:07,290 --> 00:00:13,060
のは、挿入ソート、番号のリストを取得し、それらをソートするためのアルゴリズムを見てみましょう。

5
00:00:13,060 --> 00:00:18,300
アルゴリズムは、覚えているが、単純にタスクを達成するためのステップバイステップの手順です。

6
00:00:18,300 --> 00:00:23,640
挿入ソートの基本的な考え方は、二つの部分に私たちのリストを分割することです

7
00:00:23,640 --> 00:00:26,580
ソートされた部分と、ソートされていない部分。

8
00:00:26,580 --> 00:00:29,290
>> アルゴリズムの各ステップで、番号が移動され

9
00:00:29,290 --> 00:00:32,439
ソートされていない部分から部分へソート

10
00:00:32,439 --> 00:00:35,680
最終的になるまでは、リスト全体がソートされます。

11
00:00:35,680 --> 00:00:43,340
23、42、4、16、8、15  -  6ここソートされていない番号のリストです。

12
00:00:43,340 --> 00:00:47,680
これらの数値が昇順ですべてではありませんので、それらはソートされていないしている。

13
00:00:47,680 --> 00:00:53,890
我々はまだ選別開始していないので、私達は私達のソートされていない部分すべての6つの要素を考慮します。

14
00:00:53,890 --> 00:00:59,270
>> かつて我々は選別開始、我々はこれらの左側にそれらのソート番号を置くことにしましょう​​。

15
00:00:59,270 --> 00:01:03,600
だから、私たちのリストの最初の要素は、23から始めてみましょう。

16
00:01:03,600 --> 00:01:06,930
我々は、まだ我々のソート部分内の任意の要素を持っていない

17
00:01:06,930 --> 00:01:12,460
ので、単に23が私たちのソート部分の始点と終点であると考えてみましょう。

18
00:01:12,460 --> 00:01:16,510
今、私たちのソート部分は、1つ数、23を持っています

19
00:01:16,510 --> 00:01:20,260
と私たちの無分別の部分は、これらの5つの数字を持っています。

20
00:01:20,260 --> 00:01:27,320
現在、ソートされた部分に私たちのソートされていない部分、42の次の番号を挿入してみましょう。

21
00:01:27,320 --> 00:01:35,930
>> そうするために、我々は23から42を比較する必要があるでしょう - 私たちのソート部分の唯一の要素をこれまでのところ。

22
00:01:35,930 --> 00:01:41,980
四十二は23より大きいので、単に末尾に42を追加することができます

23
00:01:41,980 --> 00:01:45,420
リストのソートされた部分。すばらしい！

24
00:01:45,420 --> 00:01:51,850
現在、私たちのソート部分は2つの要素を持っており、私たちの無分別の部分には、4つの要素を持っています。

25
00:01:51,850 --> 00:01:57,200
だから、ソートされていない部分の次の要素は、ここ4に移動してみましょう。

26
00:01:57,200 --> 00:02:00,230
だから、ここでこれは、ソートされた部分に配置する必要がありますか？

27
00:02:00,230 --> 00:02:04,220
>> 覚えておいて、私たちは、ソートされた順序で、この番号を配置したい

28
00:02:04,220 --> 00:02:08,680
従って私達のソート部分が正しくソートされたすべての回で残っています。

29
00:02:08,680 --> 00:02:14,380
我々は42の右に4を配置した場合、その後私たちのリストは順不同になります。

30
00:02:14,380 --> 00:02:18,380
それでは、私たちのソート部分に右から左へ移動し続けることができます。

31
00:02:18,380 --> 00:02:23,260
私たちが移動すると、まずは、新しい番号のために場所を空けるために下の位置にそれぞれの番号を移動できます。

32
00:02:25,440 --> 00:02:31,740
さて、4も23未満であるので、我々はどちらかそれをここに配置することはできません。

33
00:02:31,740 --> 00:02:34,480
23右の一箇所を移動してみましょう。

34
00:02:36,500 --> 00:02:43,120
>> 我々はソート部分の最初のスロットに4を配置したいと思いますことを意味します。

35
00:02:43,120 --> 00:02:46,300
リスト内のこのスペースは既に空だったかに注目してください、

36
00:02:46,300 --> 00:02:51,120
我々は彼らに遭遇してきたように、私たちは、ソートされた要素を下に移動してきたので。

37
00:02:51,120 --> 00:02:52,740
かしこまりました。だから、私たちは途中でそこにいる。

38
00:02:52,740 --> 00:02:57,990
ソートされた部分に16を挿入することによって、我々のアルゴリズムを続けましょう。

39
00:02:59,260 --> 00:03:03,820
シックスティーンが42未満であるので、の右に42を移動できます。

40
00:03:05,700 --> 00:03:10,190
シックスティーンも23未満であるので、のは、その要素を移動できます。

41
00:03:11,790 --> 00:03:20,820
>> さて、16が4よりも大きい。我々は4と23の間に16を挿入したいようなので、それが見えます。

42
00:03:20,820 --> 00:03:24,620
右から左にリストのソートされた部分を通って移動しながら、

43
00:03:24,620 --> 00:03:29,160
4は、数よりも小さい場合、我々が見てきた最初の番号です

44
00:03:29,160 --> 00:03:31,540
我々は、挿入しようとしている。

45
00:03:31,540 --> 00:03:35,820
だから、今、私たちは、この空のスロットに16を挿入することができます

46
00:03:35,820 --> 00:03:40,520
その、覚えて、我々は以上のソート部分に移動する要素で作成しました

47
00:03:40,520 --> 00:03:43,340
我々は彼らに遭遇してきたように。

48
00:03:43,340 --> 00:03:47,900
>> かしこまりました。今、私たちは4つの要素と2つのソートされていない要素をソートしている。

49
00:03:47,900 --> 00:03:51,600
それでは、ソートされた部分に8を動かしてみましょう。

50
00:03:51,600 --> 00:03:55,010
エイトは42未満です。

51
00:03:55,010 --> 00:03:56,940
エイトは23未満です。

52
00:03:56,940 --> 00:04:00,230
と8は16未満です。

53
00:04:00,230 --> 00:04:03,110
しかし8は4よりも大きくなっています。

54
00:04:03,110 --> 00:04:07,280
そこで、我々は4と16の間に8を挿入したいと思います。

55
00:04:09,070 --> 00:04:13,650
15  - そして今、我々は単にソートするには、左側の1以上の要素を持っています。

56
00:04:13,950 --> 00:04:16,589
フィフティーンは、42未満である

57
00:04:16,589 --> 00:04:19,130
フィフティーンは23未満です。

58
00:04:19,130 --> 00:04:21,750
そして15は16未満です。

59
00:04:21,750 --> 00:04:24,810
しかし、15は8より大きい。

60
00:04:24,810 --> 00:04:27,440
>> 私たちは私たちの最終的な挿入を作りたい場所だから、ここにある。

61
00:04:28,770 --> 00:04:30,330
そして、我々は完了です。

62
00:04:30,330 --> 00:04:33,540
私たちは、ソートされていない部分には多くの要素を持っていない

63
00:04:33,540 --> 00:04:36,670
と私たちのソート部分が正しい順序である。

64
00:04:36,670 --> 00:04:40,270
番号が小さいものから順に並べられます。

65
00:04:40,270 --> 00:04:44,330
それでは、我々だけで実行された手順を説明し、いくつかの擬似コードを見てみましょう。

66
00:04:46,760 --> 00:04:51,740
>> 1行目に、我々はリストの各要素を反復処理する必要があることがわかります

67
00:04:51,740 --> 00:04:57,060
目以外の、ソートされていない部分の最初の要素は単になってしまうので

68
00:04:57,060 --> 00:05:00,220
ソートされた部分の最初の要素。

69
00:05:00,220 --> 00:05:06,320
2行目と3行目では、我々は、ソートされていない部分の我々の現在の場所を追跡している。

70
00:05:06,320 --> 00:05:10,450
要素は、我々が現時点でソート部分に移動している数を表し

71
00:05:10,450 --> 00:05:15,600
jは、ソートされていない部分に私たちのインデックスを表します。

72
00:05:15,600 --> 00:05:20,980
>> 4行目に、我々は、右から左へソート部分を反復している。

73
00:05:20,980 --> 00:05:26,010
私達は私達の現在の位置の左側にある要素回繰り返し処理を停止したい

74
00:05:26,010 --> 00:05:30,050
我々は挿入しようとしている要素より小さい。

75
00:05:30,050 --> 00:05:35,600
5行目で、私たちは右に1スペースに遭遇した各要素をシフトしている。

76
00:05:35,600 --> 00:05:40,950
我々は最初の要素を見つけたときそのように、我々は明らかに挿入するスペースがあるでしょう

77
00:05:40,950 --> 00:05:44,080
我々が移動している要素より小さい。

78
00:05:44,080 --> 00:05:50,800
6行目では、我々は、ソートされた部分を通って左に移動し続けることが私たちのカウンタを更新しています。

79
00:05:50,800 --> 00:05:56,860
最後に、7行目に、我々はリストのソートされた部分に要素を挿入している。

80
00:05:56,860 --> 00:06:00,020
>> 我々は、それが位置jに挿入しても大丈夫だと知っている

81
00:06:00,020 --> 00:06:05,360
我々はすでにそこに右に1スペースであることが使用されている要素を移動したためである。

82
00:06:05,360 --> 00:06:09,460
覚えておいて、我々は、右から左へソート部分を通って移動している、

83
00:06:09,460 --> 00:06:13,960
しかし、我々は左から右にソートされていない部分を通って移動しています。

84
00:06:13,960 --> 00:06:19,090
かしこまりました。現在、アルゴリズムがかかったことを実行中のどのくらいの時間を見てみましょう。

85
00:06:19,090 --> 00:06:25,300
まず、このアルゴリズムは、最悪の場合に実行するためにどのくらい時間がかかるか質問を頼むよ。

86
00:06:25,300 --> 00:06:29,040
我々はビッグO記法を使って、この実行時間を表していることを思い出してください。

87
00:06:32,530 --> 00:06:38,500
私たちのリストをソートするために、我々は、ソートされていない部分の要素を反復しなければならなかった

88
00:06:38,500 --> 00:06:43,430
潜在的にソートされた部分のすべての要素をそれらの各要素に対して。

89
00:06:43,430 --> 00:06:47,950
直感的には、O（n ^ 2）操作のようなこの音。

90
00:06:47,950 --> 00:06:51,840
>> 私たちの擬似コードを見てみると、我々は、別のループ内にネストループを持っている

91
00:06:51,840 --> 00:06:55,290
その、確かに、O（n ^ 2）操作のように聞こえる。

92
00:06:55,290 --> 00:07:01,590
しかし、リストのソートされた部分は、最後の最後まで全体のリストが含まれていなかった。

93
00:07:01,590 --> 00:07:06,920
それでも、我々は潜在的にソートされた部分の冒頭に新しい要素を挿入することができます

94
00:07:06,920 --> 00:07:09,320
アルゴリズムの反復ごとに、

95
00:07:09,320 --> 00:07:14,500
これは、我々はソートの部分に、現在、各要素を見なければならないだろうことを意味します。

96
00:07:14,500 --> 00:07:20,090
だから、それは、我々は潜在的に、2番目の要素に対して1つの比較を行うことができることを意味

97
00:07:20,090 --> 00:07:24,660
第三の要素の2つの比較、などなど。

98
00:07:24,660 --> 00:07:32,480
だから、トータルのステップ数は、1からリストの長さから1を引いたまでの整数の和である。

99
00:07:32,480 --> 00:07:35,240
我々は合計でこれを表すことができます。

100
00:07:41,170 --> 00:07:47,270
>> 我々はここで和に行くことはありませんが、それはこの総和に等しくなることが判明

101
00:07:47,270 --> 00:07:57,900
N / 2  - 同等のN ^ 2/2で2オーバー、 -  N（N-1）。

102
00:07:57,900 --> 00:08:00,800
漸近的な実行時の話をするとき、

103
00:08:00,800 --> 00:08:05,170
このn ^ 2という用語は、このn任期を支配しようとしている。

104
00:08:05,170 --> 00:08:11,430
だから、挿入ソートは、Big O（n ^ 2）である。

105
00:08:11,430 --> 00:08:16,150
我々はすでにソートされたリストに挿入ソートを実行した場合。

106
00:08:16,150 --> 00:08:20,960
その場合、我々は、単に左から右へ並べ替え部分を構築したい。

107
00:08:20,960 --> 00:08:25,050
そこで、我々は唯一のnステップの順序に必要になります。

108
00:08:25,050 --> 00:08:29,740
>> 挿入ソートは、nのベスト·ケースの性能を有することを意味し、

109
00:08:29,740 --> 00:08:34,130
その我々はΩ（n）で表す。

110
00:08:34,130 --> 00:08:36,190
そして、それは、挿入ソートのためのそれだ

111
00:08:36,190 --> 00:08:40,429
我々はリストをソートするために使用できる多くのアルゴリズムの一つ。

112
00:08:40,429 --> 00:08:43,210
私の名前はトミーであり、これはCS50です。

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
ああ、あなたは一度だけ、それが起動する停止することはできません。

115
00:09:01,620 --> 00:09:04,760
ああ、我々はそれをやった -  >>ブーム！