1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] トミー：のは、選択ソートを見て、アルゴリズムを見てみましょう

2
00:00:09,980 --> 00:00:12,800
番号のリストを取得し、それらを並べ替えるため。

3
00:00:12,800 --> 00:00:15,750
アルゴリズムは、覚えているが、単純にステップ·バイ·ステップである

4
00:00:15,750 --> 00:00:18,370
タスクを実行するための手順。

5
00:00:18,370 --> 00:00:21,470
選択ソートの基本的な考え方は、分割することである

6
00:00:21,470 --> 00:00:23,390
2つの部分に私たちのリスト - 

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

8
00:00:26,810 --> 00:00:30,200
アルゴリズムの各ステップで、番号がから移動されている

9
00:00:30,200 --> 00:00:33,800
結局までソート部分にソートされていない部分

10
00:00:33,800 --> 00:00:35,880
リスト全体がソートされます。

11
00:00:35,880 --> 00:00:38,510
そこでここでは6つの番号のリストです - 

12
00:00:38,510 --> 00:00:44,010
23、42、4、16、8、15。

13
00:00:44,010 --> 00:00:47,680
今のところ全体のリストはソートされていないと見なされます。

14
00:00:47,680 --> 00:00:51,770
16のような数はすでに正しい順序であるかもしれませんが

15
00:00:51,770 --> 00:00:56,040
場所、我々のアルゴリズムはこれを続けて知る方法がありません

16
00:00:56,040 --> 00:00:57,980
リスト全体がソートされます。

17
00:00:57,980 --> 00:01:01,355
だから我々は我々の並べ替えまで未ソートするすべての数を考慮します

18
00:01:01,355 --> 00:01:03,800
それは自分自身。

19
00:01:03,800 --> 00:01:06,890
我々はリストが昇順になりたいことを知っています。

20
00:01:06,890 --> 00:01:10,200
だから我々は我々のリストのソートされた部分を構築したいと思う

21
00:01:10,200 --> 00:01:13,280
左から右へ、小さい方から大きい方へ。

22
00:01:13,280 --> 00:01:17,970
そのためには、最低限のソートされていない要素を見つける必要があります

23
00:01:17,970 --> 00:01:21,350
およびソート部分の終わりにそれを置く。

24
00:01:21,350 --> 00:01:25,370
このリストがソートされていないので、実行する唯一の方法は、

25
00:01:25,370 --> 00:01:29,330
思い出して、ソートされていない部分の各要素を見

26
00:01:29,330 --> 00:01:32,010
最低と比較どの要素である

27
00:01:32,010 --> 00:01:33,770
と各要素。

28
00:01:33,770 --> 00:01:36,150
だから我々は最初の23を見てみましょう。

29
00:01:36,150 --> 00:01:38,650
これは、我々が見てきた最初の要素であるので、私たちは覚えているだろう

30
00:01:38,650 --> 00:01:40,050
最低でもそれ。

31
00:01:40,050 --> 00:01:42,320
次に、我々は42を見てみましょう。

32
00:01:42,320 --> 00:01:46,720
42は23より大きいので、23は最小です。

33
00:01:46,720 --> 00:01:51,210
次は23未満で4なので、4を覚えているだろう

34
00:01:51,210 --> 00:01:52,880
新しい最小値として。

35
00:01:52,880 --> 00:01:56,380
次は4より大きい16であるので、4

36
00:01:56,380 --> 00:01:57,980
まだ最小値です。

37
00:01:57,980 --> 00:02:03,670
8は4よりも大きく、15が4よりも大きいので、4でなければなりません

38
00:02:03,670 --> 00:02:05,980
最小のソートされていない要素。

39
00:02:05,980 --> 00:02:09,350
だから、たとえ人間として我々はすぐに4があることがわかります

40
00:02:09,350 --> 00:02:12,300
最小の要素は、我々のアルゴリズムは見てする必要があります

41
00:02:12,300 --> 00:02:15,710
 - 私たちは4を見つけた後でも、すべてのソートされていない要素、

42
00:02:15,710 --> 00:02:16,860
最小要素。

43
00:02:16,860 --> 00:02:19,900
だから今我々は最小の要素、4を見つけたので、今度はお勧めします

44
00:02:19,900 --> 00:02:23,410
リストのソートされた部分にそれを移動します。

