1
00:00:00,000 --> 00:00:05,726
>> [音楽再生]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD：選択ソートです
ご想像のとおり、アルゴリズム、

3
00:00:08,600 --> 00:00:10,470
要素の集合をソートします。

4
00:00:10,470 --> 00:00:12,470
また、アルゴリズムのリコール
ステップバイステップのセットです

5
00:00:12,470 --> 00:00:15,260
タスクを完了するための手順の。

6
00:00:15,260 --> 00:00:17,580
>> 選択で並べ替え
基本的な考え方は、これであります

7
00:00:17,580 --> 00:00:22,080
最小のソートされていない要素を検索し、
ソートされたリストの最後に追加します。

8
00:00:22,080 --> 00:00:26,970
事実上、これは何をするかビルドがあります
ソートされたリスト、一度に一つの要素。

9
00:00:26,970 --> 00:00:29,800
擬似コードにそれを破壊
我々は、このアルゴリズムを述べることができ

10
00:00:29,800 --> 00:00:34,490
次のように、なるまでこれを繰り返します
何のソートされていない要素が残っていません。

11
00:00:34,490 --> 00:00:38,660
ソートされていないを検索し
データは、最小値を見つけるために、

12
00:00:38,660 --> 00:00:44,130
次いで、最小値を交換します
ソートされていない部分の最初の要素。

13
00:00:44,130 --> 00:00:47,130
>> それは、これを視覚化するのを助けることができます
それでは、これを見てみましょう。

14
00:00:47,130 --> 00:00:49,710
これは、私が争う、あります
ソートされていない配列と私はしました

15
00:00:49,710 --> 00:00:53,040
すべてのことを示すことによってそれを示しました
要素で、赤色に着色されています

16
00:00:53,040 --> 00:00:54,420
彼らはまだソートされていません。

17
00:00:54,420 --> 00:00:57,670
これは、全体で
配列のソートされていない部分。

18
00:00:57,670 --> 00:01:02,020
>> それでは、以下のステップを介して行ってみよう
この配列をソートするために選択ソート。

19
00:01:02,020 --> 00:01:05,296
そこで再び、我々はつもり繰り返しです
まではソートされていない要素が残っていません。

20
00:01:05,296 --> 00:01:07,920
我々は、全体を検索つもりです
データは、最小値を見つけるために、

21
00:01:07,920 --> 00:01:11,990
し、次いでその値を入れ替えます
ソートされていない部分の最初の要素。

22
00:01:11,990 --> 00:01:14,380
>> 今、再び、全体
配列がソートされていない部分です。

23
00:01:14,380 --> 00:01:16,534
赤の要素のすべてがソートされていません。

24
00:01:16,534 --> 00:01:18,700
だから我々はを検索し、
私たちは、最小値を見つけます。

25
00:01:18,700 --> 00:01:20,533
私たちは、先頭から開始
我々は、最後に移動

26
00:01:20,533 --> 00:01:23,630
私たちは、最小値は、1です見つけます。

27
00:01:23,630 --> 00:01:24,860
だから、一部一つです。

28
00:01:24,860 --> 00:01:29,440
そして、第二部では、とその値を入れ替えます
ソートされていない部分の最初の要素、

29
00:01:29,440 --> 00:01:31,340
または、最初の赤の要素。

30
00:01:31,340 --> 00:01:34,980
>> この場合であろうと
5、私たちは1と5を交換します。

31
00:01:34,980 --> 00:01:37,320
我々はこれを行うと、我々はできます
視覚的に私たちがしたことを参照してください。

32
00:01:37,320 --> 00:01:41,260
最小の値を持つ要素を移動
配列の、非常に先頭に。

33
00:01:41,260 --> 00:01:43,920
効果的にその要素をソートします。

34
00:01:43,920 --> 00:01:47,520
>> そして、私たちは実際に確認することができます
そして、状態1ということは、ソートされます。

35
00:01:47,520 --> 00:01:52,080
そして、私たちはソートされた部分を示すだろう
私たちの配列の青、それを着色することもできます。

36
00:01:52,080 --> 00:01:53,860
>> 今、私たちは再びプロセスを繰り返します。

37
00:01:53,860 --> 00:01:57,430
我々は、ソートされていない部分を検索
最小の要素を見つけるための配列。

38
00:01:57,430 --> 00:01:59,000
この場合には、2の。

39
00:01:59,000 --> 00:02:02,100
>> 私たちは最初にすることを入れ替えます
ソートされていない一部の要素。

