>> MARK GROZENスミス：こんにちは、私はマークだ スミスはGrozen、これはクイックソートです。
ただ挿入ソートとバブルのような ソート、クイックソートはのためのアルゴリズムである
リストや物事の配列をソート。
簡単にするために、のは、これらのことを想定してみましょう 物事は単なる整数ですが、
クイックソートはのために働くことを知っている 数字だけよりも。
クイックスタートは少し複雑です 挿入またはバブルよりも、それはだ
また、はるかに効率的 ほとんどの場合。
ちょっと待って。
彼は「最も言った 例、 "NOT"すべての "？
興味深いことに、NO。
すべてのケースは同じである。
あなたは、この詳細については心配しないでください まだビッグO記法を見たが、していない
クイックソートはO（nは二乗）アルゴリズム 最悪の場合、同じよう
挿入またはバブルソート。
しかしながら、典型的には、はるかに作用する 古いアナログmのアルゴリズムが挙げられる。
なぜ？
私たちは、後でそれに得られます。
しかし、今のところ、ちょうど学習させる 、クイックソートがどのように機能する。
>> それでは、これをQuicksorting見ていきます 最小の整数の配列
最大に。
ここでは、整数6を持っている 5、1、3、8,4、7,9、および2。
まず、最後の要素のピック この配列 - この場合は、2 -
そのコール "ピボット"次に、 二つのことを見てスタート -
1、私は呼びます最小のインデックス、 の右側に滞在してASへ
壁と、二つ、左端の 私は "現在の電話するよ要素、
要素。「われわれがやろうとしていることである 他の全ての他の要素を見
ピボットよりも、すべての要素を入れて ピボットより小さい
壁の左側とすべての人 ピボットより大きい
壁の右。
そして、最後に、我々は、ピボットをドロップします の間に置いて、その壁の右
それよりも小さいすべての数値 とすべての数字も大きく。
>> それでは、それをしてみましょう。
2を拾う、で壁を置く 始まると、「現在の6を呼ぶ
要素。「だから私たちは見てみたい 私たちの現在の要素、6。
そして、それはより大きいですので、 2、我々はそこにそれを残す
壁の右。
その後、我々は我々のように5を見て進む 現在の要素と見ている。この
我々は、再び、ピボットよりも大きいので、 それが右側にある場合、それを残す
壁の側面。
我々は上に移動します。
私たちの現在の要素がある 今1、および - OH。
これは今とは異なります。
現在の要素は今よりも小さく、 ピボット、私たちはそれを配置する
壁の左側にある。
これを行うには、ちょうど切り替えることができます 最小のインデックスを持つ現在の要素
ちょうど壁の右側に座っている。
今、私たちは一つのインデックスまでの壁を移動 その1は左側にあり
今、壁の側面。
>> 待つ。
私はちょうど上の要素を混ぜ 壁の右側には、私はしませんでした？
心配しないでください。
それはいい。
我々は今のところ気に唯一のもの へのすべてのこれらの要素である
壁の右を大きくしている ピボットより。
実際の順序はまだ負いません。
>> 今、戻ってソートする。
だから我々は見に継続 残りの要素。
この場合、我々はあることがわかり よりも、他の要素より少ない
ピボットので、我々はすべての上に置いておく 壁の右側。
最後に、我々は現在の要素を取得する で、それをピボットであることがわかります。
今、それは我々が二つ持っていることを意味 配列のセクションで、最初の人間
ピボット上の左側にある小さな 壁、第二の存在の
ピボットより大きい 壁の右側。
我々は、間のピボット要素を入れたい 2、その後、我々は知っているよ
ピボットは、その右側にあることを 最終的なソートさ場所。
だから我々は、上の最初の要素を切り替える ピボットで壁の右側に、
そして我々は知っている、ピボットの その右の位置にある。
>> 次に、このプロセスを繰り返します サブアレイは、左とピボットの右側。
最後の部分配列は1つなので 要素の長い、我々は、すでに知っている
ソートされたどのようにあなたが外にすることができるので、 あなただけの1要素なら注文？
部分配列の右側のため、我々 ピボット壁を5であり、ことがわかる
ただ6のままになります。
そして現在の要素も 6として開始。
だから、6は5より大きい。
それがある場合、我々はそれを残す 壁の右側。
今、上の移動、3が5未満である。
だから我々は最初の要素でそれを切り替える 壁のちょうどいい。
今、私は1、最大の壁を移動しました。
今、8に進む。
図8は、5よりも大きい そして私たちはそれを残す。
4は5より小さいので、我々はそれを切り替える。
そして上。
>> 我々は上のプロセスを繰り返すたびに、 配列の左側と右側。我々
ピボットを選択し、比較を行う そして左の別のレベルを作成し、
右のサブアレイ。
この再帰呼び出しがされるまで継続します 我々は我々がした最後に到達
に、全体的な配列を分割 長さ1だけサブアレイ。
そこから、私たちは、配列がソートされている知っている で、すべての要素を持っているので
いくつかのポイントは、ピボットされて。
つまり、すべての要素のために、すべての 左の数字は低いです
値とするすべての数字 右の大きな値を持つ。
>> この方法は、非常にうまく動作するかどうか 選択したピボットの値は
ほぼ中間にある リスト値の範囲。
我々は移動した後、これは、次のことを意味する できるだけ多く約あり周りの要素、
ピボットの左側の要素 右側にありますように。
との分割統治性 クイックソートアルゴリズムは、その後、取得され
をフルに活用。
これは、Oの実行時に作成（N Nログを、） 我々はしなければならないNマイナス1 Nので
各世代やログオンの比較 N私たちは、リストを分割する必要があるため、
N回を記録。
しかし、最悪の場合には、この このアルゴリズムは、実際にはO（nすることができます
乗。）各世代であるとし、 ピボットがちょうどそうであることを起こる
最小または最大の 我々は、ソートしている数字。
これは、リストを分解を意味する n回と意思Nマイナス1
比較ひとつひとつの時間を。
これにより、nのoを二乗。
>> どのように我々は方法を改善することができますか？
方法を改善するための一つの良い方法です その確率を削減する
ランタイムは、これまでに実際にある NのOの二乗。
この最悪、最悪のシナリオを覚えている 場合にのみ発生する可能性
選択したピボットは常に最高である または配列内の最小値。
これが起こる可能性が低いことを確認するには、 私達はでピボットを見つけることができます
複数の要素を選択し、 中央値をとる。
>> 私の名前は、マーク·Grozen·スミスです これはCS50である。
>> 簡単にするために、のは、これらのことを想定してみましょう 物事は単なる整数ですが、
そのQuicksertを知っている -
Quicksert？
申し訳ありません。
>> ここでは、整数を有する 6、5、1、3、8、4、9。
>> スピーカ1：本当に？
>> スピーカー2：そこに停止しないでください。
>> スピーカ1：本当に？