45
00:02:23,410 --> 00:02:27,320
これが最初のステップですので、これは我々が4を配置することを意味

46
00:02:27,320 --> 00:02:29,680
リストの先頭。

47
00:02:29,680 --> 00:02:33,040
今のところ23は、リストの先頭にある

48
00:02:33,040 --> 00:02:36,080
4と23を交換してみましょう。

49
00:02:36,080 --> 00:02:38,870
だから今、私たちのリストは次のようになります。

50
00:02:38,870 --> 00:02:42,710
それがあるので、私たちは、4を最終的な位置になければならないことを知っている

51
00:02:42,710 --> 00:02:45,890
冒頭最小の要素と要素の両方

52
00:02:45,890 --> 00:02:46,960
リストの。

53
00:02:46,960 --> 00:02:50,650
我々は二度とそれを移動する必要がないことを意味し、これはそう。

54
00:02:50,650 --> 00:02:53,910
だから、別の要素を追加するには、このプロセスを繰り返してみましょう

55
00:02:53,910 --> 00:02:55,910
リストのソートされた部分。

56
00:02:55,910 --> 00:02:58,950
それだから我々は、我々は4を見てする必要がないことを知っている

57
00:02:58,950 --> 00:03:00,000
既にソートされています。

58
00:03:00,000 --> 00:03:03,540
だから我々は、我々はどのように覚えているだろう、42で起動することができます

59
00:03:03,540 --> 00:03:05,290
最小要素。

60
00:03:05,290 --> 00:03:08,700
そこで、次の我々は、42未満である23を見たので、よ

61
00:03:08,700 --> 00:03:11,620
23が新しい最小値であることを覚えている。

62
00:03:11,620 --> 00:03:14,870
次に我々はそう、23未満である16を参照

63
00:03:14,870 --> 00:03:16,800
16新しい最小値です。

64
00:03:16,800 --> 00:03:19,720
今、私たちはそう、16未満である8を見れ

65
00:03:19,720 --> 00:03:21,130
8新しい最小値です。

66
00:03:21,130 --> 00:03:25,900
そして最後に8が15未満であるため、我々は8が最小であることを知っている

67
00:03:25,900 --> 00:03:27,780
ソートされていない要素。

68
00:03:27,780 --> 00:03:30,660
だから我々はソートに8を付加するべきであることを意味している

69
00:03:30,660 --> 00:03:32,450
リストの一部。

70
00:03:32,450 --> 00:03:35,990
たった今4のみソート要素なので、配置したい

71
00:03:35,990 --> 00:03:38,410
4から8の隣。

72
00:03:38,410 --> 00:03:41,920
42以来のソートされていない部分の最初の要素である

73
00:03:41,920 --> 00:03:47,260
リストには、我々は42と8を交換したいと思う。

74
00:03:47,260 --> 00:03:49,680
だから今、私たちのリストは次のようになります。

75
00:03:49,680 --> 00:03:53,830
4および8は、リストのソートされた部分を表しており、

76
00:03:53,830 --> 00:03:56,440
残りの番号がソートされていないを表す

77
00:03:56,440 --> 00:03:58,260
リストの一部。

78
00:03:58,260 --> 00:04:00,630
それでは、別の反復を続けましょう。

79
00:04:00,630 --> 00:04:03,850
我々が見ている必要はありませんので、私たちは、23で、この時間を開始

80
00:04:03,850 --> 00:04:05,770
彼らがきたので、もう4と8

81
00:04:05,770 --> 00:04:07,660
既にソートされて。

82
00:04:07,660 --> 00:04:10,270
16は23よりも小さいので、私たちは覚えているだろう

83
00:04:10,270 --> 00:04:12,070
新しい最小値として16。

84
00:04:12,070 --> 00:04:18,149
16は42未満であるが、15は16よりも小さいので、15でなければなりません

85
00:04:18,149 --> 00:04:20,480
最小ソートされていない要素。

86
00:04:20,480 --> 00:04:24,580
だから今我々は15〜23を入れ替えたい

87
00:04:24,580 --> 00:04:26,310
私たちは、このリストを与える。

88
00:04:26,310 --> 00:04:30,500
リストのソートされた部分は、4,8及び15で構成されており、

89
00:04:30,500 --> 00:04:33,210
これらの要素はまだソートされていない。

