1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZENスミス：こんにちは、私はマークだ
スミスはGrozen、これはクイックソートです。

3
00:00:10,390 --> 00:00:13,520
ただ挿入ソートとバブルのような
ソート、クイックソートはのためのアルゴリズムである

4
00:00:13,520 --> 00:00:15,720
リストや物事の配列をソート。

5
00:00:15,720 --> 00:00:19,080
簡単にするために、のは、これらのことを想定してみましょう
物事は単なる整数ですが、

6
00:00:19,080 --> 00:00:22,060
クイックソートはのために働くことを知っている
数字だけよりも。

7
00:00:22,060 --> 00:00:24,720
クイックスタートは少し複雑です
挿入またはバブルよりも、それはだ

8
00:00:24,720 --> 00:00:27,560
また、はるかに効率的
ほとんどの場合。

9
00:00:27,560 --> 00:00:28,150
ちょっと待って。

10
00:00:28,150 --> 00:00:30,760
彼は「最も言った
例、 "NOT"すべての "？

11
00:00:30,760 --> 00:00:31,710
興味深いことに、NO。

12
00:00:31,710 --> 00:00:33,560
すべてのケースは同じである。

13
00:00:33,560 --> 00:00:36,650
あなたは、この詳細については心配しないでください
まだビッグO記法を見たが、していない

14
00:00:36,650 --> 00:00:39,730
クイックソートはO（nは二乗）アルゴリズム
最悪の場合、同じよう

15
00:00:39,730 --> 00:00:41,430
挿入またはバブルソート。

16
00:00:41,430 --> 00:00:44,950
しかしながら、典型的には、はるかに作用する
古いアナログmのアルゴリズムが挙げられる。

17
00:00:44,950 --> 00:00:45,750
なぜ？

18
00:00:45,750 --> 00:00:46,810
私たちは、後でそれに得られます。

19
00:00:46,810 --> 00:00:49,610
しかし、今のところ、ちょうど学習させる
、クイックソートがどのように機能する。

20
00:00:49,610 --> 00:00:53,080
>> それでは、これをQuicksorting見ていきます
最小の整数の配列

21
00:00:53,080 --> 00:00:54,260
最大に。

22
00:00:54,260 --> 00:01:00,110
ここでは、整数6を持っている
5、1、3、8,4、7,9、および2。

23
00:01:00,110 --> 00:01:03,480
まず、最後の要素のピック
この配列 - この場合は、2  - 

24
00:01:03,480 --> 00:01:06,870
そのコール "ピボット"次に、
二つのことを見てスタート - 

25
00:01:06,870 --> 00:01:10,220
1、私は呼びます最小のインデックス、
の右側に滞在してASへ

26
00:01:10,220 --> 00:01:13,970
壁と、二つ、左端の
私は "現在の電話するよ要素、

27
00:01:13,970 --> 00:01:17,260
要素。「われわれがやろうとしていることである
他の全ての他の要素を見

28
00:01:17,260 --> 00:01:20,930
ピボットよりも、すべての要素を入れて
ピボットより小さい

29
00:01:20,930 --> 00:01:24,140
壁の左側とすべての人
ピボットより大きい

30
00:01:24,140 --> 00:01:25,570
壁の右。

31
00:01:25,570 --> 00:01:29,560
そして、最後に、我々は、ピボットをドロップします
の間に置いて、その壁の右

32
00:01:29,560 --> 00:01:32,970
それよりも小さいすべての数値
とすべての数字も大きく。

33
00:01:32,970 --> 00:01:34,460
>> それでは、それをしてみましょう。

34
00:01:34,460 --> 00:01:38,540
2を拾う、で壁を置く
始まると、「現在の6を呼ぶ

35
00:01:38,540 --> 00:01:41,590
要素。「だから私たちは見てみたい
私たちの現在の要素、6。

36
00:01:41,590 --> 00:01:44,200
そして、それはより大きいですので、
2、我々はそこにそれを残す

37
00:01:44,200 --> 00:01:45,610
壁の右。

38
00:01:45,610 --> 00:01:48,980
その後、我々は我々のように5を見て進む
現在の要素と見ている。この

39
00:01:48,980 --> 00:01:51,840
我々は、再び、ピボットよりも大きいので、
それが右側にある場合、それを残す

40
00:01:51,840 --> 00:01:53,190
壁の側面。

41
00:01:53,190 --> 00:01:53,880
我々は上に移動します。

