1
00:00:00,000 --> 00:00:02,826
>> [音楽再生]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD：だから挿入ソートは別です
このアルゴリズムは、我々は配列をソートするために使用することができます。

4
00:00:09,370 --> 00:00:12,350
このアルゴリズムの背後にある考え方
あなたのソートされた配列を構築することです

5
00:00:12,350 --> 00:00:19,670
代わりに、外要素をシフトします
あなたが行くような方法は、部屋を作るために。

6
00:00:19,670 --> 00:00:22,240
これは多少異なります
選択ソートやバブルから

7
00:00:22,240 --> 00:00:25,460
ソート、例えば、どこ
私たちは場所を調整しています、

8
00:00:25,460 --> 00:00:26,910
ここで、我々はスワップを作っています。

9
00:00:26,910 --> 00:00:29,760
>> この場合、私たちは実際にしています
やってスライド要素であります

10
00:00:29,760 --> 00:00:31,390
道のうち、オーバー。

11
00:00:31,390 --> 00:00:34,030
このアルゴリズムをどのように
擬似コードで働きますか？

12
00:00:34,030 --> 00:00:37,646
まあちょうど任意としましょう
配列の最初の要素は、ソートされます。

13
00:00:37,646 --> 00:00:38,770
我々は場所に構築しています。

14
00:00:38,770 --> 00:00:42,660
>> 我々はつもり一度に一つの要素に行くしていて、
それを構築し、私たちが見る最初の事

15
00:00:42,660 --> 00:00:43,890
1つの要素の配列です。

16
00:00:43,890 --> 00:00:47,720
定義することにより、1
要素の配列がソートされます。

17
00:00:47,720 --> 00:00:50,850
>> その後、我々は、このプロセスを繰り返しますuntil--
我々は、以下の処理を繰り返します

18
00:00:50,850 --> 00:00:52,900
すべての要素まで、ソートされています。

19
00:00:52,900 --> 00:00:57,770
次のソートされていない要素を見て、
ソートされた部分に挿入し、

20
00:00:57,770 --> 00:01:01,209
必要な数をシフトさせることにより
道の外の要素の。

21
00:01:01,209 --> 00:01:03,750
うまくいけば、この可視化
あなたがです正確に何を参照するのに役立ちます

22
00:01:03,750 --> 00:01:05,980
挿入ソートで起こっ。

23
00:01:05,980 --> 00:01:08,010
>> だからもう一度、ここで私たちです
全体未ソート配列、

24
00:01:08,010 --> 00:01:10,970
すべての要素が赤で示されています。

25
00:01:10,970 --> 00:01:13,320
そしてのは従ってみましょう
私たちの擬似コードのステップ。

26
00:01:13,320 --> 00:01:16,970
まず最初にすることは、私たちが呼んでいます
配列の最初の要素、ソート。

27
00:01:16,970 --> 00:01:20,920
だから我々はちょうどつもりだと言います
5、あなたは今ソートされています。

28
00:01:20,920 --> 00:01:24,570
>> その後、我々は次を見て
配列のソートされていない要素

29
00:01:24,570 --> 00:01:27,610
そして我々はそれを挿入したいです
ソートされた部分に、

30
00:01:27,610 --> 00:01:29,750
要素の上にシフトすることもできます。

31
00:01:29,750 --> 00:01:33,470
だから、二人は次のソートされていないです
配列の要素。

32
00:01:33,470 --> 00:01:36,250
明らかに、前所属します
5ので、私たちがやるつもりです

33
00:01:36,250 --> 00:01:41,580
ソートの第二のために取って2を保持しています、
以上の5をシフトし、次に2を挿入

34
00:01:41,580 --> 00:01:43,210
5の前に、どこに行く必要があります。

35
00:01:43,210 --> 00:01:45,280
そして今、我々は、2つのソートされていると言うことができます。

36
00:01:45,280 --> 00:01:48,400
>> あなたが見ることができるように、我々はこれまでのところ唯一きました
配列の二つの要素を見ました。

37
00:01:48,400 --> 00:01:50,600
私たちは見ていません
まったく休むが、我々はしました

38
00:01:50,600 --> 00:01:54,582
でソートし、これらの2つの要素を持って
変速機構の方法。

39
00:01:54,582 --> 00:01:56,410
>> だから我々は、再度処理を繰り返します。

40
00:01:56,410 --> 00:01:58,850
次のソートされていないを見てください
要素は、それは一つです。

41
00:01:58,850 --> 00:02:04,010
、のは、第二のために、その脇に保持してみましょう
以上のすべてをシフトし、1を入れて

42
00:02:04,010 --> 00:02:05,570
どこに行く必要があります。

43
00:02:05,570 --> 00:02:08,110
>> 繰り返しますが、まだ、私たちは今までしました
1、2、5を見ました。

44
00:02:08,110 --> 00:02:12,480
我々は来ている他に何かわかりません、
しかし、我々はこれらの3つの要素をソートしました。

