DOUG LLOYD：だからCS50に、我々は、約学びました ソートや検索の様々な アルゴリズム。 そして、時にはそれがすることができます 続けるには少しトリッキー 何アルゴリズムのトラックが何を行います。 私たちは本当にだけしました あまりにも表面を脱脂、 他の多くの検索があります およびアルゴリズムをソート。 だから、このビデオLETでの わずか数分かかります 試してみて、各アルゴリズムを蒸留します その中核的な要素まで あなたがほとんどを覚えています それらについての重要な情報 そして、明確することができます 違い、必要に応じて。 

最初は、選択ソートです。 選択ソートの基本的な考え方 最小のソートされていない要素を見つけることです 配列内とでそれを交換 その配列の最初のソートされていない要素。 私たちは、最悪の場合のことを言いました その実行時間をn乗しました。 そして、あなたは理由を呼び出したい場合は、取ります 選択ソートのビデオを見て。 最良の実行時間 また、nは2乗さ。 

バブルソート、その背後にある考え方 1は、隣接する対を交換することです。 だから、それはあなたを助ける重要なのです ここでの違いを覚えています。 ソートされているので、これまでの選択、 smallest--バブルを見つけます ソートスワップ隣接する対です。 私たちは、隣接する対を交換 要素の彼らの場合 これは効果的に、順不同であります 右に大きな要素を泡、 同時に、それはまた始まり 左に小さい要素を移動します。 最悪のケースの場合は、ランタイム バブルソートのN乗されます。 最良の実行時間 バブルソートのnです。 そのような状況にあるため、 我々はactually--ません 我々はする必要はありません まったくスワップを行います。 私たちは、1つを行う必要があります すべてのn個の要素を通過。 

挿入ソートでは、 ここでの基本的な考え方は、シフトしています。 つまり、挿入ソートのキーワードです。 我々は、ワンススルーステップになるだろう 左から右に配列。 私たちがそうであるようにと、私たちはしています 要素をシフトするつもり 我々はすでにのためのスペースを作るために見てきました どこかにフィットする必要が小さいもの バックそのソートされた部分です。 だから我々は、ソートされた配列を構築1 左から右に時間の要素、 私たちは部屋を作るために物事をシフトします。 の最悪の場合の実行時間 挿入ソートは、n乗されます。 最良の場合の実行時間はNです。 

キーワードsort--マージ ここで分割し、マージされています。 私たちは、かどうか、完全な配列を分割 それは6つの要素、8要素ですが、 万elements--我々はそれを分割 半分、半分、半分にダウンして、 我々は、配列の下になるまで、 nは1素子アレイ。 nは1素子アレイのセット。 だから我々は1で開始 1000要素の配列、 我々は我々のポイントを取得 千一素子アレイを持っています。 その後、我々はそれらのサブ配列をマージし始め バック一緒に正しい順序です。 だから我々は2つ​​の1要素の配列を取ります そして、2要素の配列を作成します。 我々は2つ​​の2素子アレイを取ります そして、4素子配列を作成 などというように、我々はするまで 再び、1つのN要素の配列を再構築。 

の最悪の場合の実行時間 ISマージソートn回のnを記録します。 我々は、n個の要素を有するが、 この再結合過程 ログ取りのnを取得するための手順 完全な配列にバックします。 時間を実行する最良の場合も、n個のログです nは、このプロセスは本当にないので、 アレイがあったかどうか気に ソートやないで開始します。 プロセスは同じですが、あります 短絡事に方法はありません。 だからN N最悪の場合にログインすると、 N N最良のケースでログインします。 

我々は2つ​​の話を 検索アルゴリズム。 だから、線形検索が反復処理についてです。 私たちは、アレイ全体進みます 一度、左から右に、 番号を検索しようとしています 私たちは、探していること。 最悪の場合の実行時間は、n個の大Oです。 これは、繰り返し処理私たちがかかる場合があります 一つ一つの素子の両端 我々が探している要素を検索します 以下のため、いずれかの最後の位置で、 ではない、またはまったく。 しかし、我々はそれまでを確認することはできません 我々はすべてのものを見てきました。 ベスト・ケースをM、我々はすぐに見つけます。 の最良の実行時間 線形探索は1のオメガです。 

最後に、二分探索がありました、 これは各種の配列を必要とします。 それは非常にです忘れないでください 考慮すべき重要なこと 二分探索で作業する場合。 それはit--使用するための前提条件です あなたが探している配列を介して ソートする必要があります。 それ以外の場合は、キーワード 分割統治です。 半分に配列を分割し、 要素の半分をなくします あなたを介して進むようたびに。 このため、分割統治の 半アプローチで分割のもの、 最悪の場合の実行時間 バイナリサーチの 実質的にこれは、nはログ 線形検索のnよりも優れています。 最良の実行時間はまだ一つです。 

我々はすぐにそれを見つけるかもしれません 初めて我々は、分裂を作るが、 再び、ということを覚えています バイナリ検索があるが、 線形検索よりも実質的に良好 ログであることのおかげでN N対、 あなたが仕事を通過する必要がある場合があります 、最初にあなたの配列をソートします 応じて、それはあまり効果的になるかもしれません ソートされた反復の大きさ。 

私はダグロイドだけど、これはCS50です。