42
00:01:53,880 --> 00:01:56,750
私たちの現在の要素がある
今1、および -  OH。

43
00:01:56,750 --> 00:01:58,030
これは今とは異なります。

44
00:01:58,030 --> 00:02:00,890
現在の要素は今よりも小さく、
ピボット、私たちはそれを配置する

45
00:02:00,890 --> 00:02:02,570
壁の左側にある。

46
00:02:02,570 --> 00:02:06,555
これを行うには、ちょうど切り替えることができます
最小のインデックスを持つ現在の要素

47
00:02:06,555 --> 00:02:07,970
ちょうど壁の右側に座っている。

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
今、私たちは一つのインデックスまでの壁を移動
その1は左側にあり

50
00:02:17,570 --> 00:02:19,750
今、壁の側面。

51
00:02:19,750 --> 00:02:20,310
>> 待つ。

52
00:02:20,310 --> 00:02:23,450
私はちょうど上の要素を混ぜ
壁の右側には、私はしませんでした？

53
00:02:23,450 --> 00:02:23,890
心配しないでください。

54
00:02:23,890 --> 00:02:24,930
それはいい。

55
00:02:24,930 --> 00:02:27,570
我々は今のところ気に唯一のもの
へのすべてのこれらの要素である

56
00:02:27,570 --> 00:02:29,570
壁の右を大きくしている
ピボットより。

57
00:02:29,570 --> 00:02:31,760
実際の順序はまだ負いません。

58
00:02:31,760 --> 00:02:33,200
>> 今、戻ってソートする。

59
00:02:33,200 --> 00:02:35,840
だから我々は見に継続
残りの要素。

60
00:02:35,840 --> 00:02:39,075
この場合、我々はあることがわかり
よりも、他の要素より少ない

61
00:02:39,075 --> 00:02:42,100
ピボットので、我々はすべての上に置いておく
壁の右側。

62
00:02:42,100 --> 00:02:45,980
最後に、我々は現在の要素を取得する
で、それをピボットであることがわかります。

63
00:02:45,980 --> 00:02:48,830
今、それは我々が二つ持っていることを意味
配列のセクションで、最初の人間

64
00:02:48,830 --> 00:02:51,820
ピボット上の左側にある小さな
壁、第二の存在の

65
00:02:51,820 --> 00:02:54,500
ピボットより大きい
壁の右側。

66
00:02:54,500 --> 00:02:57,040
我々は、間のピボット要素を入れたい
2、その後、我々は知っているよ

67
00:02:57,040 --> 00:03:01,000
ピボットは、その右側にあることを
最終的なソートさ場所。

68
00:03:01,000 --> 00:03:04,980
だから我々は、上の最初の要素を切り替える
ピボットで壁の右側に、

69
00:03:04,980 --> 00:03:06,410
そして我々は知っている、ピボットの
その右の位置にある。

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> 次に、このプロセスを繰り返します
サブアレイは、左とピボットの右側。

72
00:03:15,650 --> 00:03:18,700
最後の部分配列は1つなので
要素の長い、我々は、すでに知っている

73
00:03:18,700 --> 00:03:22,480
ソートされたどのようにあなたが外にすることができるので、
あなただけの1要素なら注文？

74
00:03:22,480 --> 00:03:28,860
部分配列の右側のため、我々
ピボット壁を5であり、ことがわかる

75
00:03:28,860 --> 00:03:32,250
ただ6のままになります。

76
00:03:32,250 --> 00:03:34,970
そして現在の要素も
6として開始。

77
00:03:34,970 --> 00:03:36,200
だから、6は5より大きい。

78
00:03:36,200 --> 00:03:38,590
それがある場合、我々はそれを残す
壁の右側。

79
00:03:38,590 --> 00:03:41,060
今、上の移動、3が5未満である。

80
00:03:41,060 --> 00:03:44,160
だから我々は最初の要素でそれを切り替える
壁のちょうどいい。

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
今、私は1、最大の壁を移動しました。

83
00:03:50,750 --> 00:03:53,010
今、8に進む。

84
00:03:53,010 --> 00:03:56,480
図8は、5よりも大きい
そして私たちはそれを残す。

85
00:03:56,480 --> 00:03:58,720
4は5より小さいので、我々はそれを切り替える。

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
そして上。

88
00:04:03,570 --> 00:04:04,820
そして上。

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> 我々は上のプロセスを繰り返すたびに、
配列の左側と右側。我々