40
00:02:02,100 --> 00:02:05,540
この場合、2つもあることを起こります
ソートされていない部分の最初の要素。

41
00:02:05,540 --> 00:02:08,650
だから我々は、それ自体で2を交換し、
これは実際には2つだけを残し

42
00:02:08,650 --> 00:02:11,257
それは、それがソートのWHERE。

43
00:02:11,257 --> 00:02:13,840
引き続き、全体を検索
最小の要素を検索します。

44
00:02:13,840 --> 00:02:15,030
これは3つです。

45
00:02:15,030 --> 00:02:17,650
私たちは最初にそれを交換
5である素子。

46
00:02:17,650 --> 00:02:19,450
そして今、3つがソートされます。

47
00:02:19,450 --> 00:02:22,440
>> 私たちは再びを検索し、我々
最小要素が4である見つけます。

48
00:02:22,440 --> 00:02:28,070
我々は、最初の要素とそれを交換します
ソートされていない部分、今4がソートされます。

49
00:02:28,070 --> 00:02:29,910
>> 私たちは5であることを見つけます
最小要素。

50
00:02:29,910 --> 00:02:32,900
私たちは最初にそれを交換
ソートされていない一部の要素。

51
00:02:32,900 --> 00:02:34,740
そして今5がソートされます。

52
00:02:34,740 --> 00:02:36,660
>> そして最後に、私たちの
ソートされていない部分が構成されてい

53
00:02:36,660 --> 00:02:38,576
単に1つの要素の、
私たちは全体を検索

54
00:02:38,576 --> 00:02:41,740
私たちは6であることを見つけます
最小の、そして実際には、唯一の要素。

55
00:02:41,740 --> 00:02:44,906
そして、我々はそれがソートされていることを述べることができます。

56
00:02:44,906 --> 00:02:47,530
そして今、我々は我々の配列を切り替えました
完全にソートされていないされてから

57
00:02:47,530 --> 00:02:52,660
赤で、完全にソートします
青色で、選択ソートを使用。

58
00:02:52,660 --> 00:02:54,920
>> そこでここでは最悪のシナリオは何ですか？

59
00:02:54,920 --> 00:02:57,830
まあ最悪で
場合、我々は以上のを見ています

60
00:02:57,830 --> 00:03:02,170
配列の要素のすべて
最小のソートされていない要素を見つけます、

61
00:03:02,170 --> 00:03:04,750
我々は繰り返す必要が
このプロセスをn回。

62
00:03:04,750 --> 00:03:09,090
配列の各要素のために一度
私たちだけのため、このアルゴリズムでは、

63
00:03:09,090 --> 00:03:12,180
一度にソートつの要素。

64
00:03:12,180 --> 00:03:13,595
>> 最良のシナリオは何ですか？

65
00:03:13,595 --> 00:03:15,040
まあそれは右、全く同じですか？

66
00:03:15,040 --> 00:03:18,440
私たちは実際にはまだをステップ実行する必要があります
配列のすべての単一の要素

67
00:03:18,440 --> 00:03:22,040
それがあることを確認するために、
実際には、最小の要素。

68
00:03:22,040 --> 00:03:26,760
>> だから、最悪の場合の実行時間は、我々
プロセスをn回繰り返す必要があり、

69
00:03:26,760 --> 00:03:28,960
n個の要素のそれぞれについて一度。

70
00:03:28,960 --> 00:03:31,940
そして最良の場合のシナリオにおいて、
私たちは同じことを行う必要があります。

71
00:03:31,940 --> 00:03:35,340
>> だから、戻って私たちの考え
計算の複雑さのツールボックス、

72
00:03:35,340 --> 00:03:39,250
最悪です、あなたは何を思いますか
選択ソートのためのケースランタイム？

73
00:03:39,250 --> 00:03:41,840
最高です、あなたは何を思いますか
選択ソートのためのケースランタイム？

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> あなたは、nのビッグOの二乗と思いました、
nのビッグオメガ二乗しましたか？

76
00:03:49,325 --> 00:03:49,950
あなたは正しいだろう。

77
00:03:49,950 --> 00:03:52,490
ものであり、実際には、
最悪の場合と最良の場合の実行

78
00:03:52,490 --> 00:03:55,100
選択ソートのための時間、。

79
00:03:55,100 --> 00:03:56,260
>> 私はダグロイドです。

80
00:03:56,260 --> 00:03:58,600
これはCS50です。

81
00:03:58,600 --> 00:04:00,279