45
00:02:12,480 --> 00:02:16,030
>> 次のソートされていない要素があります
3、私たちは横に置いておきましょう。

46
00:02:16,030 --> 00:02:18,200
私たちは私たちの上にシフトします
これは、この時間に必要

47
00:02:18,200 --> 00:02:21,820
以前のように、すべてではありません
2つのケースは、それだけで5です。

48
00:02:21,820 --> 00:02:25,440
そして、我々は三スティックよ、
2と5の間。

49
00:02:25,440 --> 00:02:27,849
>> シックスは、次のソートされていないです
配列に要素。

50
00:02:27,849 --> 00:02:31,140
実際には6 5よりも大きいので、
私たちも、任意のスワップを行う必要はありません。

51
00:02:31,140 --> 00:02:35,710
私達はちょうど右の6つのタックすることができます
ソートされた部分の端。

52
00:02:35,710 --> 00:02:38,270
>> 最後に、4つです
最後にソートされていない要素。

53
00:02:38,270 --> 00:02:42,060
だから私たちは横に置いておきましょう、以上のシフト
我々はオーバーシフトする必要がある要素、

54
00:02:42,060 --> 00:02:43,780
そして、それが属する4を置きます。

55
00:02:43,780 --> 00:02:46,400
そして今、見て私たちはソートしました
すべての要素の。

56
00:02:46,400 --> 00:02:48,150
挿入に注意してください
ソート、我々は持っていませんでした

57
00:02:48,150 --> 00:02:50,240
アレイ全体を前後に移動します。

58
00:02:50,240 --> 00:02:54,720
私たちは、アレイにわたって行ってきました
一度、私たちは物事をシフト

59
00:02:54,720 --> 00:02:59,870
ために、我々はすでに、遭遇するだろうと
新しい要素のための部屋を作るために。

60
00:02:59,870 --> 00:03:02,820
>> だから、最悪の場合は何
挿入ソートとシナリオ？

61
00:03:02,820 --> 00:03:05,090
最悪の場合、
アレイは、逆の順序です。

62
00:03:05,090 --> 00:03:11,180
あなたは、n個の要素の各々をシフトする必要があります
n個の位置まで、ひとつひとつの時間、私たち

63
00:03:11,180 --> 00:03:12,880
挿入を行います。

64
00:03:12,880 --> 00:03:15,720
それはシフトの多くのです。

65
00:03:15,720 --> 00:03:18,014
>> 最良の場合には、
アレイが完全にソートされます。

66
00:03:18,014 --> 00:03:20,680
ソートの何が起こったかのように
例では5と6と、

67
00:03:20,680 --> 00:03:23,779
私達はちょうどそれをタックそうな場所
任意のシフトを実行することなく、

68
00:03:23,779 --> 00:03:24,820
我々は、本質的にそれを行うだろう。

69
00:03:24,820 --> 00:03:27,560
>> あなたは私たちのことを想像した場合
アレイは、6を通じて一つでした

70
00:03:27,560 --> 00:03:29,900
私たちはすることから始めたいです
いずれかを宣言すると、ソートされます。

71
00:03:29,900 --> 00:03:33,300
二つは、私たちはただ缶1の後に来ます
1と2がソートされても、[OK]を、言います。

72
00:03:33,300 --> 00:03:36,190
三は[OK]を、ので、2つの後に来ます、
1と2と3がソートされています。

73
00:03:36,190 --> 00:03:39,590
>> 私たちはしている、任意のスワップを行っていません
ちょうどこの任意の行を移動します

74
00:03:39,590 --> 00:03:42,460
私たちが行くようにとの間でソートされ、ソートされていません。

75
00:03:42,460 --> 00:03:46,646
効果的に私たちは一例で行ったように、
我々が進むにつれて、青の要素を回します。

76
00:03:46,646 --> 00:03:48,270
だから、最悪の場合の実行時間は、その後、何ですか？

77
00:03:48,270 --> 00:03:51,854
覚えておいてください、私たちはそれぞれをシフトする必要がある場合
n個の要素おそらくn個の位置、

78
00:03:51,854 --> 00:03:54,020
うまくいけば、それはあなたを与えます
最悪の場合は、そのアイデア

79
00:03:54,020 --> 00:03:57,770
ランタイムは、nのビッグOの二乗です。

80
00:03:57,770 --> 00:04:00,220
>> 配列は完全である場合
私たちがしなければならないソート、すべての

81
00:04:00,220 --> 00:04:04,480
一つ一つの要素を見ています
一度、その後、我々は完了です。

82
00:04:04,480 --> 00:04:08,440
そのように最良の場合には、n個のオメガです。

83
00:04:08,440 --> 00:04:09,490
>> 私はダグロイドです。

84
00:04:09,490 --> 00:04:11,760
これはCS50です。

85
00:04:11,760 --> 00:04:13,119