91
00:04:13,670 --> 00:04:17,010
ピボットを選択し、比較を行う
そして左の別のレベルを作成し、

92
00:04:17,010 --> 00:04:18,240
右のサブアレイ。

93
00:04:18,240 --> 00:04:21,500
この再帰呼び出しがされるまで継続します
我々は我々がした最後に到達

94
00:04:21,500 --> 00:04:25,290
に、全体的な配列を分割
長さ1だけサブアレイ。

95
00:04:25,290 --> 00:04:28,060
そこから、私たちは、配列がソートされている知っている
で、すべての要素を持っているので

96
00:04:28,060 --> 00:04:29,330
いくつかのポイントは、ピボットされて。

97
00:04:29,330 --> 00:04:32,720
つまり、すべての要素のために、すべての
左の数字は低いです

98
00:04:32,720 --> 00:04:36,420
値とするすべての数字
右の大きな値を持つ。

99
00:04:36,420 --> 00:04:38,980
>> この方法は、非常にうまく動作するかどうか
選択したピボットの値は

100
00:04:38,980 --> 00:04:41,930
ほぼ中間にある
リスト値の範囲。

101
00:04:41,930 --> 00:04:45,630
我々は移動した後、これは、次のことを意味する
できるだけ多く約あり周りの要素、

102
00:04:45,630 --> 00:04:48,390
ピボットの左側の要素
右側にありますように。

103
00:04:48,390 --> 00:04:52,380
との分割統治性
クイックソートアルゴリズムは、その後、取得され

104
00:04:52,380 --> 00:04:53,850
をフルに活用。

105
00:04:53,850 --> 00:04:57,500
これは、Oの実行時に作成（N Nログを、）
我々はしなければならないNマイナス1 Nので

106
00:04:57,500 --> 00:05:01,640
各世代やログオンの比較
N私たちは、リストを分割する必要があるため、

107
00:05:01,640 --> 00:05:03,210
N回を記録。

108
00:05:03,210 --> 00:05:06,160
しかし、最悪の場合には、この
このアルゴリズムは、実際にはO（nすることができます

109
00:05:06,160 --> 00:05:09,850
乗。）各世代であるとし、
ピボットがちょうどそうであることを起こる

110
00:05:09,850 --> 00:05:12,520
最小または最大の
我々は、ソートしている数字。

111
00:05:12,520 --> 00:05:15,870
これは、リストを分解を意味する
n回と意思Nマイナス1

112
00:05:15,870 --> 00:05:17,690
比較ひとつひとつの時間を。

113
00:05:17,690 --> 00:05:20,490
これにより、nのoを二乗。

114
00:05:20,490 --> 00:05:22,000
>> どのように我々は方法を改善することができますか？

115
00:05:22,000 --> 00:05:25,100
方法を改善するための一つの良い方法です
その確率を削減する

116
00:05:25,100 --> 00:05:28,150
ランタイムは、これまでに実際にある
NのOの二乗。

117
00:05:28,150 --> 00:05:31,860
この最悪、最悪のシナリオを覚えている
場合にのみ発生する可能性

118
00:05:31,860 --> 00:05:35,320
選択したピボットは常に最高である
または配列内の最小値。

119
00:05:35,320 --> 00:05:38,630
これが起こる可能性が低いことを確認するには、
私達はでピボットを見つけることができます

120
00:05:38,630 --> 00:05:42,610
複数の要素を選択し、
中央値をとる。

121
00:05:42,610 --> 00:05:44,650
>> 私の名前は、マーク·Grozen·スミスです
これはCS50である。

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> 簡単にするために、のは、これらのことを想定してみましょう
物事は単なる整数ですが、

124
00:05:50,930 --> 00:05:51,970
そのQuicksertを知っている - 

125
00:05:51,970 --> 00:05:53,160
Quicksert？

126
00:05:53,160 --> 00:05:55,200
申し訳ありません。

127
00:05:55,200 --> 00:06:02,000
>> ここでは、整数を有する
6、5、1、3、8、4、9。

128
00:06:02,000 --> 00:06:03,200
>> スピーカ1：本当に？

129
00:06:03,200 --> 00:06:04,850
>> スピーカー2：そこに停止しないでください。

130
00:06:04,850 --> 00:06:06,100
>> スピーカ1：本当に？

131
00:06:06,100 --> 00:06:08,491