90
00:04:33,210 --> 00:04:36,900
しかし、それだけでソートされていないので、次の要素、16、ことが起こる

91
00:04:36,900 --> 00:04:38,480
既にソートされています。

92
00:04:38,480 --> 00:04:42,060
しかし、知っている我々のアルゴリズムのための方法はありませんその16

93
00:04:42,060 --> 00:04:45,230
すでに正しい場所にあるので、我々はまだする必要が

94
00:04:45,230 --> 00:04:47,870
全く同じプロセスを繰り返します。

95
00:04:47,870 --> 00:04:53,750
だからそう、我々は16が42未満であることを確認し、16は23未満です

96
00:04:53,750 --> 00:04:56,230
16は最小要素である必要があります。

97
00:04:56,230 --> 00:04:59,010
それは、それ自体には、この要素をスワップすることは不可能ですので、我々はできる

98
00:04:59,010 --> 00:05:01,780
単にこの場所にしておきます。

99
00:05:01,780 --> 00:05:04,660
だから我々は我々のアルゴリズムの1以上のパスが必要です。

100
00:05:04,660 --> 00:05:09,370
42は23よりも大きいので、23でなければなりません

101
00:05:09,370 --> 00:05:10,970
最小ソートされていない要素。

102
00:05:10,970 --> 00:05:17,410
かつて我々は我々の最終的に終わる、23と42を入れ替える

103
00:05:17,410 --> 00:05:18,530
ソートされたリスト - 

104
00:05:18,530 --> 00:05:23,390
4、8、15、16、23、42。

105
00:05:23,390 --> 00:05:26,830
我々は、それがだから42が正しい場所にある必要があります知っている

106
00:05:26,830 --> 00:05:30,210
唯一の要素が残って、それが選択ソートだ。

107
00:05:30,210 --> 00:05:32,100
現在、いくつかで我々のアルゴリズムを定式化してみましょう

108
00:05:32,100 --> 00:05:34,540
擬似コード。

109
00:05:34,540 --> 00:05:37,760
1行目では、我々は我々が上に統合する必要があることがわかります

110
00:05:37,760 --> 00:05:39,530
リストのすべての要素。

111
00:05:39,530 --> 00:05:42,150
1つの要素から最後の要素を除いて

112
00:05:42,150 --> 00:05:44,230
リストがすでにソートされています。

113
00:05:44,230 --> 00:05:48,100
2行目では、私たちは、ソートされていないの最初の要素を考慮する

114
00:05:48,100 --> 00:05:51,080
私達が私達の場合と同じように、最低でもするリストの一部

115
00:05:51,080 --> 00:05:53,750
たとえば、私たちはと比較する何​​かを持っている。

116
00:05:53,750 --> 00:05:57,260
3行目は、我々は繰り返し処理する第2のループを開始

117
00:05:57,260 --> 00:05:59,170
各ソートされていない要素。

118
00:05:59,170 --> 00:06:02,150
我々は知っている私に繰り返された後、ソートされた部分

119
00:06:02,150 --> 00:06:05,330
私たちのリストの各ステップからそれで私は要素持っている必要があります

120
00:06:05,330 --> 00:06:06,890
ソートつの要素。

121
00:06:06,890 --> 00:06:11,770
だから最初にソートされていない要素は、位置iに1を加えたでなければなりません。

122
00:06:11,770 --> 00:06:15,440
4行目の、私たちは最小に現在の要素を比較する

123
00:06:15,440 --> 00:06:17,750
我々はこれまで見てきた要素。

124
00:06:17,750 --> 00:06:20,560
現在の要素が最小値より小さい場合

125
00:06:20,560 --> 00:06:23,870
要素は、次に我々は、新規としての現在の要素を覚えている

126
00:06:23,870 --> 00:06:26,250
行5で最小。

127
00:06:26,250 --> 00:06:29,900
最後に、ライン6と7で、私たちは最小値を入れ替える

128
00:06:29,900 --> 00:06:33,080
これにより第1ソートされていない要素を持つ要素、

129
00:06:33,080 --> 00:06:36,990
リストのソートされた部分に追加します。

130
00:06:36,990 --> 00:06:40,030
かつて我々はアルゴリズム、尋ねるべき重要な質問があります

131
00:06:40,030 --> 00:06:43,370
プログラマとしての自分自身はそれがどのくらいかかりましたか？

132
00:06:43,370 --> 00:06:46,970
私たちは最初にどのくらいの時間がかかりますかこの質問を聞いてみよう

133
00:06:46,970 --> 00:06:50,070
アルゴリズムは、最悪の場合に実行するには？

134
00:06:50,070 --> 00:06:51,640
我々はこのランニングを表すリコール

135
00:06:51,640 --> 00:06:55,060
ビッグO記法と時間。

136
00:06:55,060 --> 00:06:58,650
ソートされていない最小の要素を決定するために、我々

137
00:06:58,650 --> 00:07:01,880
本質的には、リスト内の各要素の比較をしました

138
00:07:01,880 --> 00:07:04,040
リスト内の他のすべての要素。

139
00:07:04,040 --> 00:07:08,430
直感的に、これはnの二乗演算のOのように聞こえる。

140
00:07:08,430 --> 00:07:12,050
私たちの擬似コードを見てみると、我々はまた、中にネストされたループを持っている

141
00:07:12,050 --> 00:07:14,420
確かにOのように聞こえる別のループ、

142
00:07:14,420 --> 00:07:16,480
nの二乗の動作。

143
00:07:16,480 --> 00:07:19,250
しかし、我々は目を通す必要はありませんでしたことを覚えておいてください

144
00:07:19,250 --> 00:07:23,460
リスト全体をソートされていない最小の要素を決定する？

145
00:07:23,460 --> 00:07:26,600
かつて我々は4は、例えば、ソートされたことを知っていた、私たちはしませんでした

146
00:07:26,600 --> 00:07:28,170
再びそれを見て必要があります。

147
00:07:28,170 --> 00:07:31,020
だから、これは実行時間を下げるのでしょうか？

148
00:07:31,020 --> 00:07:34,510
長さ6の私達のリストのために、私たちは5を作るために必要な

149
00:07:34,510 --> 00:07:37,990
最初の要素のための比較のための4つの比較

150
00:07:37,990 --> 00:07:40,750
第二の要素、というように。

151
00:07:40,750 --> 00:07:44,690
すなわち、ステップの総数はの和であることを意味します

152
00:07:44,690 --> 00:07:49,160
1からのリストの長さから1を引いたの整数。

153
00:07:49,160 --> 00:07:51,005
我々は合計でこれを表すことができます。

154
00:07:57,980 --> 00:07:59,910
我々はここで和に入ることはありません。

155
00:07:59,910 --> 00:08:04,900
しかし、それはこの総和がn倍に等しいことが判明

156
00:08:04,900 --> 00:08:07,540
nはマイナス2以上1。

157
00:08:07,540 --> 00:08:14,220
または同等に、nは2以上2以上マイナスn乗。

158
00:08:14,220 --> 00:08:18,860
漸近的な実行時の話を、このn乗項

159
00:08:18,860 --> 00:08:22,070
このn任期を支配しようとしている。

160
00:08:22,070 --> 00:08:27,850
だから、選択ソートは、n乗のOである。

161
00:08:27,850 --> 00:08:31,460
私たちの例では、選択ソートは、まだするのに必要なことを思い出してください

162
00:08:31,460 --> 00:08:33,850
すでにソートされた番号かどうかをチェック

163
00:08:33,850 --> 00:08:35,450
移動する必要がありました。

164
00:08:35,450 --> 00:08:38,929
だから我々はすでに上に選択ソートを実行した場合ことを意味します

165
00:08:38,929 --> 00:08:43,070
リストソート、それはそれとして同じステップ数を必要とするであろう

166
00:08:43,070 --> 00:08:46,340
完全にソートされていないリストをひくときだろう。

167
00:08:46,340 --> 00:08:51,470
だから、選択ソートは、乗nの最高のケースの性能を持っている

168
00:08:51,470 --> 00:08:56,820
その我々はオメガNの2乗で表す。

169
00:08:56,820 --> 00:08:58,600
そして、それは選択ソートのためのそれだ。

170
00:08:58,600 --> 00:09:00,630
私たちができる多くのアルゴリズムの一つに過ぎ

171
00:09:00,630 --> 00:09:02,390
リストをソートするために使用します。

172
00:09:02,390 --> 00:09:05,910
私の名前はトミーであり、これはCS50です。